3. Прямые методы решения.

Для стационарных схем типа (47) наиболее сложным является вопрос о фактическом вычислении разностного решения.

В самом деле, -мерная схема (46) является линейной алгебраической системой с неизвестными (если по каждой координате взято N интервалов). Матрица этой системы в двумерном случае изображена на рис. 89. В общем случае эта матрица ленточная, причем лента слабо заполнена и имеет полуширину

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

При большом N это число действий неприемлемо велико; кроме того, лента матрицы не помещается в оперативной памяти ЭВМ. Поэтому прямое решение линейной системы (46) методом Гаусса возможно только в двумерных расчетах, и то при небольшом .

Замечание. Если строить схемы высокого порядка точности (например, сплайновые) или использовать последовательность сгущающихся сеток (обычно при N = 4, 8, 16, 32) с уточнением по способу Рунге, то даже при небольшом числе узлов удается получить удовлетворительную точность расчета.

Рис. 89.

Для некоторых важных частных случаев эллиптических задач разработаны очень быстрые прямые методы; перечислим (они подробно изложены, например, в [3, 6, 31]).

Быстрое преобразование Фурье применимо к задаче Дирихле в прямоугольнике. Оно основано на том, что если число интервалов по каждой переменной разбивается на множители, то вычислять коэффициенты дискретного преобразования Фурье можно не по формулам Бесселя типа (2.44), а по более экономичным рекуррентным формулам. Если , то метод является особенно быстрым и требует всего действий на каждый узел сетки.

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

Будем искать разностное решение в виде разложения Фурье;

(52)

Подставим разложение (52) в соотношение (51), умножим на игпр и просуммируем по от 0 до . Замечая, что

и учитывая условие ортогональности гармоник (см. гл. II, § 2, п. 4), найдем

где

являются дискретными коэффициентами Фурье правой части уравнения. Формулы (53), (54) позволяют найти искомое разностное решение.

Однако эти формулы неэкономичны. Необходимо вычислить N коэффициентов причем нахождение каждого коэффициента по формуле (54) требует примерно операций. Следовательно, задача (51) решается за операций, т. е. много медленнее, чем в методе прогонки.

Если число интервалов сетки составное, то формулу (54) можно преобразовать так, что требуемое количество операций уменьшится. Представим индексы в следующем виде:

Запишем формулу (54) в виде двойной суммы:

Отбросим в показателе степени последнее слагаемое, и получим следующее выражение коэффициентов Фурье:

где

Вычисление N коэффициентов по формуле (55) требует операций; вычисление вспомогательных коэффициентов по формуле (56) производится еще за операций. Следовательно, число операций, необходимое для нахождения коэффициентов Фурье по формулам (55), (56), равно оно существенно меньше, чем (например, при меньше в раз).

Если К в свою очередь разбивается на множители, то формулу (56) следует преобразовать аналогичным образом. Это позволяет еще уменьшить объем вычислений.

Приведем без вывода рекуррентные формулы вычисления коэффициентов Фурье для случая

причем

Число вспомогательных коэффициентов ранга равно N, поэтому для вычисления коэффициентов всех рангов по формулам (57) требуется около операций.

Если учесть, что , то нетрудно найти оптимальное число сомножителей и оптимальное значение Но для программирования считается более удобным, если в последнем случае требуемое число операций равно , что мало отличается от оптимального случая и почти не уступает по скорости методу прогонки.

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

поставлена первая краевая задача в прямоугольной области.

Введем равномерную сетку и составим разностную схему

Будем искать разностное решение в виде разложения Фурье

Аналогично одномерному случаю, получим следующие выражения для коэффициентов Фурье:

где

Запишем последнюю формулу в следующем виде:

Каждая сумма в формулах (62) имеет тот же вид, что и в формуле (54). Поэтому, если N и М разлагаются на множители, то каждую сумму можно вычислить по рекуррентным формулам типа (57). Если при этом , то число операций на каждый узел сетки, аналогично одномерному случаю, есть . Следовательно, быстрое преобразование Фурье даже в многомерном случае по экономичности мало уступает самому быстрому одномерному методу — прогонке.

Метод декомпозиции, или нечетно-четкой редукции, применим для той же задачи, что и быстрое преобразование Фурье. Он использует исключение всех нечетных точек из системы уравнений типа (46).

При исключение выполняется рекуррентно и число действий на узел сетки составляет

Матричная прогонка применима даже для случая областей сложной формы. Число действий на узел сетки в этом методе есть Но если требуется решить на данной сетке большую серию задач с различными правыми частями и граничными значениями, то, сохраняя и используя результаты промежуточных вычислений, можно сократить это число действий до

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