1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 69

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 69)

 .   . an104223. Численные методы линейной алгебрыт. е. занулялись бы элементы a31 , . . . , an1 в первом столбце. Нетрудновидеть, что Q1 выглядит следующим образом1 0 ··· 0 0 0 × ··· × × .... ...×.. .0Q1 =  .. .. . . . .. × × 0×··· × ×Далее, когда A умножается на такую матрицу Q1 слева, то в ней неизменяются элементы первой строки. Когда матрица Q1 A умножаетсяна Q⊤1 = Q1 справа, то в ней не изменяются элементы первого столбца.Поэтому в матрице Q1 AQ⊤1 , как и в Q1 A, первый столбец имеет нулив позициях с 3-й по n-ую.Далее выбираем матрицы отражения Q2 , Q3 , .

. . , Qn−2 так, чтобыумножение слева на Qi давало нули в позициях с (i + 2)-ой по n-ую вi-ом столбце. Эти матрицы имеют вид!0I,Qi =0 Q̃iгде в верхнем левом углу стоит единичная матрица размера i × i, аQ̃i — матрица отражения размера (n − i) × (n − i). При этом последующее умножения справа на Q⊤i = Qi также не портит возникающуюпочти треугольную структуру результирующей матрицы. Получающаяся в итоге матрица QAQ⊤ с Q = Qn−2 . . . Q1 действительно являетсяверхней почти треугольной.Далее мы увидим, что хессенбергова форма матрицы в самом делепомогает при реализации некоторых методов решения проблемы собственных значений, а частности, QR-алгоритма (см.

§3.18г).3.17Численные методы для симметричнойпроблемы собственных значенийи сингулярного разложенияСимметричная проблема собственных значений, как мы могли видеть, своими свойствами выделяется из общей проблемы собственных3.17. Численные методы для симметричной проблемысобственных значений изначений матриц. Для симметричных (эрмитовых в комплексном случае) матриц все собственные значения вещественны, а собственныевекторы ортогональны. Симметричная проблема собственных значений обладает хорошей обусловленностью.

Эти обстоятельства позволяют выделить её в качестве важнейшего частного случая общей проблемы собственных значений. Кроме того, с симметричной проблемойсобственных значений для матриц!0 A∗∗∗A A,AA ,A 0тесно связана с задачей нахождения сингулярного разложения матрицы A (см. §3.2г). Как следствие, логично рассматривать вместе численные методы для симметричной проблемы собственных значений исингулярного разложения.3.17аМетод Якоби для решения симметричнойпроблемы собственных значенийВ этом параграфе мы рассмотрим численный метод для решениясимметричной проблемы собственных значений, т.

е. для вычислениясобственных чисел и собственных векторов симметричных матриц. Онбыл впервые применён К.Г. Якоби в 1846 году к конкретной 7 × 7матрице, а затем был забыт на целое столетие и вновь переоткрытлишь после Второй мировой войны, когда началось бурное развитиевычислительной математики.Идея метода Якоби состоит в том, чтобы подходящими преобразованиями подобия от шага к шагу уменьшать норму внедиагональной части матрицы. Получающиеся при этом матрицы имеют тот же спектр,что и исходная матрица, но будут стремиться к диагональной матрицес собственными значениями на главной диагонали.

Инструментом реализации этого плана выступают элементарные ортогональные матрицывращений, рассмотренные в §3.7д. Почему именно ортогональные матрицы и почему вращений? Ответ на эти вопросы станет ясен позднеепри анализе работы алгоритма.Итак, положим A(0) := A. Если матрица A(k) , k = 0, 1, 2, . . . , ужевычислена, то подберём матрицу вращений G(p, q, θ) вида (3.86) такимобразом, чтобы сделать нулями пару внедиагональных элементов в позициях (p, q) и (q, p) в матрице A(k+1) := G(p, q, θ)⊤ A(k) G(p, q, θ). Желая4243.

Численные методы линейной алгебрыдостичь этой цели, мы должны добиться выполнения равенства(k+1)apq(k+1)(k+1)aqqapp(k+1)aqp!=cos θ − sin θsin θ cos θ=×00×!!⊤(k)apq(k)aqqappaqp(k)(k)!cos θ − sin θsin θ cos θ!,где, как обычно, посредством «×» обозначены какие-то элементы, конкретное значение которых несущественно.

Строго говоря, в результатерассматриваемого преобразования подобия в матрице A(k) изменятсяи другие элементы, находящиеся в строках и столбцах с номерами p иq. Этот эффект будет проанализирован ниже в Предложении 3.17.2.Опуская индексы, обозначающие номер итерации и приняв сокращённые обзначения c = cos θ, s = sin θ, получим×00×!=app c2 + aqq s2 + 2scapq2sc(aqq − app ) + apq (c2 − s2 )2sc(aqq − app ) + apq (c − s )22app s + aqq c − 2scapqПриравнивание внедиагональных элементов нулю даёт.app − aqqc2 − s2=.apqscПоделив обе части этой пропорции пополам, воспользуемся тригонометрическими формулами двойных углов:app − aqqc2 − s2cos(2θ)1===.2apq2scsin(2θ)tg(2θ)Результат проведённой выкладки для удобства дальнейшего использования обозначим через τ , т.

е. τ = 1/ tg(2θ).Пустьsin θ= tg θ.t :=cos θ3.17. Численные методы для симметричной проблемысобственных значений иВспоминая тригонометрическую формулу для тангенса двойного углаtg(2θ) =2 tg θ,1 − tg2 θмы можем прийти к выводу, что t является корнем квадратного уравненияt2 + 2τ t − 1 = 0.(3.151)Его дискриминант (4τ 2 + 4) положителен и, следовательно, уравнение(3.151) всегда имеет вещественные корниpt1,2 = −τ ± τ 2 + 1.При этом из двух корней мы берём наименьший по абсолютной величине, равныйpt = −τ + sgn τ · τ 2 + 1,если τ 6= 0,если τ = 0.t = ±1,Первую формулу для улучшения численной устойчивости лучше записать в виде, освобождённом от вычитания близких чисел, так чтосоответствующий корень есть√√(−τ + sgn τ · τ 2 + 1)(τ + sgn τ · τ 2 + 1)√t =(τ + sgn τ · τ 2 + 1)=1√(τ + sgn τ · τ 2 + 1)при τ 6= 0.Наконец, на основе известных тригонометрических формул, выражающих косинус и синус через тангенс, находим c и s:1,c= √2t +1s = t · c.Займёмся теперь обоснованием сходимости метода Якоби для решения симметричной проблемы собственных значений.Предложение 3.17.1 Фробениусова норма матрицы A, т.

е.!1/2nX,a2ijkAkF =i,j=14263. Численные методы линейной алгебрыне изменяется при умножениях на ортогональные матрицы слеваили справа.Доказательство. Напомним, что следом матрицы A = (aij ), обозначаемым tr A, называется сумма всех её диагональных элементов:tr A =nXaii .i=1Нетрудно проверить, что привлечение понятия следа позволяет переписать определение фробениусовой нормы матрицы таким образом!1/2nnXX1/2aij aij = tr (A⊤ A).kAkF = j=1i=1Следовательно, для любой ортогональной матрицы Q справедливо1/2kQAkF = tr (QA)⊤ (QA)=1/2tr A⊤ Q⊤ QA=1/2tr (A⊤ A)= kAkF .Для доказательства аналогичного соотношения с умножением на ортогональную матрицу справа заметим, что фробениусова норма не меняется при транспонировании матрицы.

Следовательно,⊤ kAQkF = Q⊤ A⊤ F = kQ⊤ A⊤ kF = kA⊤ kF = kAkF ,что завершает доказательство Предложения.Следствие. Фробениусова норма матрицы не меняется при ортогональных преобразованиях подобия.Для более точного описания меры близости матриц A(k) , которыепорождаются конструируемым нами методом, к диагональной матрицевведём величину!1/2X2ND(A) =aijj6=i— фробениусову норму внедиагональной части матрицы. Ясно, чтоматрица A диагональна тогда и только тогда, когда ND(A) = 0.3.17.

Численные методы для симметричной проблемысобственных значений иПредложение 3.17.2 Пусть преобразование подобия матрицы A спомощью матрицы вращений G таково, что в матрице B = G⊤ AGзануляются элементы в позициях (p, q) и (q, p). ТогдаND 2 (B) = ND 2 (A) − 2a2pq .(3.152)Итак, в сравнении с матрицей A в матрице B изменились элементыстрок и столбцов с номерами p и q, но фробениусова норма недиагональной части изменилась при этом так, как будто кроме зануленияэлементов apq и aqp ничего не произошло.Доказательство. Для 2 × 2-подматрицы!app apqaqpaqqиз матрицы A и соответствующей ей 2 × 2-подматрицы!bpp 00 bqqв матрице B справедливо соотношениеa2pp + a2qq + 2a2pq = b2pp + b2qq ,так как ортогональным преобразованием подобия фробениусову нормаматрицы не изменяется.

Но, кроме того, kAk2F = kBk2F , и потомуND 2 (B) = kBk2F −=kAk2F−nXb2iii=1nXa2iii=1= ND 2 (A) − 2a2pq ,−a2pp+a2qq+b2pp+b2qq!поскольку на диагонали у матрицы A изменились только два элемента— app и aqq .4283. Численные методы линейной алгебрыТаблица 3.11. Метод Якоби для вычисления собственныхзначений симметричной матрицыВходСимметричная матрица A.ВыходМатрица, на диагонали которой стоят приближенияк собственным значениям A.АлгоритмDO WHILE метод не сошёлся )выбрать ненулевой внедиагональныйэлемент apq в A ;обнулить apq и aqp преобразованием подобияс матрицей вращения G(p, q, θ) ;END DOТеперь можно ответить на вопрос о том, почему в методе Якобидля преобразований подобия применяются именно ортогональные матрицы.

Как следует из результатов Предложений 3.17.1 и 3.17.2, умножение на ортогональные матрицы обладает замечательным свойствомсохранения фробениусовой нормы матрицы и, как следствие, «перекачивания» её величины с внедиагональных элементов на диагональв результате специально подобранных цепочек таких умножений. Придругих преобразованиях подобия добиться этого было бы едва ли возможно.Итак, всё готово для организации метода вращений Якоби — итерационного процесса приведения симметричной матрицы к диагональному виду, при котором внедиагональные элементы последовательноподавляются. Как уже отмечалось, занулённые на каком-то шаге алгоритма элементы могут впоследствии вновь сделаться ненулевыми.

Норезультат Предложения 3.17.2 показывает, что норма внедиагональной части матрицы при этом всё равно монотонно уменьшается. ВТабл. 3.11 схематично представлен простейший вариант метод Якоби.3.17. Численные методы для симметричной проблемысобственных значений иРассмотрим вопрос о критерии остановки метода Якоби, тесно связанный с оценкой точности получающихся приближений к собственным значениям. Очевидной идеей является использование нормы NDвнедиагональной части матрицы, когда итерации останавливаются придостижении неравенства ND(A) < ǫ для заданного допуска ǫ > 0.

Ноболее элегантное решение этого вопроса может быть основано не теореме Гершгорина (см. §3.16г). Если A — симметричная n × n-матрица,полученная на каком-то шаге метода вращений Якоби, то ясно, чтоеё собственные значения локализованы в интервалах [aii − ∆, aii + ∆],i = 1, 2 . . . , n, гдеX∆ = max|aij |.1≤i≤nj6=iПри общем уменьшении величины внедиагональных элементов значение ∆ также становится маленьким и обеспечивает точность оценивания собственных значений, лучшую чем с помощью ND.Различные способы выбора ненулевых внедиагональных элементов,подлежащих обнулению, приводят к различным практическим версиям метода Якоби.

Выбор наибольшего по модулю внедиагональногоэлемента — наилучшее для отдельно взятого шага алгоритма решение.Но поиск этого элемента имеет трудоёмкость n(n − 1)/2, что можетоказаться весьма дорогостоящим, особенно для матриц больших размеров. Преобразование подобия с матрицей вращений обходится всегов O(n) операций! Чаще применяют циклический обход столбцов (илистрок) матрицы, и наибольший по модулю элемент берут в пределахрассматриваемого столбца (строки).Наконец, ещё одна популярная версия — это так называемый «барьерный метод Якоби», в котором назначают величину «барьера» назначение модуля внедиагональных элементов матрицы, и алгоритм обнуляет все элементы, модуль которых превосходит этот барьер.

Характеристики

Список файлов книги