Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 63
Текст из файла (страница 63)
На самом деле для многих, если не для большинства, дискретных аналогов эллиптических уравнений в частных производных матрица коэффициентов разностных уравнений будет симметричной и положительно определенной. В таких случаях итерации Гаусса — Зейделя всегда сходятся, однако для сходимости метода Якоби симметричность и положительная определенность не являются достаточными. Следующую теорему мы приводим без доказательства. Т е о р е м а 8.4.3. Если матрица А является симметричной и положительно определенной, то при любом начальном приближении х итерации Гаусса — Зейделя сходятся к единственному решению уравнения Ах = Ь. Даже если методы Якоби и Гаусса — Зейделя сходятся, сходимость может оказаться настолько медленной, что сделает практическое использование этих методов невозможным. Это замечание относится, в частности, к разностным аналогам эллиптических уравнений в частных производных.
Так, например, асимптотически на каждой итерации по методу Гаусса— Зейделя для уравнений (8.4.9) при У = 44 ошибка умножается на множитель, примерно равный 0,95. Метод Якоби для этой задачи сходится приблизительно в два раза медленнее, причем с увеличением У скорость сходи- мости обоих методов уменьшается. В ряде случаев скорость сходимости метода Гаусса — Зейделя можно значительно увеличить. Давайте, исходя из текущего приближения х», л(»+1) сначала вычислим х; для данного 1 по итерации Гаусса — Зейделя л(»+1) 1 / (»+1) (») х; = — ~Ь; — 2: а;;х, — Х ачх. ан 1<1 1>1 (8.4,14) аи~ ! Отсюда, перегруппировав члены, получаем а..х.( ) + со Х а .х( Й .<.
б1 1<1 =(1 — ьэ)аих„— 1о Х а,,-х. +с,1Ь,. (») (») 1>1 л (»+1 ) а затем, используя значение х; в качестве промежуточного, вычислим 1-ю координату нового приближения по формуле х( ) = х( ) + ь1(х( ) — х( )), (8.4.15) где ы — параметр, введенный для увеличения скорости сходимости. Мы можем переписать (8.4.14) и (8.4.15) следующим образом. Подставим сначала (8.4Л4) в (8.4.15) Если, как и раньше, воспользоваться представлением А = Р— Л вЂ” (т, то эту <»+11 связь между компонентами нового приближения х и старого приближения х~, справедливую при 1 = 1,..., и, можно записать в матричной (») форме как Рх»+ ' — со Ах»+ ' = (1 — оэ) Рх" + со Ух» + с,э Ь.
Так как матрица Р— оэ», по-прежнему нижняя треугольная н по предположению имеет отличные от нуля диагональные элементы, она является невы- рожденной, и мы получаем х"+' =(Р— оэср) ' [(1 — со)Р+оэУ] х" +со(Р— сот.) ' Ь. (8.4.17) Это соотношение определяет метод последовательной верхней релаксации. Отметим, что, как и в случае метода Гаусса — Зейделя, при фактических вычислениях обычно используют покомпонентные формулы (8.4.14)— — (8.4,15), Если со = 1, то (8.4.17) есть просто обычный метод Гаусса — Зейделя. Мы ограничимся вещественными значениями параметра со.
Тогда для сходимости метода последовательной верхней релаксации необходимо, чтобы выполнялось 0 ~ со < 2. Выбор оэ в этом диапазоне, вообще говоря, не гарантирует сходимости, но в том важном случае, когда матрица А симметрична и положительно определена, имеет место следующее обобщающее теорему 8,4.3 утверждение, которое мы также приводим без доказательства.
Т е о р е м а 8.4.4 (О ст ров с ко го — Р е й ч а). Если матрица А симметрична и положительно определена, то при любом оэ Е (0,2) и любом начальном приближении хо итерации метода последовательной верхней релаксации (8,4.17) сходятся к решению уравнения Ах = Ь, Разумеется, мы бы хотели выбрать параметр со так, чтобы максимизировать скорость итераций (8.4,17). Однако в общем случае это представляет очень трудную проблему, н мы здесь ограничимся только тем, что приведем без доказательства некоторые относящиеся к этому вопросу результаты.
Для класса матриц, которые называют упорядоченными согласованно со свойством А *), разработана довольно полная теория, которая соотносит скорость сходимости метода последовательной верхней релаксации со скоростью сходимостн метода Якоби и позволяет понять, как выбрать оптимальное значение оэ. Мы не будем давать точное определение этого класса матриц, а только отметим, что в него попадает матрица (8.2,10) для уравнений (8.4.9), а также многие другие матрицы коэффициентов разностных схем для эллиптических уравнений в частных производных, Фундаментальным результатом для этого класса матриц является связь между собственными значениями Х~ итерационной матрицы метода последовательной верхней релаксации Н = (Р— соЕ) ' [(1 — оэ) Р + оэУ] и собственными значениями итерационной матрицы метода Якоби У= Р '(1. + У) .
Каждому нулевому собственному значению матрицы У кратности р соответствуют р собственных значений матрицы Н„„рав- ') Подробнее об этом классе матриц см. Форсайт, Вазов ~ 89, и, 22. Ц,— Примеч. пер. 2бв ных сс — 1, Ненулевые собственные значения 1 для этого класса матриц образуют пары + д;, которым соответствуют собственные значения мат- рицы Н„„удовлетворяющие соотношению (Л. + со — 1)~ = Х.с,Рдз (8.4.18) Это квадратное уравнение относительно Х;, которое определяет два значения Хс для каждого значения дс~. В предположении, что все сс; вещественны и по абсолютнои величине меньше единицы, с помощью (8.4.18) можно получить оптимальное значение м, минимизирующее спектральный ра- Рис.
8.18. р (Н„ 1 как функция от со 1 2 ю диус р(Н ) матрицы Н, который и определяет скорость сходимости метода. Если обозначить оптимальное значение сс через соо, то оно выразится через спектральный радиус матрицы У как и =2~(1+,(1 — р'), р=рЯ. (8.4.19) Значение ойдо всегда заключено между 1 и 2. Соответствующее значение р(Н ) есть Р (Н ) «>о (8.4.20) Кроме того, из (8.4.18) можно определить поведение р(Н ) как функции от сс.
Это поведение показано на рис, 8.18, Мы можем получить представление о возможном ускорении сходимости на примере уравнений (8.4.9) . Собственные значения соответствующей итерационной матрицы Якоби вычисляются явно. При этом максимальное собственное значение определяется выражением р(l)= соал/г =1 — тс'йд~2, й =1/(%+1), (8,4.21) где при больших Л~приближенное равенство выполняется с высокой точностью. Если мы подставим (8.4.21) в (8.4.19), то получим 2 1 — ~рт — с~ ~ ~ ~ь ссо— р (Н,„) = 1 ~~(1 — 'аь~ Ь ' ' 1 ~~1 ~ю~'ь~ (8.4.22) 269 Если теперь для иллюстрации взять У = 44, то р (У) = 0,9976, р (Н) = 0,995, с зо = 1,87, р (Н,„) = 0,87.
(8.4.23) Отсюда видно, что асимптотически на каждой итерации ошибка метода Якоби умножается на множитель 0,997б, а метода Гаусса — Зейделя — на множитель 0,995, т.е. скорость сходимости метода Гаусса — Зейделя примерно (а/ + Н) ит+1/2 (а/ 1Г) 11т +/1 Здесь Н вЂ” матрица размера Л/~ Х /)/ (8.4.26) А А А ') Под скоростью схолимости линейного итерационного процесса (8.4.10) обычно понимают вели а1ну — 1пр(н), обратно пропорциональную числу итераций, необходимых для получения следующего верного знака (см. 189], и.
2)З) — /))иьчеч. пер. 270 в два раза больше* ). В методе же последовательной верхней релаксации ошибка умножается на 0,87, т.е. этот метод будет сходиться примерно в 30 раз быстрее метода Гаусса — Зейделя. Более того, с увеличением /)/ улучшение сходимости будет все более заметным (см. упражнение 8.4.9). Иэ предыдущего ясно, что возможно очень сильное увеличение скорости сходимости метода Гаусса — Зейделя. Однако здесь есть целый ряд сложностей. Во-первых, многие большие разреженные матрицы, которые возникают в практических задачах, не являются "упорядоченнь|ми согласованно со свойством А", и приведенные теоретические результаты к ним неприменимы. Введение параметра со по-прежнему можетпривести к увеличению скорости сходимости, но этого нельзя гарантировать заранее, и, кроме того, за исключением метода проб и ошибок, здесь нет способа выбора хорошего значения оз.
Далее, даже если матрица коэффициентов "упорядочена согласованно со свойством А", получение хорошего приближения к соо может оказаться непростым делом. Действительно, нам удалось получить явные выражения (8.4.22) и вычислить значения (8.4.23) только благодаря специальной структуре уравнений (8.4.9), которая позволила осуществить точное определение р(/) . Так как в общем случае это сделать невозможно, то, чтобы воспользоваться формулой (8.4.19), необходимо предварительно оценить величину р(/), что само по себе является весьма сложной задачей. Таким образом, даже в тех случаях, когда применима предыдущая теория, для определения подходящего значения озо может оказаться необходимым прибегнуть к методу проб и ошибок. Мы теперь вернемся к неявным методам переменных направлений, описанным в разделе 8.2.
Там мы выписали для уравнения теплопроводности разностные уравнения (см. (8.2.19) и (8.2.20)) т+1 т+1 т+1, х т ~ 1/2 т+1/2 т+1/2 2+а)и,/ — и//+, — и// . =(а — 2)и,, +и/, +и. (8.4.25) где верхние индексы соответствовали различным моментам времени. Однако мы можем интерпретировать соотношения (8.4.24) — (8.4.25) как итерационный метод решения уравнения Лапласа, где верхние индексы указывают номер итерации. Пусть и — вектор (8.2.9), где неизвестные иН упорядочены в соответствии с нумерацией узлов сетки слева направо и снизу вверх. Тогда (8.4.24) можно переписать как (а1+ 1~) и~+~ = (а1 — Н) и'"+'~з +Ь. (8.4.27) Комбинация соотношений (8.4.26) и (8.4.27) представляет собой неявный метод переменных направлений Писмэна — рэчфорда.
Величина а, которая в случае уравнения теллопроводностн была функцией от Ьх и Ьг, теперь играет роль положительного параметра, правильный выбор которого позволяет добиться увеличения скорости сходимости. Отметим, что хотя прн реализации метода переменных направлении обычно используют запись трехдиагональных систем в виде (8.4.24)— (8.4.25), для теоретических рассмотрений матричное представление (8.4.26) — (8.4.27) оказывается удобнее. Если мы выразим и "~~ из (8.4.26) и подставим в (8.4.27), то после умножения слева на (а1 + Р) получим и +' =Ви +Ф, гп=01,..., (8.4.28) (8.4.29) где В = (а1 + Р) ' (а1 — Н) (а1 + Н) ' (а1 — У), Ф = (а1+ Р') ' (а1+ Н) ' Ь. В предположении, что а > О, входящие в (8.4.29) обратные матрицы существуют.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
