Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 23
Текст из файла (страница 23)
Возводя обе части уравнения (6) скалярно в квадрат, получим ), гллл)л =) гл )Р— 2тл,(гл, Агл) + тл„) Агл~~'. (7) Отсюда видно, что 1~глл,~~ достигает минимуь1а, если (Агл, гл) тллл = (8) )Агл1л Таким образом, в методе минимальных невязок переход от й-й итерации к (й+1)-й осуществляется следуюшим образом. По найденному значению х„вычисляется вектор невязки г„=АՄ— ( и по 11а формуле (8) находится параметр т„., Затем по формуле (5) досчитывается вектор х,., Метод минимальных певязок (8), (8) сходится с той же скоростью, что и Метод простой итерации с оптимальным параметром т.
Справедлива Т е о р е м а 1. Пусть А — симмегри !ная положительно определенная матр11ца, Для погрешности метода мини«!альных невязок выполняется оценка !!А(х„— х)!! =р",!~А(х,— з)~!, п=0,1,..., (9) где р,=, $= ! — т ).в и (А) (! 0) )'пмх ('1) Д о к а з а т е л ь с т в о. Рассмотрим тождество (7) . При заданном векторе г, правая часть этого тождества достигает минимума, если т,+, выбрать согласно (8). При любом другом значении т««, правая часть тождества (7) может только увеличиться. Поэтому, полагая в (7) ть«, = т„где 1чмп (А) + ~та«(А) получим неравенство !!г«.„,))з( й (Š— т,А) г«~~з и, следовательно, 1!г«т, 1!- \~~Š— т,А ! ~!г«)!, (12) Согласно следствию 2 теоремы 1 из 9 4 имеем )Š— т,А6=р„поэтому при всех Й справедливо неравенство 1!г«,!, '=,р„!!г«!!, (13) или, что то же самое, неравенство 1~ А (х,,— х) Р, «= р, !!А (х,— х) ~Е Отсюда н следует оценка (9).
3 а меч ание. Используя доказательство теоремы 1, можно получить полезное неравенство (и, и)' < (Ар у) (А 'и, и) ~ — ~Л+ =) (у, у)з. 1 / — 1 4 т )'$/ (14) справедливое для симметричных положительно определенных матриц А и любого вектора учао. Для доказательства (14) запишем тождество (7) при т«+и определенном согласно (8). Тогда получим (Аг«, г«) 1! г«„!)з=',!г ))«в 1А «Р Учитывая неравенство 113), получаем (Аг«, г«)з О -.!г«!!з- ', <1,!!г«)!т !, 'Аг«!з или (Аг«, г«]т ~ (г«, г«) (Аг„, г«), (Аг«, г«)'>(! — о') (г, г«) (Аг«, Аг«).
117 Сделав замену А!т»=у и учитывая, что 1 — р,»=41/(!+в)', получим соответ- ственно неравенства (у. ур ~ (А 'у, у) (Ау, у), 4$ (у, у)а в, (А 'у, у) (Ау, у), (! + $)х которые совпэдаи!т с (14). Обратно, если непосредственно доказать неравенства (14), то нз них можно вывести утверждение теоремы 1. 2. Метод минимальных поправок. Запишем неявный итерацион- ный метод (2) в виде х»~.! — х» гВ Г» (15) где г,=Ах,— !' — невязка.
Вектор ге» = В-'г„ называется поправка!1 на (й+1)-й итерации. Поправка се» удовлетворяет тому же уравнению, что и погрешность з„=х,— х неявного метода, т. е. уравнению ы» -! м» В " +Ам»=0. та, (16) Будем предполагать, что  — симметричная положительно определенная матрица. Методом минимальных поправок называется неявный итерационный метод (2), в котором параметр т,+, выбирается из условия минимума нормы рге„, Л!!л = (Втв»е„п!»+,)'" при заданном векторе а м В случае В=Е метод минимальных поправок совпадает с методом минимальных невязок. Найдем выражение для итерационного параметра т.„. Перепишем (16) в виде ту»ч, = те» вЂ” т,+,В-'А тв» Для реализации метода минимальных поправок требуется на каждой итерации решить систему уравнений Вгу»с х», откуда найдем поправку ш„, н решить систему уравнений Во„=Аи!м откуда найдем вектор о»=В-!Аш», необходимый для вычисления параметра т,»,. Скорость сходимостн метода минимальных поправок определяется границами спектра обобщенной задачи на собственные зна- чения Ах=ЛВх.
(18) Теорема 2. Пусть А,  — симметричные положительно определенные матрицы и ). !„(В-'Л), ). „(В-'А) — наименьшее и наи- 11а и вычислим ) и!»„1",л = 1,'и!» (!в — 2т».д(Аи!», и!») + 1»„(В 'Лив, Лго»). Отсюда следУет, что 1~и!,~! '(зв бУдет минимальной, если положить (Аы», и!„) (В »Ам», Ап!») (17) большее собственные значения задачи (18). Для погрешности метода минимальных поправок выполняется оценка ЦА(х„— х)(!е,=-.Д(!А(х„— х))! „п=О, 1, ...
(19) где Л,„(В- А) (+~ ' Л,„(В-'А) ' Доказательство. Перепишем уравнение для поправки (16) в виде ег,, -ег + Сох=О, г~.1 (20) где п,=В иш„С=В '"АВ-"'. Выражение (17) для итерационного параметра тг+, принимает вид (Сгы ег) тж,—— (21) 10г((* ' Уравнения (20) и (21) — это те же самые уравнения (6), (8), которые возникают в методе минимальных невязок.
Поэтому можно воспользоваться теоремой 1 и записать оценку (!3), которая теперь примет внд ((ей+1(! «~ро(!ш(! (22) где ! †р 1+$ Заметим, что Х „(С) =Л„„(В-'А) и Л „(С) =Х (В 'А). Кроме того, !',и,()=((ВИшгЯ)(=1В "гг (=1гг!~-, =!(А(х» — х)1! г,~,=г„— т„~,Аг„, имеем ((гг,1((л =) гг )д — 2тг„(Агм Агг) + тг„(А'гм Агг).
Следовательно, ((г„„!',-л будет минимальной, если положить (Агм Агг) тй+1 = (А~ге, Агг) 119 Отсюда и следует оценка (19). 3. Метод скорейшего спуска. Рассмотрим явный метод (4) и выберем итерационный параметр т,~, из условия минимума ((г„+Д при заданном векторе г„где г„„,=х,+,— х. Поскольку погрешность г„удовлетворяет уравнению Так как величина г„=х„ — х неизвестна (поскольку неизвестно точное решение к), надо учесть, что Аа,=г,=Ах, — 1, и вычисление т~+, проводить по формуле (гз га) (23) (Айн ге) Так же, как н в теореме 1, доказывается, что метод скорейшего спуска сходится с той же скоростью, что и метод простой итерации с оптимальным параметром т=т.. Для погрешности метода скорейшего спуска справедлива оценка 'зх,— х~~ (р" 1~х,— х~~„, п=б, 1, ..., (24) 1 — ч 1 ы(А) где р,=, й= 1+ $ Л~,„(А) Неявным мегодо 1 скорейшего спуска называется метод (2), в котором параметр т,-,, выбирается из условия минимума !!г,~Д, Так как погрешность г,=х„— х удовлетворяет уравнению г,+, — — г,— т..пВ-'Аг„, получим !!г~~,'1А =/!гг(лз — 2те„(Ага, В 'Аг~) + т~3„(АВ 'Аг„, В 'Агз), илн 1гй 114 =1гф,(4 — 2тз~, (Гм Шг) + т(,1 (Ашм ~О/).
Следовательно, ))гз„'1А будет минимальной, если положить (гз мь) 'гам = (25) (Амм чч) При этом для неявного метода скорейшего спуска справедлива оценка (24), где л ь (в 'А) Л,„(В-А) ' 4. Метод сопряженных градиентов. Метод сопряженных градиентов является двухшаговым итерационным методом, т. е. для нахождения новой итерации х„,, используются две предыдущие итерации х„и х„,. Следовательно, здесь возрастает требуемый объем памяти, нужно помнить не только вектор х„, но н к„,.
Применение двухшагоных методов оправдывается тем, что при правильном выборе итерационных параметров скорость сходимости будет выше, чем у одношаговых методов. Например, рассматриваемый далее метод сопряженных градиентов при любом начальном приближении сходится за конечное число итераций.
Пусть А — матрица системы (1) и  — симметричная положительно определенная матрица. Рассмотрим следующий класс не- 120 явных двухшаговых итерационных методов: В ь" " ь" ' ' +А ь=.) й=1 2,, (26) та~ ьы Здесь а,„, т,,— итерационные параметры, которые будут определены далее. Для начала счета необходимо задать два начальных приближения х, и х,. Начальное приближение х„будем задавать произвольно, а вектор х, вычислять по олношаговой формуле, которая получается из (26) при й=б, а,=1, т. е. по формуле В ' '+Ахч=~.
(27) тг Если параметры аыь тьы найдены, то новое приближение х„+, выражается через два предыдущих значения х, и х„, по формуле х!з.1 =аАз-!ХА+ (1 — а~ ~!)хп-~ тйз-1аьз.!жь (28) гле ш, = В-'г„г, = Ах,— 1. 5. Минимизация погрешности. Перейдем к вопросу о выборе итерационных параметров в методе (26). Для погрешности г,= =х„— х получим уравнения =а, (Š— т,,В 'А)г„-"(1 — а,,)г,, й=1 2 г,=(Š— с,В 'Л)го. Введем, как и ранее, вспомогательную функцию о,=,4' г„, для которой 1~о„11= 112„~',. Функция о, удовлетворяет уравнениям в;...
= аь„(Š— ть„С) оь+ (! — а„,) о„„й = 1, 2,, (29) од — — (Š— т,С) оя, (30) где С=А"'В 'А'". Будем считать, что А и  — симметричные положительно определенные матрицы, удовлетворяющие неравенствам (31) Тогда С"=С>0, причем Т, Е ( С ( ТхЕ. (32) Исключая последовательно из уравнений (29), (30) векторы о„о„..., о„ь найдем, что о„=Р,(С) о„ (33) где Р„(С) — многочлен степени 1з от оператора С, удовлетворяющий условию Р,(0) =Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
