А.А. Самарский - Введение в численные методы (1113832), страница 34
Текст из файла (страница 34)
Этот алгоритм позволяет найтп решеш|е исходной задачи (2) за 0(Р(~Мг1оягФг) действий. Метод разделения переменных моя'но комбинировать с методом редукции нли декомпозиции, являющимся модификацией метода Гаусса. В результате получим алгоритм с числом действий 0~5)У,У,1ойг)тг, что в два раза меньше, чем для алгоритма разделения, приведенного выше. 2. Итерационные методы, Для решения разностной задачи Дпрнхле для уравнения Пуассона в прямоугольвике наиболее зкономичнымн являются прямые методы. В настоящее время пмеготся стандартные программы на алгоритмических языках фортран и алгол для решения уравнений Пуассона в прямоугольнике с краевыми условиями трех тинов, а также со смешанными краевыми условнямн. Однако в случае, когда область не является прямоугольником нл~ рассматриваются уравнения с переменными коэффициентами, применяются итерационные методы.
Фактически прямые методы экономичны лишь в случае, когда переменные разделяются. В гл. П1 рассмарпвалась теория итерационных методов для уравнения 224 гл. гь эллнпткческие уРАвнегшя где А =А*=.О. Сравнеяпе различных методов проводилось для модельной одномерной задачи на отрезке 0<в(1: у„-,„=- — )'(х), х =- Уц Ос. ((Лг,. у =ум =-О. Для нее оператор А имеет впд Ау = — у-„„, Грашгцы оператора А опредетяются постояннымя 4 .
яь 4, яй 6 =- —,е)пе —.' Л =- —. созз —, Ьа 2' !з' Число итераций для рассмотренных в гл. 111 методов за- висит от отношении 6 зкв кв Л 2 4 Рассьштрпм теперь в качестве модельной двумерную задачу Дкрпхле в единичном квадрате (), = )г = 1) на квадратной сетке с шагом Ь = — Ь, = Ьг.. Ау =- — у-, — у- =- гр, <(,у~ П. (10) Число интервалов по каждому нз направлений равно Х, так что Ь = 1/Х Границы 6 и Л оператора А найдены в 2 1 (см. (18) нз $1), отношение 0=6!Л совпадает с (9). Отсюда следует, что число итераций ве зависит от числа измерений (если Ь, чьЬ., й М(ь то слабо зависит), Поэтому те оценки числа пторацпн различных ~гтерзцпоппых мотодов, которые мы получилп для одномерной моделышй задачи, справедливы и для двумерного случая.
В случае неквадратной сетка число итераций для двумерной задачи мо'кет несколько отличаться от числа итераций для одяомерпой задачи. Мы рассмотрим здесь лишь попеременно-треугольный ггтерацнопкый метод для ренгеппя ревностной задачи Дпрнхле (10). 3.
Попеременно-треугольный метод. Для решения операторного уравнения Аи=/, А=Аз)0, А: Н Л, (!1) в гл, )П рассматрпвалпсь двуслойные одношаговые птерацпопые методы, которые заппсывалпсь в следующеп 3 3. Ргшгние Разностньгх РРавнкнии 225 капоппческой форме: В Уаз1 Р» +А у таа1 й = О, 1» ..., и, для всех да~в, (12) где В: В- В, В=ва)0.
Для Л и В выполнены условия 7В А 7В, 7~0, (13) гпе 7ь 7» — постоаппые. Минимальное число птерацпй ш(пв(з) прк заданных (1») 7„7, достпгается прп выборе чебышевскнх параметров та 2 ! — з т» ,Ро» т у " ! —,й т й — -1,2,...,!1, (14) В = э + а»Л,) 1) о В + ШЛ»), (!5) где А, и Л» — операторы с треугольпымн матрицами А', — А.„ Л, -'†, А, == А, а В =..Оз ) 0 — произвольный оператор, получаем попеременно-треугольный метод. Обычно В =(И»1!1) — днагопальпая матрица. В гл.
1П дана теория этого метода и найдены постоянные 7„7» и а» прп заданных условнях Л з б»0, А»ь» ~А»~( 4 Л, б) О, Л) 6) О, (16) которые мол!по записать з эквивалентном виде: (,4д, д) ) б (Вд, д), (В-'Лад, Л,д) ~ ~— ' (Ад, д). В этом случае имеем 2'Р»! с (17) а» = = 1/бз' 4 —. Ъ' »! ' гле о„прпнадлежпт пекоторому специально упорядоченному множеству пулей полкиома Чебышева; прн таком упорядочении метод (12) является вычнслптельно устончизым. Д!»я определения (й+1)-й птерации имеем уравнение Вд», =-!"», Г» = Вд» вЂ” т»а,(Ад, — !). 11исло лействпй прн вычислекпн д„„, завпснт от В. Вы- бирая 226 гл. г!. оллпптнческие гвдвнення а для числа итераций верна оцепка и (е) пд (е) =, !и —.
2 (18) з' 4. Попеременно-треугольный метод для разностной задачи Дирихле. Обратимся к задаче (10). Оператор А представим в виде суммы А = А, +А„где ((- ах( х» Ех( Ухд А,у= — + — ', А,у ю —— д Ь( Д п положим Р Е. Сопряженность А, и А,; А,=А, устанавливается сравнением их матриц нли с помощью первой разпостной формулы Грина: (А,У, и) = (У А(о) = — (у, Аде). Для определения у,„, получаем уравнение Вуде, = (Е+ аА1) (Е+ е)Ад)уд»1 = Гд, а х Ед = ВУ» + т»11(ЛУ» + (Р) (Уд=)(, Уд = 0 пРи х ~ У„).
Значения у»», находятся последовательно пз уравнения (Е+ юА()У»п *= Ед, (Е+ е)А»)Уи( = Уд"' Отсюда получаем формулы '1 ' '1) ы (» дд' д', 1 о У»(-1((1. (1)- ! а О( х(е», 1 (1, + 1, 1 ) + х а», ((,, ( + 1) 1.,1 (1) (( (! -(-х — х) Чтобы определить У» (1„11), выбираем узел 1, = 1, й =- '(1) 1 в левом углу прямоугольника; тогда остальные два узла (1, — 1, 1,) и (1„1',— 1) шаблона 1((о 1',), ((, — 1, (1), о О„(1 — 1)) лея(ат па границе и, следовательно, у"'(1,— о. о( ) -1, й) = У")((„11 — 1) 0 иавестиы, Зная Уд прк 1': = 1, 1,-1, последовательно находим у»' при 1,=2, 3, ... '(1) ..., 11', — ! и ( 1 (на первой строке).
Далее, полагаем 227 3 3. Ргшенив Рлзностных ггавнении (, = 2 и находим последовательно ул па второй строке прп ' (л) о (л = 1, 2, ..., Ж вЂ” 1, Для определения у,+, проводим вычисления на шаблоне (((о (л), ((,+1, (л), ((о (л+1)) по столбцам сверху вниз: фиксируем 0 =№ — 1, № — 2, ... ..., 2, 1, и при каждом (, меняем 0 =6(л — 1, № — 2, ...
О ..., 2, !. Начинаем счет усы с узла ((, № — (, (л = 6(л — 1) в верхнем правом углу. Следует отметить, что о счет ул+, можно таки(е вести по строкам справа налево: фиксируем 1, № — 1, № — 2, ..., 2, 1 н при каждом (л меняем (~ =(л('( — 1, № — 2, ..., 2, 1. Впрочем, вычисление л(П ул можно вести пе по строкам, а по столбцам сниау вверх. Это видно из самих формул. Вычисления ведутся по рекуррентным формулам (19); счет, очевидно, устойчив.
Алгоритм подобного типа, как уже отмечалось, называют алгоритмам бггуи(гго счета. Подсчитаем число арифметических действий на один узел сетки: вычисление Е, требует 10 операций сложения и 10 операций унион ения; вычисление у,л, при заданном Ел требует 4 операции ело>кения и 0 операций умножения. Итого требуется для определения у,„, в одном узле провести 14 операций сложения к 16 операций умножения, Число действий можно уменьшитзч если хранить в оперативной памяти ке одну, а две последовательности (у,) и (ш,+,) и для определенпя ул+, пользоваться алгоритмом ч (Е+ (оА~)илю(л = ЛУл+ (, (Е+ (гАл)и(лл( = юлл((л о Улл~ Ул + тл+((гл+ь В этом случае для перехода от у, к у,+, достаточно 10 операций сложений и 10 операций умножения па один узел.
5. Выбор параметров попеременно-треугольного метода для разностной аадачи Дирнхле. Чтобы воспольаоваться общей теорией гл, 111 (см. з 5 гл, 1П), пало найти постоянные 6 и Л, входящие в условие (16), В нашем случае А А, + А, ~ 6Е, где 6 — наименьшее собственное значение оператора А, равное 6 = 4 —, з(пг —, + — зшг 'г / 1 . аа! 1, кв (20) л З(л 228 Гл у|. эллиптичкскик угавнкния Рассмотрпы оператор А10-'А, = А,Л,.
Учитывая, что А, =- ЛЕ,(а,Ь, — , 'аузз)за-. (а('+ аз) (Ь' ,— ' Ь.',), находим (А,А.,у, у) — (А,у, Аву) = - (( †„ Е., -~ †, и.,), Е) С < †., Š†Š) ((Е )' 4. (Е. Г, О) ~ ~ | ? С | 2 ~ !~ ~ ~ ~ ~ ~ ~1 ~~ ~ ~ ~ ~ ~ ~ ~ ~| ~~ ~ ~ ~ ~ ~ ~ ~ ~ ! | ~ ~ | 2 ~~ ~ ~~ е ~ т ~ ~ й 1 ~ в К, †1. — 1 = — '+ — '„~ У ((у,.) +(у„,)е].. Ь1)11» /1, 1)) '= ~ —. + — ) ( у, у), < ь' КЕ) 1 11 так как (см. $ 1 гл. У) ЯЕ-) (Лусу) =: Х йа Х (уе,),';,6 + Х Ь Х (у.',)';„)11 — (г=а — 11=О Сравнивая неравенства (А,Аеу, у) » (—, —; —, (Лу, у) в Л)ЛЕ»» — ' Л, е'1 1 л закл)очаги, что Л ==- 4 (21) Зная б и аь находим 1) = б/(1 и по формулам 2 5 гл.
У находим параметры 1„11, с, после чего оцениваем число итераций по формуле 2 ( 1 1 — )/" п(е) 1и — (1и —, р, —.— Е )( Ог Пользуясь л(с), выбираем устойчивый иаоор чебышевскпх паРаметРов а„ т,ы и е) = 2/УГА. Приведем результат сравнения методов решения по числу итераций п„(е); метода простой итерации(л, (е)), (1) явкой схемы с чебышевским набором (л, (е)) и попе- (1) ремекно-треугольного метода (пе (е)) для двумерной по(з) дельной аадачи (10), пользуясь приближенными формулами п(11) (с) 2,'Ье, л(зе) (е) 3,2'Ь,.лоз (е) 2 ()'' )/)1 при е = 10' (табл. 2).
З Х РЕШЕНИЕ РАЗНОСТНЫХ УРАВНЕНИЙ Табл ада 2 "о(') (1) а(Е)(е) ес (е) (3) ()'(О ()50 (НОО 32 (60 220 О 2( 29 200 5 000 20 ООО где с, и се — постоянные. Прн Ь, — = Ь =— 1 получаем уран- пеппе Пуассона Ли = — 1. Разностпая схема строится па сетке ые = (х, = = ()ЬЬо 11Ь1))' 1„= О, 1, ..., Л)„, Ь, = („1Л)„, а = 1, 2). Каждый оператор 1.„заменяем па трехточечном шаблоне (х„— Ь„, ха, х„+ Ь„) разпостпъ(п оператором: где, и(х") — -- и((1, ~ 1) Ь„(еЬ ), и(' е) .—.. и (1)Ь„((ел. 1) Ье). Для а, и ае можно выбрать простейшие выражения ( 1 ! а)(х,. хе) —. 1(, (х, — 1'2Ь„хе) = Ь( ( — 1,''1 ) ае (х„хе) = Ье (х„хе — 1,'2Ье) = Ье обеспечивающие второй порядок аппроксимации; Л,и — 1.„и = О (Ьй).
() результате оператору сп ставится в соответствие раз- ностный оператор ва пятиточечном шаблоне: Ли = Л(и .(- Леи =- (л(и- ) - (пеи- ) 6. Равностные уравнения с переменными коэффициен- тами, Пусть требуется н прямоугольнике (' =((х„х,): О ( х (1, и=1, 2) решить задачу Дприхле для аллип- тического уравнения с переменными коаффпциептами: 1 л =- 1,(и + 1,. и = — 1 (х), х = (х„х.) ен (1, и == р (х), х еа Г, (22) 1 аи = — ((1е'а (х) — „.' " ). О< с, »<)(а(х) »» с), а=-1, 2, 220 ГЛ. ГХ ЭЛЛИПТИЧЕСКИЕ УРАВНЕНИЯ Напишем разноствую схему Ау= — 1(х), з ыа, у=)А(х), зш (а, 0(с,<а ~са, а=1, 2, (23) соответствующую задаче (22).
Введем в пространстве сеточных фушщпй В йх оператор Лу= — Лу, А=А,+Л,, а о А,у = — Л,у, А,у = — Л,у и запишем (23) в операторной форме: Ау=у, у, сршН, Оператор А, очевидно, является самосопряжепным: (Лу, и) = (у, Ли). Из формулы Х,-1 и, — 1' М.,).. Оу "' =- 4 (" (у.—,)'),й н неравенства 0 ( с, -= а ( са следует, что с,(Лу, у) = (Лу, у) -= гх(Лу, у) плн сгЛ ( Л а С,Л, (24) где Л есть изученный выше опоратор Лапласа а Лу = — — у- — ух1хт хеху (25) Отсюда заключаем, что о с,6Е ( А ~ схЬЕ, а а где 6 и й определяются формулами (20), (21). Для решения задачи (23) можно воспользоваться по- переменно-треугольным методом с оператором В=(Е+ыЛ~)(Е+ыЛЕ), Л,+Л~= — Л, Л, =Л, при В =- Е. а В етом случае имеем у,В ~ А < уаВ, где у, = с~ум уз = о о =- стус, а постоянные у, и у, найдены для оператора где ~р отличается от 1 только в 4 приграничных узлах (0 =1, Ю~ — 1, 0~(х~Жх) н (О~ВАЛ'о (х-1, )Уа — 1) в х Рзшение Рлзностных углвнкння 231 (25), Для шола итераций имеем оценку / 1 2 пв (с) ж 1/ — 'лв(е), п„(е) =, )п —.
2 2гч Для уравнения с переменными коэффициентами требуется в )'с,/с, раз больше итераций, чем для уравнения Пуассона, Таблица 3 л= пвз л= шзв а, с, П = Воел о=к э =воок 39 47 53 57 59 20 23 25 26 23 46 92 184 367 45 90 180 360 720 2 8 32 128 512 Однако мошно не вводить оператор Л, соответствующнн оператору Лапласа, а сразу представить оператор с переменпымн коэффициентами в виде А = А, + А„ Оператор В выбирается в форме В = (Р+ ыА,)Р '(Р + вАл), (26) где Р=И(з)Š— диагональная матрица, Для применения обгцей теории надо найти постоянные 6 и Ь, входящие в условия А~)6Р,АлР 'Ав~( 4 А Коэффициент л((л) вы- А бирается из условия максимума отношеяия в) = 6/Л, и, следовательно, макспмУма 6 7~/Тм В РезУльтате полУ- чается алгоритм, у которого число итераций и,(е) слабо зависит от отношения с,/с,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
