А.А. Самарский - Теория разностных схем (1989) (1160092), страница 88
Текст из файла (страница 88)
х, метолы Ркшения 'сеточных РРАвненнн ео ния нестационариой задачи  — „+ Аи = 1, причем параметр тй+1 можно рассматривать как шаг по фиктивному времени А+1 Та+1 = Х тт. та=1 Различие между итерационными схемами и схемами для не- стационарных задач состоит в следующем: а) итерационная схема (3) точно аппроксимирует уравнение И), так как решение и уравнения И) при любых В„и т„+, удовлетворяет уравнению '(3); б) выбор параметра т„+, и операторов В„следует подчинить лншь требованиям сходимости итераций и минимума арифметических действий (экономичности) для получения решения исходной задачи с заданной точностью (в случае нестационарных задач выбор шага подчинен прежде всего требованию аппроксимации).
Пусть ®е) — общее число арифметических действий, которые надо вьгаолнить, чтобы получить при помощи метода (3) решение уравнения И) с заданной точностью е ~0 при любом выборе начального приближения. Схему (т, е. (Т„) и (В,)) надо выбирать так, чтобы ()(е) было минимальным. Если п = п(е) — минимальное число итераций, при котором достигается точность е, то ме> Ч (е) = ~с~ ()й = В,п, где чй — число действий для нахождения й=1 й-й итерации. Задача о минимуме Д(е) сводится к задаче о минимуме числа итераций п(е) и числа 91, которое зависит от В,. Бели В, Š— единичный оператор, то (3) называется явной итерационной схемой " +Ауй=(, й=0,1,2, ..., для любого у,йиН. ИО) ТА+1 Если же В, т*"Е, то схема (3) — каленая.
2. Стационарные схемы. Основная теорема о сходимости итераций. Часто используются итерационные схемы В "'" "" + Ау, = 1, й = О, 1, ..., (3 ) с постоянным оператором В и постоянным параметром т, называемые стационарными методами итераций. К ним, в частности, относятся известные методы Зейделя и верхней релаксации (см. $3). В этом случае уравнение (9) для погрешности зй уй — и имеет вид й+1 йй В +' +Ага=О, й=0,1, °, г =у — и. (9') Такое же уравнение верно и для поправки 1ой= В-'(Ау„— )). Оператор В является, вообще говоря, несамосопряженным и имеет обратный В '. И 2.
двъхсловныв итвРАционныв схемы 527 Т е о р е м а 1. Если А — свмосонряженный положительный оператор (А = А*> О), то условие В> — тА, или (Вх, х) > —.(Ах, х) для всех хеН (И) 1 т достаточно для того, чтобы метод итераций (3') сходился в Н„ со скоростью геометрической прогрессии; Иг„+,И„~РИг,И., й=о, 1, ..., р<1, (12) где р=(1 — 2тбвб/ИВ!Р)и' — знаменатель прогрессии, 6 = шш Ль(А), бв =, ш(п Ль(В, — тА/2), В, (В+ Вв)/2 — симметричная часть оператора В.
Доказательство. Выражая г„+, из (3'): г„+,— — Яг„, Я= =.Š— тВ 'А, найдем ИггыИ л= (Аг,+„г„г,) = (АЯг„, Яг„) =' (А(Е— — тВ 'А)г„, (Š— тВ 'А)г,)=12Д вЂ” тПАВ 'Аг„г„)+(В 'Аг„Аг,))+ +т'(АВ 'Аг„, В 'Аг„). Учитывая, что А = Ав, и подставляя сюда 1 Аг„= — Вом оь= — В 'Аг„, где оь = — (гь+, — гь), получим И гь+, ))л = () гь ~л — 2т (( — тА/2) ою оь). (13) Иа положительности (в силу (И)) оператора Р=  — тА/2>О следует его положительная определенность в конечномерном пространстве Н (см. Дополнение, И 1, и. 3):  — тА/2вбвЕ, бв ) О, (И') где бв — наименьшее собственное значение оператора Р,=В,— — тА/2, так что 2т (( — тА/2) оь, ог) ~ )226„$ иа!!2.
(13') С другой стороны, имеем Иеген = (Аг„,гь) =(Воип А 'Воь)( < )!А-'1ИВо„!Р ( ИА-'ИИВИ*Ио„Иг = !!ВИ'ИЦР/6 и, следовательно, 3 оьЙг)~(6/~В!/2)/!гь!~. Подставляя (13') и (14) в (13), получим оценку Йгь+2!Йг= =Иихф(ргИгд(!гл, где р* 1 — 2тббь/ИВИг(1, откуда следует (12) и неравенство Иг„И*< р"Иг,Ил, показывающее сходимость итераций, так как р"- О при п- . Для поправки ю„В-'(Ау„-/) получается та же оценка. Замечание.
Условие (И') при ааданном В определяет те значения т, при которых итерации сходятся. Так, для явной схемы (В Е) (условие (И') выполнено, если все собственные аначения Л,(Š— тА/2) 1 — тЛь(А)/2>О, т. е. 1 — тИАИ/2>О, итерации сходятся при любом т ~ 2/ИАИ. Отметим также, что полученная выше оценка. для р, вообще говоря, груба для оценки числа итераций н(е, Ф) и дает лишь правильный порядок для и при )т'- 528 гл. х.
метОды Рзшкния паточных Ргавниннй 3. Явная схема с оптимальньгм чебышевским набором параметров. Рассмотрим явную схему ИО) с параметрами т„л„... ..., т, которые выберем так, чтобы число итераций п в(е) было минимальным. При етом предполагается, что А — самосопряженный положительный оператор и известны границы его спектра, т. е. 'наименьшее (71 >0) и наибольшее (71) собственные значения: А = Аа > О, 7,Е < А < 7,Е, 7, > О. Иб) Последнее условие означает, что 7,1хП1 < (Ах, х) < 71))хП1 для любого х 1в Н. Если параметр т=сопзс не зависит от й (т, т,=...=т„=т), то ИО) называют схемой простой итерации: у1+1 у1 — т(Ау» — )). Иб) Для невязкн г,=Ау„— ), как было показано в п. 1, выполняется однородное уравнение "+Ага=О, й=0,1,2,..., г,=Аус — )енН,(17) 1+1 клн г,+, = 81+,г1, 81+1 =Š— т„+,А.
Отсюда выразим г. через ге.' г„т„„т„8181... и„, И8) где ҄— разрешающий оператор, являющийся полиномом пй степени относительно оператора А: Т„=У„(А) =(Š— Т,А)(Š— Т,А)...(Š— т А), И9) так что г„У„(А)г,. Для г„получаем оценку Пг„П < ПУ„'(А)П Пг,П вЂ” д„1г,П. (20) Наша задача состоит в оценке ~У„(А)П через 71 и 7„в отыскании таких параметров т„т1, ..., т„, при которых достигается минимум величины д„= !!У„(А)П. Операторный полипом У„(А) = П (Š— т А) = ~ саА", са = 1, У„(0)=-1, Фи 1 является самосопряженным оператором, так как любая степень оператора А есть самосопряженный оператор: А" = (А")*.
Пусть (Л., $,) — собственные значения и ортономированные собственные функции оператора А: АВ. Л,$., а=1, 2, ..., Н, 0<Л~<Л1<...<Л1, где Н вЂ” размерность Н, причем Л1= ш(пЛ. = 7„Л шах Л. - 71. 1 ° 1-1 1 й Учптывая, что А Ь= Л~А 5,.= Л зо т. е. Л~ есть собственное э з. двтхспоннык итиэационнык схиэы . 529 значение оператора А; получаем о ! о Уо (А) ооа = Х саА ооо = ~ с~~ ~саХа ооа = Уе (Хо) $а~ а о а о нли Х(У„(А)) = У (Х(А)).
Таким образом, собственные вначения операторного полинома У„(А) равны полиному У„(Х) от собственных значений Х Л(А) оператора А. Так как (У.(А))о =У (А), то ~ У„(А)!)( шах ! У„(х) !. (21) т1состо Наша вадача — отыскание шш ! У„(А) ~ — сводитсй к задаче онов,...,оо о минимаксе полинома У„(л). Проведем аамену переменных, полагая и = 0,5(("( ° 7а)Ф+ 7г+ 7Л ° (22)' При этом отрезок (7„7о] отображается на отревок (-1, 1) и, следовательно, У„(х) У„(й, сон ! — 1, 1), причем У„(0) =1.
Надо найти полипом, наименее уклоняющийся от нуля на отрезке ( — 1, П, для которого шах !У (о)! минимален, при до-осо<~ полнителъном условии нормировки У (с,) = 1, где Ф, соответствует х О. Из (22) при х= О находим (23) о .т„я Таким полиномом является полипом Чеоышева У„(г) =— то (оо) где Т (Й сов(иагссовС) прн )о! <1. При )о! > 1 полипом Т И) определяется по формуле Т„(1) = 0,5((т+ Ю вЂ” 1)" + (1 — У~С вЂ” 1)"), )(! ) 1.
(25) Так как шах ! Т„(С) ! = 1, то (л<а ш(п,шах )У„(х)(=шш шах )У„(1)~= 1I)Т (Ф,))=д„. (26) (оа) та<осто (оа] -асосо Чтобы найти т„т„..., т„, потребуем совпадения нулей полинома У„(8) с нулями полинома Чебышева, которые известны: та=сов я, й=1,2, ...,и. (27) Полипом У„(х) = (1 — т,хП1 — т,х)... (1 — т„х) имеет нули прп ха=1!тв й= 1, 2, ..., и. 530 Гл. х. метОды Решения свточкых Рравнивий— Учитывая связь (22) между х и 1, получаем 2 = ((т, + т,)+ +(тэ — т1)1,)ти откуда следует т, от~+ тг+ (тт — т~)1~), й 1, 2, ..., и. В дальнейшем будем пользоваться обозначениями т," р' 1+3* р' 1+У$ ' ' т+т,' Параметр т„запишем в виде 1+р,у, (29) Итак, параметры т„тц ..., Т„определены. Найдем выражение для у У!Т (1О)), 1 = — 1!рь Так как !ь! ~1, 'то используем для Т„(1;) формулу (25): )Т (1)! 1 1+ 1 1 "+ Преобразуем выражения в скобках 1+1+2'Я 1+ Я 1 — $1 — л р1' 1+1 — 2'Л 1 — т'э — 1+И н, следовательно, (30) .
Чп = 1+ р,"' Таким образом, для схемы (14) с оптимальным набором параметров т„т„..., т„, определяемых по формуле (29), имеем !!Ау„— 11 ( ч„)!Ау, — Я!, (31) где д„определяется по формуле (30). гр," Определим я = в(е) так, чтобы ц» = — ',„: е. Для этого + '," достаточно, чтобы р1 ~ (е/2 или )п (2/е) )п(1/р ) ' (32) е е. дВухслОйные итеРАционные схемы 531 Из разложения функции 1п — = 2х+ — ~ + )хе, 0<х<1 1+е 1/ 1 1 2 ~ (1 ( -)е (1 -)е ) з где 0(х <х, видно, что 1п — )2х, 1п — =1п ' ~ ) 1+е 1 1+1/ 1 е Р 1 И ) 2 Я, н, следовательно, неравенство (32) выполнено при и ) и, (е), п„(е) = = — 1,г — 1п —. (33) 1п(2/е) 1 Г те 2 2~/4 2 у г, е Эта оценка для числа итераций более удобна, чем (32).
4. Схема простой итерации. Формально полагая в (29) и 1, мы получаем метод простой итерации: ~1+1 У» (34) с параметром (35) „(.н,„) 2„ + „(-'а) 2 те + (34') 71 те так как 1, = сое — = О, т, = те. При этом 2О1 д1= = ро 1+ре Для невязки т„= Ау„— ( имеем уравнение у„+1 Яуе, 8 =Š— т,А. Так как Т1 Я, то иа (20) и (35) следует оценка для нормы оператора перехода Щ= ре= —. Вычисляя и ите1-1- 4 ' раций по методу простой итерации, мы найдем те=8"т., 1т.1< ре"Ы. е 1а (1/е) Условие р, ~<е выполнено, если п~ )1 1, что, в свою 1 (~Фе) ' очередь, имеет место при п)п,(е), п,(е) = (36) 5. Модельная вадача. Сравнение методов. Для сравнения рааличных итерационных методов испольэувм раэностную эадачу Дирихле для уравнения Пуассона в квадрате 70 < х, < 1, ' О~хе ей 1) с 11 1, 1, предполагая, что сетка вл квадратная, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
