А.А. Самарский - Теория разностных схем (1989) (1160092), страница 96
Текст из файла (страница 96)
Покажем, что при выполнении условий (34) справедлива оценка 1 — к„ ' 2бав , ПЯ Пз< ", где и = ", .„а=1,2. - (37) 1+ко. 1+об Ь, В самом деле, рассмотрим тождества П(Š— вА )хП*= П(Е+ вА,)хР— 4в(А х, х), Ц(Е+' вА,)хР ЦхР+ вд!А,хб*+ 2а(А„х, х). Отсюда з силу неравенств (34), (35) следует $(Е+ вА„) хП'((1/бе+ а'Л,„+ 2в) (А„х,'х), (А„х,х)> " $(Е+вА )хП~, 1+ оРб„а„+ 2вб ~ (Š— вАа) х) ~ (1+ ~ (Е'+ аАа) хП ° 580 гл. х. методы Решения сеточных ЗРАВнениЙ 1 — х~ Полагая затем х (Е+еА,)-'у, имеемЙЯ„у)э( +„" ЙуЙэ, что хе и требовалось. Пользуясь (37), получаем Параметр ге выбирается из условия минимума функции г'(гэ). Функция Е,(ге) =(1 — х,)/(1+хг) достигает минимума (а хг— максимума) прн го - 1/Уб,д~„а )г,(ю) = (1 — х,)/(1+ х,) — при ю 1/У6,~$,.
Эти значения совпадают при б,йг бэЬ„Н в этом случае справедливо неравенство 1 — )/'ч, 6„. ~ЯгЕ ~э(уэ Рэ= ~ э, ))а= — ~ а=1 2 1+ у Ч, 1+ у Чэ а (38) причем в 1/Уб,~, = 1/У6,~1„а для погрешности е„у„— и верна оценка И(Е+ о)Аэ)Е„И ~ ~р"И(Е+ юАэ)ээИ. (39) Если б,б,чьб,йм то полагаем г» 1/УЬЬ, где 6=ш1п(б„б,), а А=шах(йо Лэ). По сравнению со случаем самосопряженных операторов А, и Аэ (см. п.
4) число итераций увеличивается в 2 раза. Это вид- 1-УЧ но, например, прн бг . б, б и Л, Ь> Ь из (38):р= 1+')/Ч ( 1-Ъ/ч ) вместо р= ~ ), полученного в п. 4, если применить оцен- ~ т+Мч )'* ку (39) для случая самосопряженных А, и А,. э 5. Другие нтерационные методы 1. Трехслойиые итерационные схемы. До сих пор мы изучали только двухслойные итерационные схемы для решения операторных уравнений Аи = У с самосопряженным оператором А в предположении, что известны границы 7, и 7, спектра оператора А в Н либо в Н„где В=Не~Π— некоторый оператор (стабилизатор). В этом параграфе мы рассмотрим и другие итерационные методы. Начнем с трехслойных (двухшаговых) итерационных схем.
Пусть требуется решить уравнение Аи-/, А: Н вЂ” Н, (1) 'с самосопряженным н положительно определенным оператором, $6. Дгттнв нтвг»ционньди мвтоды 58$ границы спектра которого известны: А = А', "(дЕ < А < 7»Е, "(д ) О. (2) Первую итерацию у, находим по двухслойной схеме простой итерации. Схему (3) обычно получают следующим образом. Уравнение И) ааписывают в так называемом подготовленном виде: и = и — тАи+ т~ = Е(т)и+ т~, Е(т) Š— тА, и выбирают параметр т так, чтобы 1181! была минимальной.
Для этого, как мы знаем иэ 1 2, надо положить т=т,: и о(т,)и+ т,д. (5) Это уравнение можно переписать иначе: И + а) и И + а)Еи+ И + а)т4 и= И+а)ои — аи+ И+а)т»7, и уже к нему применить явную схему,' заменив И+а)Еи ни И + а)Еу„а аи на ау,, Параметр а выбирается иэ требования минимума итераций. Мы не имеем возможности останавливаться на оценке скорости-сходимости схемы (3) и выборе а» Приведем лишь окончательный реаультат. Применяя к (3) оператор А, убеждаемся в том, что невязка г» =Ау» — ~ удовлетворяет однородным уравнениям г»+,— — (1+а)Е㻠— аг» о й=1, 2, ..., (6) г, Ено где гв = Ау, — ) ди Н любое. Для этой задачи при а = рд слраведпива оценка 1Ау„— )11 ( д„!1Ау, — )!1, (7> где Ч.=р," 1+ ' ",, и (8у Трехслойная итерационная схема связывает три итерации у» „у» и у,+„так что у»+, определяется через у» д, у».
Явная схема обычно ааписывается в виде у»+, = И + а)Еу» — ау», + И + а) т»), й = 1, 2, „3) уд = Еу»+ т»1, любое у» ж Н аадано, где 3 = Š— т,А — оператор перехода для двухслойной схемы простой итерации с оптимальным параметром т,: 2 в ( — ''т" с тд а= р„р,=, $= —. (4> в т+7 ™ $+Л' т 582 гл. х. мвтоды гвпшния сзточных тглвнвнни Для числа итераций, очевидно, верна оценка р~ 1в — +1в 1+ — 'з 1+р, 1в— Рз которая выполнена при 1а +1в(1+ ) и~~ (8) 2Л Сравнение (8) с выражением для д„в случае чвбышевской схе- В мы дь = —,„показывает, что обв схемы имеют одинаковый. яв асимптотический порядок при 5- 0 по числу итераций 1 1 1 п = и (е) = О ~ ~- 1п — „~, однако число итераций для трехслойной схемы несколько больше. Трехслойная схема'требует большей памяти (при определении у,+, надо помнить векторы у„ и у„,), сильнее зависит от неточностей в задании постоянных 7, и 7„ чем двухслойная чебышввская схема.
Поэтому на практике целесообразнее пользоваться чебышевской схемой, а не трехслойной, если заданы Ъи 7 ° Замечание. Переход от явной к неявной трехслойной схеме сводится к замене в уравнении (3) А на В 'А и 1' на В '/, так что у„'+~ И+аПŠ— т,В 'А)у„— ауь,+И+а)тзВ 7' или Ву+, И+ аП — т А)у, — аВуз, + И + а)т1, ИО) Ву, Ву,— т,Ау,+т,1, й=1, 2, ..., у,ыН задано. Уравнение ИО) можно получить, если вместо (5) написать тождество Ви= И+аПВи — т,Аи) — аВи+ И+а)т,1 и расставить в соответствующих местах номера итерацкй (см.
ИО)). Формулы (4) для т, и а остаются в силе, однако 7, и Т,— границы оператора А не в Н, а в Нз.' 7 В <А < 7аВ, 7~>О, В В*>О. И1) При этом для решения задачи ИО) вместо (7) выполняется оценка 1 у- — Лв- <у.1Ауе — Яв- ° (12) где д„по-прежнему определяется формулой (8). В качестве В можно взять оператор (76) ив $3 для ПТМ. з з. дгттив ититдционныи мктоды 583 2. Метод минимальных невязок. До сих пор мы .всюду предполагали, что постоянные '7, и 7» — границы оператора А, ааранее известны. Может оказаться,что они либо априори неизвестны, либо вычисляются очень грубо.
Тогда целесообразно пользоваться так называемыми итерационными методами вариационного типа, которые не используют в явном виде первичной информации опараметрах 7, и 7». Это — методы скорейшего спуска, минимальных невязок, сопряженных градиентов (трехслойная схема) и др. Мы рассмотрим здесь лишь два метода: метод минимальных невязок и метод скорейшего спуска. Это двухслойные схемы.
Начнем, как обычно, с явной схемы: д+ " +Ау»= ~, й= 0„1;2,..., задано у сиН» (13) тд+ или У»+~ Уд — тд+Л г» Ау» — ~ — невязка. ИЗ') гаазичие между методами минимальных невязок и скорейшего спуска только в формуле для параметра т»+,. Для метода минимальныя невяаок (А1»з гд) тд+д —— , где гд = АУ» — 7'. (14) -~ Агд !!з Это получается из условия минимума нормы невязки 1г»+,П.
Напишем уравнение для невязки: д+» д +Аг»=0, й=0„1,2,...„ тд+д (15) и вычислим ~ гд+» ~д = ~ гд !!д — 2тд+д(Агы гд) + т»+» ~ Агд д!!. (16) Правая часть в И6) есть полипом второй степени Р»(тд+д от па- Р раметра т,вв Приравнивая нулю производную Р,(тд+»), находим т„+, согласно И4). Вторая проиаводная при этом значении т»+~ положительна и, следовательно, величина !!г,+,1 минимальна. Все зти рассуждения сохраняют силу и в том случае, когда А — несамосопряженный оператор. Отсюда сразу следует и априорная оценка ~гд~»~~ (рд)гд!!, т. е.
~Аӄ— ~~(р»1Аур — 7!~, (17) где р, 'И вЂ” $)/И+ $), $7~/7», а 7~ и 7» — точные границы оператора А Ад) О. В самом деле, так как при значении т»+1 И4) правая часть в И6) минимальна при фиксированном гд ~в Н, то при любом дру- 384 тл. х. Методы Рипения сеточных уРАВнений том аначении и, в частности, при т т, она должна возрастать: та+1 ~ (еета а1а 2те'(Агю 1'а) + те !) 4та Р( 1 та — Ъ4га))а ~( (~Š— т А)(а(таД, ИЗ') Р у„+1 у,— т,+,(Ау,— 7) = уа- т,+,г, Й И4).
Объем вычислений из-эа формулы Ц4) для т,+, здесь больше, чем в случае простой итерации. Нетрудно написать неявный метод минимальных нееязок: Уа+1 Уа — та+,игм юа В-'(АУ, — 7), И8) который обычно называют методом минимальных нонраеок. В этом случае вместо уравнения Аи 7 надо рассмотреть уравленне Си ф, и Вьи, С В-'АВ-", ф В-"'*7, И9) н применить к нему явный метод минимальных невяаок: х„+, — — х„— т,+,(Сха — ф), где (Сга, га) та+, — — ',, га = Сха — ф. (Сга, Сга) Подставляя сюда х, Вьу„, С В ЧАВ ь, ф В 17 и преобразуя та=В-'а(Ауа-)) =В-';, (Ст„та) (В ЕАВ-'т„, В ьг,) (Аюм ига), (Сг„Сг„) = (В 'Аиь В 'аАюа) = (В 'Агеа, Акга), где ига В 'т„— поправка, получаем уравнение (48), в котором надо положить (Аш „ша) та+1 = геа = В га.
(В ~Аш~„Аша) (20) Вместо оценки И7), очевидно, получим ~Ау — Л!)в 1(ре (Ауе — 71в-1. (24) ! та+1!) ~( ! Š— теА 1 1!! га еа С другой стороны,из э 2, и. 3 известно, что )!Š— т,А!! = р, при т. — 2/(7, + 7,). Тем самым доказана оценка (47), из которой видно, что метод минимальных повязок сходится с той же скоростью, что и метод простой итерации (если для вычисления т, при этом используются точные значения 7, и 71). Вычисления в методе минимальных невязок проводятся по фо мулам $ а диъч'ие итвг»ддионныв мктоды 585 3.
Метод скореюпего спуска. Для явного метода скорейшего спуска у,+,=у,— т„+,(Ау,— ~), й=0, д, 2, ..., аадано любое у,дяН, параметр т,+, определяется по формуле (гд~ г») т»ед —— , г» =Ау» — ), )д = 0,1,2, ... (Аг», г») ' (22) (Аи», и») т»» д —— —, (25) ЦАи» Ц Повторяя рассуждения, проведенные в и.
2, получаем оценку Ц ив Ц ~ ~Ро Ц и» Ц. (26) Теперь остается перейти от и, к а„= А ьидь Учитывая, что Аац —— =А(у» — и) =Ау» — ~=г„, (Аид, и„) =!!Аа»8» = !!г»Р, !1Аи»)) = = (Аг„, г,), цреобраауем (25) к виду (22). Иа неравенства (26) следует Цуа — пЦА~(Ро Цуо — пЦАъ (27) так как Ц и„Ц» = (и»а ил) = (Аааэ аа) = Ц авЦА. Таким' обрааом, метод скорейшего спуска сходится в Н» р той же скоростью, что и метод простой итерации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
