А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (2000) (1160081), страница 8
Текст из файла (страница 8)
Спектральные задачи линейной алгебрыОсновные обозначениях = {х • } = {Я|)х 2 ,...,х„} — n-мерный векторА = {ву} — матрица с вещественнымиэлементами ai}£7 — единичная матрицаD = :diag{d,, d 2 , . . , d n } — диагональная матрицаХи г == 1,2,...,п — собственные значения<Р%, * == 1,2,... ,п — собственные вектора(х,у) = Х/ ,!Л — скалярноепроизведение«=|Тем самым собственные значения А матрицы А являются корнямихарактеристического многочлена n-ой степени (5.2). Задача отыскания собственных значений и собственных векторов матрицы сводитсяк построению характеристического многочлена, отысканию его корнейи последующему нахождению нетривиальных решений уравнения (5.1)для найденных собственных значений.В вычислительной практике рассматривается как полная проблемасобственных значений, когда необходимо найти все собственные значения матрицы А, так и частичная проблема собственных значений, когдаищутся только некоторые собственные значения, например, максимальные (минимальные) по модулю.5.2.
Численные методы решения задачна собственные значенияНачнем с приведения некоторых полезных фактов о свойствах собственных значений и собственных векторов квадратной матрицы. Далеерассматриваются методы решения частичной и полной проблемы собственных значений.5.2. Численные методы решения задач на собственные значения675.2.1.
Свойства собственных значенийи собственных векторовКвадратная вещественная матрица порядка п имеет п собственных значений, при этом каждое собственное значение считается столько раз, каковаего кратность как корня характеристического многочлена. Для симметричной матрицы А собственные значения вещественны, а собственныевектора, соответствующие различным собственным значениям, ортогональны, т. е. (ф1, <р*) — О, если г Ф j .Отметим также некоторые свойства собственных значений и собственных векторов для сопряженной матрицы .4*:А*ф = цф.(5.3)Для спектральных задач (5.1), (5.3) имеемAj = /i,-,t=l,2,...,n,(уЛ^') = 0,хфуДве квадратные матрицы А и В одинаковых размеров называютсяподобными, если существует такая невырожденная матрица Р, что А =Р~1ВР.
Подобные матрицы имеют одни и те же собственные значения,так как из (5.1) непосредственно следуетВф = \ф,ф = Р<р.Поэтому вычислительные алгоритмы решения спектральных задач базируются на подобном преобразовании матрицы к матрице В, для которойспектральная задача решается проще. В качестве В естественно выбиратьдиагональную матрицу, причем в данном случае это будетA = diag{A,,A 2 ,...,A„}.Упорядочим собственные значения симметричной матрицы А по возрастанию, т.е. А| < А2 < • •• < А„. Свойства собственных значенийи собственных функций связаны с отношением Релея(Аз* д*^'Отметим,(х,х)например, что для любого ненулевого вектора х справедливы неравенства(Ах,х)А| ^ —. г- ^ Ап.(х,х)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*\т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
