1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 71
Текст из файла (страница 71)
. , 0)⊤ . Соответственно, произведение1 (λ /λ )k (z /z )212 1V ...k(λn /λ1 ) (zn /z1 )сходится к первому столбцу матрицы V , т. е. к собственному вектору, отвечающему λ1 . Вектор x(k) , который отличается от Ak x(0) лишьнормировкой, сходится к собственному вектору v1 , а величина λ̃ =hy (k+1) , x(k) i сходится к hAv1 , v1 i = hλ1 v1 , v1 i = λ1 .Из проведённых выше выкладок следует, что быстрота сходимостистепенного метода определяется отношениями |λi /λ1 |, i = 2, 3, .
. . , n,— знаменателями геометрических прогрессий, стоящих в качестве элементов вектора (3.156). Фактически, решающее значение имеет наибольшее из этих отношений, т. е. |λ2 /λ1 |, зависящее от того, насколько модуль доминирующего собственного значения отделён от модуляостальной части спектра. Чем больше эта отделённость, тем быстреесходимость степенного метода.Пример 3.18.1 Для матрицы (3.14)1 23 4,при вычислениях с двойной точностью степеной метод с начальнымвектором x(0) = (1, 1)⊤ за 7 итераций даёт√ семь верных знаков доминирующего собственного значения 12 (5 + 33) ≈ 5.3722813.
Детальнаякартина сходимости показана в следующей табличке:4363. Численные методы линейной алгебрыНомеритерации1234567Приближениек собственному значению5.05.34482765.37394455.37216495.37228945.37228085.3722814Быстрая сходимость объясняется малостью величины |λ2 /λ1 |, которая, как мы могли видеть в Примере 3.2.3, для рассматриваемойматрицы равна всего лишь 0.069.Для матрицы (3.15)1 2,−3 4при тех же исходных условиях степенной метод порождает последовательность значений λ̃, которая случайно колеблется от примерно0.9 до 4 и очевидным образом не имеет предела. Причина — наличие у матрицы двух одинаковых по абсолютной величине комплексносопряжённых собственных значений 2.5 ± 1.936 i (см. Пример 3.2.3).
Отметим, что для симметричных (эрмитовых) положительно определённых матриц в степенном методе в качестве приближения к доминирующему собственному значению можно брать отношениеkx(k+1) k2,kx(k) k2x(k+1) = Ax(k)(см. [78]).Наконец, необходимое замечание о сходимости степенного методав комплексном случае. Так как комплексные числа описываются парами вещественных чисел, то комплексные одномерные инвариантныепространства матрицы имеют вещественную размерность 2. Даже будучи нормированными, векторы из такого подпространства могут отличаться на скалярный множитель eiϕ для какого-то аргумента ϕ, такчто если не принять специальных мер, то в степенном методе видимойстабилизации координатных представлений комплексных собственных3.18. Численные методы для несимметричной проблемысобственных значенийвекторов может не наблюдаться.
Тем не менее, о факте сходимости илирасходимости можно при этом судить по стабилизации приближения ксобственному значению. Либо кроме нормировки собственных векторовследует предусмотреть ещё приведение их к такой форме, в которойкоординатные представления будут определяться более «жёстко», например, требованием, чтобы первая компонента вектора была бы чистовещественной.Пример 3.18.2 Рассмотрим работу степенного метода в применениик матрице1 2i,3 4iимеющей собственные значенияλ1 = −0.4308405 − 0.1485958 i,λ2 = 1.4308405 + 4.1485958 i.Доминирующим собственным значением здесь является λ2 .Начав итерирование с вектора x(0) = (1, 1)⊤ , уже через 7 итераций мы получим 6 правильных десятичных знаков в вещественной имнимой частях собственного значения λ2 .
Но вот в порождаемых алгоритмом нормированных векторах x(k) —−0.01132 − 0.43223 i,x(9) =−0.11659 − 0.89413 i0.40491 − 0.15163 i(10),x=0.80725 − 0.40175 i0.27536 + 0.33335 i,x(11) =0.64300 + 0.63215 i0.22535 + 0.36900 i(12),x=−0.38795 + 0.81397 iи так далее — нелегко «невооружённым глазом» узнать один и тот жесобственный вектор, который «крутится» в одномерном комплексноминвариантном подпространстве. Но если поделить все получающиесявекторы на их первую компоненту, то получим один и тот же результат1.,2.07430 − 0.21542 i4383.
Численные методы линейной алгебрыи теперь уже налицо факт сходимости собственных векторов.Как ведёт себя степенной метод в случае, когда матрица A не является диагонализуемой? Полный анализ ситуации можно найти, например, в книгах [42, 44]. Наиболее неблагоприятен при этом случай, когдадоминирующее собственное значение находится в жордановой клеткеразмера два и более.
Теоретически степенной метод всё таки сходитсяк этому собственному значению, но уже медленнее любой геометрической прогрессии.Пример 3.18.3 Рассмотрим работу степенного метода в применениик матрице1 1,0 1т. е. к жордановой 2 × 2-клетке с собственным значением 1.Запустив степенной метод из начального вектора x(0) = (1, 1)⊤ , будем иметь следующееНомеритерации1310301003001000Приближениек собственному значению1.51.31.09900991.03329631.0099991.00333331.001То есть, для получения n верных десятичных знаков собственного значения приходится делать примерно 10n−1 итераций, что, конечно же,непомерно много. При увеличении размера жордановой клетки сходимость степенного метода делается ещё более медленной.3.18бОбратные степенные итерацииОбратными степенными итерациями для матрицы A называютописанный в прошлом параграфе степенной метод, применённый к обратной матрице A−1 , в котором вычисляется отношение результатов3.18.
Численные методы для несимметричной проблемысобственных значенийпредыдущей итерации к последующей, т. е. обратная к (3.153) или (3.154)величина. Явное нахождение обратной матрицы A−1 при этом не требуется, так как в степенном методе используется лишь результат x(k+1) еёумножения на вектор x(k) очередного приближения, а это, как известно (см., в частности, §3.13), эквивалентно решению системы линейныхуравнений Ax(k+1) = x(k) .Так как собственные значения матриц A и A−1 взаимно обратны,то обратные степенные итерации будут сходиться к наименьшему поабсолютной величине собственному значению A и соответствующемусобственному вектору.Таблица 3.13. Обратные степенные итерации для нахождениянаименьшего по модулю собственного значения матрицы Ak ← 0;выбираем вектор x(0) 6= 0;нормируем x(0) ← x(0) /kx(0) k2 ;DO WHILE ( метод не сошёлся )найти y (k+1) из системы Ay (k+1) = x(k) ; λ̃ ← x(k) , y (k+1) / y (k+1) , y (k+1) ;x(k+1) ← y (k+1) /ky (k+1) k2 ;k ← k + 1;END DOЧтобы в отношенииhx(k) , l(k) i,hx(k+1) , l(k) iкоторое необходимо вычислять в обратных степенных итерациях, знаменатель не занулялся, удобно брать l(k) = x(k+1) .
Тогда очереднымприближением к наименьшему по модулю собственному значению матрицы A являетсяhx(k) , x(k+1) i,hx(k+1) , x(k+1) i4403. Численные методы линейной алгебрыгде Ax(k+1) = x(k) . Псевдокод получающегося метода представлен вТабл. 3.13.Практическая реализация решения системы линейных уравнений(5-я строка псевдокода) может быть сделана достаточно эффективной,если предварительно выполнить LU- или QR-разложение матрицы A, азатем на каждом шаге метода использовать формулы (3.65) или (3.82).Пример 3.18.4 Рассмотрим работу обратных степенных итерацийдля знакомой нам матрицы1 2,3 4√собственные значения которой суть 21 (5± 33), приблизительно равные−0.372 и 5.372.Запустив обратные степенные итерации из начального вектора x(0)= (1, 1)⊤ , за 7 итераций получим 7 верных значащих цифр наименьшего по модулю собственного числа 0.3722813.
Скорость сходимостиздесь получается такой же, как в Примере 3.14.1 для доминирующегособственного значения этой матрицы, что неудивительно ввиду одинакового значения знаменателя геометрической прогрессии λ2 /λ1 .Обратные степенные итерации особенно эффективны в случае, когда имеется хорошее приближение к собственному значению и требуется найти соответствующий собственный вектор.3.18вСдвиги спектраСдвигом матрицы называют прибавление к ней скалярной матрицы,т. е. матрицы, пропорциональной единичной матрице. При этом вместоматрицы A мы получаем матрицу A+ϑI для некоторого вещественногоили комплексного числа ϑ. Если λi (A) — собственные значения матрицы A, то собственными значениями матрицы A + ϑI являются числаλi (A)+ ϑ, тогда как собственные векторы остаются неизменными. Цельсдвига — преобразование спектра матрицы с тем, чтобы улучшить работу некоторых алгоритмов решения проблемы собственных значений.Если, к примеру, у матрицы A наибольшими по абсолютной величине были два собственных значения −2 и 2, то прямое применениек ней степенного метода не приведёт к успеху.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
