Samarskij A.A. Vvedenie v chislennye metody (ru)(400dpi)(T) (969542), страница 33
Текст из файла (страница 33)
Обычно берут Ло Л', — 50 — 100, так что число уравнений в системе (1) равно 10' — 10'. Решение систем столь высокого порядка методом Гаусса потребовало бы числа действий порядка (Л',— 1)'(Лгг — 1)', т, е, 10' — 10" действий, если бы у системы (1) пе было одного хорошего качества: матрица системы является слабо заполненной и имеет лишь -5Лг,Лг, отличных от пуля элементов.
Поэтому для решеняя системы раэностных уравнений удаатся построить методы, требующие 0(Лг )и Лг) и даже 0(У) депствий, где Ж = (Лг, — 1)(Лг, — 1), Опкшем один пз прямых методов репгения разпостной задачи Дирихле уравнения Пуассона в прямоугольнике. Перепнпгем задачу (1) в вгтде Лу = у-„, „+у-,, == — гр(х), хя егы у(„„= О, (2) где у(х) — у(х) прп х ш гш„а гр(х) определяется по фор- мулам (14) пз 1 1. гл.
ть аллиптичхскнн »ч»внвния 222 Ее регпе)гпе можно найти методом раэделегп)я переменных. Пусть (с»2) (х»), Х»',,~) (12 = 1, 2,...1 Л㻠— 1) — собственные функции и собственные впачепия задачи Лди-'гРю=0, х)над', п(0) с((1) О. (3) Выражения для 4,, и г»2 (х,) даны в и. б, 2 1.
< 2) (2) 2 1'азлоягим реьчеипе у(х„х2) и правую часть )р(х„х,) по собственным функциям 1)г», ) ' ~2] К»-1 р(х„х.) =-, с), (х,) г), (х»), ~1 Д. =-1 Л»-1 )г (х) х») -= ~ Ч1»2(х,) п»,(Х»), ».,=! где х,„=1„))„, ) =1, 2, ..., Л вЂ” 1, и=1, 2, сд,,(х,) и Ч)»2(х,) — коэффициенты Фурье, например, Л» — 1 )Г»,, (Х,) = ~ ))ВР (Х„)2)12) Сд„()'.)12). Применим оператор Л Л, + Л, к произведению С».1»,: Лед, (х») ид, (х») =- 1» (х,) Л,с» (х.,) + сд (х)) Л»1)» (х.) =- <2) сд (х2) Л1с», (х1) 2»~ сд (х1) у» (Х2) =- 1(Л)сд (х)) — 2,)~~с» (х))~ сд, (х ).
Подставляя эатем это выражение в (2) и учитывая (5), получим Л» 1 (Л)сд (х,) — )»12)с» (х,) + <рд (х))3 и» (х») = О. (6) »1=1 В силу ортогональности (и»2 (х»)) это тождество возможно только при равенстве нулю выражения в фигурных скобках: Л)с»2(х,) — )»»с»2 (х,) = — )р»2(х1), гс» =- 1, 2,..., У» — 1, Г») х1 — — 11)111 0~11(У1, сд (1 Ь1) = О, 1 =- О, Уп (7) $2.
Решенкк Рханостных г'Равнении а2З В самом деле, угшожая (6) скалярно на гг, (х,), имеем мг г гт -г О= ~~~ ('Ь(иьггьг) = ~х~ ~( 1ьбыг = ( )ьг = О, ь г А=г где ( )»г — содержимое фигурной съобки (6). Задачи (7) решаются методом прогонки; всего требуется .'тг — 1 раз использовать алгоритм прогонки для й,= =1, 2, ..., йгг — 1.
Зная сг,(хг), найдем по формуле (4) решение задачи (2). Для этого надо сначала вычислить козффициенты Фурье г)гь (х,) (й,=:1,2,...гд'г — 1) Из формул (4) и (5) видно, что у(х„х,) и ~рг,(х,) вычисляются по формулам одного и того же вида: Ж-г Ьлг и;= т„агз(п —,, г= 1,2,...,Дг — 1. (8) г=г Разработан специальный алгоритм быстрого преобразования Фурье для вычисления сумм, который позволяет вычислить сумму (8) за 5%1оиг)т' арифметических действий (при %=2", п — целое число) вместо 0()Уг) при обычном способе суммирования. Этот алгоритм позволяет найтп решеш|е исходной задачи (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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
