Федоренко Р.П. Введение в вычислительную физику (1185915), страница 35
Текст из файла (страница 35)
Простейшие формы алгоритмов неустойчивы. Можно сближать В с — ет, решая уравнение Ви = х подходящим итерационным методом, например методом Переменных иаправлений. При этом, естественно, иет необходимости в очень точном решении уравнения, достаточно ограничиться каким-то числом «виутренних» итераций. Так мы приходим к семейству «двухступенчатых» итерационных алгоритмов.
Их оптимизация, в частности выбор наилучшего (с точки зрения эффективности процесса в целом) числа внутренних итераций, связана с достаточно сложиым анализом. Такие итерационные процессы д теория их оптимизации построены Е. Г. Дьяконовым. Миогосеточиый метод. Опишем конструкцию своеобразного итерационного алгоритма, получившего в последние годы широкое применение по причинам, которые удобно обьяснить несколько позже. Метод достаточно сложен алгоритмически, сложен ои и для теоретического анализа даже в самом простом случае. Поэтому мы ограиичимся самым общим описанием и качественным обьясиеиием механизма, обеспечивающего высокую скорость сходимости итераций.
Исходной идеей этой конструкции является следующее замечаиие. Все собственные функции оператора о (разиостиого) зГ « = з1п — зш — условно разделим иа две части: гладкие крв . Етв , » ж л ( р < ЛЧ2 и 4 < йЧ2) и негладкие (р з 'ЛЧ2 или д ~ лЧ2) функции, т.е. разделим низкие и высокие гармоники и частоты Х некоторой условной границей. Легко построить итерациоиный метод, эффективно гасящий иегладкую компоненту погрешности (и иевязки). В самом деле, метод простой итерации и' = и'+ т(Ьи' — ~), как было показано, гасит (р, д)-компоиеиту погрешноСти, умножая ее за один шаг на 1тз 8 141 гашение эллиптических э»д»ч методом снох 1 — тХ . Высокие частоты расположены, очевидно, между Х, ли —— = (4/Лз) зшз(пН/4Я) 2/Л» и Х„,, „,, 8/Лз.
Выбирая т оптимальным для этой части спектра, т.е. т = 2Л»/(2 + 8) = 0.2Л», получаем убывание негладких компонент погрешности (невязки) в процессе итераций со скоростью (О.б) ', т.е. достаточно быстрое. На остальной части спектра сходимость, конечно, очень медленная. Так, компонента (1, 1) погрешности убывает с показателем 1 — 2пэт 1 — 0.4(п/Ф)» за шаг.
В целом итерационный процесс оказывается неэффективным. Однако неболыпое число таких итераций «сглаживает» невязку: высокие гармоники в ней гасятся, основную роль играет гладкая компонента. Таким образом, после 1 итераций имеем приближение и', удовлетворяющее уравнениям (А и')» — /» — — г,', (внутри) и' — р = 0 (на границе) (это просто определение невязки г).
Если бы мы могли решить уравнения (Ьн) = г' (внутрн) и»,„= 0 (на границе) то функции ю была бы поправкой в том смысле, что точное решение и» = и» вЂ” е» . На первый взгляд, найти поправку ю — задача такой же степени трудности, как и исходная. Но после /итераций с т = 0.2Л» ситуация изменилась: невязка г' стала гладкой функцией и уравнение для поправки можно решать на другой, более грубой сетке. Предположим для простоты изложения, что М= 2~, и наряду с основной сеткой с шагом Л = 1/М введем вспомогательную сетку с шагом Н= 2Л.
Узлы этой сетки совпадают с четными узлами основной сетки (т.е. с теми узлами, (Л, »л), для которых четны оба индекса Л н лч). На этих сетках мы будем рассматривать близкие по смыслу функции — в этих случаях будем использовать одинаковые буквы для Н-сеткн и Л-сетки (большие и малые соответственно).
Итак, имеем 1'-е приближение и' и его невязку г' . Возьмем ограничение невязки на Н-сетку, т е., проще говоря, А» —— г „ (Л, т = О, 1, ..., Н/2), и решим на Н-сетке уравнение (ВЖ)» = Р 1ч.1 174 ОСНОВЫ ВЫЧИСЛИТЕЛЬНОИ МАТЕМАТИКИ Теперь вопрос в следующем: из того, что (17Вг) „= г ь 7, следует ли (хотя бы приближенно), что (йв)4 и г' и? Если да, то проведенная коррекция явно целесообразна. Вычисления (простые, но довольно о о О о ! о о о О о о о о о о о о о О о г 6 о ъ о Г Асс'-н') Ь Ь Ьг В Рис, 17 громоздкие) показывают, что ответ неоднозначен. Точнее, соотношение Ь м ж гс выполняется «в среднем», в слабом смысле слова.
Поясним это на одномерном примере. На рис. 17 показаны этапы процесса: а — гладкая на 7ь-сетке невязка г', б — ее ограничение (с нулевыми значениями на границе). здесь 4у — аппроксимация оператора Лапласа на Н-сетке. Эта задача заметно проще исходной хотя бы потому, что в ней в четыре раза меньше неизвестных и число обусловленности для системы меньше (тоже в четыре раза).
Тем не менее решение такой системы не настолько проще решения исходной задачи на й-сетке, чтобы молсно было пренебречь проблемой решения вспомогательной зщ1ачи. Пока будем считать, что вспомогательная задача так или иначе решена (приближенно, вообще говоря), Интерполируя (линейно по х и у, например) функцию 1т на узлы основной й-сетки, получаем функцию ье . Вычитая ее из и', приходим к новому приближению й = и' — и.
Что можно сказать о невязке этой функции? Вычислим ее во внутренних узлах: г = (сь(и' — ь»)) — / = г, — (с»и) 1 те з 14) гашение эллиптических злллч методом сеток иа Н-сетку Я; в — функция г = Ь(и' — и) . Обратим внимание на характер функции г: она в среднем близка к нулю и состоит, в основном, из негладких собственных функций. После этого очередная серия простых итераций с т== 0.2лз эффективно гасит невязку.
Причина именно такой структуры г разъясняется ниже. Итак, основная идея коррекции с помощью вспомогательной сетки состоит в том, что невязка из подпространства гладких сеточиык функций «перегоняется» в подпространство негладких сеточных функций, где эффективно работает метод простой итерации. Вернемся к вопросу о том, как решать задачу на вспомогательной Н.сетке, ведь она немногим проще исходной. Ответ очевиден: для этого надо использовать свою 2Н-сепсу, для нее — 4Н-сетку, и т.д. до тех пор, пока число узлов иа очерщной вспомогательной сетке не станет совсем уж незначительным.
Однако окупит ли эффект ускорения сходимости затраты на вспомогательные вычисления? Ответ на этот вопрос не очевиден, он требует проведения сложных и достаточно аккуратных оценок. Такие оценки были проделаны и было доказано (сначала' для задачи Пуассона в прямоугольнике, затем для гораздо более общих и сложных эллиптических задач), что норма невязки убывает со скоростью, не зависящей от шага сетки, т.е. необходимое для ее уменьшения в е ' раз число арифметических операций есть СНз1п е ' (С не зависит от Ф). Это асимптотически рекордный результат.
При достаточно большом Ф описанные выше (и в сущности все остальные известные сейчас) методы уступают многосеточному. Однако постоянная С в этой оценке вычисляется настолько грубо, что лучше считать ее неизвестной. Могло бы оказаться, что преимущество многосеточного метода по сравнению, например, с методом переменных направлений наступает при сюль больших Н, какие на практике ие используются. Такие вопросы выясняются путем вычислительного эксперимента. Мнопэчисленные реализации многосеточного метода и результаты вычислений показали, что метод оказывается эффективным уже на тех сравнительно скромных сетках (Н порядка 50, 100), которые давно используются в практических расчегах. Приведем для иллюстрации табл.
11, в которой показаны результаты вычислительного эксперимента по решению некоторых уравнений многосеточным методом. Основная сетка имела 103 х 108 узлов„ первая вспомогательная (Н= Зл) — Збх36, вторая — 12х12. В табл, 11 показаны вид аппроксимируемого оператора, шаблон аппроксимации, и — число итераций, затрачиваемых на сглаживание иевязки, предшествующее обращению к вспомогательной задаче, и, наконец, средняя скорость убывания невязки с номером итерации 1.
Прн этом 1 — это число итераций на основной сетке 108 х 103, включая время работы, затрачиваемое на решение вспомогательных 177 й 141 гвшвннв эллиптичгских злдлч мвгодом сеток задач (в единицах, равных времени на одну итерацию на основной сетке). В дальнейшем многосеточный метод был усовершенствован. Усовершенствования касались таких деталей, как способ вычисления невязки Я на Н-сетке через невязку г на Ь-сетке, форма основных итераций, методы интерполяции с гг= на л-сетку, и некоторых других.
Все эти технические усовершенствования сделали алгоритм одним из наиболее эффективных, выдерживающих конкуренцию даже с некоторыми узкоспециализированными, применимыми только к задаче Пуассона (уравнение с постоянными коэффициентами Ьи = г') в квадрате, Замечательным оказался тот факт, что и алгоритм метода, н теорема о независимости скорости сходнмости от шага сетки, выдержали обобщения прн усложнении задачи за счет переменности коэффициентов, произвольного вида области и т.п. Однако наибольшая популярность и широта применения метода в настоящее время связаны с его приложением к такому мощному средству решения эллиптических задач, как метод конечных элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
