Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 53
Текст из файла (страница 53)
Снова применяем формулы (10), (11), (12), увеличив в них все инлексы на единицу. Получим 14 — — 0.84456137. После шести шагов процесс стабилиз14руется на Гз = 0.79670667. Это значение совпадает в пределах точности с )ч. 314 ПОЛНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ (гл, Г/ Вычисляем теперь другой корень, исходя нз тех же начальных приближений (А=О, (,=0.3, (а=1. Значения у, находим по формуле у,=, ', .)Л вЂ” ГВ!. После трех шагов процесса получим ) з = 0 63828382 с удовлетворительной точностью.
5 50. Метод ортогонализации последовательных итераций Излзгаемый метод, подобно методу А. Н. Крылова и методу Хессенберга, имеет целью отыскание равной нулю линейной комбинации последовательности итераций произвольного вектора матрицей А. В то время как в методе Крылова это делается прп помоши решения линейной системы, а в методе Хессенберга постепенным наращиванием нулевых компонент в „исправленных" итерациях, в этом параграфе мы для той же цели применим процесс ортогоиализации.
Именно, исходя из вектора Х„строим его итерацию АХ, и ортогонализуем ее с вектором Х„т. е. строим вектор Х = АХ, +дых, так, что (Х,, Х,)=0. Это будет выполнено, если (АХО Хг) Х~~= — (Х,,'Х„) . Далее, строим вектор АХ, и ортогонализуем его с векторами Х, и Х,. В результате придем к вектору Х,=АХ+и,„Х,+А Х,, где (Ахь Хг) (АХа, Хе) ам = (Х„Х,) К' = (Х„Х.) Процесс естественно продолжается по формулам Хг,, =АХ,+д; Х, +умха+ ... +д.нхп (АХО ХА) х х (й=' 2 .'0 (Ь А) до тех пор, пока мы не придем к нулевому вектору. Это во всяком случае произойдет на а-м шагу процесса, но может случиться и ранее, если минимальный аннулирующий Х, полипом не является характеристическим полиномом.
Ясно, что Хг+, — — чь (А) Х,, где полиномы т,(Г) связаны друг с другом рекуррентными соотношениями т (()=(Г+-абдт~- Ю+ . +8мтв(Г). ф 50] мвтод огтогонализлции последовательных итвглций 315 Таким образом, вычислив все коэффициенты л.;., мы можем последовательно вычислить все полиномы Тв — — 1, у,(Г),, 9~(()=т(Г) В случае, если процесс оканчивается раньше времени. мы получим минимальный аннулирующий вектор Х, полипом. Заметим, что в нормальном сдучае АХ+ХО=О, где Х есть неособенная мзтрнца со столбцами Х,, ..., Х„, а Юп и'ш ь'2н в пи Таким обрззом, матрица А подобна матрице — О.
Это обстоятельство позволяет определить собственные векторы матрицы А в точности тем же процессом, что и в методе Хессенберга. В прилагаемой табл. !Н. 12 дается численная иллюстрация метода на примере матрицы Леверье. Таблица состоит из пяти частей. В первой части помещены взаимно ортогональные векторы Х,, ..., Х, и их итерации.
Части П, !П и !Н содержат (Х,', Х„), (АХ„ Хь) и лц, соответственно. В части Н вычисляются коэффициенты характеристического полинома по рскуррентным формулам. При вычислении итераций производится обычный контроль по суммам. Из табл. !Н. 12 видно, что коэффициенты характеристического полинома вычислены с достаточной степенью точности. В качестве контроля можно также вычислить теоретически нулевую матрицу АХ+ОХ. Метод ортогонализации итераций в общем случае довольно трудоемок. Обьем вычислительной работы при его применении больше, чем, например. при применении метода Хессенберга. Однако в случае, если матрица А симметрична, картина чрезвычайно упрощается, именно, в этом случае матрица О будет трех- диагональной. Лействительно, матрица Х, столбцы которой попарно ортогональны, может быть представлена в виде Х= УО, где (У вЂ” ортогональная матрица, В=(д,, ..., г(„1, г(г=~ (Хп Хг).
Из равенства АХ+ ХО =0 следует, что ООО = — У 'АУ. Если А симметрична, то матрица — У 'АУ тоже симметрична. Следовательно, г(щфг — — г(гп,к(; ~ Так как дм — — О при 1 — /) 1, то д~; — — О при 1 — у) 1, т. е. О действительно есть трехдиагональная матрица. Метод ортогонализации итераций в применении к симметричной матрице носит название метода м я н им альных итераций. Он бьш впервые описан Ланцошем в его широко известных работах [2! — (5!. Среди вычислительных методов линейной алгебры метод 316 ПРОБЛЕМА СОБСТВЕННЫХ ЭНАЧЕННЙ (ГЛ. !ч ПОЛНАЯ с- л в о 'С' ОЪ "С' ОЪ Яй Я о о я со я о со со сс !«., сс со й'Д сс оов СС СС О О О Фс О О с О О СС О й о П о О О \ о' М Ф о' И А$ ОООО сО О О ф сО о оя О О О СС о ( о со яВ со о со' со Яя Я со о СО "С со о со о о о о о о о с-: ! Й о й" со 3 со о сс Сс СС 5:"яз со Ю Сс со осч Й Я ( ( со Ф со о СО сО со со о со ' со о ф 51) Метод ВРАщения минимальных итераций занимает исключительно важное положение в виду многочисленных связей его с другими современными методами, точными и итерационными.
Методу минимальных итераций и его обобщениям будет посвящена гл. Ч!.и частично гл. Ъ!!. 5 51. Преобразование симметричной матрицы и трехдиаго- нальному виду посредством вращений Вращением мы будем называть преобразование координат с эле- ментарной матр ицей врзщения 1 ' !1) В; = — сА;+ аА~ Вт — — — зА;+ сА~. (2) т) Г и вен с !1), [2!. при се+ за = 1. Геометрически вращение может быть интерпретировано как поворот базисных векторов е; и ет на некоторый угол, осуществляемый в плоскости, натянутой на векторы е; и е . Матрица Тн ортогональна. Мы покажем,') что любую симметричную матрицу можно привести к трехдиагональной форме посредством цепочки вращений, т.
е. цепочки преобразований подобия с матрицами вила Тн. Произведем необходимые подсчеты. Пусть А †симметричн матрица, В = АТсн С = Т,',В = Т,',АТО Легко видеть, что все столбцы матрицы В совпадают со столбцами матрицы А, за исключением 1-го и У-го столбцов, которые получаются из соответствующих столбцов матрицы А по формулам: 318 полнАЯ НРОБлемА сОБстВенных знАчений (ГЛ. Ю аг с= л -+л. 1.00 0.42 0.64 ' 0.66 0.42 1.00 0.32 0.44 0.54 0.32 1.00, 0.22 0.66 0.44 0.22 1.00 (4) В свою очередь строки матрицы С совпадают со строками мат- рицы В, за исключением 1-й и у-й, которые получаются из соответ- ствующих строк матрицы В по таким же формулам: С = сВ' + ЯВ' С' = — лВ'+ сВ', При этом для построения строк С и С' нужно вычислить только четыре элемента си, с;,, с О с г (причем с,; только для контроля, так как су,— — с;, но онн получаются неодинаковыми вычислениями). Остзльные элементы строк С' и С" не только теоретически равны соответствующим элементам столбцов В, и В), но при их вычисле- нии выполняются одинаковые действия.
Пусть 1 ч.(ч.~. Покажем, что с и з можно выбрать так, чтобы с;,;=О. Действительно, с;, =дг;= — за; „+са,, так что в лг достаточно взять — = — и, следовзтельно, с аг а~ 3= щ ) аа ы+ ага Выбор знака знаменателя безразличен. Весь процесс приведения симметричной матрицы к трехдиагональ- ному виду выглядит так. За счет преобразований посредством Т,з :., Т,„ аннулируются по очереди элементы первой строки, начиная с третьего. Затем за счет Тзи ..., Т,„ аннулируются эле- менты второй строки, начиная с четвертого. Ясно, что при этом элементы первоИ строки больше меняться не будут.
Действительно, первые два элемента первой строки не будут меняться при преобра- зованиях посредством Тзп ..., Т,„. Оставшиеся, равные нулю эле- менты, будут подвергаться линейным однородным преобразованиям и потому останутся равными нулю. Далее, за счет преобразований посредством Тмв ..., Т,„ аннулируются элементы третьей строки, начиная с пятого и т, д. Из сказанного выше ясно, что каждое последующее преобразо- вание не будет изменять ранее аннулированные элементы. ' Таким (л — 1) (л — 2) образом, самое большее через преобразований, мы пе- рейдем от двиной симметричной матрицы А к трехдиагональной матрице О'.
Вычислительную схему метода проиллюстрируем на примере матрицы 319 ф 51! метод ВРАщения уже встречавшейся ранее в примерзх решения системы линейных уравнениИ. Характеристический полипом этой матрицы равен !" — 4!а+ 4.?52Р— 2.! 11856!+ 0.28615248. Здесь все коэффициенты вычислены точно. Собственные значения матрицы (4), вычисленные с точностью до 5 ° 10 ', суть )„ =- 2.32274880, )ч = 0.79670669, Лз = 0.63828380, )ч = 0.24226071. Процесс трехдиагонализацни проведен в табл.
1Ч.1 3. Таблица состоит из четырех частей. В части !1 наряду с данной матрицей А расположены результаты последовательных преобразований подобия посредством Т,, Та, Т„. Последняя матрица является искомой матрицей Б. Части ! и !Ч вспомогательные, часть !1! — контрольная. Дадим описание одного шага заполнения таблицы (заключающегося в осуществлении преобразования посредством матрицы Тм). В части !! переписываются все элементы предыдущей матрицы, кроме элементов, лежащих в двух строках и двух столбцах с номерами ! и 7'. Затем (-й и 1-й столбцы преобразуются по формулам (1) и элементы преобразованных столбцов, кроме элементов с индексамн !1, !7, 7!. 77' записываются ва надлежащие местз в части П. Выделенные четыре элемента вносягся в часть !.
Образованная матрица заполняется далее по симметрии. Оставшиеся четыре элемента строятся затем по формулам (2) над числами, помещенными в части 1. В четвертую часть записываются коэффициенты с и з, определяющие матрицы вращений (в последней строке) и необходимые для их вычисления числа. Контроль (часть И!) осуществляется при помощи вычисления соответствующих столбцовых сумм (для контроля операций над столбцами) н при помощи вычисления следов построенных матриц, которые должны быть равны между собой.
После того, как построена трехдиагональная матрица, подобная исходноИ матрице А, отыскание собственных значений может быть осуществлено различными способами. Наиболее прямым путем является построение характеристического полинома у(!) для матрицы 3 (а следовательно. и подобной ей матрицы А) по рекуррентным формулам Р, = 1, 7, (7) = — (! — за,) ~, , (!) — з,. „~, а (Т), !„ (!) = ( — 1)" У (!) и затем нахождение его корней. ЗНАЧЕНИЙ !ГЛ. 1сР ПОЛНАЯ ПРОБЛЕМА СОБСТВЕННЫХ Яйд ЯЯО ОООО зй! 39 ОО (фЯ ОО сОО О 00 О С ССС ОООО ! о ! 00 С'0 О О ! ! 33 О О а О О О 1~ЯЗ 3 й,8 О О О ОООО 'С' СС Я С'С ОООО ! й - ь оо О 'Оо О О О р 4 Ф й О СЗ СД О О О О ООО Ой 00 О О яз 00 315 ООО ! й~й о Н! сч ОООО й О О ООО Й ! ОО ! -й О О С- о сс 00 00 О с0 00 сс о Сс с' СС С'0 с' о О СС 0с О О Д Оо О О О О ! с;! а С0 00 С' с Б! О ф Сс СО о о с'с с с с0 С'4 О О О О э 5Н метод ввхщиння Коэффициенты полиномов 1~) (г) удобно вычислять следующим образом, Коэффициенты располагаются согласно схеме ООО .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
