А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 66
Текст из файла (страница 66)
На практике встречаются и другие алгоритмы реализации метода сопряженных направлений. Приведем один нз них. Для этого будем трактовать схему (9) как схему с поправкой. Из (9) получим У»+э=у» — а»+гз» з»+г= — ю»~д+Ь»»~за»=0, 1, ..., з =во, (21) где ш»=В" тгь г»=АУ» — 1, а параметры а»от и Ь» связаны с а»од н т»+т следующими формулами: а»,, = а»,т»+ „Ь» =- (аг», — 1) пот»Дсо»о гт»» т). Получим выражения для Ь» и а»+,.
Из (19), (20) найдем Ь»= (Рю», г»)!(Рш» ь з»,), »=1, 2..., (22) Для а»„, из этих же формул легко получить рекуррентные соотношения, однако можно найти явное выражение для а»+, ( хьх») ( юьз»)» ) (23) ( ь р») (Р'ь '») формулы (21), (22) и (23) описывают второй алгоритм метода сопряженных направленпй, Здесь вычисления проводятся в следующем порядке; 1) по заданному уо вычисляется невязка го — — Ауо — ), решается уравнение Вио — — го для поправки юо и полагается зо=юо; 2) по формуле (23) находится параметр а, и вычисляется у,=уо — ахзо. Далее для»=1, 2, ...
последовательно выполняются действия: 3) вычисляется невязка г»=АУ» — 1 и решается уравнение для поправки Вю»=г»1 4) по формуле (22) вычисляется параметр Ь» н находится з» по формуле а» =- ы»+ Ь»з» вЂ” г', 5) по формуле (23) определяется параметр а»о, и приближение у»+, вычисляется по формуле у»о, = у» — а» „,з». Отметим, что в приведенном алгоритме необходимо хранить у», ю» н зь т. е. такой же объем промежуточной информации, как и в первом алгорнтме. 354 $4. Примеры трехслойных методов Итерационные приближения вычисляются по трехслрйной схеме ВУ»дд —— — ад„( — т»,,А) Уд+(! — аддд) ВУд, +адддтд+1(', й= — 1,2, ..., (2) Ву, = ( — т,А) у»+ т11 уд Е Н, а итерационные параметры адд, и тд„, находятся по формулам (Рвь гд) (Рвд вд) '1»+1 а Д+1-', й=0, 1,..., (3) (Рвд, гд) 1 (Рвд-и г»-1) ад,) й=1,2,...,сг =1, где в»=В дг — поправка, г =Ау — ( — невязка, гд — — у» — и— погрешность.
Выбор параметров ад и тд по формулам (3) обеспечивает в случае самосопряженного и йоложительно определенного оператора ОВ 'А минимум для любого п нормы погрешности ад в Но при переходе от у, к у„. Рассмотрим теперь частные случаи методов сопряженных направлений, определяемые выбором оператора Р. В 3 2 были рассмотрены четыре примера двухслойных градиентных методов.
Каждому из этих двуслойных методов соответствует определенный трехслойный метод сопряженных направлений. 1'(ы перечислим эти методы с указанием условий на операторы А и В, которые обеспечивают самосопряженность оператора ОВ 'А. Для этих методов имеет место теорема 2, а вид неравенств, которые определяют постоянные у, и уь будет указан в описании соответствующего метода.
1) Метод соиряженных градиентов. Оператор 0: 0 = А. Условия: у,В(А(у,В, у,)0, А=А*>0, В=В*>0. Формулы для итерационных параметров: (дд вд) (' гд»1 (гь вд) ( (вь вд) ' д гд ('д-ь вд-1) "» l 2) Метод соиряженнах невязон. Оператор 0: О==- Л'А. Условия: у,(Вх, Вх)~(Ах, Вх)(уд(Вх, Вх), В*А = А" В. у, > 0, (г' 1. Частные случаи методов сопряженных направлений. В 3 3 были построены трехслойные итерационные методы сопряженных направлений, используемые для решения линейного урав- нения Если выполнены предположения А = А' > О, В= В* > О, АВ=ВА, то условия имеют вид у,В(А(у,В, у,>0.
Формулы для итерационных параметров: (Ав», с») / т»»с (Аи», с») 1 'с + а»,= ! — — ' »+с (Ав», Аи») ' »+с С, т» (Аи» с, с» с) и»! 3) Метод сопряженных поправок. Оператор Р: Р = АВ 'А. Условия: усВ(А< у,В, у, >О, А =А*>0, В=В*>О. Формулы для итерационных параметров: (А в ),„('1 ' (А») ! ')-с »+с (В" »Авв Аи») ' "+' С, 'с» (Аи» с, и» с) и» / 4) Метод сопряженных погрешностей. Оператор Р: Р =- В,.
Условия: В= — (А ) »В у В <А*А<у Вд В»=В >О. Формулы для итерационных параметров: (с», с») ( т»+, (св с») 1 ') "с (Ав», с») ' »+' ~ т» (с» и с» д сс» / 2. Локально оптимальные трехслойные методы. Вернемся теперь к рассмотренному в 2 3 способу построения итерационных параметров сс».„и т»», для трехслойной схемы метода сопряженных направлений.
Йапомним, что параметры сс»с и т»+, были выбраны из условий (Сх, „х»с) =0 и (Сх», х»,)=0 в предположении, что итерационные приближения у„у„..., у» обеспечивают выполнение условий (Сху,х;)=О, 1=0, 1, ...,( — 1, »=1, 2, ...,й. (4) Для идеального вычислительного процесса условия (4) выполнены, поэтому выбор параметров а „и т»», по полученным в 3 3 формулам действительно обеспечивает минимум нормы погрешности г»»с в Нр при переходе от у» к у»»с. В реальном вычислительном процессе, который учитывает наличие ошибок округления, итерационные приближения 1(с, у„..., у» будут вычислены неточно, и, следовательно, условия (4) не будут выполняться. В ряде случаев это может привести к уменьшению скорости сходимости метода, а иногда и к его расходи- мости. Построим сейчас одну модификацию метода сопряженных направлений, не обладающую указанным недостатком. Для приближенного решения уравнения Аи=) рассмотрим трехслойную итерационную схему Ву໠— — сса+с ( — та+»А) у»-(-(1 — сс»+,) Ву» с+а»»,та» ~, (5) й=1,2, ...
356 с произвольными приближениями у, и у,~Н. Считая у„и у,, заданными, выберем параметры»а», н т»„из условия минимума нормы погрешности г»„в Но, т. е. из условия локальной оптимизации за один шаг йо трехслойной схеме. Эту задачу решим при единственном предположении о положительной определенности оператора РВ *А. Для этого перейдем к уравнению для эквивалентной погрешности х„=Рч*г»: х»+, — — а»х, (Š— т,,С) х»+ (1 — а»х,) х» „С = Рц В 'АР и . (6) Для сокращения выкладок введем обозначения 1 — а»+, — — а, т„.„а»+, — — Ь (7) и перепишем (6) в следующем виде: х»„=х„— а(х„— х»,) — ЬСх . (8) Задача ставится так: выбрать а и Ь из условия минимума нормы х„+, в Н. Вычислим норму х»~,. Из (8) получим ~ х», )! ' =- (, 'х» (! '+ ая !! х„— х», )! х + Ь') Сх» )! '— — 2а(х», х,— х,,) — 2Ь(Сх„, х,)+2аЬ(Сх», х» — х»,).
Приравнивая частные производные по а и Ь нулю, получим систему относительно параметров а и Ь )х — »,~~ха+(Сх», х — х»,)Ь=(х», х —,), (Сх, х„— х»,) а+!! Сх»(!' Ь =(Сх», х»). Определитель системы равен !) х — х», ('(!Сх» ) ' — (Сх„, х„— х»,)' и в силу неравенства Коши — Буняковского обращается в йуль лишь тогда, когда х» — х, пропорционально Сх„: х„— х„,= =4Сх». В этом случае уравнения системы пропорциональны, и она сводится к одному уравнению (Ь+а!()!!Сх !!,'=(Сх», х„). (10) Так как прн этом (8) имеет вид х„„=х» — (Ь+аа) Сх», то, полагая в (10) а=0, получим из (7), (10) (Схь х») (Сх», Сх»)' (11) Если определитель не равен нулю, то, решая систему (9), получим а— !, 'Сх»1' (хь х» — х»,) — (Схь х») (Схь х» — х»,) !)х» — х»,!)')Сх»1' — (Сх», х» — х» д) ' (Схь х») 1, (Сх», х» 1) (Схь Сх») ' (Сх», Сх») Отсюда, используя обозначения (7), найдем формулы для параметров а»„и т (Сх»,х» — х» 1) (Схь х»,) — (х» ь х» — х»,) (Схь Сх») (Сх», Сх») (х» — х» ь х» — х» 1) — (Сх», х» — х» 1) (12) (Схь х») +! — а»+» (Схь х»-0 (Сх», Сх») а»+, (Схь Сх») 357 Полученные ранее формулы (11) можно рассматривать как частный случай общих формул (12), полагая а»», =- 1, если знаменатель в выражении для и»»> обращается в нуль.
Формулы (12) сложнее формул для параметров ес»„и т».» метода сопряженных направлений, полученных в 3 3. Здесь требуется вычислять дополнительные скалярные произведения. Однако построенный здесь итерационный процесс (5), (!2) менее подвержен влиянию ошибок округления, погрешности, допущенные на предыдущих шагах, затухают. Связь между локально оптимальными трехслойными методами и методами сопряженных направлений устанавливает Теорема 3.
Если для метода (5), (!2) начальное приближение у, выбрано следующим образом: Ву,=( — т,А)у»+т,~> т,= ' ' > (13) то в случае самосопряженного оператора РВ 'А метод (5), (12) совпадает с методом сопряженных направлений. Доказательство проведем по индукции. Из условия теоремы следует, что приближения у„полученные здесь и в методе сопряженных направлений, совпадают. Пусть совпадают приближения у„у„..., у». Докажем, что у„„построенное по формулам (5), (12), совпадает с приближением у»„метода сопряженных направлений. Из сделанных предположений следует, что итерационные параметры т„ т„ ..., т» и а„ сь„ ...,ес» обоих методов также совпадают. Если будет показано, что совпадают и параметры т»», и а»,! в этих методах, то утвержДение теоремы 3 будет доказано.
Так как у„ у„ ..., у» †итерационн приближения метода сопряженных направлений, то в силу леммы выполнены условия (Сх>о х;)=О, 1=0, 1, ..., ! — 1, 1=1, 2, ..., й. (14) Подставляя (14) с )=й — ! н 1=3 в (12) и используя само- сопряженность оператора С, получим (х»», х» — х»-») (Схы Сх») (Схм х») (Сх», х»)» — 1Сх» ! ! х» — х», (! ' +' (Схм Сх») Итак, параметры т»»т локально оптимального метода и метода сопряженных направлений совпадают.
Осталось показать„что совпадают параметры ех»»>. Из (6) и (13) получим х„— х», — — (сь» — 1) (х„,— х„,) — а»т»Сх», й = 2, 3, ..., ,(15) х» — т»Сх» 338 Из (1б) следует, что разность хд — х, есть линейная комбинация Сх„Сх„..., Сх», и имеет следующий вид". д-2 хд — хд,— — — а»т»Схд,+ ~.", ~Сх, й' -2, ( 1=» ' х,— х, = — т,Сх„ где коэффициенты р, выражаются через т„т„..., тд; и а„а„..., а»,. Умножая левую и правую части (17) скалярно на хд, и хд — хд, и учитывая (14), получим (х» „хд — хд,) == — а»т (Схд „х,), (18) !! хд — хд, !,» = а»те (Сх» „хд,).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
