Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 18
Текст из файла (страница 18)
~ 4. СТКПКННОЙ МКТОД Степенной метод позволяет находить максимальное по модулю собственное значение и соответствующий ему собственный вектор диагонализируемой матрицы АЕМ„. ~ 4.1. Описание алгоритма Теорема 1 (Степенной метод). Пусть матрица А е М„имеетп полную систему ортонормированных собственных векторов е;, т' = 1,..., и: Ае; = Л;е;, (е;, ез) = б;1, причем (Л»( > )Лг! > )Лз( » ...
(Л„(т.е. вектора занумеровантя в порядке убывания модуля собственного значениц причем собственное значение с максимальным модулем — не кратпное). Тогда для всякого вектора х»о» б С" такого, что (х»о»,е,) ф О, итперационнтяй процесс. х»ь»О = Ах»~», Л»»~» = ', й = 0,1, (,Сь+ц,Сг)) (х("), х("~) сходится к собственному значению Л» (собственному значению с максималь- ным модулем), причем К.Ю.Богачев Методы нахождения собственных значений ~4. СТЕПЕННОЙ МЕТОД а величины е, = „сходягпся к собственному вектору, соогпветствующе))х(") )) му Л1 (с точностью до постоянного множителя/: е, = еееег+ О ~л,) где е'~ — число, по модулю равное 1. / я ~ я И е=г юе г в=1 Поэтому х~~) = с1Л",е1+О ((Л~~)), х<~+О = с1Л1+~е1+О ~)Л~~""().
Далее, вычислим Цх~~) Ц = 1х~~), х~~)) = (с1л~е1+ О (!Л~~!), с1л~е1+ О (!Л~~/)) = ~.,)')л,)'"+ о (~л",~~л,'~),: (хы + ),' ~")) = ( Л7+ е + О (~Л$+ ~),с Л7е + О (~Лгь~)) = Л, ((с,)')Л,("+ О ()Л",((Л,"!)) . Следовательно, л,(~,,~ р,~ "~о(~арф 1.~о(,„'Р , ') =л ~,„~ р ~с ~а(~Л р ~) 1„О(, л',) = ( .(ь--1), (ь)~ 1х("), х(") ) =л +о Аналогично, с1Л1ег + О (/Лф)) (ь) е ))""Ч (~„р~Л,р~.~а(щп~))иг (, „О( ° '))'" = е'~е1+ О с (Л где е'~ = -'"'- (~-~~-) . Торема доказана. Методы нахождения собственных значений К.Ю.Богачев Доказательство. Поскольку вектора ем...,е„образуют базис в С", то х~о) = ~; с;е;, причем по условию сг — — 1х~о), е1) ф О. Вычислим ~5. МЕТОД ВРАЩЕНИЙ ЯКОБИ вЂ” сумма квадратов внедиагольных элементов матрицы В.
Пусть А = (а; ) Е М„(К), А = А" = А'. Всякая симметричная вещественная матрица диагонализируема в некотором евклидовом базисе, т.е. существует ортогональная матрица 0 е 0(п) и диагональная матрица Л = с11афЛы..., Л„) такие, что А = ОЛО". Отсюда Л = О*АО = ОАО*, где обозначено 0 = 0* е 0(п).
Очевидно, что для диагональной матрицы Х(Л) = О и для всякой матрицы В ЦВ) > О. Следовательно а) Х(ОАО ) > О для всякой 0 ь. 0(п); б) Х(ОАО*) = Б(Л) = О, если 0 = 0*. Следовательно, матрица 0 = 0* является регпением задачи минимизации функционала Х(ОАО*) на группе ортогональных матриц: Х(ОАО*) -+ шш Ого(п) Если мы найдем какое-то решение 0~ этой задачи, т.е. Х(О~АО*,) = О, то матрица Е(О~АО*,) диагональна и ортогонально подобна матрице А.
Следовательно, на ее диагонали стоят искомые собственные значения матрицы А. Будем строить последовательность симметричных матриц А = Ао,Аы,Аь, . такую, что для всякого Й = 1, 2,...: 1) Следующая матрица ортогонально подобна предыдущей (и потому ортогонально подобна исходной) А = 0 А~ ~О~, Оо Е 0(п). (2) 2) Сумма квадратов внедиагональных элементов следующей матрицы строго меньше суммы квадратов внедиагональных элементов предыдущей матрицы: Е(Ао) < Е(Ао ~) (3) т.е.
последовательность (Е(Аг))~~, строго монотонно убывает, что в силу Е(Ао) > О гарантирует существование предела 1пп Е(Ао). 3) Этот предел равен нулю: 1пп Е(Аг) = О. Й-+оо (4) Матрицы Оо Е 0(п) в (2) подбираются на шаге й так, чтобы удовлетворить условиям (3), (4). Методы нахождения собственных значений К.КЛ Богачев Теорема 1. Пусть е > Π— произвольно.
Тогда в процессе (1) --- ® существует й = йо такое, что ЦАоо) < е. При этом для всякого собственного значения Л матрицы А существует г', 1 < 1 < и, такое, что )Л вЂ” ав ! < (го) ~/п — 1~а, где (а; ) — элементы матприцы Аоо. Другими словами, диагональ 1ьо) матрицы Аоо с точностью ~/и — И/г представляет собой набор собственных значений матрицы А. 35. МЕТОД ВРАЩЕНИЙ ЯКОБИ 87 Доказательство.
В силу (4) для всякого е ) О существует й = Ьр, такое, что О < Е(Аьь,) < е. В силу (2) всякое собственное значение Л матрицы А является собственным значением матрицы Аьь,. По теореме Гершгорина для всякого Л вЂ” собственного значения матрицы А~„ существует ь', 1 < г < ть, такое, что )Л вЂ” аьь ~! < В';(Ау„) = ',ь (а( '~( < 4=1 .ьФ < «Й — 1«/Е(А~,) < «/и — 1«7е Теорема доказана.
В методе вращений Якоби В качестве ортогональных матриц Оь в (2) используются матрицы элементарного вращения (см. стр. 43): Оь = Т;" = Т; (дь). Угол у подбирается так, чтобы удовлетворить (3), а индексы ь и !' — так, чтобы удовлетворить (4). 3 5.2. Выбор угла вращения Вычислим для произвольной симметричной матрицы А и произвольной матрицы элементарного вращения Ть матрицу В = Т,"АТ и выражение Х(В) — Е(А) = ~~; (Ь~ — а~~ ). Ь,пь=ь ь т-тп При умножении А на Т;, слева изменяются только строки г и 1 матрицы А, при умножении Т;,А на Т,', справа изменяются только столбцы ь и т матрицы Т; А. Поэтому все элементы, не находящиеся в строках ь, 1 и столбцах г, 1, у матриц А и В = Т;,АТ,', совпадают: 6ь„„= аь, при 1 ф г', т, нь ф г', т.
Следовательно, Е(В) — Х(А) = ~ ~(62 — а2 ) + ~~ (~б — а~~ ) + ~~ь (Чьь — а~~,) + ~ь (Ь~~ — а~~) ььь=ь ььь=ь ь=ь ь=ь т~ь,з' тп~ь,~' ьФь,у ьфь,э +(ЬР аь ) + (62 а~~ ) ((Ь~ + ~ь ) — (а~ + а~~,„)) + ~ ~((Ь~ьь + Ьь~ ) — (аьРь + а~~ )) + 2(61 — а~ ) т=ь ь=ь ьььфЬ,у ь~ь„ь (здесь мы использовали симметричность матриц А и В: а; = а;, Ь; = Ь; для всех г, 1' = 1,..., в). Без ограничения общности мы можем считать, что ь < т'.
В силу строения матрицы Т; (см. (1.12.1)) и правил умножения матриц получаем для всех тнч1 = 1,..., ть, нь, 1 ф ь, 1: К.Ю.Богачев Методы нахождения собственных значений ~5. МЕТОД ВРАЩЕНИЙ ЯКОБИ с О)~яп соз ) (б) Матрицы преобразования в (5) и (6) ортогональны и потому сохраняют длины (двумерных) векторов. Поэтому Следовательно, Е(В) — Е(А) = 2(Ь~ — а~.). (7) Это выражение будет минимально, когда 5;у = О. Определим угол вращения из уравнения у = О. Из выражения (7) вытекает, что достаточно рассмотреть 2 х 2 симметричные матрицы А и В: Вычислим с оя Фан — яп ~раО соз уа;, — яп~раВ яп чаи + соя ~ра; з1п уа; + соя ~ра,, / и 6; = яп~р(соя~ран — в1пуа;~)+сезар(сезара;, — яп~раВ) 2 = яп у сов уаа — яп р а;, + сов ~ра;.
— яп у соя ~ра,, 1 = — яп 2р(аа — аВ) + сов 2~ра;,. 2 Из условия 6; = О получаем уравнение 1 2 — з1п2~р(аи — а") + сов 2уа; = О откуда 2а,1 если аа ф а,, аи — аВ 7г 4' если аи — — а, . 1 соз 2~р = (1 + 1б~ 2У)1~~ сов р= — 1+, „2 Р„ япр = ядп(ф2~р) ~ — ~1— 1,2 ~ (1+ Ца 2~р)11~) ~ Методы нахождения собственных значений К.Ю.Богачев Будем выбирать у Е [ — —, — ]. Тогда соя 2у > О и яап(я1п у) = я1ип(1и2~р). Сле- 1 7 4 довательно, ~5. МЕТОД ВРАЩЕНИЙ ЯКОБИ Обозначим х = — 2и;,, у = аи — и2,. Тогда сов 21р = 1 М 1/2 (х2 + У2)1/2 ' 2 1+ У2 х 1821р = —, У сов 1р = — 1+ ',, зш 1р = яяп(ху) — 1— Однако при ~у~ — э со числа 1 и могут оказаться близки и при вычи- М (х2 + у2)1/2 слепни их разности возникает большая вычислительная погре1пность.
Поэтому зш ~р вычисляют по формуле х (у) яп21р 1и21рсоз21р у (х2+ У2)1/2 ЯП1Р = 2сояу 2созу 2соз111 х в18п(у) з18п(ху)~х~ 2 сов у (хя + у2)'/2 2 соз1р (х2 + У2)'/2 Окончательно, расчетные формулы имеют вид: (8) (где х = — 2а;1, у = аи — а ). Таким образом, для выполнения условия (3) достаточно выбрать произвольный внедиагональный элемент а;, ф. О и сделать преобразование Т;.(12) с (ь — ц углом 1р, определенным по приведенным выше формулам. э 5.3.
Стратегии выбора обнуляемого элемента Обеспечим выполнение условия (4) за счет выбора номера (з,у) обнуляемого элемента а; . Это можно сделать несколькими способами, которые называют 11 — О сн1ратегиями выбора обнуляемого элемента. Именно стратегия выбора обнучяемого элемента в значительной степени определяет трудоемкость алгоритма метода вращений Якоби. К.Ю.Богачев СОЗ 1Р = 1/2 "(.2+ 2) ' 1 яву= 1/2 при У=О яцп(ху) ~ х ~ яп1р —..., при уф О 2 соз 1р (х2 + У2) '/2 Методы нахождения собственных значений ~5.
МЕТОД ВРАЩЕНИЙ ЯКОБИ 90 З 5.3.1. Метод вращений с выбором максимального элемента В качестве а; выбираем максимальный по модулю внедиагональный эле[й — 1) мент матрицы Аь 1. )а(; )! = гпах )а~~ )! (9) )~ти Лемма 1. При выборе (9) обнуляемого элемента условие (4) выполнено. Доказательство. При любой стратегии выбора элемента а; из (7) сле(й — 1) дует, что Х(Аь) = г'(Аь 1) — ~а;з (10) Пусть а(, ) выбран как (9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
