Самарский - Введение в теорию разностных схем (947501), страница 74
Текст из файла (страница 74)
Параметр то+~ можно рассматривать как шаг (переменный оо! в общем случае) по фиктивному времени 1о„, = ~ т,. о=~ Обычно задается некоторая точность в > О, с которой надо найти приближенное решение задачи (4). Если 11и11 1, то требуется, чтобы выполнялось условие 11уо — и 11»(е при й>и(в). (9) Здесь п(е) — минимальное число итераций, гарантирующих заданную точность е. (Условие 11и11= 1 может быть выполнено после перенормировки и и 7 путем введения масштабного множителя.
Пусть, например, Н вЂ” гильбертово пространство, Л =А'>О, тогда 11и11л=11Йл-ь Если 11Г11л-~ =Мо. то, полагая и = Мой, 7" = М«7, получим для й уравнение Ай = 7 с 1й1(л = Е) 4 с Р»зностн»я э»д»ч» дияихлв 453 Так как точное решение и неизвестно, то условие (9) неудобно для практической проверки.
Его можно заменить одним из условий (! О) (11) где (Ау» — 1) — невязка в уравнении (4) при подстановке д» вместо и. Если при некотором й выполнено одно из условий (!О) или (11), то считается, что требуемая точность достигнута, и вычисление последующих приближений прекращается. В (9)— (! 1) могут фигурировать, вообще говоря, разные е. В общем случае в качестве меры сходимости итераций принимается отношение !!у» — иЦ!(у» — и!! и т. д., так что например, требования (9) и (!1) заменяются требованием !! у» — и !! < е (! у» — и !! или !! Ау» — ) !! < е !! Ау» — г!!.
Уравнению (4) можно поставить в соответствие большое число итерационных схем (6) с любыми В» и т». Как следует выбирать В» и т»? Качество итерационной схемы характеризуется, прежде всего, числом Я(е) действий, которые надо произвести, чтобы получить решение задачи (4) с заданной точностью е) 0 при любом выборе начального приближения у». Оператор В» и параметры т» надо выбирать так, чтобы число действий Я было минимальным (в некотором смысле).
» м) Общий объем вычислений Я(е) равен Я(е) = ~ д», где д»вЂ” »-1 число действий для вычисления итерации номера й, или С?(е) = = дп(е), где 9 — среднее число действий для одной итерации. Если д удовлетворяет требованию экономичности (например, д = О(М), где Л' — число узлов сетки гл» в случае разностного эллиптического уравнения), то задача о минимуме Я(е) сводится к задаче о минимуме числа итераций и(е).
Запишем (6) в виде В»у»+, = В»у» + т»+, () — Ау»). (12) Отсюда видно, что д» зависит только от вида В». Укажем типичные формы экономичных операторов: !) В» = Š— единичный оператор (явная схема (6)), 2) В» — треугольный оператор (с треугольной матрицей), 3) В» — факторизованный оператор вида В» ° В»~~ ... В~»~, где В», а 1, 2, ..., р — экономичные операторы.
(м Вообще В» следует выбирать так, чтобы соответствующая с~в~а для уравнения папаболнчрскргр тищ нр??н?гась рдмр- МИЧЮОЙ. гл. шц. итзгдционнын мьтоды 454 Мы остановимся подробно на итерационных схемах для разиостной задачи Дирихле. 2. Схема простой итерации (явная схема). Рассмотрим задачу Дирихле в прямоугольнике оо = (О (х„(1, а = 1, 2): Ли= — 1(х), х=(х„х,)ен 6, и1,=р(х).
(13) Соответствуюшая разностная задача Дирихле имеет вид Ло = — 1(х), хе= вд, о ~ = р(х), Л=Л +Ля Лад=ух к ' (14) где вл=(х,=(1йо 1йо), 1,=0, 1, ..., Ф„а=!, 2) — сетка с шагами й, и й,, уд — граница сетки. Задача (14) подробно исследована в гл. 1»1, $ 1. Простейшей двухслойной итерационной схемой является явная схема (метод Якоби) с постоянным параметром: " = Лдл+ ~(х), хы вл д»! = р(х), до= до(х), (1б) й = О, 1, ... Так как д»ы определяется по явной формуле д»», = уд + + т(Лдд+1) и у» = 0(Ж), то число итераций зависит только от параметра т, который выбирается из условия минимума числа итераций (такая задача решается точно). Чтобы найти т, рассмотрим устойчивость по начальным данным однородного уравнения с однородными граничными условиями и произвольными начальными данными »+' » =Лг, гл, хывл, й=О, 1, ..., (16) г, = го (х) = уо (х) — и (х).
г»! =О, тл Пусть Н вЂ” пространство сеточных функций, заданных на вл и обращаюшихся в нуль на границе ул, (,) — скалярное произведение: №-! №-! (о, га)= х.'4 ~о(1~й, 1ойо)оа(1~йо 1»йо)йА, и ! А = — Л вЂ” линейный оператор, заданный иа Н. В гл. 1»1, $2 было показано, что А является линейным само- сопряженным операгором, А = А', и ЬИгй»~((Аг, г)~ЬЦгй», [17) $ !. Разности»я задача днгнхлв где б= 4рз!п — + — з1п — ), ! ' а о!Ь! 1 ° о о!Ь2 ~! Ь! 21 Ьо~ 21» ) 2 па! 1 2 ооЬ! й= 4 — осоз — + —,соз ! Ь~! 21, Ь! 21» ) (!3) Решая (19) относительно гааь получим гае! = 5га, 5=Š— тЛ, (20) где 5 — оператор перехода. Из (20) находим га Таг„Т» 5», (2! ) где Т,— разрешающий оператор. Оценим Цг»Ц.
ЦгаЦ»ЦГаЦЦгоЦ=Ц5Ц Цгой (22) так как Ц5»Ц=Ц5Ц», поскольку 5 = 5' (см. гл. !, Ц 3). Итерации сходятся, если Ц5Ц <!. Требование ЦгаЦ < е ЦгоЦ будет, как видно из (22), выполнено, если ЦЯ» < е, т. е. 1и (1/е) !~т'плГлг! (23) Величина !п(1/Ц5Ц) обычно называется скоростью сходимости итераций. Чем меньше Ц5Ц, тем меньше п(е) (тем больше скорость сходимости). ЦЯ зависит от т. Выберем т из условия минимума Ц5Ц. Так как 5 = 5*, то ЦВЦ равна модулю наибольшего собственного значения Гаа = Гаа(5) оператора 5: Ц5Ц= шах! Гаа !. ' (24) Из определения 5 (20) следует, что )аа 1 — тХ», где Х»=Х»(А)— собственное значение оператора А.
В результате мы приходим к следующей задаче минимакса: найти то значение параметра т, при котором достигается пни гпах ! 1 — тХ» !, где О <,б< »Г»а < б. (25) о>о а Здесь б — наименьшее, б — наибольшее собственные значения оператора А, так что б <)» <Л, Ь=Г, 2, ..., (ЬГ! — 1) Х(№ — 1), !.а — собственное значение номера Ь оператора А. Оценка (17) является точной. Задача (!6) зквивалентна операторному уравнению а»! а +Лг»=0, Й=О, 1, ..., го — любой вектор из Н. (!9) 458 гл, чи!. итвяхционныв методы (30) Функция /(Л) = ! ! — тХ(, очевидно, достигает максимума либо при Х = 6, либо при Х = Л: гпах ! 1 — т7 !=и!ах(! 1 — т61, ! 1 — тЛ !). (28) з~г~а Л е м м а 1. Если 0 < 6 < Л < Л, т ) О, то в †2 гп!и гпах !1 — тХ! = =рг при т=т,= .
(27) т > о г ~ !д М Л+6 6+а' Доказательство. Рассмотрим функции !р! (т) = ~ ! — тб( и !рг(т) =(! — тЛ!. Они изображены на рис. 20, !р!(т) убывает при 0 < т < 1/6 и возрастает рт при т) !/6; !рг(т) убывает при 1 0 < т < !/Л и возрастает при т) !/Л. Так как Л ) 6, то кри- 5( /=у— вые !р,(т) и !рг(т) пересекаются в точке т = то е= (1/Л, !/6), при- У чем ср!(то) = 1 — тоб, !рг(то) = с Я(т/=!1-тЮ! = тгЛ вЂ” !. Приравнивая эти выражения: ! — тоб = тоЛ вЂ” 1, ! ! находим ! то = 2/(6 + Л), Рг= ! — тоб= тгЛ Рис. 20. = (Л вЂ” 6)/(Л + 6) .
Из рисунка 20 видно, что в точке тг достигается минимум функции !р(т) = гпах((! — тб), ) ! — тЛ)». Тем самым найдено оптимальное значение т = тм при котором р(т) =~~5(т)~! имеет минимум, так что 11 за ~~ » «ро1хо3 при т = то = 2/(Л+6). (28) Подставляя сюда вместо 6 и Л их значения (18), находим лг! г ! г 2(л',+л,') ' В случае квадратной сетки, т. е. при Ь, = Ьг = Ь, имеем тг = Ьг/4. Схема (15) принимает вид у = — (у(, "+ рЛ "!+ у~+!'!+ р!+"!)+ — /, у „, ~ =р(х).
(29) Подсчитаем число итераций, достаточное для достижения точности е. Для простоты предположим, что !, = !г- 1, тогда 6 — згп —, Л= — соз —. Формула (27) дает 8 . г ЯЛ 8 г ЯЛ Лг 2 ! Лг 2 г-гк'!юа 3 01 ) 18~ (~Л/2) и (в) ~) з !. ялзностнля злдлчл дияихлв 457 Оценим асимптотический порядок для числа итераций при И- О: ро ж 1 — 213г(пИ/2) 1 — 0,5п'И' !п(1/рз) = О блейзом 2 !и (!/е) п(е) ) т.
е. число итераций пропорционально числу узлов сетки и яв- ляется величиной 0(И 1п(1/е)). Так как 4=0(Лг)=0(И '), то общее число действий О= 0(И 1п(!/е)). Погрешность в определении решения задачи Дирихле (13) есть сумма погрешности О(/г') самой разностной схемы (14) и погрешности е итерационной схемы. Естественно требовать, что- бы эти погрешности были величинами одного порядка, т.
е. е = 0(Иг). Тогда!п(1/в) = 0(!ий !) и О= 0(И !и И !). В настоящее время имеются методы, которые обеспечивают точность е: а) для прямоугольника с числом итераций п(е) = = 0(!и И (п(1/е))(пропорционально логарифму числа узлов сет- ки агг) и общим числом действий О= 0(И '1пИ '!п(1/з)) (про- дольно-поперечная схема или неявный метод переменных на- правлений), б) для областей более сложной формы и уравнений с пере- менными коэффициентами п(е) = 0(И г!п(!/е)), О= 0(И г!и(!/е)).
Сравнение с такими методами показывает, что метод простой итерации является слишком трудоемким (неэкономичным). В основе построения схем а) и б) лежит следующий прин- цип: итерационная схема, трактуемая как разностная схема для уравнения теплопроводности (1), должна быть экономичной. Тогда задача теории сводится к выбору итерационных парамет- ров из условия минимума числа итераций (минимума нормы разрешающего оператора Т„). 3.
Неявный метод переменных направлений (продольно-по- перечная схема). Рассмотрим задачу (!4), В качестве итера- ционной схемы возьмем продольно-поперечную схему с перемен- ным шагом по времени для уравнения теплопроводности (1): , гга а! = Лгу!+'6+ Лгу/+ /(х), х ен ег„, у!+У ! р(х), (31) т!'+г /+г /+Уз = Лгр!+т +Л У/"г+/(х), х ен егы У/+! ! =(г(х), (32) т/„г .а где / = О, 1, ..., да = иа(х) и уяьгп — промежуточное значение (подитерация), а иа(х) — произвольное начальное приближение, Гл. у!и, итеР»циоиные метОды у/+У вЂ” ти! Л,у/+У =р/ /+ ! и по столбцам уравнений вида у'+' — '" Л у'+' = у"'*.
— т/!.! 2У Таким образом, вычислительный алгоритм тот же, что и в случае уравнения теплопроводности. Для вычисления одной итерации требуется д = 0(Л/) = = 0(1!62) арифметических действий. Ускорение сходимости итераций, по сравнению с явной схемой, достигается за счет соответствующего выбора параметров (т!/!!) и (т!/2!). Каждое из уравнений (31) и (32) аппроксимирует задачу (14) точно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
