Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Таков качественный механизм неустойчивости метода чебышев-ских итераций. Поняв его, можно понять и то, чтб нужно изменить, чтобы метод стал устойчивым. Достаточно очевидно, что нужно перебирать параметры T1 < т2 < ... < Tj не в их естественном порядке (и не в обратном), а как-то «в разбивку», с тем чтобы частичные произведения .
PtW = П о - W)’ = П (1 -
j-1 j=k.+1
были при любом к более или менее равномерно ограниченными на всем интервале [/, L]. Здесь последовательность параметров хп(^ — та же самая, но как-то переставленная.
Ho это наводящие соображения, а точная постановка задачи и ее решение достаточно сложны. Тем не менее задача решена: рациональные перестановки итерационных параметров, приводящие к устойчивому итерационному процессу, были получены почти одновременно В. И. Лебедевым и В. Н. Финогеновым, а также А. А. Самарским и Е. С. Николаевым. Рецепт построения этих устойчивых
перестановок достаточно прост в случае і = 2Г. Нужная перестановка получается рекуррентно.
Пусть имеется перестановка для і = 2Г:
{«(;)}; = !, 2 2' •
Тогда перестановка для /' = 2r+I получается заменой каждого n(j) парой n(j), 2r+1 + I — n(j). Этот рецепт дает г = I, i = 2: п={ 1, 2}
г = 2, г = 4: и = {1,4, 2,3},
г = 3, і = 8: «={1,8,4, 5, 2, 7,3,6}
158
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
[Ч. I
и т.д. Если теперь 1/tj (;' = 1,2,..., г = 2Г) — корни полинома Чебышева на [/, L] степени г, расположенные в естественном порядке: х1>х2> ... , а {«(;)} (j = 1, 2, ..., і) — «устойчивая» перестановка, то итерационный процесс
uj+i = uj + xin(j+i)(Duj-f), j = 0, 1, 1,
сходится в соответствии с теорией, не учитывающей погрешностей округления. Процесс устойчив, и погрешности округления не оказывают существенного влияния.
При вышеизложенном порядке использования итерационных параметров получаем процесс со следующими характеристиками:
Ill'll IIv0II ехр(— IvfUL').
Такая же формула имеет место и для невязки:
Ikil » Ik0II ехр(—2blllL).
В нашем случае имеем L = SN2, I = 2л2, т.е.
ехр (—2і VUL) = exp (—іл/N)
и, например, за N итераций погрешность убывает в 20 раз. Это не так уж быстро, но в методе простой итерации за то же время погрешность умножится лишь на 0.95 (при N= 100).
Отметим, что метод простой итерации и чебышевское ускорение имеют широкую сферу применения при решении систем линейных уравнений вида Au = /. Изложенное выше основано на таких свойствах оператора А:
а) самосопряженность: -At = A (отсюда следует вещественность спектра А и ортонормированность базиса собственных векторов);
б) положительность спектра А: 0 < I H Xk H L;
в) для организации расчетов нужно иметь только оценки для границ спектра I, L (снизу для I, сверху для L).
В заключение приведем два полезных замечания.
Замечание 1. Обычно ход итерационного процесса контролируют, выводя на экран PC, например, норму невязки (она вычисляется по ходу работы алгоритма, так как основная расчетная формула имеет вид uj+l = Uj + xrJ). В методе простой итерации У WIl монотонно убывает. При чебышевском ускорении Ц W |] меняется немонотонно: она убывает только за полный цикл из і итераций. На промежуточных итерациях возможен сильный рост ||W||.
Так как г = D-iV, то ||r|| ^ НиЦ/Х1,1.
Замечание 2. Выбор длины цикла і (степени полинома Чебышева) не совсем прост. Можно, задав погрешность є, рассчитать і,
РЕШЕНИЕ ЭЛЛИПТИЧЕСКИХ ЗАДАЧ МЕТОДОМ СЕТОК
159
используя приведенные выше оценки. Анализ показывает, что более эффективным является другой способ: использовать полиномы степени і я» VUT ~ N, повторяя цикл итераций длиной V LI I до получения нужной точ'ности.
Метод переменных направлений. Эффект чебышевского ускорения недостаточен. Имеются и более быстрые итерационные методы. В частности, большие успехи были получены на основе метода переменных направлений, в котором используется так называемый принцип установления. Решение стационарного уравнения Дu = f, uI а?3 = <р является пределом при г-*оо решения u(t, х) уравнения теплопроводности Ut = Au — /. Метод простой итерации, как нетрудно заметить, есть просто решение этого уравнения по явной схеме, а условие т0 = 2/(L + I) « 2/8N2 як 0.25h2 похоже на условие Куранта. Таким малым шагом трудно получить достаточно большие t, отсюда и большое число итераций.
Как известно, метод переменных направлений, допускает счет с произвольным шагом х. Кажется, можно получить сколь угодно большие t за один шаг! К сожалению, дело не так просто, так как при этом теряется аппроксимация. Тем не менее метод переменных направлений при достаточно аккуратном его оформлении действительно приводит к существенно более эффективным итерационным процессам. (Полезно оценить оптимальный эффект в процессе, использующем схему «ромб»; см. § 12.)
Одна стандартная итерация (переход и1 в ul+l) метода переменных направлений состоит из двух «полуитераций».
1. Сначала по известной и1 находится промежуточная функция и* из уравнения
Функция и* находится серией раздельных прогонок по горизонтальным линиям сетки, и это требует 0(N2) операций.
