Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 108
Текст из файла (страница 108)
Система уравненай (7) может быть получена из (6) также умножением обеих частей (6) скзлярььа на вш(хбпь/ь,ь), / = 1,..., М вЂ” 1. Выражение (7] при фиксированном / представляет собой систему линейных алгебраи*юских уравнений с трахдььшоншгьььой матрнцей относительно неизвестных и/(Ьг), ит(26г), ..., и/((/У вЂ” 1)Ьь), которая может быть решена, например, методом прогонки. Таким образом, алгоритм репьения задачи (1) заклшчвеься е следующемь а) находим из (4в) при каждом и,, О < и < /7, коэффициенты уь/(п/я), б) при / = 1,..., М вЂ” 1 решаем методом прогонки систему уравнений (7). В результате получаем функции и (и/ы), У = 1,..., М вЂ” 1; 686 18. Методы решения сеточных эллиптических уравнений в) из формулы (4') при гп = 1,..., М вЂ” 1, и = 1,..., !У вЂ” 1 вычисггяех~ значения функции и(щйм пйз). Оценим затраченное каличеепю арифметических операций Пусть М = 2".
В агом случае, исполщуя алгоритм быстрого двскретного прсобРазовании ФУРье, найдеы все ьг! зз О(М1У !ойг М) аРифметических операцив. При нахождении коэффициентов в потунбугттн О(М!У) опс раций. Наконец, при вычпслении и из (4') с исполгыованиелэ быстрого дискретного преобразования Фурье понадобится О(М)У!ойт М) ош.
раций. Ппэтт~му суммарное количество арифметических операций, необходимых для нахождения решения, в данном глучао по порядку равно О(М!У1ойз М). В частности, при М = !У получаом О(дух 1оМ !У). Рассмотренный и~етод даст решение намного быстрее, чем мшпш Гаусса. ()днако енот ыетод применим линн. в случае, когда исходная область являетгя прямоужнгьникоьц в то врелш как метод Гаусса прнмоним и в слу ше областей общей формы.
В случае прямоугольника существует ряд других ыегодов решения с такой же всимптотикой числа дейпвий. Как уже отмечалось, один из вариантов мар~в-алгоритма с пркомлсмой величиной вычислительной погрепшости решает задачу за О(!У~) арифмгти вских опер щий при !У = М = 2и Расслклрим другие приближенные мечиды решения сис"пмы урашэ. ний (1), донускающие обобщение на сзучай более общих. чем примоугтвп пик, областей. В основу эгнх мшодов положено то свойство системы уравнений (1), ччо рнгузплкг применения матрицы снгчтмы к вектору вычисляется по простым формулам и вг тр~бугш запоминания мазрицы.
Количество арифметических с~пераций, затрачиваемое на вычисление рщулшвчв приыеигпия матрицы к вектору, по порядку равно 0(МЛ'), т. е. пропорционв.ныло длине вектора. Ранее мы упоминалн, что матрица А системы уравнений (1) симметрична и положительно определена и в рассматриваеиол~ случае ш собствепвыс значения Личо 0 < га < М, 6 < и < !У, лежат в пРомежУгкс 4в!пз '— "бл 4в1пх чйс 4созз Я" 4совт х — 'З 2 ' 2 2 2 — -1- .
<Л.,в< т +— !ц Ц Ь! !ь Поэтому дня решения сиглемы уравнений можно применить, например, метод простой итерации в ы1 .! +Ав =!э, и =с, т (8) 2 т=т г= Л,+Л;' где с — вектор начального приближения. Согласно 8 6.6 параметр т це- лесообразно выбрать иэ соотношения Глава 10. Мшады рсаюнвя уравнений в частных аровзвадиых При этом метод (В) сходится со скоростью геометрической прогрессии н показатель скорости схадимости мешда равен Л вЂ” Лш 1 2Лтг При Ь =- >и =- йэ имеем Л, /Л = хэ>л /4+ 0(йл), поэтому ггтйх д = 1 — — + О(Л'). 2 Пусть с — та нюстгм с которой неабхшшлго найти регпение системы уравнений (1).
Нормы погрешностей х" = и — гл" и зв г = и — и" г на соседних слоях связаны соотнопгением Задача 3. Показать, чта нрн т = т,г расчетные форлгулы (В) приобре- тают видг э е„м =-(н, „->-в„,, „->-е„,,юг+ам,)+ — 'рш,. как в случае прямоугольника, твк и в случае произвольной области. Поэтому для выполнения неравенства ()г~() < г))х~)) достаточно выбрать и твк, чтобы выпшпгялось неравенство дв < с.
Отсюда гг)1ггд( > !п(е г]. Так как д = 1-хх>гг/2+О(>лл), та (1пд) = / 1п(1 — хт>гэ/2+О(>л~))! = хз>гэ/2+ О(>г4). При малых Л имеем требювание 2 и > — (п(е ). (9) кз>гэ Так как нас интересует глучай малых с, т.е. когда точность репнвгия системы достаточно высока, то второй член в правой чанги (9) может быть отброшен. Поэтому в данном случае количество итераций и по порядку должно быть равно 0(б э1п(е )). На каждом гпаге итерации матрица умножается на вектор.
Отсюда может возникнуть впечатление о необходимости запоминания матрицы А. На самом деле это не так. Нам необходим лишь ргвультат применения матрицы А к вектору в, который вычнгзгяшгл по формулам 4е„„, — в л㠄— в,„л „вЂ” в„,,тьл — в Ав) >гэ Поэтому лгатрацр А эаааменашь не нада. Д>гя вычисления значения функции (камаоненты вектора) Ав в одной точке требуется конечное число арифметических операций, поэтому на каждом гпвге итерационного метала (В) затрачивается 0(6 э) арифметических операций. Общее количество арифметических операций, необходимых для получения решения с точностью е, таким образам, равно О (>г 4 йл(е л )) = О(>да) Ьлс () .
18. Методы решения сеточных элляпткческю< уравневий 587 В данном случае была описана слепа примевеияя метода орщтой шервции к решению системы сегочвых эллиптических уравнений (1), аппроксимирующих исходную задачу в прямоугольной области; одиако все рассг.л<лел<ш ш<раведлины также и для случая п<юизвольной области, гели сотка выбирается равномерной, а грани*нп<е условия апвроксимируются их <сносом< в блял<айший уз<л сеточкой границы.
Сл<щуат ответить, что при этом, вообще говоря, неизвестны точные границы Л,мчл Л„„„, гпектра матрицы состоим. Зги величины мол<но оценить, например, следующим обрыв<<. Пугп ыгочиый првмоугольиик К' со сторонами 1', и 1~ содержится в Пл, а сеточный прямоугольник К" со гтороиами 1<' и 1<' <ядер>кит Йл.
(узлы К' лвляются узлами йл и уюлл й<, «вляк<тс» узлами К".) Тогда имеет люгго соотношение л',„< л, < л,"„„„ гле Л'„„„минимальное ссбство<люе значение сешчпой задачи Дирихле в яр»- моугольнике К', к Л,"э„. — максимальное < сбствеинос зпачевве с<"и< шой <плачи Дирихлг в прял<оугольнике К", Выбирал г = 21'(Л'э,э Е Л'„'э„), кожно првблн<кенно ивхолить решение си<ямы урашкпий (1) методом орос<ей итерашш с той ж< всишп<ликой числа арифиети колях операцвй. что и в прелыд<чцем случае. Задача ф Показать, что длв гцерлциоппого процесса < ибыпювским вабпром параметров требуемое число операций О(<Л<111пе)).
Задача б. Получить такую же оценку числа действий для оптимального линейного итерапиоивого процесга. Задача б. Получить чакую же оценку числа действий для трех<лобного итерационного процесса (ель З 6.6, задача 3) с фиксироваяпым итсрациоиныы пары<стром ш. Задача 7. Показать, что средняя трудоемкость трехслойного итерационного процесса (см. ч С.С) с фиксированным параметрол< ш может быть сиижепа вдвое за счог сл<щующсго обстоятельства. При иахождевии и при 1 четвом вычислякггси и заломила«птя только зна*п:пия в точках с четной суммой <л + и, а при 1 нечетном — в точюы с печатной суммой <и -1- и.
Заметим, что в случае прямоугольника в ыегодс переменных направлений (21) (если его рассматривать как ичврациопиый метод) можно указать последовательность переменных шагов по времони, цри которой общее число операций будет равно 0(Д<з 1<<1<'1!пг 1). Заметим, что все описываемые выше методы укладывакптя в общую схему решения стационарных уравнений путем уставовления. В частности, двухслойныо «жерациоиные методы можно рассматривать как апщюксимацию уравнения 888 Глава ! О. Машды решевив уравнений е частных ораизвадных а трехслойные — как аппроксимацию уравнения д'и ди — т+у =Ь +(, д1 В случае необходимости решения более сложных стационарных задач дла уравнений ь частнымя произиднымн часто идут по такому пути. Строят нестацпанарный процесс, сходягцийся к решению задачи, а эшен в кюгество итерационного працегта берут дискретную апщюксимацию этого нестациопарного процосса.
Например, в случае уравнения Ли+ 1 =- О один из таких процессов установления описывается уравнением д и они ди —; — + —,— э"у — =- гУи+ 1. дздх дну д1 Задача 8. Дохэзатгь что при определенном соопюпннии между спасами по й т, у гхточная аппроксимация этого уравнения преврашагптя в метод сверхралаксэции для решения сеточного уравнения заи+ 1 = й. В случае, когда область С есть квадрат и )ц = йя = й., указан, итерационный параметр у, ври кагором число итераций для получения решения г точностью е будет порядка — РГ !п(г ).
Эффективными методами решения сеточных эллиптических уравнений являются интенсивно развиваемые в посланное время мазтщ фиктивных компонент и многогеточпый метод. По сути дела они пгкжг укладыва~отся в общую схему построения итерационных методов, н проблема заключаетгя в выбора соответствующоп> персабуславливателя. В ите1ящионном методе фиктивных компонент, предназначенном для решения сеточного уравнения Пуассона в абласля произвольного вида, на каждоы шаге итерационного щюцессэ шобхадимо рошпгь порвуго краевую задачу для уравнения Пуассона в некотаралг прямоугольника, содержащем внутри себя эту обвыть. Если для ращения последней задачи применяется какой-либо из эффективных л1етодов (н;шряыер, марш- алгоритм), та при любом р для получения решения с точпоишю О(йа) погребуагсн О(>~ з(1п8() арифметическях операций.
Метод Федоренко (называемый также лпюгосеточным метадон). К числу наиболее эффективных и употребляемых метадон решения сеючных эллиптических задач (включая краевые задачи для систем уравнений Наны Стокса) относится л~ногогеточный метод, предложевный в шестцлесятые гады. Сначала практн псков использование этого меюда носило эпгшоллческий характер из-за неприспособленности сущыпвававгпего тогда программного обеспечения к использованию методов такого типа. Основная идея атаги метода заключается в следующем. Пусть рыпается сеточная храевал задача Ььиь = (ь. Подбирается некоторый итераци- 18.
Методы решения сеточных эллиптических уравишшй оиный процесс такой, что уже при небольшом чигле итераций обеспечивм.тся определенное сглаживание погрешности. Таким образом, решение исходной задачи сводится к решению задачи с относительно более гладким решением. Решение задачи с гладким решением на соске с шагом 6 близко к решениго задгчи на сетке с более крупным гшзгоы, например с шагоы 26. Предлшастся решить уравнение для погрешности иа более грубой сетке и затем, проинтерпсли1ював иа исходную а:тку, пгшучигь сущеспинно лу.ппсе приближение к ргпюпию. Дпя приб:псжсииого решении задачи на сетке с шагом 26 применяетгл аналогичная процедура с переходом к решению задачи па сетке с ша|ъы 46 и так далек Часто сдпа итершсвя на сетке с пшгом 6 гостоит и дву- или трехкратном приыенсвии описанной процацуры перехода к решению задачи на штко с шагом 26.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
