А.А. Самарский - Теория разностных схем (1989) (1160092), страница 95
Текст из файла (страница 95)
Для погрешности хл+, у„+, — и, х,+ л у„+ „— и получаем однородные уравнения (Е+ ввАв)хлвл (К вЂ” ввАв)хв, (Е+ вв 4в)ул+в (Е вв'4в)ел+ив О. 1 2 ", хвшК еадано. Обоэначая ов=(К+ввАв)х и исключая иэ И6) ал+ь, получим уравнение в,, ЯвЯво„й О, 1, ..., Р.ввК, Ий) э 1 итвглцнонныв мвтоды пвгнмвнных нлпглвлвнян 573 с оператором перехода Я =Я,Я„ Я ~(Е+ вьА ) '(Š— вгА~), Я, (Е+ в,А,) '(Š— в,А,). Отсюда видно, что 1о„„,)) < 1Я,Я,11о»1; надо оценить Ы,Я,)) и найти ю!п1Я,Я,1. »~ »х Нам понадобится следующая Лемма.
Пусть дан оператор А: П- Н и выполнены условия А А»>0, ЬЕ<А <ХЕ, б>0. (21) Тоеда норма 1Я(в))! оператора Я(в) (Е+ вА) '(Š— вА) при 1 в» имеет наименьшее еначение равное у'оа 1 ю(п)Я(в)~ =1Я(в»)~= ~, где т) = —. а 1+БИЧ ' Для докаэательства заметим, что 'Я(в) есть оператор перехода двухслойной схемы (Е+вА) "~~ " +Ауь= О, й = 0,1,. у»енН; (22) с оператором В = Е+ вА, так что у~, = Я(в)у„, )~у„„~) <р(у,1, где р — р(в) — ))Я(в)!!. Чтобы найти ю)пр(в), воспольэуемся 'теоремой 3 'иэ э 2 гл. У1 о р-устойчивости 'схемы (22).
В этой теореме утверждается, что необходимые и достаточные условия для выполнения оценки ))у»+ 1» < р1у»1» имеют вид :,Р (Е+ вА) (А ( — ~-(Е + вА) при любом 0 < р < 1 и любом операторе Р Р» > О, перестановочном с А, например, В=Е или Р А (в теореме 3 Р=В или Р-А, у нас В=Е+вА). Этя условия эквивалентны операторным неравенствам — Е ( А ( — Е„где $ = — ' и р = —.
$1 .1 — р 1 — ф в ~ св " 1+р 1+э Сравнивая их с (21), видим, что — (б, — )Ь или $в( —, так что $ (т). (23) э Минимум р соответствует максимуму $, который достигается, если в (23) ваять $/в =б, 1/($в) = Л, 4 = Уц 574 гл. х. методы Решения сеточных уРАВнениЙ и, следовательно, в $/б = т'т)/б 1/)бЬ а,. При этом ш(п р(в) = р(в.) = И вЂ” 'т'т))/И+ т'т)), что и требовалось доказать.
Этот же результат можно было бы получить и собом, если учесть, что р= ~Я(в)1= шах ~ 1 ™,„~, где )!, А,(А) — собственное значение оператора А. венно убеждаемся в том, что штпр(в) =ш1п шах ~ ~= ш(п шах~ 1 другим спо- Непосредст- аЛ вЂ” 1 1 аЛ+1 / = р (а,) = при в = ва 1 — )/Ч 1+ т/ч Вернемся теперь к задаче И9). Воспользуемся преобразованиями (9) и ИО) для операторов А„ А, н параметров а, и в,, полагая э +г ч+ 2~ Тогда оператор (20) преобразуется к виду Я = ЯД, Я, = (Е+ аАт) '(Š— вАт), Яр — — (Е+ вА,) '(Š— аА,), причем ВЕ ( (Аа ~~ Ер а = 1» 2. т) ) Ох где т) и параметры р, д, г определяются по формулам (14) и И5). Учитывая аатем неравенство !)Е!! < )!3,1!)Яр!! н, в силу леммы, ш(п ))Е,1 шш1Ер!! = И вЂ” т'т))/И+ "т'т)) при в* в, т'т)/б убеждаемся в том, что для решения задачи И8) верна онриорйая оценка ~(Е+ азАт) хе~(~ рр!)(Е+ атАр) хр!) р = ~ т (24) ~ 1+')/Ч / * если в, ть в, определяются по формулам г+ ча а1 =, ~1+ р ар = (рвр — ')/(1 — рар)р ар УЯЯ.
(25> 1+Ра В частности, при б, бр б и:Ьт Ь, Ь имеем т) б/Ь а е итвгацнонньш мвтоды пвгвмвнньтх непгавлвния 575 Из (24) следует, что условие.окончания итераций р" ( е выполнено, если и)и (е), и (е) =, где 5=в П1 1Ю 1п (1/е) 2 ~/Ч 1+и Рассмотрим в качестве-примера модельную задачу иэ $2. Для нее бе = 6,=6= 4э(де~ — )(Ь', Л, = Ье = Ь = 4соэе( — ")/йе и У7) = ~ сяе — ж — ж157й.
2 2 Сравним МПН (17)' с параметрами (25) с явным чебышевским методом +Ауе=1, й=0,1,..., те+ исследованным в т 2. Там было показано, что число итераций и)и (е), и (е)==, 5=7,/уе. <е1 1е> 1п (2/е) 2 )/$ В данном случае 7, б,+б, 26, 7е=й,+ Ле 25 и 5=6/Л=т).
Таким 'образом,п (е) ж =, и (е) ж —, т. е. МПН <е> 1п (2/е) <ю 1п (1)е) 2Уч ' ' 4)/ч требует примерно в 2 раза меньше итераций, чем явный.чебышевский метод. Однако для модельной задачи при переходе от й-й к (й+1)-й итерации на один уэел сетки надо выполнить: 1) 5 сложений и 4 умножения в случае явного чебышевского метода, 2) 12' сложений и 14 умножений в случае МПН (увеличение числа операций связано с применением метода прогонки сначала по строкам, а аатем пе столбцам).
Отсюда следует, что явный чебышевский метод более экономичен, чем МПН в случае неперестановочных операторов. Оба метода для модельной эадачи требуют О~ — )д ~ итераций. ',Й е) 5. Факторвэованные итерационные схемы и МПН. Рассмотренный выше метод переменных направлений эквивалентен двухслойной итерационной схеме В "'+' "е +Ау„=( (26) с фактериэованным оператором (ФО) В (Е+ ю,А,)(Е+ юеАе) (27).
и итерационным параметром (28) т = ю~+ юе. 576 ГЛ. Х. МЕТОДЫ РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИЙ В самом деле, перепишем (17) в виде В1уо+» Соуо+ М1 Воуо+1 Сюуо+и+ воЛ (29) где В, Е+в,.4„В, К+в,Ао, С,=Š— в,А„С;=Š— в,А,. Исключим подытерацию у„+то Для этого применим к первому уравнению (29) оператор С„ко второму — оператор В„сложим полученные уравнения и учтем, что В,С, =С,ВО а,С, +в,В, ° ю1(Š— в А,)+в,(Е+в А,) — (в,+в,)Е: В,Воуо+, С,с,у„+ (в, + в,)1. (30) Заметий теперь, что В,В,— С,С,= (ю,+воНА,+А,), и запишем (30) в каноническом виде (26). Обратный ход рассуждений очевиден. Если А, и А, неперестановочны, то оператор (27) не является самосопряженным и схема (26) не принадлежит семейству двухслойных итерационных схем из $ 3, для которого развита общая теория.
Рассмотрим случай, когда А, и А,— перестановочпые операторы, А,А,=А,А, и выполнены условия (5), (6). Тогда ФО (27) самосопряжен и положителен: В=Во)0. Из (30) видно, что схема (26) имеет оператор перехода Я = Я1ВМ В~о= Во Соо в= 1~2. В п. 4 найдены параметры в, и в„при которых достигается минимум )!о(в)1, равный р: юпвз где т), в„в, определяются согласно (14), (15) и (25). Зная о о Р, в, и в„нетРУдно найти постоанные эквивалентности 7, и 7о операторов В и А: 7,В~А «7,В, (31) необходимые для использования оператора В в, общей теории. Воспользуемся теоремой 3 из 4 2 гл.' Ч( о необходимых и достаточных условиях р-устойчивости схемы (26): Подставляя сюда р и т в, + в„находим о ( — р 24 ' 1-(-р в +в (1+5)(~ +в) ' 7~ в,+в (1+$)(в +в,) (32) Факторизованный оператор вида (27) можно построить на базе некоторого оператора В=В*)0, который представим в 3 ь етеглгшонные методы пеРеменных напвавлении $77 виде суммы Л = В, + „ В, = В,В„ Ва = Ла > Оэ баЕ («Ла «( ЬаЕ, Образуем факторизованный оператор а = 1, 2.
В (Е+ аВ,НЕ+ вВ,) (33) о о о о Тогда вместо (31) напишем 7,В<В < 7,В, где 7, и .7, вычисляются по формулам (32). Если оператор В есть регуляризатор для А: с,Л«А <с,Л, то постоянные эквивалентности А н В: 7,В ( А ~ 7,В, очевидно, равны о о 7~ Су7~ И 7оо Са'(ь Построенный таким образом факторизованный оператор (33) используем для метода с чебышевским набором параметров: В зы ~ +Аул=1, й=1,2, ...,и, уз~1. та+ Для числа итераций имеем и)ио(з), и (с) =, 5= — —,' )в (2/е) 2 УЧ о з (/6 з+ч с где ц определяется, согласно (22), через параметры 6„6„Ь, и Ь, операторов Л, и В,.
Для попеременно-треугольного метода (ПТМ) с чебышзвским набором параметров в $3 была получена такая же оценка и,(е), однако там ц выражалось через б и Ь по другим формулам.' Если В= — Л, Л вЂ” разностный оператор Лапласа и рассматривается задача Днрихле на квадратной сетке в единичном квадиь рате, то т) = В/Ь = 18з — как для ПТМ, так и для факторизованной схемы МПН (26) — (28). Поэтому оба метода требуют одинакового числа итераций, однако ПТМ в целом экономичнее; так, для вычисления одной итерации в этом случае требуется меньше арифметических действий.
Впрочем, для такой модельной задачи лучше всего положить В=В и определятв уооа решая уравнение Ву,+, — — Е„г"'„=Ву,— т„+,(Ау„— ~) прямым методом (декомпозиции нлн быстрого преобразования Фурье). Таким образом, трудно указать ситуацию, в которой схема (26) — (28) предпочтительнее, чем, например, ПТМ. Замечание 1. Рассмотренный в пп. 2, 3 МПН с переменными параметрами, очевидно, эквивалентен двухслойной схеме (26) с параметром т =то таз + тз' и, факторизованным оп а) 578 ГЛ.
Х. МЕТОДЫ РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИЙ оператором В» = (Е + т»Н)А,) (Е + т1»~А»). Замечание 2. Если А есть сумма р~2 попарю пврестановочных операторов: Р А = Х Аа1 Аа = Аа) 01 6аЕ~(Аа(ЛаЕ. Ьа>01 а 1 а=1,2 . ° ° р АаАЗ=АЗАае а,~=1,2,...1р, то непосредственное применение МПН (17) невозмоягие, и в качества итерационного МПН можно рассматривать схему (26) с факторизованным оператором Р В» = П (Е+ т~»")Аа), т»") ) О. а 1 В этом случае точное решение аадачи о минимаксв неизвестно, а испольауется так называемый циклический набор параметров. Для вычисления новой итерации у,+, надо решить уравнение Д (Е + т1а)Аа) у»+1 = Р что сводится к последовательному решению уравненик (Е+ т»1'1А1) у1 ) = Р» (Е+ т»а1Аа) у1. 1= у1 ') 1е = 2, ° ° ° Ъ причем у„+, у'»1.
В случае рааностной задачи Дирихле для уравнения Пуассона в р-мврном единичном кубе Аау = — Лау» Л,у = у- 1 и вычисление у,+, сводится к последовательным прогонкам по направлениям л„яь ..., хю т. е. к алгоритму типа МПН. Если ваять циклический набор параметров, то этот МПН обеспечивает точность е через и (е) =0(1п — 1п — )итерации, гдв Ь Ь, Ь, 1 11 » е) Ь„ — шаг сетки. Для этой же задачи ПТМ с операторами В»у = ~~ — у- В,у = — ~~ — уа ,'1» А1 а а а а=1 а требуется яе(е)ж =0~=1п — ), 1а(2/е) / 4 2» 3>54 "У'й ( У'Ь т. е.
асимптотика для ПТМ хуже, чем для МПН. Однако уже для р=3 при Ь> У60, т. е. для сеток с числом узлов < 2,16 ° 10', число итераций для ПТМ меньше, чем для МПН с циклическим П а итвэационныв мвтоды пвгнмвнных напгавлинин 579 набором параметров, а по общему объему вычислительной работы преимущество ПТМ весьма значительно (ПТМ экономичнее МПН в 2 — 2,5 раза).
В целом ПТМ экономичнее МПН на любых допустимых сетках. 6. МПН для случая несамосопряженных операторов. Пусть дано уравнение Аи=(А,+А,)и-~, где А, и А, — несамосопряженные положительно определенные операторы, и выполнены условия Аа)~бди Ац ~ )д Е. бд,>Оэ Лд>Оз в=1,2.
(34) а Второе условие, очевидно, эквивалентно неравенству ЦА,у(Р < Ь,(А у, у). (35) В самом деле, О ( ((Аа х, х) — — (х, х) = (у, Ассу) — — (Аау~ Аау)г -1 1 1 а а если положить х = А„у. Для решения уравнения - Аи 1 рассмотрим итерационный МПН с параметром в: (Е+ аА~)уа+а = И вЂ” вАэ)уа+ а~ (36) (Е + вАэ)ува = (Е аА~)уй+а + вР. По аналогии с п. 4 для пав = И+ вАз)ха+о где аз+~ = уыа и погрешность, получаем и,в=ЯДом Я (Е+вА,)-'(Š— аА ), а=1, 2, Пи вЦ < ЦЕАПЦР П (ЦЯ ЦЦ.ЦПР Ц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
