А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (1113878), страница 8
Текст из файла (страница 8)
г- ^ Ап.(х,х)68Глава 5. Спектральные задачи линейной алгебрыВажны также экстремальные свойства Релея. (Ах,х)A|=min—(Ах,х)—, A„ = max — —.хфО (Х,Х)хфО (Х,Х)Для локализации собственных значений произвольной матрицы Апривлекаются круги Гершгорина: любое собственное значение матрицы Алежит по крайней мере в одном из круговп| А - а „ К ^2 \а,]\,i=l,2...,п.Приведем теперь некоторые сведения о возмущении собственныхзначений при возмущении элементов матрицы. Помимо (5.1) рассмотримзадачуAlp = Xip.(5.4)Ограничимся случаем, когда все собственные значения простые.
С точностью до членов второго порядка возмущение собственных значенийза счет возмущения матрицы дается оценкой(Х-Ц^СЦА-АЦ(5.5)где ||х|| = лУ(х,х). Мерой устойчивости собственного значения А, служитвеличина* = и П Г '(5-6)которая называется коэффициентом перекоса матрицы А, соответствующим данному собственному значению.
Здесь V» — собственное значениематрицы А*. Для нормированных собственных векторов задач (5.1) и (5.5)соответствующая оценка устойчивости имеет видВ частности, для симметричной матрицы все коэффициенты перекосаравны единице и оценки устойчивости вычисления собственных значенийоптимальны.5.2. Численные методы решения задач на собственные значения695.2.2. Итерационные методы решениячастичной проблемы собственных значенийДля нахождения минимального по модулю (максимального) собственногозначения используется прямые и обратные итерации.
Пусть матрица Аявляется симметричной, все ее собственные значения простые и упорядочены следующим образом|А,|<|А2|<---<|А„|.Определим последовательность векторовхк+]=Ахк,к = 0,1,...(5.7)при некотором заданном х° (прямые итерации). Рассматривая последовательности скалярных произведений (хк,хк), (хк+\хк),при ограничении(х°, <рп) Ф 0 получимТем самым при использовании итерационного процесса (5.7) находитсямаксимальное по модулю собственное значение матрицы А.Принимая во внимание, что собственные значения матрицы А~*есть 1/А,, i — 1,2,...,я, при использовании последовательности (обратные итерации)Ук+,=А-У,(j/V)#0,k = 0,1,...(5.9)имеем,ta«£V>-±.*-.<»(у*,у")AiТем самым при обратных итерациях находится минимальное по модулюсобственное значение матрицы.Заметим, что в прямых и обратных итерациях нет необходимостив специальном вычислении соответствующих собственных векторов, таккакПтхк = <рп, \\тук=<р\к—>оок—оо(5.10)70Глава 5.
Спектральные задачи линейной алгебрыВычислительная реализация обратных итераций (5.9) может бытьоснована на однократном LU разложении матрицы А. После этого каждаяобратная итерация по вычислительным затратам эквивалентна прямойитерации.Отметим процедуру ускорения сходимости обратных ^тераций приизвестном хорошем приближении собственного значения А| к собственному значению \\. В этом случае рассматриваются обратные итерациисо сдвигом, когдаz*+l = U - A , B ) - | z * l(zV)?fcO,* = 0,1,....Скорость сходимости обратных итераций со сдвигом и без сдвига определяется отношениямиА, - А,А,соответственно. В более общей ситуации обратные итерации со сдвигомиспользуются для нахождения ближайшего к заданному числу собственного значения и соответствующего собственного вектора.5.2.3. Решение полной проблемы собственных значенийПрямые и обратные итерации хорошо приспособлены для определенияотдельных собственных значений и собственных векторов.
Для решенияспектральной задачи в целом используется фД-алгоритм. Он основанна представлении матрицы А в виде произведения А = QR, где Q —ортогональная Q'Q = E, a R — верхняя треугольная матрицы.Строится последовательность ортогональных матриц Qk и верхнихтреугольных матриц Rg по рекуррентным формуламA = QiRu4, = Q2R2,Ak.l=QkRk,Ai=RiQi,A2 = R2Q2,Ak = RkQk,Процесс построения по матрице А матриц Qk, Rk,QiZ-алгоритмом.Ak называется5.2.
Численные методы решения задач на собственные значенияПусть для невырожденной матрицы А собственные значения различны по модулю и\\\\>\\\\> — >\К\и существует представлениеА = ТКТ~\T~l=LU,A = diag{A b A 2 ,...,A n }.Тогда последовательность матриц Ак Qii-алгоритма сходится к верхней треугольной матрице, а диагональные элементы — к собственнымзначениям матрицы А.При решении полной спектральной задачи на основе QR для минимизации вычислительной работы проводится предварительное преобразовании исходной матрицы к верхней почти треугольной матрице, в которой atJ - О, i > j + 1. При рекуррентных преобразованиях (?Д-алгоритмаматрицы Ак остаются почти треугольными.Решение спектральной проблемы для симметричной вещественнойматрицы может осуществляться методом вращений (методом Якоби).
Вещественная матрица, отличающаяся от единичной матрицы четырьмяэлементами, расположенными на пересечении строк и столбцов с номерами i, j , и имеющая видT(ij) =±sО±с1где с2 + s2 — 1 называется матрицей вращения. Заметим, что матрицавращения является ортогональной и при умножении вектора на матрицувращения T(ij) меняются только г и j координаты вектора.7172Глава 5.
Спектральные задачи линейной алгебрыДля любой матрицы А и любой пары индексов i,j, г Ф j всегдаможно найти такую матрицу вращения T(ij), что элемент 6^ матрицыВ = T*(ij)AT(ij) равен нулю. Определим последовательность матрицА0 = А, А,, А2,каждая из которых получается из предыдущей с помощью преобразования подобия, определяемой матрицей вращения. На каждом шаге этогопроцесса обнуляется отдельный внедиагональный элемент.
При такомпреобразовании сумма квадратов внедиагональных элементов убывает.Последовательность матриц Ak сходится к диагональной матрице и диагональные элементы матрицы Ак в рассматриваемом методе вращений(метод Якоби) являются соответствующими приближениями для собственных значений матрицы А.Оптимизация метода вращений достигается за счет выбора элементадля уничтожения на каждом шаге преобразований. Это может бытьмаксимальный по модулю внедиагональный элемент всей матрицы Akили на выбранном столбце.5.3. УпражненияРассматриваются некоторые спектральные свойства квадратных вещественных матриц и алгоритмов нахождения собственных значений.Упражнение 5.1.
Для матрицы А — А* > О, для которой А| < А2 < • • • < А„,докажите экстремальные свойства отношения Релея.Решение. В нашем предположении о свойствах матрицы собственныезначения (р\(р2,... ,tpn образуют ортонормированный базис. Произвольный вектор X разложим по этому базису, т. е.Для отношения Релея получим{Ах,х)(х,х)»=11=15.3. Упражнения73С учетом наших предположений о спектре матрицыA , <(Ах.х) V(5П)W^-Равенство в левой (правой) части неравенства (5.11) достигается на собственном векторе <р{ (у").Упражнение 5.2.
Получите оценку (5.5) для возмущения собственного значения простой матрицы.Решение. Будем рассматривать задачу возмущения t-ro собственного значения, тем самымAip* = Л,У,Aip* = Xi<p'.С точностью до членов второго порядка малости имеемМ? ~ Ч>*) + {А~ AW « ( * < - A.V + А,(£Г - у»'').(5.12)Разложим возмущение собственного вектора по собственным векторамневозмущенной задачи:& ~ <Р = 5 Z Рч^:=1и домножим (5.12) скалярно на t-ый собственный вектор сопряженнойзадачи (5.3).
Принимая во внимание свойство ортогональности собственных векторов задач (5.1) и (5.3), из (5.12) получим{ф\(А-А)<р{) к{%-)*)(*',<?).С учетом оценки(1>{,(А-А)<р{)<\\А-А\\\Ц,<\\У\\это дает искомую оценку (5.5) при определении коэффициента перекосаматрицы А согласно (5.6).Упражнение 5.3. Покажите справедливость асимптотического представления (5.8) для максимального по модулю собственного значения симметричнойматрицы А, у которой|А,|<|А2|<---<|А„|,при использовании прямых итераций (5.7).Глава 5.
Спектральные задачи линейной алгебры74Решение. Система собственных векторов в силу наших предположенийо матрице А образует ортонормированный базис. С учетом (5.7) имееми поэтомуI»Пa x(у ,у ) = 2^ i i'\У>j/) = 2 ^ a , A '1=1•1=1Для отношения этих скалярных произведений имеем(y\yk)=Xn aih ^yhai*k)'Это и приводит нас к искомому представления (5.8).Упражнение 5.4.
Пусть в предположениях предыдущего упражнения известномаксимальное по модулю собственное значение А„. Пустьyk+i=xk+,-\nxk,fc= 0,lгде х* определяются в соответствии с (5.7), тогда(у* + У) (yk,yk)Л+0А„.А..|2*\т. е. находится следующее собственное значение.Решение.
Разложение по собственным векторам даетi=iи поэтому(ук,ук) =±а}>?кЛъ~К)\1=1(У*+,,</*) = Х>?лГ(А<-А„) 2 .i=i(5.13)5.3. Упражнения75После подстановки этих представлений получим выражение (5.13), которое дает..*-оо(ук+\ук)_.(j/*,y*)Упражнение 5.5. Покажите, что для вещественной матрицы А и ортогональной матрицы Q имеет место(5- 14 )\\Q4M = И ж .для евклидовой (сферической) нормы:/ пvt=iпJ=Iч ]/2'Решение. Непосредственными выкладками убеждаемся в справедливостиравенствагдеп1г(А) = ]Па,;.i=lПринимая во внимание, что для ортогональной матрицы Q* = Q~\получим\\QA\\2E = tr((QAYQA) =u(A'Q*QA)=tT(A*A).Тем самым имеет место равенство (5.14).Упражнение 5.6. Для симметричной матрицы А постройте матрицу вращения Т(Ы), которая обращает в нуль элемент Ьы матрицы В — Т*(Ы)АТ(Ы).Решение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
