Степенной метод нахождения собственных значений

Степенной метод нахождения собственных значений

Рассматриваются проблемы нахождения собственных значений и собственных векторов квадратной вещественной матрицы ( A ). Собственным числом называется число ( lambda ) такое, что для некоторого ненулевого вектора (собственного вектора) ( x ) имеет место равенство: $$ egin ag <1>A x = lambda x end $$

С учетом того, что ищется нетривиальное решение уравнения (1), то $$ egin ag <2>det (A — lambda I) = 0. end $$ Тем самым собственные значения ( lambda ) матрицы ( A ) являются корнями характеристического многочлена ( n )-ой степени (2). Задача отыскания собственных значений и собственных векторов матрицы сводится к построению характеристического многочлена, отысканию его корней и последующему нахождению нетривиальных решений уравнения (1) для найденных собственных значений.

Квадратная вещественная матрица порядка ( n ) имеет ( n ) собственных значений, при этом каждое собственное значение считается столько раз, какова его кратность как корня характеристического многочлена. Для симметричной матрицы ( A ) собственные значения вещественны, а собственные вектора, соответствующие различным собственным значениям, ортогональны, т.е. ( (x^i , x^j) = 0 ), если ( i
e j ). Отметим также некоторые свойства собственных значений и собственных векторов для сопряженной матрицы ( A^T ): $$ egin ag <3>A^T y = mu y end $$

Для задач (1) и (3) имеем $$ lambda_i = mu_i, quad i = 1, 2, ldots, n, $$ $$ (x^i, y^i) = 0, quad i
e j. $$

Две квадратные матрицы ( A ) и ( B ) одинаковых размеров называются подобными, если существует такая невырожденная матрица ( P ), что ( A = P^ <−1>B P ).

Подобные матрицы имеют одни и те же собственные значения, так как из (1) непосредственно следует $$ Bx = lambda z, quad z = P x. $$

Ряд стандартных программ вычисления собственных значений выполняют последовательность преобразования подобия ( P_к ), обладающих тем свойством, что матрицы ( P_k^<-1>А P_к ) становятся «более диагональными». Возникает, естественно, вопрос: «Насколько хорошо диагональные элементы матрицы аппроксимируют ее собственные значения?» Любое собственное значение матрицы ( A ) лежит по крайней мере в одном из кругов (круги Гершгорина) $$ |lambda — a_| leq sum_^n |a_|, quad i = 1, 2, ldots, n. $$

Приведем теперь некоторые сведения о возмущении собственных значений при возму- щении элементов матрицы. Помимо (1) рассмотрим задачу $$ egin ag <4> ilde ilde = ilde <lambda> ilde. end $$

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

Пусть матрица ( A ) диагонализуема, ( P^<-1>AP = mathrm(lambda_1, lambda_2, ldots, lambda_n) ), все ее собственные значения простые и $$ |lambda_1| > |lambda_2| > ldots |lambda_n|. $$ Для заданного вектора ( q^ <(0)>), имеющего единичную евклидову норму, степенной метод генерирует последовательность векторов ( q^ <(k)>) следующим образом

Читайте также:  Как уменьшить ярлыки на компьютере

Тем самым при использовании степенного метода находится максимальное по модулю собственное значение матрицы ( A ).

Учитывая, что собственные значения матрицы ( A^ <−1>) есть ( 1/lambda_i ), ( i = 1, 2, ldots, n ), используя последовательности (обратные итерации) $$ y^ = A^ <-1>y^k, quad k = 0, 1, ldots $$ находится минимальное по модулю собственное значение матрицы ( A ).

Задача 1: Нахождение максимального собственного значения степенным методом

Написать программу для нахождения максимального по модулю собственного значения и соответствующего собственного вектора симметричной матрицы с помощью степенного метода. С ее помощью найдите максимальное по модулю собственное значение матрицы Гильберта ( A ), когда $$ a_ = frac<1> , quad i = 1, 2, ldots, n, quad j = 1, 2, ldots, n. $$ при значениях ( n ) от 2 до 10.

Задача 2: Решение полной задачи на собственные значения

Написать программу для вычисления собственных значений трехдиагональной вещественной матрицы ( A ) с использованием ( QR ) алгоритма. Найти собственные числа трехдиагональной матрицы ( A ), для которой $$ a_ = 2,quad a_ = -1-alpha, quad a_ = -1+alpha, quad i = 1,2 ldots, n — 1, $$ $$ a_ <00>= 2, quad a_ <01>= -1 — alpha, quad a_ = -1 + alpha, quad a_ = 2, $$ при различных значениях ( n ) и параметра ( alpha ) (( 0 leq alpha leq 1 )). Сравнить найденные собственные значения с точными.

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

Степенной метод является итерационным процессом для нахождения собственных векторов матрицы А. Вначале проведем некоторый предварительный анализ. Возьмем произвольный начальный вектор х (()) . Предположим, что все собственные значения различны по абсолютной величине. Разложим вектор х (()) по собственным векторам матрицы А:

Умножая вектор х (0) k раз на матрицу А, получим

Когда k — 3 ? оо, у^ стремится к вектору, коллинеарному с вектором гдг. Поэтому последовательные степени матрицы А дают информацию о ее собственном значении XN. Величина этого собственного значения может быть легко найдена: учитывая второе свойство отношения Рэлея, р(у^) стремится к Хдг, когда k —? оо.

Основываясь на проведенном анализе, можно предложить следующую реализацию степенного метода:

  • 1) задать начальный вектор х (0 ^;
  • 2) для каждого значения k = 0,1. вычислить у ( * +1) = Ax (k) ;
  • 3) следующее приближение вычисляется как =
Читайте также:  Id cooling icekimo 120w

= У ( ^ 1 )/||у (Ь1 )|| (эта процедура называется нормализацией, и она предназначена для того, чтобы предотвратить переполнение или исчезновение порядка);

4) если при некотором значении k ||х^ +1 ^ — х^|| (А+1) есть приближенный собственный вектор zjV и % = — р(х +1 >) есть приближенное максимальное по модулю собственное значение Х^.

Сходимость степенного метода. Если все Хп различны и (zjv, х ) * О, тогда

и справедлива следующая оценка

Таким образом, скорость сходимости степенного метода зависит от того, насколько XN_ t| меньше, чем XN.

Пример 4.2 (степенной метод) Рассмотрим следующую матрицу:

Выберем начальный вектор х (0) = (1, О, О, О) 1 и гр = 10

5 . Результаты вычислений приведены в табл. 4.1.

2.6. Алгебраическая проблема собственных значений

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

Различают две постановки задачи и самих этих решений:

— нахождение одного или нескольких собственных чисел (и соответственно — векторов) — частичная проблема собственных значений;

— нахождение всех собственных чисел (и соответственно — векторов) — полная проблема.

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

2.6.1. Степенной метод

Степенной метод позволяет найти наибольшее по модулю собственное значение и собственный вектор.

Пусть — собственные числа матрицы A. Для определенности предположим, что

Берем произвольный ненулевой вектор . Строим последовательность векторов

для любого номера i=1,2. n.

Докажем это в предположении, что матрица A имеет n линейных независимых собственных векторов . Запишем разложение вектора по базису из собственных векторов

Так как для k=2. n и для k=3. n , то отсюда следует, что при выполняется соотношение (* )

Взяв достаточно большой номер итерации m, мы сможем с любой степенью точности определить по формуле (38) наибольший по модулю корень характеристического уравнения для матрицы A. Для нахождения этого корня может быть использована любая координата вектора , в частности, можно взять среднее арифметическое соответствующих значений.

Так как , то при

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

Читайте также:  Настройка цветов принтера canon

2.6.2. Метод вращений

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

Сущность метода состоит в следующем.

Известно, что для симметрической матрицы A существует ортогональная матрица U такая, что

где — транспонированная к U матрица, а — диагональная матрица. Так как , то матрица подобна матрице A и, следовательно, имеет те же собственные значения, что и матрица A . Так как собственными значениями диагональной матрицы являются ее диагональные элементы, то зная U , мы можем найти все собственные значения матрицы A . Одновременно мы получим и все собственные векторы матрицы A , в качестве которых можно взять столбцы матрицы U .

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

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

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

Итерационный процесс осуществляется следующим образом.

Пусть — матрица, полученная после k — го преобразования поворота.

В матрице находится максимальный по модулю элемент . Строится ортогональная матрица простого поворота вида

Угол подбирается так, чтобы у матрицы

элемент обратился бы в нуль. Найдем выражение для этого элемента.

Матрица отличается от матрицы только столбцами с номерами и , причем последние имеют такой вид:

Матрица отличается от матрицы только строками с номерами i и j , причем эти строки имеют такой вид:

Из требования, что , получаем

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

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

Ссылка на основную публикацию
Сообщение на тему жесткий диск по информатике
Информатика Основным устройством хранения информации в компьютерной системе является жесткий диск. Большой объем и энергонезависимость сделали его наиболее пригодным для...
Слова содержащие приставку корень суффикс и окончание
Примеры разборов слов, у которых есть все основные морфемы: приставка, корень, суффикс, окончание. у бор к а у дивл ени...
Словарь для it специалистов
ykaneva 2018-04-09T16:54:33+00:00 September 13th, 2017 | Практика английского | 7 Comments 7 142,973 Сегодня день программиста. По этому поводу в...
Сообщение о выигрыше айфона
Да, почти всегда это обман и развод на деньги. Те, кто проводит ВКонтакте, Инстаграме и других соцсетях «конкурсы», «розыгрыши айфонов»,...
Adblock detector