Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 62
Текст из файла (страница 62)
Какому типу методов отдать предпочтение в конкретной ситуации, зависит от целого ряда обстоятельств, таких, как характеристики используемой ЭВМ, вид уравнений, требуемая точность решения и т.д. Тем ие менее можно сказать, что при решении трехмерных эллиптических уравнений итерационные методы обычно оказываются эффективнее прямых, а для нелинейных уравнений использование итерационных методов является неизбежностью. Давайте рассмотрим линейную систему Ах = Ь, не делая на этот раз никаких предположений относительно А, за исключением того, что адФО, 1=1,...,п, (8.4.1) т.е. диагональные элементы должны быть отличны от нуля. Вероятно, самой простой итерационной процедурой является метод Якоби.
Пусть в качестве начального приближения к решению выбран вектор хо . Определим следующее приближение по формулам (1) 1 (о) х; = — (Ьз — Х а;,.т, ), 1=1,...,и. (8.4.2) ал )~ю Полезно представить эти соотношения в матричной форме. Для этого положим а~~ азг О (8 4.3) алп О а~г аз~ О а1л ага О а„ ал, л — ~ ал~ 263 8.3.1.
Выполните алгоритм гауссова исключения для матрицы на рис. 8.15 и убедитесь, что при упорядочивании узлов динамического манекена по алгоритму минимальной степени не возникает никакопз заполнения. 8.3.2. Рассмотрите исходную нумерацию узлов динамическом манекена на рис. 8,8, Прежде всего обратите зту нумерацию, т.е. пусть узел 1 станет узлом 14, узел 2— узлом 13 и т.д. Примените теперь алгоритм минимальной степени к динамическому манекену с так пронумерованными заново узлами (если возникает неоднозначность, используйте узел с меньшим исходным номером).
Сравните переупорядоченную матрицу и ее заполнение со случаем матрицы на рис. 8.15. 8.3.3. Рассмотрите разреженный вариант алгоритма Холецкого (см. гл. 3) в применении к симметричным положительно определенным матрицам. Покажите, что заполнение при этом идентично заполнению при симметричном гауссовом исключении 8.3.4. Рассмотрите краевую задачу (8.2.2) — (8.2.3). Зля аппроксимации вторых производных воспользуйтесь формулами (3.2.3б). Составьте матричное уравнение, аналогичное (8.2.10) . Зля точек сетки, которые примыкают к границе, придется использовать формулы (8.2.4).
Выпишите матрицы, соответствующие лексикографическому и черно-белому упорядочиваниям. и всю последовательность итераций Якоби определить как х " = Р '(Ь + Вх"), 7( = О, 1, (8.4.4). Близкий итерационный процесс можно получить, если учесть следующее соображение. После того как х1 вычислено по формуле (8.4.2), его (1) (1) можно использовать при вычиспенин х1, и выглядит вполне естественным использовать именно зто значение, а не первоначальное прнближе(о) ние х1 . Если мы будем использовать новые значения сразу после их получения, то придем к формулам х; = — (Ь; — 2: а;х Х а(х.
), 1'=1,...,и, (1) 1 (1) (о) (8.4.5) ап 1<1 1>1 определяющим первый шаг итераций Гаусса — Зейделя. Чтобы представить зтн итерации в матричной форме, введем верхнюю и нижнюю треугольные матрицы О а11 ... а1и О ... ази О аи — 1,и О (8.4.ь) О аз 1 О а„ а„„, О а„1 Если умножить 1-е уравнение (8,4.5) на ап, то, как легко убедиться, и уравнений (8.4.5) можно переписать в виде Рх! (х1 — Ь + ухо (8.4.7) Матрица Р— т'.
невырождена, поскольку она является нижней треугольной матрицей с отличными от нуля диагональными элементами. Следовательно, из (8.4.7) мы имеем х' = (Π— 1'.) 1(Ухо + Ь) и всю последовательность итераций Гаусса — Зейделя можно определить как х"+ ' = (Р— А) ' [Ух" + Ь], й = О, 1,... (8.4.8) Запись итераций Якоби и Гаусса — Зейделя в виде (8.4.4) и (8,4.8) полезна дпя теоретических целей, но при фактически.". вычислениях обычно исполь зуют покомпонентные формулы (8.4.2) и (8.4.5). Давайте рассмотрим применение этих итерационных методов к дискретному аналогу уравнения Лапласа на квадрате.
Простейшие разностные так что А = Р— В. Тогда, как легко проверить, (8.4.2) можно переписать в виде х' = Р ' (Ь + Вхо) уравнения (8.2.7) дпя этой задачи (при /7 = 0) имеют вид и;+1, +и; 1,т+и;;„+и; 7, — 4иб =О, /,/=1,...,Ж (8.49) т,е. новое приближение по Якоби к решению в точке (1, /) есть среднее с,/ +1 с,,/ 1 Старое Старое Старое Старое Новое Старое г — 1,/" с-1„/ (+1,/ Старое с+1„/ Новое а с/-1 б с/-1 Рис. 8Л7. Смещения в методах Якоби и Гаусса — Зеаделя: а) смещение Якоби; б) смещение Гаусса — Зейделя предыдущих приближений в четырех соседних точках сетки (~' + 1, /), (1, / + 1).
По этой причине метод Якоби иногда называют методом одновременных смещений. Обратите внимание, что в методе Якоби порядок, в котором обрабатываются уравнения, несуществен. В методе же Гаусса— Зейделя ситуация другая — каждому способу упорядочивания уравнений фактически соответствует свой итерационный процесс. Если мы упорядочим точки сетки слева направо и снизу вверх, как это было сделано в разделе 8.1, то шаг метода Гаусса — Зейделя будет определяться формулами (1) 1 (1) (1) (о) (о) иЧ (и( — 1 /+ и~! — 1+ и~+1 /+ и~ /-1) т.е.
новое приближение в точке (1,/) снова будет средним значением приближений в четырех соседних узлах сетки, но. теперь используются два старых и два новых значения. Различие двух этих методов схематически показано на рис. 8.17. Мы теперь рассмотрим вопрос о сходнмости итерационных методов. Как метод Якоби, так и метод Гаусса — Зейделя представляют собой частные случаи общего итерационного процесса х"" =Нх" +с/, й=0,1,..., (8.4.10) где задание матрицы Н и вектора д определяет конкретный метод.
Так, в методе Якоби Н = Р ' В и Ы = Р ' Ь, в то время как в методе Гаусса— Зейделя Н = (Р— /.) ' (/ и и = (Р— Л) ~ Ь. Предположим теперь, что х'— точное решение системы Ах= Ь. Тогда в методе Якоби мы имеем (Р— В)х' =Ь или х* =Р 'Вх*+Р 'Ь, Неизвестными здесь являются и;; ((,/ = 1,..., Ф), а значения остальных и; считаются известными из граничных условий. При заданном начальном приближении и," один шаг по Якоби дпя уравнений (8.4.9) есть просто (о) (1) 1 (о) (о) (о) (о) и» = — (и,.+г /+и,-,;+и, .„+и;,,), 4 а в методе Гаусса — Зейделя (Ю вЂ” Š— У)х' =Ь или х' =(Ю вЂ”,1.) 'Ух'+( — й) 'Ь, так что в обоих случаях х' =Нх'+б.
(8.4.11) Если теперь вычесть (8.4.11) из (8.4.10), то мы получим е~" =Не", й=0,1,..., (8.4.12) где е =х — х' есть ошибка на А-м шаге. Уравнение (8.4.12) представляет собой основное соотношение, определяющее поведение погрешности приближенного решения в итерационных методах вида (8.4.10). Мы уже анализировали это уравнение в другом контексте в гл. 6 (см. теорему 6.1.4) и пришли к заключению, что векторы е" будут стреми~ься к нулю при й- в том и только том случае, если спектральный радиус р(Н) матрицы Н меньше единицы. Мы переформулируем этот основной результат для итерационного метода (8.4.10) .
Т е о р е м а 8.4 1. Итерации (8.4.10) сходятся к решению х' при любом начальном приближении х в том и только,том случае, если р(Н) < 1. Теорема 8.4.1 не ограничивается методами Якоби и Гаусса — Зейделя. Она применима к любому итерационному процессу вида (8.4.10) при условии, что вектор х' удовлетворяет (8.4.11), и является основным теоретическим результатом для таких итерационных методов. Согласно этой теореме, чтобы исследовать сходимость конкретного итерационного метода, мы должны определить, меньше ли единицы спектральный радиус итерационной матрицы этого метода. В общем случае это очень сложная проблема, решение которой может потребовать вычисления всех собственных значений итерационной матрицы.
Однако для некоторых итерационных методов и для некоторых классов матриц удается сравнительно просто показать, что критерий сходимосги выполняется. Мы сейчас приведем несколько таких примеров для методов Якоби и Гаусса — Зейделя. Т е о р е м а 8.4.2. Предположим, что матрица А строго диагонально доминирующая, т.е. !аи !> Х !ац!, ~'= 1„...,п. (8.4.13) /Фс Тогда итерации Якоби и итерации Гаусса — Зейделя сходятся к единственному решению уравнения Ах = Ь при любом начальном приближении хь. Для метода Якоби эта теорема доказывается очень просто.
Так как Н = = В ' В, то из (8.4.13) сразу следует, что сумма абсолютных величин элементов каждой строки Н меньше единицы, т.е. !! Н !!„( 1. Но тогда все собственные значения матрицы Н по абсолютной величине меньше единицы и можно воспользоваться теоремой 8.4.1. Дпя метода Гаусса — Зейделя доказательство несколько сложнее, и мы его здесь не приводим. Условие строгого диагонального доминирования является довольно ограничительным, и ему, в частности, не удовлетворяет разностная схема (8.4.9) для уравнения Лапласа: в большинстве строк матрицы коэффициентов соответствующей системы имеется четыре внедиагональных элемента. по абсолютной величине равных 1, так что соотношения (8.4.13) как стро- гие неравенства не выполняются.
Тем не менее, если воспользоваться другой техникой (см. дополнительные замечания), то можно показать, что для разностных уравнений (8.4.9) оба рассматриваемых метода сходятся. Матрица коэффициентов уравнений (8.4.9), очевидно, является симметричной (см. (8.2.10) ), и, кроме того, можно показать, что она положительно определенная.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
