§ 37. Метод Федоренко

В работе Р. П. Федоренко, ЖВМ и МФ 1, № 5 (1961), предложен метод итерационного решения разностных эллиптических задач, названный им релаксационным. Для уменьшения нормы первоначальной погрешности в раз этот метод требует всего арифметических действий, где М — число шагов сетки по одному направлению, с — некоторая постоянная, не зависящая от М. Напомним, что наиболее быстросходящийся среди рассмотренных выше (и вообще всех других известных) методов метод Дугласа — Рэкфорда требует для той же цели арифметических действий.

Границы применимости метода Федоренко почти такие же, как у простейшего метода установления. Дополнительным ограничением является требование «плавности», «гладкости» первых собственных функций, которое для эллиптических задач обычно выполнено.

В простых примерах экономия машинного времени по сравнению с лучшими в смысле скорости сходимости другими итерационными методами убедительно подтверждается уже при . Надо иметь в виду, что логика организации расчета релаксационным методом существенно сложнее, как мы увидим, чем логика расчета, скажем, по схеме Ричардсона. Поэтому машинное время существенно зависит от качества программы.

Простейшая оценка скорости сходимости (для разностной аппроксимации уравнения Пуассона в квадратной области на квадратной сетке при заданных значениях решения на границе) была получена Р. П. Федоренко, ЖВМ и МФ 4, № 3 (1964).

В работе Н. С. Бахвалова, ЖВМ и МФ 6, № 5 (1966), исследована сходимость метода Федоренко и был получен тот же результат для разностного аналога первой краевой задачи в прямоугольнике для общего эллиптического уравнения с гладкими коэффициентами

Наконец, Г. П. Астраханцев, ЖВМ и МФ И, № 2 (1971), получил аналогичный результат для разностной аппроксимации третьей краевой задачи для самосопряженного эллиптического уравнения в произвольной двумерной области с гладкой границей.

Обоснования довольно громоздки, поэтому мы ограничимся качественным описанием идеи метода и самого алгоритма Федоренко, отсылая за доказательствами к оригинальным работам и обзорной статье Р. П. Федоренко, УМН 28, в. 2 (1973).

1. Идея метода.

При решении итерациями задачи

будем отправляться от простейшего процесса установления

который в целом сходится очень медленно, но неравномерно на различных гармониках. Погрешность в соответствии с записывается в виде конечного ряда Фурье

где коэффициенты разложения погрешности и нулевого приближения Числа лежат на отрезке , где

Положим

Если при этом условии хотя бы одно из чисел или s больше, чем то

Поэтому вклад высокочастотных гармоник или в погрешность (3) за один шаг итерационного процесса уменьшается почти вдвое и вскоре становится малым. После нескольких итераций по формуле (2) погрешность будет существенно содержать только гладкую компоненту (гармоники ), потому что низкочастотные гармоники умножаются на числа которые ближе к единице. Очень медленно гасится вклад первой гармоники при сделанном выборе

Обозначим полученное в процессе итераций (2) приближение через U, а погрешность и через . Если бы мы знали погрешность , то нашли бы искомое решение . Однако относительно мы знаем только, что оно удовлетворяет уравнению

где — известная сеточная функция — это невязка, возникающая при подстановке в уравнение (1):

Задача (7) для определения поправки v проще исходной задачи (1) лишь в том отношении, что относительно v заранее известно, что это гладкая сеточная функция. Поэтому для определения v вместо задачи (7) можно приближенно рассматривать такую же задачу на вдвое более крупной сетке, которая (при четном М) является подсеткой исходной сетки:

Звездочкой мы обозначили величины на укрупненной сетке. Задачу таем итерациями по формулам

приняв за нулевое приближение . Здесь

Каждый шаг итераций вчетверо менее трудоемок, чем шаг итераций (2), потому что расчетных точек вчетверо меньше. Кроме того, благодаря быстрее происходит погашение самой медленно убывающей компоненты ошибки. В соответствии с (6)

и для погашения вклада раз нужно вчетверо меньше итераций. Результат итераций по формуле обозначим V. Проинтерполируем V на исходную сетку (линейно). Гладкие компоненты будут получены почти правильно. Возникающая при интерполяции погрешность будет относительно интерполируемой гладкой функции мала, но ее фурье - разложение будет содержать все гармоники (погрешность интерполяции негладкая из-за изломов в узлах интерполяции). Кроме того, негладкая компонента К, не имеющая отношения к искомой поправке, при интерполяции тоже дает случайный вклад в негладкую составляющую полученной при интерполяции функции V. Итак, гладкая компонента разности близка к гладкой компоненте искомого решения но негладкая компонента не очень мала и носит случайный характер.

Поэтому следует проделать еще несколько шагов исходного итерационного процесса (2), приняв за начальное приближение. Это быстро погасит привнесенную при интерполяции негладкую составляющую погрешности, которую итерации (2) гасят почти вдвое за один шаг.

2. Описание алгоритма.

Ускорение сходимости, достигнутое за счет использования укрупненной сетки и итерационного процесса , может оказаться недостаточным. При большом М (мелкой сетке) задача на укрупненной сетке все еще трудоемка. Поэтому при ее решении в свою очередь Целесообразно проделать еще одно укрупнение сетки вдвое, при решении задачи на вчетверо укрупненной сетке снова использовать процесс удвоения сетки и увеличения т. д. В экспериментах Р. П, Федоренко сетка укрупняется не вдвое, а втрое. При оказывается достаточным двух укрупнений. Будем считать для простоты, что т. е. М является некоторой степенью двойки.

На исходной сетке делаем несколько шагов итераций (2), чтобы «выгладить» погрешность. Погрешность нам неизвестна, поэтому можно следить за этим по невязке которая тоже выглаживается. Результат вычислений запоминаем. Затем для поправки v рассматриваем задачу на укрупненной сетке, делаем несколько итераций , чтобы выгладить «поправку к поправке» и результат V запоминаем (он занимает вчетверо меньше места в памяти, чем U). Для вычисления поправки к Г рассматриваем задачу на еще вдвое укрупненной сетке, делаем несколько итераций с шагом и запоминаем результат Г. Этот процесс вычисления поправок к поправкам на вдвое укрупненных сетках продолжаем k раз, пока не дойдем до самой крупной сетки и поправки

Затем начинаем возвращение на мелкую сетку. Сначала с самой крупной сетки интерполируем полученную там последнюю поправку на сетку вдвое более мелкую, вносил эту проинтерполированную поправку в и делаем несколько итераций, чтобы погасить привнесенную при интерполяции ошибку. Результат этих итераций интерполируем на еще вдвое более мелкую сетку, уточняем с его помощью хранящуюся для этой сетки поправку делаем несколько итераций и производим следующую интерполяцию. На предпоследнем шаге после внесения в V поправки и итераций получим поправку V, которую интерполируем на исходную сетку. Проделав несколько, итераций (2) над , получим результат.