Самарский - Введение в теорию разностных схем (947501), страница 78
Текст из файла (страница 78)
(2) э+! с произвольным начальным вектором ус ен Н. Предполагается, что операторы А и В удовлетворяют требованиям А=А'>О, В=В'>()Е, (!>О, (3) у, В ~ (А ( уэВ, у, > у, > О, (4) е) В нвписвнни этого пункте пронимал участив Е. С. Николаев. Гл.
Рп!. итеялцнонные методы 476 где у, и у2 — постоянные энергетической эквивалентности операторов А и В. Из (3) н (4) следует положительная определенность оператора А. Всюду в этом параграфе будем считать, что оператор В не зависит от номера итерации й. Изучение сходимостн итераций по схеме (2) сводится к оценке при й - оо решения гь = у„ — и однородного уравнения 22 1 — 22 В 2+1 2.+Аех=О, /г=О, 1, 2, ..., г,=д,— и.
(5) 'Фы Неявная схема (2) эквивалентна явной схеме (см. гл. 111) хьэ, =52~1хм 5241=Š— т„+,С, й =О, 1, ..., х,1:=: Н, (6) где С вЂ” один из операторов С=С, = А~В 'Аь или С=С = В "АВ '/» при х,=А г„ и при хь=В гм (8) Из (6) находим х„= У„(С) хз, где У„(С) = П (Š— тьС), (О) 2-1 зх 1!6 ~!У„(С)йх 1, (10) где разрешающий оператор У„(С) есть операторный полипом степени и.
В силу условий (3) и (4) оператор С вЂ” самосопряженный, с границами у1 и у21 С=С' Е<С< Е. 1 У1 У2 (!) Поэтому норма операторного полинома У„(С) оценивается по формуле (см. Л. В. Канторович и Г. П. Лкилов [1)): [1 У„(С) ~[ < гпах )У„(1') !. (12) и [т„тп Параметры Т1, Т2, ..., т находятся из условия минимума !~У„(С)1~ или ппп тпах ~У„(1)~ и, как будет показано ниже, 1 т) -121 7,1 выражаются через нули полнномов первого рода П. Л. Чебы- шева Т„(х). Нам понадобятся некоторые свойства полиномов П.
Л. Че- бышева (см. В. Л. Гончаров [1[) Т„(х) = соз (и агссоз х), — 1 ~ х «< 1, а = О, 1, 2, Та(х) = 1, Тз [х) = х, И З Е ТЕОРИЯ ИТЕРАЦИОННЫХ ДВУХСЛОЙНЫХ СХЕМ ОБЩЕГО ВИДА 477 Для вычисления полиномов высоких степеней можно использовать рекуррентное соотношение Т„е, (х) 2хТ„(х) — Т„, (х). Справедлива формула 2Т,(х) =(х+ )/хз — 1) +(х — )/хз — 1), которая доопределяет Т„(х) при [х[ ) 1.
Корнями полинома Т,(х), очевидно, являются числа (13) 2А — ! ),А=сов и, й=1, 2, ..., а. 2п (14) Рассмотрим теперь полипом У„(!), заданный на промежутке у| (! (уз и яормированный так, что У„(0) = 1. Такнмн свойствами обладает, например, полипом Уп(Г) = П (1 — ТА!), ! Бн ['71 М. (15) Ставится задача — среди таких полиномов найти полипом, наименее отклоняющийся от нуля на отрезке [уьуз] (т. е. имеющий наименьший гпах[У„(7) [, ! Ее [уь уз[) и нормированный к 1 при ! = О. Линейная замена ! = 05 ( (у, — у,) х + уз+ у) Т„(х) =-~-"-.-~-, [х[< 1, Т„(х) где Т„(х) — полипом П.
Л. Чебышева первого рода. Максимум отклонения Т (х) от нуля равен гпах [Т„(х) ! = -1<п~~ " 17п (хо)1 Подставляя сюда выражение (13) для Т„(хв), получаем ! шах [Т„(х) [ = ., ) е ~)/и,+У1/р,-1) +~1/р Уф,-~) позволяет свести эту задачу к построению полинома, наименее отклоняющегося от нуля в промежутке — 1 (х (1 и принимающего значение 1 в точке ха = — (уз + у1)/(уг — у1) = — 1/рю Где ра = (1 — Б)/(1 + Б) Б = у~/у Решением последней задачи (см. В. Л. Гончаров [1)) является полином и $ Е ТЕОРИЯ ИТЕРАЦИОННЫХ ДВУХСЛОИНЫХ СХЕМ ОБЩЕГО ВИДА 479 Вернемся к схеме (2). Из теоремы 1 следует, что для нормы разрешающего оператора Й„(С), определяемого формулой (9), имеет место неравенство !!Я.
(С) )(<й., если параметры (тА) выбраны согласно (18). При этом справедлива оценка решения задачи (б) (! х„!! < д„!! х, !(, которой соответствует следующая априорная оценка для решения задачи (5): !! ВР )!о «< ф„!! е, Ц, где В = А или В = В.
Отсюда видно, что через и итераций начальная погрешность !!ЕАЬ уменьшится в 1)д„раз. Требование о„< е будет выполнено, если число итераций л)~ и(е), где п(е) = 1Н(!Вп) ' При $- 0 получаем следуюгцую оценку для числа итераций п(е), прн котором д„< е: Так, например, если рассматривается разностная аппроксимация задачи Дирихле для уравнения Лапласа в квадрате 0 < хь хе < 1 на квадратной сетке, й1 = ЬЕ = Ь (см. гл. Б, $2), то Схему (2) с указанной в (18) последовательностью параметров ТА, й = 1, 2, ..., и, часто называют схемой Ричардсона, При исследовании сходнмости итераций вместо неявной схемы (2) достаточно рассматривать явную схему А +Сха=ф, й=О, 1, ..., а — 1, (20) А+! х,— произвольный вектор, или хА+, — — 52+,хА + ТА+,ф, ВА+, = Š— ТА+,С, (20') которая соответствует уравнению Со = ф.
При изучении сходимости этой схемы с параметрами (18) мы предполагали, что вычислительный процесс является идеальным, т. е. вычисления ведутся с бесконечным числом знаков. Гл. чн!. нтеРАционные методы 460 о(х,,) — 2о(х!)+о(х!Ы)=0, х;=Й, 1(~!'~<А/ — 1, о (0) = 1, о (1) = О, /! = 1/М. 4 .Епа 4 аль В этом случае С!7= — уе„, у!= — „, 3!п' — ', )8, у,= — „, соз' —, $ =!да —. Возьмем 20 уравнений (А/ = 20) н положим е = 10 '. па 2 Теоретическая оценка показывает, что для получения решения задачи с точностью з достаточно взять п)~п(е), где п(е) = =(1п(2/е))1(!пр, !))63. Параметры т!,Тм ..., Т„выбираем по формуле (18) при п = 64.
Результаты вычислений на БЭСМ-4 даны в таблице !. В первой строке указан номер итерации й, во второй строке — вели- чина ЛА =!! !7А — !/А ! !!с = п1ах )РА (х!) !/а ! (х!) !. О~а <! Итерационный процесс расходится, и при й = 64 наступает аварийный останов машины. Таблица 1 53 56 57 54 6,3 10' ! 1,9 10' 7,2 1О' 0,12 61 60 З,З ° 1О" 37 !Ог 2 6.
10а 2,5 ° 10" 5 10" Ь» Если брать параметры та в обратном порядке, т. е. поло2й — 1 жить в формуле( 18) Ха = — соз — и, й = 1, 2, ..., п, то неустойчивость итерационной схемы выражена более сильно и аварийный останов наступает при й = !2 (см. таблицу 2), Однако на самом деле вычисления ведутся с конечным числом знаков и на каждом этапе вычислений появляются ошибки округления, которые приводят к неустойчивости при достаточно больших п = п(е, р,) итерационной схемы с параметрами (18). Неустойчивость схемы (2) с параметрами (18) можно проиллюстрировать на следуюшем простом примере, сосчитанном на машине БЭСМ-4 (расчеты проведены Д.
А. Гольдиной). П р и м е р. Требуется решить систему разностных уравнений и 4 а. теоРпя нтеРАцноиных днухслойных схем оашего внд» 431 Таблица 2 2 ) 3 ~ 4 В ~ 6 3,7 1оа ~ 1,2'1О'а 26 !О ~ !6 !О В2 !О' 39,6 в о ~ !о 7 10" ) 1,2 ° 10" ( 1,7 10'а 1,3 ° 10' а 3,3 ° 10" Ошибки округления можно трактовать как возмущение правой части уравнения Со = ф на каждом шаге. Итерационная схема (2) с параметрами (18) неустойчива по правой части. Причиной неустойчивости является тот факт, что норма оператора 5» = Š— т»С — оператора перехода от (й — 1)-й итерации к й-й итерации, при отрицательных Л» может быть больше единицы, так как !15 !! — пр Л (О 1 — Ра ! Х» ! !!51,!!>1, если ро(!+21 Л»!)>1. В то же время !!5»!1= Р' ') <1 при Л»>0. Установим эти формулы.
Так как 5» = 5», то !! 5„!! = ецр 1(5»х, х) !. Учитывая, что у,Е(С(уоЕ, найдем Цхо 1 (т»у, — 1) Е ~ (т»С — Е » ((т»уо — 1) Е. ця,,))=,' ' -, ' (! — 2»(! а, ))со!!'!. с/» !6 А. А Самарскиа Подставим сюда т„= т,/(1+ роЛ») и учтем, что -тоу, = 1 — ро, тоут = 1+ ро. Тогда получим т»у, — ! = ро(1 +Л»)/(1+роЛ») т»у, — 1 = ро(1 — Л»)/(1+роЛ»).
Отсюда видно, что !15»!1=т»уа при Л» ( О, !! 5„!! = 1 — т»у, при Л» > О. Если Л» < О и /ц )~ /ц„ где йо — наименьшее число, для которого )м< О, и выполняется условие р, (1+ 2 1Лм!) > 1, то !!5»+,!!>!!5„!!> 1.
Поэтому а П!151!!>1!5»,!! '>1 и погрешность округления, появившаяся 1»а при определении у»„будет увеличиваться с ростом й от йо до и. Пусть 3=у,/у, ~ 1, так что ро= 1 — 25+ 0(~~) и Л», = 2»с — ! соз ' я<0, 2л гл. Тп1, итеехционпые методы 482 Предположим, что !ХМ ! > 0,5, а $ ( 0,01. Тогда !! Зм 1! = и =3(1 — 6$)+0(80)>3 ° 0,9=2,7 и И1!51!!>2,7" ! и Теорема 1 фактически выражает устойчивость схемы (2) по начальным данным. В случае реального вычислительного процесса, как показывают приведенные выше примеры, необходимо исследовать устойчивость итерационной схемы по правой части, а также устойчивость по начальным данным при переходе от х0 к хх для любого А = 1, 2, ..., и. Как было показано в гл.
Ч, 5 2, устойчивость по правой части есть следствие равномерной устойчивости по начальным данным, т. е. устойчивости при переходе от любого х, к любому хм где й > ! > О. Требование равномерной устойчивости по начальным данным гарантирует вычислительную устойчивость итерационной схемы.
Поясним зто утверждение. В результате ошибок округления находится не решение задачи (20'), а решение Ух задачи тх+! = = ох+!х! + ТОР!Фд + ьх, й)~0. Чтобы оценить величину погрешности вычислений хх — х1„надо найти оценку решения задачи (21) 20з! = 50!!20+ т01!ф0+ ьы 20=20 — хо через 2м Фы сх. Из (21) следует (см. гл. Ч, 9 2) 20 = Т, 020+ л т1 Тм !Ф/ + 2 Ть Бг- / ! 1! !1 20 !! ((!! ть 0 !Щ 20 11+ Х т! !! тъ 1 111! ф !!+ Х !! тм 1!! )! ь 11, (22) Тм ! — — Ц Я„Т„, 0 = Е, !! ф !1 = !пах!~ фг !(, 1-1- ! 0Я1<0 где (! ь 1! = шах ~! ь! 1~. Ж1~п Достаточно убедиться в том, что величины !! Тм 0 ~1, ~~; тг!! Тм 111, / ! ~ ~! Тмг!! ограничены для всех й «-'л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
