Бабенко - Основы численного анализа (947491), страница 111
Текст из файла (страница 111)
Методге реиленив аогеброичееной вроблеьмьг гобетоенньгх вночмшй 639 интерполяции и пользоваться формулой (4) в процессе приближенного вычисления корней уравнения (3). Найдя собственное значение до соответствующий собственный вектор предлагается определять, решая совместную систему (1), например методом!'аусса. Данный метод по числу операций уступает методам Крылова и Данилевского, поскольку требует для определения характеристического многочлена .= п~~г3 умножений и делений. Однако это далеко не главный дефект этого метода.
Основной его нодостаток (и это уже должно быть ясно читателю) состоит в его малой точности даже для матриц не очень высокого порядка. А,=Р, лАггг ьРго.ы пг=1,2, г .4о=А таким образом, чтобы предельная матрица .4, = 11ш А была либо т ео диагональной, либо треугольной. Для симметрических матриц в качестве такой группы матриц преобразования берется группа ортогонавьных матриц 0(п). Пусть ортогональная матрица Олм имеет элементы в позициях (1, г), (г, д) г (~, г), (71 д), равные соответственно с, — в, в, с; остальные диагональные элементы равны 1, а внедиагональные равны О. Величины с, в вещественные числа, удовлетворяющие соотношению сэ ' ва = 1.
Легко подсчитать элементы матрицы В = АО, Ясно, что вне 1-го н дьго столбцов элементы матриц Аг В будут совпадать, а 1-й н бпй столбцы лгатрицлп В будут иметь вид (ое) 6, = саг + зад г Ьд = — ва, ' сЬю где а„ад -- соответственно бй, дьй столбцы матрицы А. Если С = 0' В = гг .—.. О,' АО, и с', Ь', о', 6' гуты-е ибле строки матриц С, В. соответственно, то с =.Ь +вЬд, сг = — вЬ -,.6~.
(6) а остальные строки матриц С, В совпадают. Полагая С = (сы)" ~ из соотношений (о), (6) получим сн =-с агг -, '2свачэ -в ало д цо = ам(с — в ) —, св(аю — ан), сВ = в ан — 2свагд+ с адгч см = ам, (7) й ф г, У. 1 ф г',г 71 2. Метод Якоби. Описание итерационных методов начнем с метода, используемого для решения полной проблемы собственных значи ний для симметрической матрицы А, предложенного К. Якоби в 1846 г.
Итерационные методы решения полной проблемы собственных значений основаны на следующем соображении. При переходе от лгатрицы А к подобной матрице В =- Р лАР спектр сохраняется, а, собственные векторы преобразуются очевидным образом: ж = Ру, где уг ю - собственные векторы соответственно матриц В, А. Далее выбирается группа матриц Р, определяющих преобразование подобия, и стронтся последовательность матриц 540 Глава 3, Теория итграций и лчвтоды рвштшя нзкоторит задач Если ры ..., р„-- собственные значения матрицы Аг, то ее след зр Аг = р инвариантен относительно преобразования подобия. Поэтому з=з ~ а~~~ — — эр А = зр (О'ЛгО) = зр Сг, цг-:з и, следовательно, о о'-(А) .- о~(С) .
~(сьь — ааль). ь=1 (9) Из формул (5), (6) вытекает, что аьт = сею если й Г' з, ~. Рассматривая матрицы второго порядка Из приведенных формул можно сделать некоторые вполне очевидные выводы. Прежде всего покажем. что с помощью конечного числа преобразований подобия посредством матриц типа О, можно произвольную симметрическуго матрицу преобразовать к трехдиагональззому виду.
В самом деле, элементы матрицы Ом определим из условия сжз, = О, а в силу (5), (6) это условие можно записать в виде са ц, + зазтз = О. Поэтому достаточно положить альп з аз, цз 2 г 112' ' г г 1дг' (а„к, + а...) (а~,, — ' а...) Отсюда следует„что для того, чтобы получить матрицу, у которой элементы в позициях (п, 1), ..., (и, и — 2) равны нулю, нужно применить последовательно преобразования О„ г „ и ..., Оз „ н Затем можно у полученной матрицы обратить в нуль элементы в позициях ~п — 1, 1), ..., (п — 1,п — 3), применяя последовательно преобразования О„з „г, ..., Оз „г. Равные нулю элементы и-й строки в силу соотношений (5) не будут меняться. Продолжая этот процесс, получим в итоге трехдиагональную матрицу, поскольку последующие преобразования не будут менять ранее аннулированные элементы. Всего нам придется сделать 1+... + и — 2 = (п — 1)(п — 2)/2 преобразований подобия.
Таким образом, задача на собственные значения для произвольной симметрической матрипы сводится к аяалогичной задаче, но для трехдиагональной матрицы. Теперь обсудим метод Якоби. Параметры с, г преобразования Ои и саму позицию (1, г) целесообразно определить, требуя, чтобы вновь полученная мартица была ближе к диагональной, чем исходная матрица.
В качестве меры близости возьмем сумму квадратов нелиагональных элементов в и о (А) = ) а~~г — ~~~ аью й, г--.1 т=1 э 7. Меглодм 7гегггеггггл алгебуеическоп вроблемм собсшесниьгт, оилчигип 041 замечаем., что в силу соотношений (7) "г =-0 АО, н поэтому из (8) получаем 2 2 э 2, э э 2 с„1с +2с,«=пи л.а + а, Стало быть, из (9) вытекает, что ти(А) — сг~(С) = 2(а — с ). (10) Отсюда следует, что если мы на каждом шаге позицию (г, «) будем выбирать нз условия 'а, ' = шах)аы~ мг ьу'-г и потребуем, чтобы с, = О, то получим последовательность симметрических матриц (.4ог), для которых гт (Ае) > сг' (Аг) > ..., где Ае = А.
Условие с, = 0 в силу (7) приводит к уравнению я в, (с — о )+ се(а — ав) = О, полагая в котором с = сов Вг е = гйп В, получим сй2В = агг агэ Угол д определим условием В, < я/4; тем самым все элементы матрицы О,' АО, будут однозначно определены. Рассмотрим вопрос о быстроте сходимости последовательности 1А ). Поскольку гтэ(А) < п(п — 1)ал, то из (10) получаем сг~(С) =- о~(А) -- 2а' < (1-- )си(А), и, следовательно, о'(Агл,-г) < (1 и'(4гл); (и — 1)п.г поэтому на(.4 ) < (1 — ) о. (Ло). Тем самым доказана ссодимость метода Якоби.
Если собственные значения матрицы А различны, то можно получить болев точные результаты о скорости сходимости метода Якоби. В основе дальнейших рассуждений лежит следуяпцее простое 542 Глава 3, Творил итераций и методы решения некоторых задач Ь~э (и — 1)«езСа Ьн — Ьо ~ Да(С вЂ” 2)(С вЂ” '!) Доклзатнльство. 1(руг 1(, = Л: Л вЂ” Ьи, < 2 Ь„~ лежит в круэф« ге 1(; —..
(Л: ~л — Ь„~ < (п — 1)«), и, согласно условию, он не пересекается с кругами 1( (~ ф 1). Поэтому в круге 1(, лежит собственное значение Л, матрицы В. Собственный вектор х = (хы ..., х„х,, ы.... х„), согласно предложению 5 Э 1, нормируем условием т, = 1. Тогда, записывая в координатах соотношение Вх = Л,х, получим хь — —— ь..— л, ь-,— л, ~Ам « Ьа — Л, = — ~~ Ь„х,. эф! (14) Заметим, что в силу условия предложения ~ьрй — Л,( = 'Ььь — Ьи + Ьи Л,~ «э Д вЂ” ~ьи — л.: 3 > Д вЂ” ( — 1)е > (1 — С ')Д.
Поэтому и, следоватешьно, складывая эти неравенства, получим С(п — 1)в Е ' (С... 2)Д Подставляя в (14) соотношения (13) и используя последнее неравенство, после простых преобразований придем к неравенству (12). П Допустим теперь, что собственные значения матрицы А удовлетворякет неравенству ~ль — Лр > Д (й ф 1). После т итераций матрица Ао, будет иметь элементы а., удовлетворяющие неравенству а„< е 1т1 (ы) (й эс 1).
Если (и -- 1) Д" 1 « 1, то для любого ~', =. 1, 2, .... п матрица А„„ будет удовлетворять предложению 1. Поэтому Ле =а 'ЬО(в ) Предложение 1. Пусть В = (быф ~ — симмелпри сескал матрица, элементы, которои удовлетворюот неравенствам Ьы <. (й ф1); (Ьи — Ььь( > Д > 0 (й ф 1), Если (и, — 1) "Д з < С «(С > 2), то леатрица В имеегп собственное значение Л, такое., что й 7. Методы релисиил олгебраи меной проблемы собственныя оночений 343 При дальнейшем проведении итераций угол О., определяемый соотношением (11), будет порядка е, поскольку числитель -- порядка, а знаменатель отграничен от нуля величиной г1 — 2(п — 1)с. Все меняющиеся недиагональпые элеъгенты на данном шаге итераций изменяются на величину порядка еэ, так как в формулах (о), (6) с = 1+ 0(ггэ) = 1+ 0(ея), в =- 0(е). Следовательно, не более чем через п(п — 1)уг2 итераций все недиагональные элементы будут иметь порядок 0(еэ), и, стало быть, налицо квадратичная сходимость метода Якоби.
В случаях кратных собственных значений картина будет сложнее. ."гг!ы описали одну из тактик проведения якобиевых итераций. Применяются и другие тактики (см. (11О, 114)). Собственные векторы матрипы Л находятся после того, как мы получили матрицу А — По'олАПои, с малыми элементами вне диагонали. Определим компоненты вектора с = (сг, ..., ~г г, 1, с,.„г, ..., со)' с помощью формул 1га1 — — й -~ г — — .гг, ама — а„ Тогда вектор (Почи)Е будет приближенным собственным вектором матрицы Л, причем, как следует из формул (12), (13), его компоненты определены с точностью е~. 3.
Е1е и ЯЯ алгоритмы. Несмотря на численную устойчивость метода Якоби, в практической деятельности он вытеснен другими итерационными методами, обладающими большей скоростью сходимосги и пригодными для произвольных комплексных матриц. Опишем один из таких методов так называемый ЕВ-алгоритлг. В 32 мы установили, что при выполнении определенных условий матрица А может бьгть представлена, в виде (15) где Š— нигкняя треугольная матрица с диагональными элементами, равными единице, В верхняя треугольная матрица.
Это разложение единственно. В итерационном процессе, на основании которого строится Ей-аеы горитм, в качестве группы матриц преобразований берутся нижние треугольные матрицы с диагональными элементами, равными единице. Из (13) ггоггучаем 544 Глава 3, Творил итераций и методи решения некоторых задач и далее полагаем Аз = ЕеЛе, Е АеЕе = ЛеЕз = Аю а в общем случае — у Ао~ = ЕтЛ,и, 1т'АоеЕо, —.- ЛтЕео = Атль (16) Если указанное построение возможно, то мы получаем последовательность подобных матриц, которые будут сходиться к верхней треугольной матрице в случае различных собственных значений. В самом деле, пусть собственные значения матрицы А удовлетворяют неравенствам ~Л ' » ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
