Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
В — R1R2 ¦
E +
Очевидно, B = E — ог{ф^ + . Оператор -I- имеет второй
порядок, но, к сожалению, не является строго эллиптическим. Слагаемое E при подходящем выборе о придает разностной аппроксимаций В «эллиптический» характер.
Оператор В легко обратим: решение уравнения Bv = z требует числа операций, пропорционального числу неизвестных, т.е. числу
РЕШЕНИЕ ЭЛЛИПТИЧЕСКИХ ЗАДАЧ МЕТОДОМ СЕТОК
171
узлов сетки. Чтобы убедиться в этом, выпишем подробно разностную аппроксимацию Ri и R2:
(RlV)k,m = Vk,m + G (Rlv)k,m = vk,m-a
V,c-l, m , Vk,m~Vk
• и
+
»1+1
"к, т
т
L,
і;
На рис. 16 показана сетка и расположение в ней шаблонов операторов R1, R2; такая аппроксимация обеспечивает важное свойство
R2 = /?* Из этого рисунка очевиден алгоритм «обращений» R1, R2 при известных значениях и на границе. Решение, например, уравнения RiV = z осуществляется «маршевым» алгоритмом вычисления слева-направо и снизу-вверх, начиная с левого нижнего угла области. На каждом шаге такого алгоритма в выражении (Л,и)л т из трех значений v два (vk_l т и Vk т_1) уже известны и можно вычислить
vk, т =
= Y-TMh К-І.т + ^.т-І^-
УсТОЙЧИВОСТЬ этого «марша» легко устанавливается (при ст >0).
Обращение R2 осуществляется аналогично, но в обратном направлении (начиная с правого верхнего угла области). Оптимизация оценок эквивалентности за счет ст приводит к ^2Zyl = 0(h~l). Выбирая далее последовательность итерационных параметров T1 в соответствии с теорией че-бышевского ускорения, получаем алгоритм, в котором число итераций, необходимых для уменьшения погрешности начального приближения в є-1 раз, есть (для сетки NxN) i(e) — О(VN In є '). Ограничимся здесь этими общими сведениями, отправляя интересующихся деталями (как оценивать V1, у2, как выбирать ст и т.п.) к специальной литературе.
«Двухступенчатые» итерационные методы. Почти очевидно, в каком направлении следует искать операторы В, наилучшие с точки зрения оценок энергетической эквивалентности: оператор В должен быть возможно более похожим на -D (идеальный случай: B = -D, V1 = V2=I1 достаточно одной итерации; к сожалению, она просто эквивалентна решению исходной задачи). Однако по мере сближения В с -D возрастают трудности решения уравнения Bv = z.
Рис. 16
172
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
14. I
Удачным компромиссом является, например, выбор
Де-[-4 + -^) = —A-
^Эх2 Sy2i
В этом случае V2^Vi не зависит от h, а для решения разностного уравнения —Au = z можно использовать построенные в последние годы эффективные алгоритмы для решения в прямоугольной области уравнения с постоянными коэффициентами. Ограничимся здесь только названиями методов, тем более что многие из них уже оформлены как стандартные быстро работающие программы математического обеспечения современных ЭВМ: это методы циклической редукции, быстрого преобразования Фурье (см. § 24), маршевый и некоторые другие. Кстати, включение некоторых из них в арсенал средств практических вычислений было связано с анализом вычислительной неустойчивости и разработкой вычислительно устойчивых модификаций (как это было с чебышевским ускорением). Простейшие формы алгоритмов неустойчивы.
Можно сближать В с —D, решая уравнение Bv — z подходящим итерационным методом, например методом йеременных направлений. При этом, естественно, нет необходимости в очень точном решении уравнения, достаточно ограничиться каким-то числом «внутренних» итераций. Так мы приходим к семейству «двухступенчатых» итерационных алгоритмов. Их оптимизация, в частности выбор наилучшего (с точки зрения эффективности процесса в целом) числа внутренних итераций, связана с достаточно сложным анализом. Такие итерационные процессы ц теория их оптимизации построены Е. Г. Дьяконовым.
Многосеточный метод. Опишем конструкцию своеобразного итерационного алгоритма, получившего в последние годы широкое применение по причинам, которые удобно объяснить несколько позже. Метод достаточно сложен алгоритмически, сложен он и для теоретического анализа даже в самом простом случае. Поэтому мы ограничимся самым общим описанием и качественным объяснением механизма, обеспечивающего высокую скорость сходимости итераций. Исходной идеей этой конструкции является следующее замечание. Все собственные функции оператора А (разностного)
п л • крл дтл z\, т —Sltl n~ Sm fj~ условно разделим на две части: гладкие
(р< N/2 и q < N/2) и негладкие (р> N/2 или q>N/2) функции, т.е. разделим низкие и высокие гармоники и частоты X некоторой условной границей.
Легко построить итерационный метод, эффективно гасящий негладкую компоненту погрешности (и невязки). В самом деле, метод простой итерации и‘ = и‘ + т(Ам' — /), как было показано, гасит (р, q)-компоненту погрешности, умножая ее за один шаг на
РЕШЕНИЕ ЭЛЛИПТИЧЕСКИХ ЗАДАЧ МЕТОДОМ СЕТОК
173
1 — тХ.р q. Высокие частоты расположены, очевидно, между X1 N/2 = = (4/Л2) sin2(nN/4N) « 2/Л2 и Xa^1i ЛГ_1 « 8/Л2. Выбирая т оптимальным для этой части спектра, т.е. х = 2Л2/(2 -I- 8) = 0.2Л2, получаем убывание негладких компонент погрешности (невязки) в процессе итераций со скоростью (0.6)', т.е. достаточно быстрое.