арифметических действий, т.е. число действий растет линейно относительно числа неизвестных
При решении же произвольной системы линейных алгебраических уравнений методом Гаусcа число действий пропорционально кубу числа неизвестных.
ВЫЧИСЛЕНИЕ СОБСТВЕННЫХ ЗНАЧЕНИЙ И СОБСТВЕННЫХ ВЕКТОРОВ МАТРИЦ.
Большое число задач математики и физики требует отыскания собственных значений и собственных векторов матриц, т.е. отыскания таких значений +
, для которых существуют нетривиальные решения однородной системы линейных алгебраических уравнений , (1)и отыскания этих нетривиальных решений.
Здесь
-квадратная матрица порядка m , - неизвестный вектор - столбец.Из курса алгебры известно, что нетривиальное решение системы (1) существует тогда и только тогда, когда
, (2)где Е - единичная матрица. Если раскрыть определитель
, ïîëó÷àåòñÿ алгебраическое уравнение степени m относительно .Таким образом задача отыскания собственных значений сводится к проблеме раскрытия определителя по степеням и последующему решению алгебраического уравнения m- й степени.Определитель
называется характеристическим (или вековым ) определителем, а уравнение (2) называется характеристическим (или вековым ) уравнением.Различают полную проблему собственных значений, когда необходимо отыскать все собственные значения матрицы А и соответствующие собственные векторы, и частичную проблему собственных значений, когда необходимо отыскать только некоторые собственные значения, например, максимальное по модулю собственное значение .
Метод Данилевского развертывание векового определителя.
Определение. Квадратная матрица Р порядка m называетсяподобной матрице А , если она представлена в виде
,где S - невыродженная квадратная матрица порядка m.
ТЕОРЕМА. Характеристический определитель исходной и подобной матрицы совпадают .
Доказательство.
Идея метода Данилевского состоит в том, что матрица А подобным преобразованиям приводится, к так называемой нормальной форме Фробениуса
.Характеристическое уравнение для матрицы Р имеет простой вид
т.е. коэффициенты при степенях характеристического полинома непосредственно выражаются через элементы первой строки матрицы Р.Приведение матрицы А к нормальной форме Фробениуса Росуществляется последовательно построкам, начиная с последеней строки.
Приведем матрицу А
подобным преобразование к виду
Пусть
Можн проверить,что такой вид имеет матрица , которая равнагде
Слудующий шаг - приведение матрицы
подобным преобразованием к виду , где и вторая снизу строка имеет единицу в -ом столбце, а все остальные элементы строки равны нулю:Если
то можно проверить, что такой вид имеет матрица :где
Таким образом
Далее процедура аналогичная, если на кождом шаге в очередной строке, на месте которого подобным преобразованием нужно получить единицу, не равную нулю.
В этом случае ( будем называт его регулярным ) нормальная формула Фробениуса будет получена за ( m-1 ) шагов и будет иметь вид
Рассмотрим нерегулярный случай, когда матрица, полученная в результате подобных преобразований приведена уже к виду
и элемент . Таким образом обычная процедура метода Данилевского не подходит из-за необходимости деления на ноль.В этой ситуации возможно два случая. В первом случае к-й
строке левее элемента
есть элемент Тогда домножая матрицу слева и справа на элементарную матрицу перестановок , получаем матрицу ,у которой по сравнению с матрицей
переставлены l -я и (k-1 )-я строка l-й и ( k-1)- й стодбец. В результате на необходимом нам месте оказывается ненулевой элемент , уже преобразованная часть матрицы не меняется, можно применять обычный шаг метода Данилевского к матрице . Она подбна матрице (и, следовательно, исходной матрице А ), т.к. елементарная матрица перестановок совпадает со своей обратной, т.е.Рассмотрим второй нерегулярный случай, когда в матрице
ýлемент и все элементы этой строки, которые тоже находятся левее его, тоже равны нулю. В этом случае характеристический определитель матрицы можно представить в видегде
і - единичные матрицы соответствующей размерности, а квадратные матрицы и имееют вид:Обративм внимание на то, что матрица
уже нормальную форму Фробениуса, и поэтому сомножитель просто развертывается в виде многочлена с коэффциентами, равными элементам первой строки.Сомножитель
, åñòü характеристический определитель матрицы . Для развертывания можн опять применять метод Данилевского, приводя матрицу подобными преобразованиями к нормальной форме Фробениуса.