А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 67
Текст из файла (страница 67)
Подставляя (18) в выражение (!5) для ад+, и учитывая формулу для параметра т»„, получим аде»(Сх»,, хд-») (Схь Схд) адтд(Схд ь хд,) !Схд, Схд) — (Схд, хд)» тд+,(Схь х») ! ') -д хд!Схд», хд,) е»д,/ =( —,' -Г что совпадает с формулой для параметра ад„в методе сопря- женных направлений. Теорема доказана.
Подставляя хе =Оп'гд и С=Р-и'(Р — 'А)0 — и' в (12), полу- чим следующий вид формул для параметров ад+, и тд+,! (Рвьгд — гд д (Рвь гд») — (Ре» ь у» — дд») (Рвд, вд) (Рвд, вд) (Р (㻠— гд»), уд — уд Д вЂ” (Рвд, гд — гд )е (Рв», гд) ! — ад+» (Рвд, гд») т,+, — + (Рвд, вд) а»+, (Рвд, в») Если ввести обозначения для скалярных произведений ад=(0и»», г ), Ь»=(0!сд, гд,), с =(Ргд, уд — у г(»=(Рг „у — у»,), ед —— (Р!с», !сд), то формулы (!9) перепишутся в виде (ад — Ьд) Ьд — »!дед д+д (ед — »!д) ед — (ад — Ьд)' ' ' ' ' ад= 1» т» = + а» 1 — ад+, Ьд ед аде» ед ' й=-О 1 Приведем выражения для а», (»», сд, !(» и ед для конкретных вы- боров оператора 0: !) Р=А, А=А*.
ад = (гсд, гд), йд = (!сд, гд,), с» = (гд, уд — уд,), !(»=(г» ь у» — у,,), ед=(Аи»„и»д). 2) О=А"А. ад — — (Аи»», г,), Ьд=(Агс», гд,), с, =(г,, г,— г е(д=(гд „г» вЂ” гд,), е»=(Ан»», Аи»»). 359 3) Р = А "В-'А, В = В". а„=(Аш, иг), бг=(Ашы шг,), сг=(ш, г,— г„,), бг — — (ш, ы г,— г,), ег=(В 'Аю„, Ашг). $5. Ускорение сходимости двухслойных методов в самосопряженном случае 1. Алгоритм процесса ускорения. В и, 5 ~ 1 было установлено, что в случае самосопряженного оператора ОВ 'А двухслойные градиентные методы обладают аснмптотическим свойством. Оно проявляется в том, что для больших номеров итераций скорость сходимости метода существенно понижается по сравнению с началом итераций. Было также показано, что для больших номеров итераций погрешности, рассматриваемые через одну итерацию, становятся почти пропорциональными.
Используя зто свойство, построим сейчас процесс ускорения сходимости двухслойных градиентных методов. Для решения уравнения Аи =1 (1) рассмотрим двухслойный градиентный итерационный метод В ~~" ~' +Ау„=~, я=О, 1, ..., у,ЕН, (2) (!Зать гг) й=0,1, ... (3) Пусть оператор ОВ 'А самосопряжен в Н. Тогда итерационный метод обладает асимптотическим свойством, и при достаточно большом номере итераций й имеет место приближенное равенство гь+, ж р'г„, г„= у — и.
(4) Рассмотрим сначала случай, когда в (4) выполняется строгое равенство, т. е. гь+,-— — р'г . Построим по найденным уже приближениям у„и уг+, новое приближение по формуле у = ау +, + (! — а) уы а = 1!(! — р'). (5) Для погрешности г=у — и получим г=-аг„+,+(! — и) г„=(ар'+! — а) г =11 — а(! — р')1г„=О. Следовательно, в случае выполнения строгого равенства (4) линейная комбинация (5) приближений у„и у„„дает точное решение уравнения (1). Как было отмечено в й 1, выполнение точного равенства в (4) является исключительным случаем, имеющим место лишь для специального начального приближения.
В общем случае имеет место приближенное равенство (4), а приведенные выше рас- 360 (8) 361 суждения позволяют надеяться, что некоторая линейная комби- нация у и ух~, будет давать хорошее приближение к решению исходной задачи. Найдем наилучшую среди таких линейных комбинаций. Пусть уы у„~, н ух„— итерационные приближения, полученные по ' формулам (2), (3). Будем искать новое приближение у по формуле У = иУх+в+ (1 а)Ух. (6) Поставим задачу выбрать параметр а так, чтобы норма по- грешности г=у — и в Нр была минимальной. Сначала, используя схему (2), исключим из (6) у„+,.
Получим Ву„„=( — т„,А)ух, +тх- ) и после подстановки ух„, в (6) будем иметь Ву= а ( — тх„.,А) ух~,+(1 — а) Вух+итх,„,~, (7) где у„„ находится по двухслойной схеме Ву,, =( — т „А) у„+тх, Д. Если считать, что ух — заданное начальное приближение, то схема (7), (8) совпадает со схемой метода сопряженных направ- лений, причем параметры т„„и тх„совпадают с такими же параметрами метода сопряженных направлений.
Из теории этого метода следует (п. 1 5 4, формула (3)), что оптимальное значе- ние параметра а определяется формулой а= ! (9) тх, (()их+о гх~й тх, (0вх, гх) Итак, поставленная задача о наилучшем выборе параметра а решена. Формулы (6), (9) определяют ускоряющую процедуру. Заметим, что для нахождения у можно пользоваться не фор- мулой (6), а вычислять у по следующей двухслойной схеме: Ву, =( — тх„,А)у +т Д, ВУ=( — т„„.,А)У ~,+тх,.,1, где тх„и тх,— корни уравнения т' — и (тх~, + тх„.,) т+ ать„,т„~, = О.
В качестве тх„следует взять минимальный корень. Использование (! 0) вместо (6) позволяет ие увеличивать объем запоминаемой промежуточной информации. 2. Оценка эффективности. Оценим теперь эффективность спо- соба ускорения. Прежде чем вычислять норму погрешности г= у — и в Но, преобразуем выражение (9) для а. Замена г = — и'хх в (9) дает ту,.~~ (Схх+ь хх~-0 ) -~ с г)ырВ-,А)) пг "=( — ' ,' тхэг (Схх, хх) Из (10) и (11) 5 1 имеем (Сх», х»)» !1~» !1=р» !х»!1 р»+>= (с с' )~ В ° (12) Из формулы (9) 5 1 получим (Сх», х») (Схм Сх») ' (13) Используя (12) и (13), найдем Я т»», (Сх»„>, х»+,) ! — (>»~, т»~> (Сх», х») 1 — (>'„, Р»+' Подставляя зто выражение в (11), получим — Р»,1 2г» ..~ и» (>» (14) Вычислим теперь норму погрешности г=у — и в Нр. Из (6) получим г = яг»», + (1 — а) г».
Отсюда для эквивалентной погрешности г»=0>мх» и х=Т)м'з будем иметь х=ях»,+(1 — а)х». Вычислйм норму х в Н. Получим )!х(!'=а')х»„1' +2а(1 — я) (х» „х„)-1-(1 — а)'(х»1'. Из доказанного в п. 5 з ! равенства (х„„„х») =-~~'х»„)~' следует (! х !(' = а' )~ х» „(!'+ 2а (1 — я) !! х»», (> + (1 — а)'(х» ~», Подставляя сюда выражение (14) для а и используя (12), по- лучим (>».» р»+> Так как р»,<р»„<р < 1, то ! — 2р»„+ р»„р»„) (1 — р')', (! 5) следовательно, для нормы х имеет место оценка ) х )' < ( —," — 1) (~, "',)~,. В силу асимптотического свойства для достаточно больших номеров й имеем р»„, ж р„„„поэтому эффект ускоряющей процедуры будет значителен.
Отметим, что хотя эффективное ускорение сходимости имеет место для больших номеров итераций й, этим способом можно пользоваться и для любого номера итераций. Рекомендуется время от времени прерывать процесс итераций, прово- 362 димый по двухслойной схеме (2), (3), и вычислять новое приближение по предлагаемому способу. Процесс итераций можно закончить на вычислении такого приближения, если для найденного у„„., будет выполняться неравенство 2 2 оь+э ры э 2 2 (1 — 2 2 + 'Л 2 '!!гь !Ъ <8 !!гО!! оыд ( ой+1 рйм ай+3) Действительно, в этом случае получим в силу (15) !!у — и!!р< <а1у,— и!!р, т. е.
требуемая точность з будет достигнута. 3. Пример. Для иллюстрации эффективности предлагаемого способа ускорения сходимости двухслойных градиентных методов рассмотрим решение модельной задачи неявным методом скорейшего спуска. В качестве примера возьмем разностную задачу Дирихле для уравнения Лапласа на квадратной сетке в = = (х,,=(й, Я, 0<1< М, 0<1< У, 3=1!Ж) в единичном квадрате Ли=Л,и+Л,и=О, хЕв, и)э =О, (16) Введем пространство Н, состоящее из сеточных функций, заданных на а, со скалярным произведением (и, о) = ~ и (х) о (х)УР. ХЕО Оператор А определим следующим образом: А = А,+А„А„у = — Л„о, уЕН, где о(х) =у(х) для хЕы и о)т=О. Задачу (16) запишем в виде операторного уравнения Аи =(, 1=0.
(17) В качестве оператора В выберем следующий факторизованный оператор: В = (Е + вА,) (Е + аА,), а ) О, где а — итерационный параметр. Так как операторы А, и А, самосопряжены и перестановочны в Н, то операторы А й В являются самосопряженными в Н. Кроме того, легко показать, что операторы А и В являются положительно определенными в Н. Следовательно, для решения уравнения (17) можно использовать неявный метод скорейшего спуска В этом методе Р = А и РВ 'А = АВ 'А.
Так как оператор РВ-'А самосопряжен в Н, то для рассматриваемого метода имеет место асимптотическое свойство. Из теории метода скорейшего спуска (см. и. 1 3 2) следует, что скорость сходимости метода в данном случае определяется отношением 3=7,/у„где у, и 363 у„ †постоянн энергетической эквивалентности операторов А и В: Т,В="А(Т,В, у, >О. Поэтому итерационный параметр цз выбирается из условия максимальности 9. В 9 2 гл. Х! будет показано, что оптимальное значение пз определяется по формуле 1 4 , злИ 4 л7з в==, б= — з!пз —, Л= — созз— )?Ва' аз 2 ' Ьз 2 ° при этом 26 (Дп 6))?Ч 2ф'Ч 6 уз= (1+Уп)'' ' (! ~'з1)з ' ! — Ч ' Д ' Для рассматриваемого примера 2 а1п ла 2 з1п ла пз 1+Ми ла ' 'з аз ! -, 'Мп ла ' т = —, Й=з!плй. аз аз = 2 мпла и итерационные параметры т .
Таблица 8 йз тз Йз !'з!о! Р !цэ 3,6 1О-з 2,3 1О 1,8 10 1,4 10 5 392,10-з 7'809.10-з 6 911 10-з 8'644 10-з 0,36203 0,63810 0,76998 0,81!78 ?7,31858 40,59796 26,87824 236,1883 232,1435 233,4976 26 3 9.10-з 0 85!75 18 27141 230 5962 8 876 10-з 27 3'4 10-з 0'85178 18'26983 230'6607 7 338 1О-з 28 2 9 10-з 0 85183 18 27026 230 7191 В 872.10-з 29 2,4 1О-з 0,85186 18,26895 230,7771 7,335 1О-з 1,6 10-з 1'4.10-4 1,2 1О-" 9,9 1О-з 8,845 10-з 7'318,10-з 8'843 1О-з 7,317 10 231,4121 231,4375 231,4612 231,4849 46 47 48 49 0,85226 0,85227 0,85229 0,85230 18,26677 18,26632 18,26664 18,26623 364 Приведем результаты расчетов, когда начальное приближение у, выбиралось равным у,(х) =-е'' -"*! для хЕаз, у,( = О.
Требуемая точность е бралась равной 10 4, М == 40. В табл. 8 для некоторых номеров итераций й приводятся: !!за)!01!(гз(Π— ОтНОСИтЕЛЬНаЯ тОЧНОСтЬ Ьй ИтЕРаЦИИ, РЗ— = )!за)!р!(гз,(!р — величина, характеризующая уменьшение нормы погрешности при переходе от (й — 1)-й итерации к й-й итерации, Т,'а' и узм' — приближения для у, и у„которые находятся как корни квадратного уравнения (1 — тзУ) (1 — та зу) =-озуа „й=2, 3, Заданная точность а была достигнута после выполнения 49' итераций по схеме (18). Для а=10 ' теоретическое число итераций равно 59.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
