Книги-online

Нахождение собственных значений и собственных векторов матрицы.

И в библиотеке бывают рекламные паузы.

Нахождение собственных значений и собственных векторов матрицы.

Введение.

Рассматриваемые здесь алгоритмы предназначены для поиска собственных значений матрицы A, т.е. вычисление корней характеристического уравнения:

Проблема же нахождение соответствующих собственных векторов является более простой, так как если корни характеристического уравнения известны, то задача сводится к отысканию не нулевых решений некоторых однородных линейных систем.

Основной прием использующийся при отыскании собственных значений матрицы это развертывание определителя в полином n-й степени. Отыскание же корней полученного полинома является отдельной, отнюдь не тривиальной задачей. Здесь могут пригодится методы из раздела Полиномиальные и трансцендентные уравнения..

Следует заметить, что попытка решение задачи развертывания определителя в полином "в лоб", требует значительных вычислений, и весьма трудоемка. Нетрудно показать, что непосредственное вычисление коэффициентов характеристического полинома эквивалентно вычислению 2n-1 определителей различных порядков.

Из приведенных здесь методом наилучшую скорость при больших n показывает метод Данилевского, поэтому именно ему уделено наибольшее внимание. Единственным недостатком данного метода на мой взгляд является необходимость для некоторых матриц использовать рекурсивный вызов. Наверх

Нахождение собственных значений матрицы методом А.M. Данилевского.

Сущность метода Данилевского заключается в приведении векового определителя к так называемому нормальному виду Фробениуса

Если нам удалось записать вековой определитель в такой форме, то, разлагая его по элементам первой строки будем иметь:

Таким образом задача сводится к нахождению матрицы P в форме Фробениуса подобной матрице A, так как собственные числа инвариантны относительно операции подобия.

Процедура последовательно преобразует строки исходной матрицы, начиная с последней, к виду описанному выше, при этом преобразование осуществляется таким образом, чтобы полученные матрицы были подобны.

Опишем первое из преобразований, которое приводит n-ую строку исходной матрицы A к необходимому виду. Вначале преобразуем матрицу A в матрицу B по следующим формулам:

	bi j=ai j - ai n-1an i / an n-1   при i=1,..,n; j не равно n-1;
	bi n-1=ai n-1 / an n-1,  при i=1,..,n

Последняя строка построенной матрицы B будет удовлетворять нашим условиям, но не будет подобна матрице A, поэтому проведем еще одно преобразование и получим матрицу С подобную A и сохраняющую последнюю строку:

	сi j=bi j  при i=1,..,n-2
	cn-1 j=an 1b1 j+an 2b2 j+ . . . +an nbn j  при j=1,...,n

Таким образом получили матрицу С подобную A и с последней строкой как в матрице привеленного вида Фробениуса. Продолжая, преобразуем аналогично n-1 строку матрицы С и т.д.

Допустим, что при преобразовании матрицы A в матрицу Фробенниуса P мы пришли к матрице вида:

причем оказалось, что dk k-1=0.

Тогда преобразования методом Данилевского нельзя продолжить. Здесь возможны два случая: 1. Существует элемент dk l отличный от нуля, где l < k-1 , тогда переставляем местами (k-1) и l столбцы и (k-1) и l строки получаем матрицу подобную D для которой возможны дальнейшие преобразования по методу Данилевского. 2. Все элементы k строки равны нулю, тогда полученная матрица имеет вид:

Причем D2 имеет нормальный вид Фробениуса, а матрицу D1 можно привести к нему методом Данилевского. Полином же порождающий собственные значения матрицы А, есть произведение аналогичных полиномов для D1 и D2, при этом коэффициенты полинома для D2 определены.

Процедура на вход получает матрицу A, а на выходе выдает матрицу C подобную A, при этом С имеет нормальный вид Фробениуса. Флаговая переменная S используется для определения случая когда дальнейшее преобразование не возможно, точнее: S=0 когда алгоритм успешно отработал, S > 0 когда на некотором шаге возник случай описанный в пункте 2, при этом S колличество строк в матрице D1. Наверх

Нахождение собственных значений матрицы методом Леверрье.

Процедура определяет коэффициенты характерестического полинома

матрицы A. Положим:

тогда справедливы формулы Ньютона:

Отсюда получаем линеиную алгебраическую систему:

Из которой шаг за шагом определяются коэффицитенты p1,...,pn. Следует заметить, что sk равен следу матрицы Ak, которая находятся непосредственным перемножением используя алгоритм умножения матриц. Наверх

Нахождение собственных значений матрицы методом неопределенных коэффициентов.

Процедура определяет коэффициенты характеристического полинома

матрицы A. Для этого полагаем в предыдущем равенстве

=0,1,...,(n-1), таким образом получим систему из n линейных уравнений относительно p1,...,pn. Корни системы находим используя любой из методов описанных на странице Решение систем линейных алгебраических уравнений. В блок-схеме вызывается метод Гаусса, но можно использовать любой другой метод. Наверх