Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 22

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

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

Приведем теорему о сходимости итерационного метода (14) при условиях (20). Т е о р е м а 3. Пусть А и  — симметричные положительно определенные матрицы, удовлетворяющие условию (20). Пусть задано число итераций и. Если параметры т, определить согласно (3), (4), где $=7,/7м то для погрешности будет справедлива оценка !!х„— х)),(д„)1х,— х!1„ (21) где 2Р~ 1 — и я тт (22) Доказательство.

Как и при доказательстве теоремы 2, запишем уравнение для погрешности в виде (19). Из (19) получим о„=Т и„ где Т„= (Š— т„С) (Š— т„,С) ... (Š— т,С). Отсюда следует 11о„)!( ()) Т„!) !) о,)). Пусть с,— 1-е собственное число матрицы С, 1=1, 2, ..., т. Так как ҄— симметричная матрица, норма !!Т„1) совпадает с максимумом из модулей ее собственных значений шах )(! — т„сг)(! — т„,с;) ...

(1 — т,с;)~ 1</<ж и не превосходит величины шах 1(! — т„с) (1 — т„,с) ... (1 — т,с) ~. а<т1<г<тх (23) Выбирая т„й=1, 2, ..., и+1, согласно (3), (4) при $=7,/Т„мы минимизируем величину (23) и приходим к оценке ))Т„))(д, где г)„определено согласно (22). Наконец, замечая, что ))в„'и'=!)х„— х11„ приходим к требуемой оценке (21). й 7. Итерационные методы вариационного типа *) В предыдуших параграфах рассматривались такие итерационные методы решения системы Ах=!, (1) ') При первом чтении зтот параграф можно пропустить. 115 3 а меч ание. Хотя теорема 3 и не гарантирует оптимальности итерационного метода, из оценки (21) следует сходимость метода, причем при малых й число итераций, достаточных для достижения заданной точности в, оценивается кан 1п (2/е) иа6) = =- 2 )та в которых для задания итерационных параметров требовалось знать границы (, и т, собственных значений матрицы А.

Рассмотрим теперь итерационные методы вида В "' ' +Ахь=1, (2) в которых параметры т,~, выбираются из условия минимума погрешности 1х„~,— х~~, при заданной погрешности ~|х„— х!! . Здесь Р— заданная симметричная положительно определенная матрица, 11Яе= 1'(Ро, о). В зависимости от выбора матриц Р и В получим различные итерационные методы. Скорость сходимости таких методов не выше, чем у чебышевского итерационного метода. Преимуществом их является то, что они не требуют знания границ спектра матрицы А. 1.

Метод минимальных невязок. Рассмотрим систему (1) с симметричной положительно определенной матрицей А. Обозначим через га Ах„— 1 (3) невязку, которая получается при подстановке приближенного значения х„, полученного на й-й итерации, в уравнение (1). Заметим, что погрешность г,=х„ — х и невязка г, связаны равенством Аг„=г,. Рассмотрим явный итерационный метод кь, — ха (4) тем и перепишем его в виде хь+ =ха — тьмгм (5) Методом минимальных невязок называется итерационный метод (4), в котором параметр т,~, выбирается из условия минимума 11г,+Д при заданной норме ~~гД.

Получим явное выражение для итерационного параметра тано Из (5) получаем Ах,~,=Ах,— т„.„Аг, и, следовательно, г„+, — — г,— т...Аг„, (6) т. е. невязка г„удовлетворяет тому же уравнению, что и погреш- НОСТЬ Ее=Ха Возводя обе части уравнения (6) скалярно в квадрат, получим ~гь,~з=~га~а — 2те,(гм Ага) +т~ Д Ага~~'.

(7) Отсюда видно, что ать,Д достигает минимума, если (Агм г~) тьн = (8) Таким образом, в методе минимальных невязок переход от й-й итерации к (й+1)-й осуществляется следующим образом. По найденному значению х„вычисляется вектор невязкн г„=Ах„— 1 и по 116 формуле (8) находится параметр т„„. Затем по формуле (5) досчитывается вектор х,т,. Метод минимальных невязок (5), (8) сходится с той же скоростью, что н метод простой итерации с оптимальным параметром т. Справедлива Теорема 1.

Пусть А — симметричная положительно определенная матрица. Для погреигности метода минимальных невязок выполняется оценка 11А(х„— х) !1(р",!!А(х,— х) 11, п=0, 1,..., (9) где 2 Л м(А)+Л „(А) получим неравенство !!с»+Дз( 11 (Š— т,А) гД' и, следовательно 11г„Д- 11Š— т,А1111гД. (12) Согласно следствию 2 теоремы 1 из $ 4 имеем 11Š— т,А!1 =р„поэтому при всех (з справедливо неравенство !!г»„!! ~р.1!г»11, (13) или, что то же самое, неравенство 11А (х,+,— х) 11 (р»11А (х„— х) 11.

Отсюда и следует оценка (9). Замечание. Используя доказательство теоремы 1, можно получить по. лезное неравенство (р, и)'~(Ар, и) (А-'р, р) — !1У$+ т ) (р. р)з, (14) справедливое для симметричных положительно определенных матриц А н лю. бого вектора учао. Для доказательства (14) запишем тождество (7) при ть+ь определенном согласно (8).

Тогда получим (Аг», г») 1'», )з=(1г»!'— 1Аг» 11' Учитывая неравенство (13), получаем (Аг», г»)з о <1.»1 — ', < р,'1,1 1,1 (з о или (Аг», г»)з ~(г», г») (Аг», г), (Аг», г»)~>(1 4 (г» г») (Аг», Аг»1. 117 — ап Л ы (.4) (10) 1+4 Л (А) Д о к а э а т е л ь с т в о. Рассмотрим тождество (7). При заданном векторе г, правая часть этого тождества достигает минимума, если т»+, выбрать согласно (8). При любом другом значении т,+, правая часть тождества (7) может только увеличиться. Поэтому, полагая в (7) т»,~ — — т„где Сделав замену Апта=у и учитывая, что 1 — рч'=4$/(!+1)', получим соответ- ственно неравенства (у, у)а ( (А яу, у)(Ау, у), 43 (у, у)з~ (А 'у. у) (Ау, у), которые совпадают с (14).

Обратно, если непосредственно доказать неравенства (14), то из ния можно вывести утверждение теоремы 1. 2. Метод минимальных поправок. Запишем неявный итерацион. ный метод (2) в виде хач,=х,— тВ 'ты (15) где т„=Ах,— ! — невязка. Вектор и!,=В-'тз называется поправкой на (й+1)-й итерации. Поправка и~л удовлетворяет тому же уравнению, что и погрешность х„=х,— х неявного метода, т.

е. уравнению тьн Будем предполагать, что  — симметричная положительно определенная матрица. Методом минимальных поправок называется неявный итерационный метод (2), в котором параметр т,+, выбирается из условия минимума нормы (~ьп„~,!!в= (В!в,ч„туз+,)'" при заданном векторе шз. В случае В=В метод минимальных поправок совпадает с методом минимальных невязок. Найдем выражение для итерационного параметра та+,. Перепишем (16) в виде явь+, = твз — т„+ В ~Авва и вычислим (!!ил+я!!в =!~швов — 2тл~ з(Аыл, ил) + тлю (В !Аиро Ашл).

Отсюда следует, что ~~!в,+, !(зв будет минимальной, если положить (Аыа, ыа) (В 'Аыл, Аыл) (17) Для реализации метода минимальных поправок требуется на каждой итерации решить систему уравнений Всеь=я„откуда найдем поправку !вы и решить систему уравнений Во,=Атум откуда найдем вектор п„=В 'А!вы необходимый для вычисления параметра тзео Скорость сходимостн метода минимальных поправок определяется границами спектра обобщенной задачи на собственные значения Ах=)чВх. (18) Теорем а 2. Пусть А,  — симметричные положительно определенные матрицы и ),.(В 'А), Х „(В 'А) — наименьшее и наи- 118 Доказательство.

Перепишем уравнение для поправки (16) в виде ог„, — оь + Сил=О, туг (20) где о,=Ви'1оь С=В "АВ "'. Выражение (17) для итерационного параметра т,, принимает вид (Сом ог) ть„= (21) 1Сог 1)г Уравнения (20) и (21) — это те же самые уравнения (6), (8), которые возникают в методе минимальных невязок. Поэтому можно воспользоваться теоремой 1 и записать оценку (13), которая теперь примет вид ))ог+~1! ~~ро!)ог!)~ (22) где )чо1„(С) ро= з 1+ й )'юпах (С) Заметим, что Х „(С) =-Х „(В 'А) и Х „(С) =). (В-'А).

Кроме того, )) оь () =)) В "1оь ~) = !) В *то )( = () тг ~~з, = (~ А (хь — х) ~) Отсюда н следует оценка (19). 3. Метод скорейшего спуска. Рассмотрим явный метод (4) и выберем итерационный параметр тг„из условия минимума 11г,+Д* при заданном векторе г„где г„„=х„„— х. Поскольку погрешность г„удовлетворяет уравнению г„.,=г,— т„,Аг„ имеем |1 гг„, ))лл =)) гг ))дл — 2ту„, (Агм Агг) + то+, (Аггм Ать). Следовательно, ))гг„~(л будет минимальной, если положить (Аг», Агь) го+1 = (Аггл, Аг„) большее собственные значения задачи (18). Для погрешности метода минимальных поправок выполняется оценка 1)А(х„— х)~)в, =.р",1)А(х — х)!/ „п=О, 1, ...

(19) где Х,„ы (В 'А) рг — —. $=- ° 1+ $ Х„, (В ~А) Так как величина г,=х„— х неизвестна (поскольку неизвестно точное решение х), надо учесть, что Аг,=г„=Ах„— 1, и вычисление т,„, проводить по формуле (гм г~) тйм = (Аге, г~) (23) Так же, как и в теореме 1, доказывается, что метод скорейшего спуска сходится с той же скоростью, что и метод простой итерации с оптимальным параметром т=т,. Для погрешности метода скорейшего спуска справедлива оценка 1~х„— х!1 (а~к,— хЬ, а=О, 1,..., (24) Лим (А) где р,= —, $= 1+$ Л „(А) Неявным методом скорейшего спуска называется метод (2), в котором параметр т,, выбирается из условия минимума ~~г„+Д .

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

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