В.А. Ильин, Э.Г. Позняк - Линейная алгебра (4-е издание) (1113059), страница 37
Текст из файла (страница 37)
Последние неравенства эквивалентны тому, что у,Е ~ С ~ у,Е. Поскольку кроме того матрица С = = В-и» А В-и» симметрична, то все собственные значения этой матрицы вещественны и расположены на отрезке (у„у,!. После- довательно записывая соотношение У»„= (Š— т»„С) У» для номеров й = О, 1, ..., мы придем к следующему равенству: У» = П(Š— т,С) У„ ! ! нз которого сразу же вытекает, что » )!У») (~11(Š— ч,С) )У»(. 1/=! Но тогда из равенства ) У»/! = ЦЕ»)л вытекает, что Ц4,1 яГ о»'1'Я»)~, где д» = »11 (Š— ч»С) . Следовательно, итера- 1» ! ционный процесс сходится при условии, что последовательность «и») стремится к нулю, причем тем быстрее, чем меньше вели- чины д».
111 итяРХНИОНные метОДЫ РЕШения лйнейных снстем 177 Поскольку каждое значение оз является функцией параметров т„т„..., т„, возникает задача построения оптимального набора итерационных параметров из условия минимума оз для фиксированного й. Перейдем к решению этой задачи. Предположим, что все собственные значения Х, матрицы С лежат на заданном сегменте (у„у,). Учитывая симметрию матрицы С, мы прнходнм к следующей задаче оптимизации: найти пип з)„(т„т„..., тз) = ппп П (Š— т,С) (зз) (з!) з=! = ппп (шах ~ П (1 — т;Х,) . (з!) ! 5 1!=! Поскольку все Х, лежат на отрезке [у„у,), то расширяя область по которой берется максимум, мы получим, что ш(пдю(т„тз...
„тз) ~ пнп( и!ах ~ П(1 — т11) (зз) (зй !Т,<зкз,1з=! Полученная огрубленная задача имеет более простое решение. Кроме того, при решении такой задачи не используется информация о конкретном расположении собственных значений Х, на отрезке (у„у,), а учитываются лишь границы этого отрезка. Такой подход позволяет построить набор оптимальных параметров для матриц произвольной структуры. Перейдем к решению указанной огрубленной задачи оптимизации, Положим Р (1) = П (1 — т!1) и заметим, что полянам Р (1) з=! удовлетворяет условию нормировки Р (О) = 1. С помощью замены переменной 1 уз + у! l Уз — У! Х 1 — вою (Уг+ У! О (Уз У!)) = 2 2 ! уз + у! / тю ~1 — 5 гдер, = уз — у! 2 , т, = —, мы отобразим отрезок у, ~ 1~ у, !!+уз' уз+уз' в отрезок — 1 ~ 5 ~ 1, причем точка 1 = О переходит в точку 8'=Ею= )! ° 1 ою Прн такой замене рассматриваемая задача оптимизации переходит в следующую задачу: среди всех полиномов Рю (5) степени й, г 1 удовлетворяющих условию нормировки Рз ( — ) = 1, найти таРз кой, для которого !пах (Р (3) [ минимален.
1з(к1 ИТЕРАЦИОННЫЕ МЕТОДЫ (гл, в 17В Таким полиномом, как известно, является полинам Чебышева Р» (5) = Т» (5). (Т» (5,) ) ', где соз(йагссоз5) при [5[ ~ 1, — [(5.+ У 5а — 1)»-[-(5 — 1/5' — 1)а) пРи [5[= 1. Так как шах [Т» (5)[ = 1, то )з )к! ппп !Еах [Р»(!)[= . ( 1, 1 (т!) Такако* Т» (оа) 2ра Ута — У та причем —,=ц» —— ,„, где р,= Та (за) 1 -1- Ра" Ут+~ т Для вычисления оптимального набора параметров будем исходить из равенства .(!)=П( — !)= .Т.( — '„"') ( 1 — та! т мы учли, что 5 = — ).
Приравняем корни полиномов, Ра стоящих в левой и в правой частях этого равенства. Так как полипом Р» (!) имеет корни 1, = 1/т, () = 1, 2,, й), а полинам Т„(5) имеет корни 5! = соз — п (! = 1, 2, ..., й), то учи- 2/ — ! 2» тывая, что ! = —, получим ! — Роо ! — ьаРо (/=1,2, ... то та и; 5! определены выше). Итак, оптимальными значениями итерационных параметров то 2! — ! будут значения т! = +, где 5! соз — и, 1=1, 2, ... ..., й. Итерационный процесс с указанным оптимальным набором параметров называется чебышевским. Мы приходим к следующей теореме; Теорема 6.4.
Если матрицы А и В симметричны и положительно определены и если у,В ~ А с у,В, то чебьииевский итерационньш" процесс сходится, и для погрешности 2» после выполнения й итераций справедлива оценка 12»[в ~ 9»[2»[в 2Р»! Уть — Ут вде ц» = —, при ра=, 1+ Р! р та+у та $ !) ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ )79 Если в качестве условия окончания процесса взять для заранее заданной е-точности требование !!е,е~)э ( е)~Яе~з, то из теоремы 6.4 получается для числа итераций й следующая оценка: й~й,(е), . Сравнивая эту оценку с установленной вы)п (е)2) )и р1 ше оценкой числа итераций для метода простой итерации я)яе(е)= —,, мы получим прн условии, что величина )и е )про ' )п (2)е) )п ()уе) е = уе/у, мала, что /ге(е) ж * ла(е) т е .
Сравнение 2УГ * этих оценок указывает на преимущество чебышевского метода (в случае, когда величина $ = у,/уе мала). Описанный нами чебышевский метод известен еще с начала 50-х годов. Иногда его называют методом Ричардсона. Следует отметить, что мы изучили этот метод для идеального вычислительного процесса с бесконечным числом знаков, в то время как на ЭВМ вычисления ведутся с конечным числом знаков, в связи с чем имеются числа, являющиеся машинной бесконечностью М и машинным нулем, Если в процессе вычислений на ЭВМ появляется число М, превосходящее М, то происходит аварийный останов машины (авост). С точки зрения идеального вычислительного процесса значения итерационных параметров т, можно упорядочить как угодно (любым из М способов).
Любые две последовательности итерационных параметров (т,) с точки зрения идеального вычислительного процесса эквивалентны, ибо для них требуемая е-точность достигается за одно и то же число итераций. Но при вычислении на ЭВМ различные последовательности параметров (т,) не эквивалентны. Для одних последовательностей значений (т,) может произойти аварийный останов машины вследствие роста промежуточных значений.
Для других последовательностей значений (т,) аварийного останова машины не происходит, но в связи с немонотонным характером стремления к нулю погрешности се, т. е. вследствие того, что норма матрицы Š— т,С перехода от () — 1)-й итерации к )пй может быть больше единицы, для этой погрешности не справедлива установленная нами для идеальной ситуации оценка. Вследствие указанных обстоятельств возникает теоретическая проблема — указать такой наилучший закон упорядочения значений (т,), прн котором для чебышевского метода было бы наименьшим влияние ошибок округления. Исчерпывающее решение этой проблемы можно найти в книге А.
А. Самарского «Теория разностных схем», М., «Наука», 1977 год (с, 572 и далее). !60 итерационные методы й 2. Рещение полной проблемы собственных значений методом вращений Ради простоты сначала будем рассматривать вещественную симметричную матрицу А, определяемую равенством (6.2). Заметим, что отыскание всех собственных значений и собственных векторов этой матрицы сводится к отысканию такой ортогональной матрицы Т, для которой произведение 0 = Т'АТ 6.29 ( ) представляет собой диагональную матрицу.
В самом деле, если такая ортогональная матрица Т будет найдена, то диагональные элементы матрицы В будут являться собственными значениями матрицы А, а столбцы матрицы Т будут являться соответствующими собственными векторами матрицы А *). Введем в рассмотрение сферическую норму матрицы А: ) А(сф — ~' ~'„а,', Тогда, очевидно, для диагональных элементов матрицы А будет справедливо неравенство ч Е аг,.1А~,ф, (6.30) г 1 причем это неравенство переходит в точное равенство только в случае, когда матрица А является диагональной. Заметим теперь, что при ортогональном преобразовании матрицы А (т.
е. при преобразовании вида А = (гА)т, где У и )т'— ортогональные матрицы) сферическая норма этой матрицы не изменяется "'"). Отсюда следует, что от всех ортогональных преобразований матрицы А преобразование (6.29) отличается тем, что это преобразование делает максимальной сумму квадратов диагональных элементов преобразованной матрицы и минимальной — сумму квадратов всех внедиагональных элементов этой матрицы.
«) Лля доказательства этого обозначим через )т, йю ..., Хэ диагональные элементы матрицы с) в положим ед )ед~, где элементы едГ столбца ед удовлетворяют условию: едд О прн й гь ( и едд 1. Тогда, очевидно, Ве = эдеа, т. е. Т'АТед= «дед, н так как Т' Т ', то АТед )дТею Слелоаательио, Тед являются собственнымн векторами матрицы А.
««) В самом деле, если А УАй, а символ (г С обозначает сумму всех злементов матрицы С, люкащнх на ее главной диагонали, то ~А (,'ф (г (А' А) = (г (Я'А'()'()АИ) (г (й'А'Ай) ~АН();ф = $(АК)'фф М й'А' Н,ф = (г (А)И'А') = Фг (АА') = ЦА' фф — — ИА 4. 1В1 метОд ЕРАшений Методом вращения называется итерационный метод, при котором указанная выше матрица Т находится как предел бесконечного произведения элементарных матриц вращения, каждая нз которых имеет вид 1 сокф ... 1* (Ья строка), Тц(ф) = (6.31) '1 сов ф. 1 51п ф (у-я строка), аА,— — ам при йчьу, у, у~у, у, ац —— аа сов ф+ ал в)п ф при у чь у, у, ал — — — ацв1пф+алсовф при учьу, у, ац = ап сов ф+ ам в1п ф пРН У ФУ, У, ац= — оп в)пф+ацсовф пРН У~У, У', а„= (а„сов ф+ ал в1п ф) сов ф+ (ац сов ф+ ам з)п ф) з)п ф, ал = ( — ац в1п ф+ ал сов ф) сов ф+ ( — ацв)п ф+ ам сов ф) з)п ф, йц = — ( — ац вш ф+ а„сов ф) в) и ф + ( — ац юп ф + ац сов ф) сов ф, йц = — (ап сов ф + ау! з!п ф) в! п р+ (ац сов ф + ац з1п ф) соз ф.
(6.33) В целом метод вращений состоит в построении последовательности матриц А Ат Ам " А.~ Ат+м "~ (6.32) каждая последующая из которых получается из предыдущей прн помощи элементарного шага вида А,» = Т;,АтТН. Если для упрощения записи опустить индекс ч н рассмотреть один такой шаг А =ТНАТН, осуществляемый с помощью матрицы (6.31), то для элементов ац преобразованной матрицы А мы получим следующие выражения через элементы ац матрицы А: 1гл. б итееапионные метОды 1аз Из соотношений (6.33) и из условия симметричности матрицы А вытекает следующее легко проверяемое равенство: л л л л Х~.
а2! ~ ~ аы — 2ац+ — [(ап — аг,) з1п 2!р+ 2ац сов 2!р) ° зьз -2 2~2 ~2 2 2 ! 2 Ф ! .=! 2=! !=! зл.! 2 !*! (6.34) Из этого равенства вытекает, что для максимального уменьшения суммы квадратов всех внедиагональных элементов необходимо матрицу (6.31) выбрать так, чтобы были выполнены д в а т р е бо в а н и я: 1) номера 1 и 1 выбрать так, чтобы квадрат элемента а)! был наибольшим среди квадратов всех недиагональных элементов матрицы А, т. е. выбор номеров ! и 1 подчинить условию 2 2, а!! = шах ам) !Ч2Чл 2~!<л 2 Л! 2) угол поворота !р в матрице (6.31) выбрать так, чтобы было справедливо равенство (ан — ац) зш 2<р+ 2ацсоз2<р О.
(6.35) Равенство (6.35) однозначно определяет угол !р, удовлетворяющий условиям (6,36) Это равенство позволяет вычислять соз !р и з!п !р по формулам соз !р ~ — [1 + (1 + р ) з1п!р=зепр~ 2 [1 — (1+р) ' )~ где р = 2ац/(ац — аз!). Заметим, что если матрица (6.31) выбрана так, что выполнены указанные выше требования 1) и 2), то равенстио (6.34) переходит в следующее соотношение: (6.37) в котором ац представляет собой наибольший по модулю вне- диагональный элемент матрицы, метод Впдшеиий (вз Теперь мы можем более точно сказать, что метод вращений состоит в построении последовательности матриц (6.32), каждая последующая из которых получается из предыдущей посредством ортогонального преобразования Аты = Тц А, Тз„в котором матрица Т» = То (ф) выбирается так, чтобы были выполнены указанные выше два требования ").
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
