Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 107
Текст из файла (страница 107)
Так как часго не удается вычислить точное число арифметических операдий лнГю зют подсчот достаточно громоздок, оцснивакп' лишь порядок числа арифметических операций по отношеншо к чиллу узлов сетки. Прежде всего отыетим осгГюнлгостгл рап:матриввемых систем ураввопий. Во-первых, это бсшьшая !эиьгерллоллть (большое число лгевзыетных в сигчеме]. Эта связало с желанием пачучить решение исходной дифференциальной задачи с нужной точностью, по требуот досэвто шо малого шага сетки. Во-вюрых, в каждой строке матрицы лилль конечное число элементов отлично от нуля. В гастпости, в (1) количество непужвых элементов в строке не превосходит пяти.
Все это заставляет разрабатывать специальные эффективные лгетсрьл, учитывшощие особснлошгн систем уравлыэий такого типа. !лвсгэлотриьл прежде всею, что же дает применение классического ьн, года Гаусса к релпепию системы (1). Предположилг, па граничные узлы пскллочепы из системы уравнений. Тогда вектор неизвестных, коэарыми являются значения функции во внутренних узлах, имеет разморность (!У вЂ” 1) . Поэтому прямое применение ыетсда Гаусса к решению системы (1) требует 2/3(!У вЂ” 1) +О(!У~) арифметических операций.
Кроме этого, потробуегся хранить в памяти матрицу системы, т.е. потребуется О(1У ) 4 слов ЭВМ дли хранения элементов матрицы. Заметим, однако, что ббльша» часть арифметических операций являгся несодержательной — это операции над нулевыми злеьлеэлтшли ма- 18. Методы решения се<очных эллиптических уравнений 581 трицы. Выясним, какое потребуется к< чичество арифметических операций, если вычисления проводить тш<ько над ненулевыми элементами.
Напомним, что матрица А системы уравнений (1) прв «естественной» нумерации компове<гг вектора неизвестнь<х (пп, и,э,..., ицл — <, изь ° ° °, ил-< и-<) имеет вид (с точностью до множителя й з) 4п Л<г 0 Аш Лзг Агз Англ! Ал — <,и — т Ль <,л.ч где 4 — ! 0 — 1 4 — 1 О 0 4 — 1 -1 4 а Ль.ь< — диагональные матрицы с элелюнтами па див<опали, равными — 1. Матрицы Ап имеют размерность («Ч — 1) х («Ч — Ц. Таким образом, матрица Л оказывается блочно-трехдиагональвой и в каждой ст1юке матрицы не более пяти элементов отличвы от нуля; кроме этого, матрица А являетсв ленточной < шириной ленты равной (2<Ч вЂ” 1]< все элементы а, = О прн (» — Я > ]Ч.
Задача решения системы (1) является частяым случаем решенив снсшмы и< уравшюий с щ неизвестными Ах =Ь (г] с (2э + 1)-диагональной матрицей. Для решения такой системы могут быть прил<евены, например, месю<»< Гаусса, квадратного корня, отражений и вращений с исключение»< несодержательных операций во всех <жучавх. Г1од исключением и<содержательных авераций имеется в виду следующее. Г1оскольку ай —— - 0 прн )« — у~ > з, то не надо щюводпгь оперш<ий по обнулевию этих элементов. П<нтому производятся операции лишь по обвулени<о 0(тэ) элементов. Кроме тоста ври реализации каждого шага обнуления все элементы ан — — 0 пРи (< — 1] > з остаютсЯ Равными нУлю и п<втомУ каждый шаг требует О(з) арифметических операций.
Такил< образом, общее числа операций при решении системы уравнений (2) окаляваечс»< величиной порядка 0(АР). В данном случае т = (]Ч вЂ” 1]з, а = <Ч вЂ” 1 и поэтому общее числа арифметических операций О(]Ч«). Матрица А симметричнаи и положительно определенная. Как отмечалось ранее, в случае А > О при реал<шанин этих методов не в<нникаст операции дш<ения на нуль. 882 Глава 10. Методы ревения урэшююш в частных праизвакяых Енсе один назлложный метал решения этой' системы — это метод прогонки н блочной форме. Исходную сиплому уравнении записываем н виде Алсщ + Аггпг = Уь Аш пс + Аюпг + .4гзиз = Гг, Ал — г,л — эпл — з+ Ал-гл-.гпн-г 4 Ал-гл.-спи-л =- Гл — г, -4л-ьл-гпл.-г+ Ал-ьл-спн-г = ум-ь где пь — вектор с калшонснтами нь ь щ- г,..., иь н Далее последовательно исключаем нектары неизвестных пс, пг,..., пл-г и получаелл рекуррентныо формулы, аналогичные формулам мсгада прогонки. При реализшгнсл этих формул придется щюизвсптн порядка с1У операций умпожевия и обращения матриц размерности Ф вЂ” 1, чта потребует всего порядка 2с1У~ арифметических операций.
Дополнительно требуется произвести поридка О(1У) операций умножения матрисая на вектор и глажения вскторок, для этапг потребуется 0(бсз) арнфметнчс ских операций. Общие вычишштсльлсыс затраты, таким образолс, гостсвят порцкка 2сФ~ арифметических операций. Описанные выше метсщы непос1хдствснно применимы и гзучае эллиптического уравнения или слгстслсы эллиптических уравнений с произвсльнымн, в частности, леременнылси коэффициентами и во вссх этих случаях требулот 0(Ж~) арифметических операций. В конкретном шсучае системы (2) при Ф = 2с можно предложить метод, требующий 0(Жз1лФ) арифлсетических операций. Дкя эгтяо гзсгдует щлилсснлсть ллетсщ Гаусса в векторной форме при следующем порядке исключения неизвестных: сначала исключакгп:я век'горы нс, и;л, щ,..., т.е.
всс векторы пглль затем векторы пг, пл, пш,..., т.с. все векторы пгщьсц, зателг векторы ни пш, пге,..., зсе. все векторы плщлтц и т.д. Оказывается, что при гаком способе исключения лпииюкратно умножаются и обращаютн одни н те же матрицы. Если влюсто этого запомнить произведении соответствующих матриц, та общее числа операций окажется О(1У~1обФ). Описавные методы требуют в общем случае для запоминания ленты матрицы О(1Уг) слов памяти ЭВМ.
Задача 1. Показать, чта при нумерации неизвестных лць ась аш,"., щ,л-ь нг,н-г,", пн-сд, -, ал-Ьгс — ~ количество арифметических операций в лсетоде Гаусса по порядку также равно 0()У"). Задача 2. Для случая разноспюй апщюксимацни уравнения Лапласа в произвольной двумерной области указать порядок исключевия неизвестных, при катарам решение системы получается за О(Ман) арифметических операций; здесь М вЂ” общее число узлов. 48. Мепгды решения сеточных эллиптических уравнений бйй Рассмигрим прямой метод решения системы уравнений (1), основанный иа использовании дискретного преобразования Фурье в глучюг прямоугольника. Здесь ьгы не будем предполагать, что М = Л.
Преобразуем вначале систему уравнений (1) к операторной форме. Пусть и(тЬ1, п61) — сеточная функции, оггределеинля при О < гл < М, О < и < И, которая ссответствуег решению (1), т. е. и(гл111, пйт) = и„ш. Аналогично, гр(гл161, ггйз) = уг „; узы = угла = грюе = уг и = О сеточная функция, соотвегствуюгдая правой чалги (1). Через Лг обозначим операторы евгг„, — 2е я+и, 1„ Ьэ 1 О 1 < ггг < М вЂ” 1, 1 < гг < Лг — 1, гг,„ягег — 2и „+ сша Тогда система урааневий (1) ьюжет был представлена в операторной форме Аи ю — (Л! 4. Л1) и = уг. [2) Пусть для определенности МЬ! = 1. Заметим, чзо этого всегда можно достичь, умножая обе части (1) на соответствущнй коаффициент.
Функ- ция и как функция переменного ю представнма в виде дискретной сум- мы Фурье по переменной т (см. 4 4.3)1 (4'] Аналогично продставилг уг в виде (4л) г=! (Л!и)„, (Лзе) в оствлыпях случаях; 1<п!<М вЂ” 1, 1<гг<Лг — 1, в осгэльных случаях. и — ! и[тЛ1, п61) = ~ иг(ггйз) в1п(тугп61), 1=1 м-! иу(1161) = 2) Ьги(661, пйз) вш[гг166!). г=! М-1 Чг(гл61, пЬт) = ~ гр [п61) з1п(я!и!61), 1=1 М вЂ” 1 гр (пйя) = 2 2 61гр(661, ггЬз) в1п(к2661).
Глава 10. Методы решеви» уравнений в частных проьпвсиных Подставляя полученные рвзьшжения в (3), получим м — ь — (Ль -1 Лг)и„ы= — ) (и/(п/ж)Ль зььь(хут6ь)-/зьп(х/пьЬь)Лги (пйт)) = т=ь ль — ь йу (пЬг) е/п(т/пь/ьь ). т=ь Напомним, что функции яп(тг/т) являьатгя гобствгтпьыми длв оператора Ль: епь(х/(тп + 1) 6ь ) — 2 еш (тг/тйь ) -/- яп( гт (ш — 1) /й ) Ль вш(тгттлЬ„) = — '— /ь( г куйь 4яв — — — вьп(х/тиль) == — Л.яп(тг/пь/ьь). 2 /г т' Поэтому выражение [6) может быть заменено эквивалептнььм /' 2и.(пйг) — 'в ((и — ЦЬь)-и ((ть+1)/я)) (Л/т(/) Л.и.(пЬг)+ — — 'ь т — — зш(т/тл1О) = 6 г (6) лг-ь )' уь (пйг)яп(т/тйь) ° Функции зш(хутьь/ьь), т = 1,..., М вЂ” 1, являвтгся лярном произведении артоговальными в ска- м-ь (а, ш) = ~ /ьье,тьа. =ь Поэтому (6) представляет собой систему ншавнсимых уравнений 2и/(п/ь) — т(( — 1)/г) — иь(( -~1)/я) Л в (пЬг) + — ' 1 < и < Л/ — 1; ит(О) — ит(6//я) = О, 1 = 1,..., М вЂ” 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
