Ильин, Позняк - Линейная алгебра (947283), страница 38
Текст из файла (страница 38)
Мы приходим к следующей теореме; Теорема б.4. Если матрицы А и В симметричны и положительно определены и если ТаВ ~ А ~ Т,В, то чебышевский итерационный процесс сходится, и для погрешности 2» после выполнения я итераций справедлива оценка «1) ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ 1Т9 Если в качестве условия окончания процесса взять для зара- нее заданной е-точности требование «2«««а < е«12««1а, то из тео- ремы б.4 получается для числа итераций л следующая оценка. й)йе(е) = .
Сравнивая эту оценку с установленной вы1и (е/2) 1и р, ше оценкой числа итераций для метода простой итерации а~яр(е)= —, мы получим прн условии, что величина )и е 1и (2!е) )и (1уе) $ =у»)у, мала, что й«(е)т, Йе(е)- . Сравнение 2 т' е этих оценок указывает на преимущество чебышевского метода (в слУчае, когда величина $ = 7,/7« мала). Описанный нами чебышевский метод известен еще с начала 50-х годов. Иногда его называют методом Ричардсона.
Следует отметить, что мы изучили этот метод для идеального вычислительного процесса с бесконечным числом знаков, в то время как на ЭВМ вычисления ведутся с конечным числом зна- ков, в связи с чем имеются числа, являющиеся машинной беско- нечностью М и машинным нулем.
Если в процессе вычислений на ЭВМ появляется число М, превосходящее М , то происходит аварийный останов машины (авост), С точки зрения идеального вычислительного процесса значе- ния итерационных параметров т, можно упорядочить как угодно (любым из а) способов). Любые две последовательности итера- ционных параметров «т,» с точки зрения идеального вычисли- тельного процесса эквивалентны, ибо для них требуемая е-точ- ность достигается за одно и то же число итераций. Но прн вычислении на ЭВМ различные последовательности параметров «т,«не эквивалентны.
Для одних последовательно- стей значений «т,«может произойти аварийный останов машины вследствие роста промежуточных значений. Для других после- довательностей значений «т,«аварийного останова машины не происходит, но в связи с немонотонным характером стремления к нулю погрешности 2», т. е. вследствие того, что норма матрицы Š— т,С перехода от ()' — !)-й итерации к )сй может быть больше единицы, для этой погрешности не справедлива установленная нами для идеальной ситуации оценка. Вследствие указанных обстоятельств возникает теоретиче- ская проблема — указать такой наилучший закон упорядочения значений «т,«, при котором для чебышевского метода было бы наименьшим влияние ошибок округления.
Исчерпывающее решение этой проблемы можно найти в книге А. А. Самарского «Теория разиостных схем», ))4., «Наука», 1977 год (с. 572 н далее), (гл. е итеРАциОнные метОды й 2. Решенне полной проблемы собственных значений методом вращений Ради простоты сначала будем рассматривать вещественную симметричную матрицу А, определяемую равенством (6.2), Заметим, что отыскание всех собственных значений н собственных векторов этой матрицы сводится к отысканию такой ортогональной матрицы Т, для которой произведение О = Т'АТ (6.29) представляет собой диагональную матрицу. В самом деле, если такая ортогональная матрица Т будет найдена, то диагональные элементы матрицы А) будут являться собственными значениями матрицы А, а столбцы матрицы Т будут являться соответствующими собственными векторами матрицы А «). Введем в рассмотрение сферическую норму матрицы А: )А~, = 2'; ~а,', Тогда, очевидно, для диагональных элементов матрицы А будет справедливо неравенство л Е асс ( 1А!!,э, (6.30) с-с причем это неравенство переходит в точное равенство только в случае, когда матрица А является диагональной.
Заметим теперь, что при ортогональном преобразовании матрас(и А (т. е. при преобразовании вида А = (сА)с, где (с' н К— ортогоиальные матрицы) сферическая норма этой матрицы не изменяется "). Отсюда следует, что от всех ортогональных прессбразованнй матрицы А преобразование (6.29) отличается тем, что это преобразование делает максимальной сумму квадратов диагональных элементов преобразованной матрицы н минимальной — сумму квадратов всех внеднагональных элементов этой матрицы. «) Для докззятелъствз этого обознэчнм через Хт, Хз, ..., Х„днэгонэльные элементы мэтРнцы 0 н положим ез* ')еэ«(!, где элементы еэс столбце еэ Удовлетворяют условию: еэ О прн АФ С н «ээ !.
Тогда, очевидно, Ое„=Хэез, с т. е. Т'АТеь Хъеъ, н твя яэх Т' = Т ', то АТеэ ХАТеъ. Следоветелъно Теъ являются собственными векторемн мэтрнцы А. ««) В сэмом деле, еслн А (сА)с, в снмвол (г С обознвчеет сумму всех эле. ментов мэтрнцы С, лежэщнх нз ее главной днэгонэля, то ~А ~Э - -(г (А' А) = = (г ()ТА'(У'(САД) .. й (Д'А'А)т) - ~А)т~,е= ~(А)т) ~~«Э — ))ТА'),"Э = (г (Айс)гА') (г (АА') =((А'!~Э !(А фе. метод ВРхшвний Методом вращения называется итерационный метод, при котором указанная выше матрица Т находится как предел бесконечного произведения элементарных матриц вращения, каждая из которых имеет вид 1 совф ...
1 (~'-я строка), (6.31) тц(ф) = 1 сок ф. 1 йся строка). В целом метод вращений состоит в построении последовательности матриц А Ат Ак~ " Ач~ Ат+с (6.32) аы — — ад, при й ~ 1, /, 1-ь г, /, ац=аасовф+аяв1пф при 1~с, /, йл — — — аав1пф+аясовф при 1чь/, /, а„=и„совф+ацвгпф при 1-ь1, /, йц — — — ац в1п ср+ ац сов ф при 1 чь 1, /, а„= (а„сов ф+ а» в1п ф) сов ф+ (ам сов ф+ ам в1п ф) в1п ф, ая = ( — ан в1п ф+ а» соз ф) сов ф+ ( — ац в1п ф+ ам сов ф) в1п ф, ац = — ( — а,~ в1п ф+ а» сов ф) в1п ф+ ( — ац в1п ф + ац сов ф) сов ф, йц = — (ап сов р + ад в1п ф) в 1п р + (ац сов ф + ац в1п ф) сов ф. (6 33) каждая последующая иэ которых получается из предыдущей при помощи элементарного шага вида Ати = ТцАяТц.
Если для упрощения записи опустить индекс о и рассмотреть один такой шаг А =ТцАТо, осуществляемый с помощью матрицы (6.3!), то для элементов ац преобразованной матрицы А мы получим следующие выражения через элементы ац матрицы А: 1гл. б ИТЕРАЦИОННЫЕ МЕТОДЫ 182 Из соотношений (6.33) и из условия симметричности матрицы А вытекает следующее легко проверяемое равенство: л л и и ХХ =~1 2 1 2 <'2! =,~,~ п~с — 2ам+ — [(ап — ас,) 21п21р+ 2аст соз2ср] . 2=1! 1 2=11 1 2 Сс сл ! (6.34) 2) угол поворота ср в матрице (6.31) выбрать так, чтобы было справедливо равенство (໠— а!1) зш 21р+ 2аы сов 21р О.
(6.351 Равенство (6.35) однозначно определяет угол ср, удовлетворяющий условиям (6.36) Это равенство позволяет вычислять соз ср и з)п ср по формулам соз 1 ! Г1 + (1+ р2)-1/Т2 з1п ср = зап р ~ — (1 — (1 + р') '")~ ~, где р = 2асс((асс — с!и). Заметим, что если матрица (6.31) выбрана так, что выполнены указанные выше требования 1) и 2), то равенство (6.34) переходит в следующее соотношение: 22 22 621= Е,сс а221 2а'и Ф!! 1 2=!1=1 2ФС 2+1 (6.31) в котором аст представляет собой наибольший по модулю вне- диагональный элемент матрицы. Из этого равенства вытекает, что для максимального уменьшения суммы квадратов всех виедиагоиальных элементов необходимо матрицу (6.31) выбрать так, чтобы были выполнены д в а требования: 1) номера 1 и 1 выбрать так, чтобы квадрат элемента а)с был наибольшим среди квадратов всех иедиагоиальных элементов матрицы А, т.
е. выбор номеров 1 и 1 подчинить условию ос~с = шах а21; !Ч2Ч» !~!~и 2+! метОд ВРАШений !зз Теперь мы можем более точно сказать, что метод вращений состоит в построении последовательности матриц (6.32), каждая последующая из которых получается из предыдущей посредством ортогонального преобразования А, ~ = Т), А, То, в котором матрица ТО = Ты (ф) выбирается так„чтобы были выполнены указанные выше два требования "). Докажем сходимость метода вращений.
Обозначим символом 5,* сумму квадратов всех внедиагональных элементов матрицы А„, а символом асо наибольший по модулю внедиагональный зле'«)« мент этой матрицы. Тогда в силу (6.37) справедливо равенство т 2 Г со чт 5,+,— 5,— 2~а, ) ~, ««~ (6.38) Далее, поскольку общее число внедиагональных элементов матрицы А, равно и (и — 1), а а, у — наибольший по модулю («) из этих элементов, то справедливо неравенство Из (6.38) и (6.39) вытекает неравенство 5,.ь1 ~5« ~!в (6.39) (6АО) 5,+1 ~ 5е(А) ~!в (6.4!) Из неравенства (641) сразу же следует, что 1пп 5'„1 = О, что ч «« и доказывает сходимость метода вращений.
В качестве приближенных значений собственных чисел матрицы А берутся диагональные элементы матрицы А„а в качестве приближенных собственных веиторов матрицы А берутся столбцы матрицы Ти, Т,, ... Т,,),. Более точные результаты получены В. В. Воеводиным ««). Длн случая, когда произвольная (не обязательно симметричная) матрица А не имеет жорда- ') Номера ! н / на каждом шаге выбираются такими, чтобы наибольшим по модулю являлся внеднагональныа элемент матрицы А„с этими номерамн, ") В. В. Воеводин. Численные методы ангебры, Теория и алгорифмы. — М„Наука, !9бб. Последовательно используя неравенство (6.40), записанное для номеров О, 1, ..., ч, и обозначая через 5е = 5е а(А) сумму квад- ратов всех внедиагональных элементов основной матрицы А, мы получим, что [гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
