А.А. Самарский - Теория разностных схем (1989) (1160092), страница 90
Текст из файла (страница 90)
Схема (14) с параметрами т и Ф ть = ть = —, о~ = — сов~~~в (й)), й = 1,2,..., п, рось ' обладает свойством вычислительнок устойчивости. Можно считать, что учет ошибок округления эквивалентен возмущению входных данных, т. е. начального приближения, правой части 6 а двухслонныв итвРАционныв схимы 539 и оператора А итерационной схемы (14). Тогда реальное (вычисленное) решение у„ эадачи (14) можно рассматривать как точное решение следующей задачи: Удед — Уа 1 + 4уд = 1д+д + — дск+д, й = О, 1, 2,..., и, ьд.д т~ + 1 где слагаемое адд+, учитывает погрешность, вносимую в — ую та+д Если пренебречь возмущением оператора А, то промежуточные решения у„ограничены по норме в мди»-~'»-ф-' *и;1»-д,' *%1) , где с = 1, если т Ф 2"; с = О, если т = 2', и для погрешности у„у„— и после и итераций верна оценка 3 у — и 5 ~~ д -~ у, — и ~ + —" шах ~ 7д — ' У $ + — шах $ Ц.
тд д(д<»д 3 Я д<д<дд На выводе этих оценок, выражающих вычислительную устой- Ф чивость итерационного метода с чебышввским набором (тд1, мы останавливаться не будем. В дальнейшем мы всегда будем поль- Ф Ф эоваться только набором параметров (та1, поэтому эначок ч у ть часто будем опускать и писать просто т,. Приведем результаты расчета примера из п. 5 по явной схеме (14) с упорядоченным набором параметров (ть1 В этом Таблица 5 2,1 10 д 11 10д 6,5 10 д 1,5 10д 8,? 10 д 7,2.10-а 540 ГЛ. Х. МЕТОДЫ РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИИ случае ищется решение системы уравнений Р(х, ») —.2Р(х»)+Р(х»+») =О, х»= г)г, г 1, 2, ..., УУ вЂ” 1, уг = 1/Лг, Р(0) = 1, Р(1) = О.
Число уравнений У вЂ” 1=19, в=10 ', и 64 2'. Строится-цепочка О,- О,— О, — О,— О»г- Огг- Ог, с использованием фоРмУл (44). Реэультаты вычислений с начальным приближением у,(0) 1, у,(х,) = О, »~ 0, даны в таблице 5. Из этой таблицы виден немонотонный характер сходвмости итераций. При переходе от итерации.номера У»=4у к итерации номера й+1=4у+1 погрешность Ла=!!уа — у, А воэраставт, а затем, при переходе к й=4у+2, 4)+3, 4)+4, величина Ь„ падает. й 3. Попеременно-треугольным метод 1.
Метод Зейделя. Неявные схемы, как было показано в гл."(У1, более устойчивы по 'сравнению с явными. Простейшей неявной итерационной схемой является метод Зейделя. Рассмотрим систему линейных алгебраических уравнений Аи=у, (1) или ~ аци; = у», г = 1, 2,..., У)У. 1 1 Предполагая, что диагональные элементы матрицы А (ае) отличны от нуля, а,»ФО, напишем следующий итерационный метод (метод Зейделя): я Х ац у»+,Х ацуг = у«а»»чь О, (2) ~1 гэц+1 где у» — итерация номера й.
Определение (й+ 1)-й итерации начинаем с г 1: а+1 и а а11 у1 + Д агууу = ~1 а11ЧЙО. а+1 Отсюда найдем ум Для У= 2 Имеем а+1 а+1 Н а- а,г у, + а„уа + ~~.", ацу; = уг, ааа ЧЬ О. у=а а+1 а+1 Так как значение у, уже известно и агг ча О, то йаходим уа и т. д. $ А. попегвмвнно-тгеугопьнь»й мято»» Представим матрицу А в виде суммы А А-+А++Р, (3) где А =(а»») о»»=ам при У(к, а»»=0 при ))1,— нижняя треугольная матрица с нулями на главной диагонали,4 =(а»»), ам= а»), 7)1, ап = 0 при у ~»,— верхняя треугольная матрица + + с нулями на главной диагонали, Р=(а,»бс), бе 1 при 7», бе = 0 при 7 Ф », — диагональная матрица, Польеуясь этими обовначениями, запишем метод Зейделя в виде А+1 А (А-+ Р) у + А+у = 7, у = (у„у, ..., ул). Приведем эту двухслойную схему к каноническому виду А+1 А А (А-+Р)( у — у)+ (А-+Р+А+) у = 7', (4) или (А — + Р) ( у — у) + Ау = 7.
Сравнив ее с канонической формой (5) а+1 а  — "" + Ау = ~, )» = О, 1, ..., п — 1, еадано любое у ен Ы, (6) та+1 находим В=А +Р, т, 1. Схема неявная, матрица  — треугольная и, следовательно, несимметричная (оператор В Ф Ве— несамосопряженный). Для модельной аадачи (см. $2, (37)~) .
Лу»о ж~юа у)та=О метод Зейделя имеет вид А+1 А+1 А+1 А А у» 1+ у» 1 — 4 у + у» .».1+ у» +1 = — )»а»р» так что А+1 А+1 А А а+1 У»~ 1+ г»а 1+ г»1+1+ У»а+1+а 9 У— (7) Вычисления начинаются с уела 1, = 1, 1, =1. Так как увлы А+1 (О, 1) и (1, 0) лежат на границе, то оначения у», и А+1 А+1 у» 1иевестны и вся правая часть в (7) иавестна. Значение у найдено в увле й='1, »а= 1. Полагаязатем(1 2, 3, ...прий=1, 542 Гл.
х. метОды Решения сеточных уРАВнении А+1 находим у на нижней строке, после чего переходим к строкам А+~ ' й = 2, 3, ... В результате у определяется во всех узлах сетки. В силу основной теоремы 2 из $ 1, п. 2 метод Зейделя сходится, .если А — самосопряженный (матрица А = (ае) симметрична) положительный оператор. В самом деле, воспользуемся для схемы Зейделя достаточным условием (11) сходимости итераций схемы (3') с несамосопряжениым оператором В, которое запишем в виде Во 2 А)0.
(8) Учитывая, что для схемы Зейделя В=А +Р, т=1, находим Вз = — [(А +Р)+(А + Р) ) = — (А +А++ 2Р), так как А+ — (А ) в, Р* = Р > 0 в силу А А* ) 0', получаем т. е. метод Зейделя сходится со скоростью геометрической прогрессии. 2. Метод верхней релаксации. Чтобы ускорить итерационный процесс, видоизменяют метод Зейделя, вводя в (5) итерационпый параметр в так, что (А-+-Р)(у — у)+Ау=1. (9) Этот метод называют методом релаксации. Метод Зейделя соответствует значению в-1.
Если параметр в >1, то итерационный процесс (9) называют методом верхней' релаксации. Сравнивая (9) с (6), видим, что В=А + — Р, та=1, или В вА +Р,т,=в. а+1 Оператор  — ' несамосопряженный'. Алгоритм вычисления у также сводится к обращению нижней треугольной матрицы. ,Если метод Зейделя применим всегда для А Ае)0, то для сходимости метода релаксации нужно дополнительно потребовать, чтобы 0 < в < 2.
Покажем зто. Найдем сначала В, и воспользуемся (8). В даннои случае В вА + Р, т в и В, = '/,((вА +Р) + + (вА++ Р)) = Ч,(вА+ (2 — в)Р). Отсюда видно, что В,) 0 при 0 < в < 2, а условие (8) выполнено при в < 2:  — — А =  — — А = — Р) 0 при в(2.
с в (2 — в) 2 е 2 2 э х попвгвмкнно-тРкугольный мктоп 543 Скорость сходимости эависит от параметра ед. Существуют теоретические оценки для ед и скорости сходнмостн, однако их применение требует энания границ спектра Р '(Л + А+), который не всегда легко найти. Поэтому на практике параметр ю подбирают так, чтобы минимизировать число итераций. Зто особенно удобно, если решается класс однотипных задач.
Для модельной задачи можно показать, что метод верхней релаксации оказывается весьма эффективным и сравним по числу итераций с явным чебышевским методом, так что и ви,(е), и,(е) =О~ — „1п — ). !1 3. Неявные итерационные схемы. В $2 мы исследовали сходимость явных итерационных схем А +Аул = ~, эадано любое у»енН, (10) тл+д где итерация улю непосредственно вычислялась по формуле ул+д ул — тл+1( 4ул 1). Методы Зейделя и верхней релаксации являются примерами неявных схем (6), для которых ВФЕ. При использовании неявного метода для определений новой итерации ул+, надо решить уравнение (11) Вул+д Е», Ел = Вул — тл+д(Аул — )) с иэвестной правой частью Еь В случае метода Зейделя В= =А +Р— треугольная матрица, для метода верхней релаксаг ции В = А + — Р— тоже треугольная матрица.
Поэтому определение ул+, требует минимального числа действий, а для модельной эадачи — число действий, затрачиваемых для определения ул+„ пропорционально числу уэлов сетки. В $ 2 были сформулированы требования, которыми надо руководствоваться при выборе оператора В: 1) минимум числа итераций; 2) экономичность оператора В; для раэностных эллиптических уравнений второго порядка это значит, что решение уравнения Вул+, = Рл при заданной правой части Ел должно быть найдено с эатратой числа действий, пропорционального числу узлов сетки. Основной результат э 2 — оптимальный выбор параметров (т,) — может быть перенесен на неявные схемы с В Ф Е: В "+' А + Аул = ~, й = О, 1, 2, ...,и — 1, тл+1 садако любое у елН.
(6) 544 гл. х. методы Решения сеточных РР»вненнн + Сх» = О, й = О, 1, 2, ..., я — 1,. х, еи Н задано, (14) т»+» где х» В" и», С В-"АВ-". В самом деле, так как  — самосопряженный положительный оператор, В=Ве> О, то существует оператор В" — корень из оператора В, причем (В")е В" >О. Действуя на уравнение (13) оператором В '" и заменяя иъ»=В ех,, получаем (14). Обратный ход рассуждений очевиден.
Л е м м а 1. Нусть даны операторы А=Аз>0, В В*>0, С=В "АВ '". Тогда операторные неравенства т>В< А < (,В, (> > О, (>Е < С<(,Е (15) эквивалентны. Доказательство. Рассмотрим функционал У=ПА'— ТВ)у, у) (Ау, у) — Т(Ву, у) (АВ '(В'у), В "(Внут — Т(В'у, В"у) (Сх, х) —,((х, х) = ИС вЂ” (Е)х, х), где х =В»у. Так как у (и, следовательно, х) — проиавольный вектор из Н, то из равенства 1 ИА — (В)у, у) =ИС вЂ” тЕ)х, х) (16) следует, что операторы А — ТВ и С вЂ” (Е имеют одинаковые знаки. Пусть, например, А — (>В > О.
Полагая в (16) ( = то получаем г = ИС вЂ” "(,Е)х, х) > О, т. е. С > "(,Е и т. д. Лемма доказана. Итог этих рассуждений таков: применение неявной схемы (6) для решейня уравнения Аи =) эквивалентно решению уравнения Будем предполагать, что В-В*>0, А-Ае>0> (>В<А <(»В, (»О. (12) Эти условия определяют исходное семейство итерационных методов (6).
Так как для методов Зейделя и верхней релаксации В Ф В* — несамосопряженный оператор, то они, не принадлежат исходному семейству (6), (12). Для поправки 'ю» =В-'(Ау„— )') имеем однородное уравнение (см.' $2) В»+ " + Аю» = О, й = О, 1, 2,..., и — 1, т»+» юг= В '(Ау — ~) ееН задано. (13) Эта схема эквивалентна явной схеме з з. попнгнминно-тгвтгольныи мктод 545 Сз=ф по явной схеме: ~ +Схь=ф, к=0,1,2, ...,и, задано любое х«ыН, (17) если С=В "АВ ", ф= В "), Поэтому мы можем перенести на случай неявной схемы все результаты; полученные в 3 2 для неявной схемы. Справедлива Т е о р в м а 2. Пусть выполнены условия (12). Тогда существует оптимальный набор параметров (ть), определяемых по Яормулам (27) — (29) из з 2, для решения задачи (6); причем справедлива оценка (18) 11Ау.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
