А.А. Самарский - Введение в численные методы (1113832), страница 17
Текст из файла (страница 17)
Для поправки и'„= В 'т„, т, = А у„— ) выполняется (так же, как и для погрешности г„= уг — и) однородное уравнение В ~л~ +Аи'ь=-О, й=-0,1,..., и>ю = В т(Ауа ~)ь (22) где г, Ау,— ( — невязка, и,=В 'г,— поправка, Б самом деле, из (21) находим увю = у, — тВ '(А уд — /) = у, — ти~п Ау,, — ( = Ау, — 1 — тА гоп гвы = т, — тА и:ь Так как г,=В(В 'т„) =Во:„, то отсюда следует (22). Будем предполагать, что выполнены операторные неравенства у,В«А «1гВ, '(,>О, у, -у,>0, (23) или у,(Вх, х) «(Ах, х) « "(,(Вх, х) для всех х ыН, (24) 2 т=та= т,+ тг' (23) где постоянные уо "(, известны.
Теорема 3. Пусть выполнены условия (23), (24). Тогда лшнисчальное число итераций по методу (21) достигается при З з. итвгхционных методы и ~ 1п (1/е)/!и (1/р,), (йс)) Замечаипе. Функция !р(з) =)п(1+ а)/(1 — $) — 2з полол ительпа для всех 0 < $ <1, так как <р'(з) = 2еЧ(1 — "") ) О, ср(0) = 0; поэтому 1/)и (1/р,) < 1/(2$) и условие (29) выполпеко, если п ~ п„(е) = (1/(2з)) 1п 1/е, $ = 7,/7, (30) (п,(е) — вообще говоря, пецелое). Условие (30) более удобпо для оценок. Оцепка рв ~ (з. очевидио, вьшолиева, если п„(е) ( и < п,(е) + 1. 1(озтому и качестве п достаточпо брать целуя! часть числа п„(е) + 1. 7.
Модельиая задача. Сравнение различных тперапиопных методов будем проводить иа следующей эталонной, или модельной задаче г; 1 — 2Г;--. '~! ! 2!=- — /ь ! -1,,...,У вЂ” 1, О - — 01, ол: —. Нм й .—.. —., (31) Л' разиостиой схемой для краевой задачи 0<х(1, и(0) =- р„и(1) =- рм которая являотся е' о — „= — / (х), ое Запишем систему уравпеиий сначала в матричной форме," Ао- /, (32) При этом выполняется неравенство (~ АУ!! — /,')в-! ч= Ра ((АУ!! — /((з-!, и = 1, 2,, (28) р,=(1 — Ц)/(1+в), з=;,/7т. (27) Доказательство.
Для решеипя зада ш (22) воспольауеътст! следующей оценкой (доказательство оценки приводится в гл. т') ()ю„(Ъ,( р",(и,~(, прп т - т„ (28) где р=1 — т7,. Минимум р (при котором, число итераций, минимально) достигается при т = т,: р ~ р, = = — 1 — тт1! = (1 — Ц)/(1+ с). Остается учесть, что !!и!„~1, = =! В " )<в = ~го()я-! Теорема доказана.
Требуя, чтобы р", < е, плл (1/р,)" ~ 1/е, получим оцепку для числа итерации; !08 гл тп. Решение АлгеБРАических уРАВнений где г = (гоьь г"', ..., го™) — вектоР РазмеРности )У вЂ” 1 и Л вЂ” трехдпагональная матрица размера ()У вЂ” 1) Х ()ь' — 1): 0 о — — 2 !О ! — 2 ! 0 0 ! — 2 0 ! — 2 Л г = — Аг, генП = Н, г ьн П.
Введем в Н= (ь, как обычно, скалярное произведение и-ь (у, г) — - ~' у;г,й ь 1 п воспользуемся формулами (17), (56) пз 2 4 гл. 1, в силу которых (Лг, пь) —.=- (г, Аль), т. е. А = Ае, (Аг г) Ъб~!г(~;-', 6 =- —, зьп' — ' АьЬЕ. Далее, имеем !! Л )! =- ьь = —, созз —, Ае Оцепим число итераций для явной схемы простой итерации в случае модельной задачи. Имеем Н = Е, бЕ «А. «ьАЕ, т, е. ть . п!ь лей — =- !ае — ' у =6 Для числа итераций имеем в ( ) ~ ьь, (~) =- —, )в!е 2 ! !Ь лье з Правая часть уравнения (32) имеет компоненты )', = г"ь п)ьи ь = 2, 3, ..., А' — 2, ььь = ььь+ (ьь/й, (х — ь = ьгв-ь + (ьг/й' Матрице Л соответствует оператор А, действующий в пространстве Н =(ь сеточных функций, заданных во внутренних узлах сетки ыь, =(х,= !й, 0< !«ььь), Пусть ."ьг =- г-, г — сеточная функция, заданная на сетке еьь, = — (хь = (й, О «ь «ьь!) н обращающаяся в нуль на границе прп ! = О, )У, Тогда моьено написать з х итгвхцпоппыг.
хгитоды 1ОЕ Зададим е =- 2 10 с — ис В частности, число итерации: п,(с) = 200 прп Х = 10, п„(с) = 20000 при И = 100. тогда пз (е) — „=- 2.У-'. 2 ье Первая итерация вычисляется по явному методу простой итерации: р, =- (Š— т,Л)у„+ т„) для всех р,'и Н, (34) где 2 1 — рб 71 у~ '(г ) 0 — границы спектра оператора Л = Л*: т,Е ~, .1< (Е Можно показать, по для метода (33), (34) число итераций находится из услови~г Отсюда видно, что ~О $ лз (с) ж —" )и —, 1(се < 2, гЯ (Зб) Метод простой итерации сильно зависит от числа уравнений Й (и,(с) = Ж'). Ниже приводятся методы (см.
$$ 4, 5), для которых зта зависимость и от У будет более слабой (л,(е) = Ж и и„',с) ж УУ). Задача (31) является типичной, так как апалогичпое разиостное уравиети|е моделирует разпостное уравнение Лапласа в двумерном и трехмерном случаях, а число итераций практически пе зависит от числа измерений (зависит только от й). 8. Трехслойная схема. Если у,ч, вычисляется по двум иредыдуп(нм итерациям уз и у, „ то итерационный метод называют двухгппзовыгч (1гли трехслойныМ. Приведем пример трехслойной итерационной схемы, Явная.трехслойная схема с погтояппыып параыетрамн обычно заггисывается в виде у, „= (1+ я) (Š— тЛ )д„— иу,, + (! + а) т!, (г = 1, 2, ...
(33) (1О ГЛ. П!. РЕШЕННЕ ЛЛ1'ЕБРЛНЧЕСЯНХ УРЛВНЕННИ Для модельной задачи Уз = НЫ2 и со ( 0,32 1 — 1О п (е) -1и с — 1и с„3, Л при е е о за е о Ву, =Вуо — т,Лу + т»( для всех у ~Н. Если В= Во) О, выполнены неравенства (23), (24) и и, т, вычисляются по формулам (35), то для числа итераций оценка (Зб) верна и в этом случае.
$4. Двухслойная итерационная схема с чебышевскими параметрами 1. Постановка задача. Пусть дано уравиенно Аи=(, А: Н- Н. (1) Рассмотрим итерационную схему с поременными параметрами (т,1: ЗЛ;-1 В ' '"' +Аул.=- 1, й= — 0,1,2, ..., для всех у,енН. 1!О1 (2) Однородному уравнению В о +Лзл=О Й=О 1 2 зо=уо -и, (3) то о 1 удовлетворяет не только погре1пность з, у,— и, но и поправка ш» В '(Ау,— 1) (й=О, 1, ...) с начальным условием л!о =-В '(Ауо — 1). Условие окончания итераций имеет вид ,,~~о Е! З»Зо! НЛИ 1!С! 1о ' Е!!а!» о.
(4) Из (3) видно, что з»о! =Ь»»!Е», Я»»! =Š— т»,В 'А, (5) Число итераций: л»(е) = 32 —:.00 при 1»! п,(е) 320 —:620 прп Н т. е. значительно меньше, чеи для Неявная трехслойная схема имеет Ву»+! (1+со)(В т»А)у» соВу»-!+ ( = 10, — 100, простой итерации. вид '1+ й)т,1, 11=1,2, ..., 5 ь двухслойная птвэзциоппля схатил 11! (7) у„=)!Т„1о ~ е.
Для оценки числа итераций я=п(е) надо получить неравенство (7). Рассмотрим явную схему (2) рзэз — зз чиАуз=.1, й=-0,1,2, ..., (8) аез причем задано любое у, — Н, и выберем параметры т„т....., т, пз условия пни п(е). Прп этом предполагается, что А=Аз>0, 7Е~А<7Е, 7,>0. Для невязкп г„= Ауз — ) выполняется однородное уравнение ~ +Ага=0, тх ы 1 гз — ~уз 1х пли гни=Языги Ю„„,=Š— т,э,А, Отсюда найдем г„= Т,г„Т„=Я,Я, ... Я„.
Разрешающий оператор Т„есть полинам степени и относительно А: Т,=Р„(А) =(Š— т,А)(Š— т,А) ... (Š— т„А) с коэффициентами, завпсящпмп только от т„т,, ..., т„. Для нахождения т„ть ..., т„получаем оценку 1,'г„)) ( 'зР„(А)Пг,!1, Надо найти такие т„тз,, „т„, прн которых РР (А)з минимальна, и оцепить эту норму через постоянные н 7,, Приведем без доказательства решение этой задачи.
где Я,„, — оператор перехода со слоя й на слой Й + '1. Псключая гм г, „..., г„найдем прп й = и — 1; г„= Т„г„Т„= Ь„Я„-, ... 5 5, где ҄— разрешающий оператор схемы (3). Отсюда следует, что )Мо ~ Ч зго~)ю у = "7~ зо (б) Условие окончания птерацнп (4) выполнено, если Гл Н1 Решение ллГеБРли 1еских РРавненпп Обозначим через х)„= — соз, л, 1=- 1, 2,, к, 21 — 1 . о множество нулей ёолиноша Чебы1иееа Т.„(х) = - соз (и агссоз х) па отрезке — ! < х -= 1, а через (ре)— любую последовательность этих нучеи, р, ы 1Р)„, Минимальное число итераций л(е) достигается ирп значениях параметров те ть = , )е = 1, 2, ...,и, о Ра 1.
Е + а Прн этом выполняется оценка ер" !Ау. — /1 ~,.~~ д„е !-;Р1 1-л (10) Схема (8) с итерационными параметрами (9) называется чеоышееской кгеракиояной стесоой. ч е ее1 Требование д„= е пли .р, ~ (е11+ р; ) выполнено, если рт(~е,-, плн П и (е) ) 1и =))п —,. 1 е/ р 1-~- 'Я, Замечая (ср. 3 3, и, 01, что 1о — =1и — '=".) 2 'у ~, Ую заменим (11) более сильным требованием: г я(е)) я (е) = —. 1п— е (12) удобнын для проверки.
Из (!2), очевидно, следует (1О), и д.-"-' е. Сравним по числу итераций схему (8) с указанным набором параметров и метод простой итерации на примере модельной задачи из $3. В этом случае $ Рви'Ь'/4, 1'с пй/2. Для метода простой птераппп н~,п(е) ж201е при е =-!О" ~. Для чебышевсной схемы пе'! (е) 3,4')1 при е 10 '. З г. двгхслопя гя ггтгг гцпопнля схвьгл 1(3 Отсюда зпдпо, что гге ~ 34, ллг ж 200 прп Лг = !О ()г —.— 1/10). пегги 340, гг,"г ж 20000 прп Х = '!00 (й = 11100).
2. Обоснование оптимального выбора параметров. Перейдем к доказательству оценки (!0) з случае итерационных паряпетроз (9). Пап пеооходпмо найти гп!п(Р.„(А))!. Пл) Полипом Р„(А) = П(Š— т„.!) = е.=г ге+с,4-'- ... -';се'! 4-... -'-,-с„А", се — 1, Р„(0) —. 1 является самосопряжепным оператором, Пусть йь )„(з = 1, 2,..., Дг) — собственные функции и собственные значеппя оператора А; А=, = ХД„(З„$,„) — Ь,„ч з, лг = 1, 2, ..., гр. Оператор А' имеет те же собственные функции и соб- ственные значения ),: ге А '$, = ). Д,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
