N-Iм-\

Упт- 2 %WnPWЯ р = О ? = О

Р9 1 2 , (59

Wy = ехр {2ni/N), = ехр {2ni/M).

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

«.. = /(sin?f + sinf + i). (60)

N - 1М - I

л = о m = о

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

N - 1

п = 0 М - 1

(62)

m = о

Каждая сумма в формулах (62) имеет тот же вид, что и в формуле (54). Поэтому, если N и М разлагаются на множители, то каждую сумму можно вычислить по рекуррентным формулам типа (57). Если при этом A = Li и M = Li\ то число операций на каждый узел сетки, аналогично одномерному случаю, есть О (/•i£i +A-jLa) = 0 (log (TVM)). Следовательно, быстрое преобразование Фурье даже в многомерном случае по экономичности мало уступает самому быстрому одномерному методу - прогонке.

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

уравнений типа (46). При Ла = 2" исключение выполняет-

sgmM} и составим разностную схему

Jq {ут 2упт ~Ь Уп+1, т) ~Ь

+ Ц (Уп, т-1 - 2Упт + Уп, m+i) - РУл/п = - флт- (58)

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

а= 1

Большинство итерационных методов можно символически записать в аналогичной форме:

t + Ay--f; (63)

если В и т не зависят от номера итерации k, то процесс называют стационарным.

Итерационный процесс (63) можно рассматривать как разностную схему расчета некоторой эволюционной задачи. Эту задачу можно найти, определяя нулевое или первое дифференциальное приближение разностной схемы (63). Физический смысл найденной задачи не имеет значения; важно только, чтобы она соответствовала диссипативному процессу, т. е. обеспечивала бы установление стационарного решения. Тем самым, несущественно, что именно аппроксимирует оператор В; он должен только: а) обеспечивать возможно более быстрое затухание начальных дан-. ных и б) легко обращаться, чтобы решение г/* вычислялось за малое число действий.

ся рекуррентно и число действий на узел сетки составляет 0(!og,;V).

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

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

4. Итерационные методы. В случае сложных задач неэволюционные разностные схемы Ay = - f решают итерационными методами. Простейшим из них является метод Якоби (5.51), относящийся к методам последовательного приближения. Для двумерного уравнения (46) он имеет вид

Ц Щ] hf {Уп -f 1, т~Уп-\, т) + ц {Уп, т-l Уп, т+ l)~fnm

где fe -номер итерации. Это выражение можно формально переписать следующим образом:

1Упт - д2 (Упт Уп-1, и) (Упт Уп, m-l)>

Р-гУпт = {Упт Уп+1, т) ~Ь д (Упт Уп, m+l)>

(65)

определенные на треугольных шаблонах (шаблон для показан на рис. 90 жирными линиями). Нетрудно заметить, что Aj + Aj = =-(Р1 + Р2), что позволяет записать схему (64) следующим образом:

(£ + тР1 + тР2)-(Л1 + Л,)у = ф. (66)

Слегка изменим схему (66), добавляя в левую часть член xRyRiy - у)/г, имеющий порядок малости О (т). Возникающий при этом оператор E--xRy-j-xR-j-xRyR факторизуется, т. е. представляется в виде произведения операторов E-\-xRi и E--xR.

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

Попеременно-треугольная схема, которую мы рассмотрим на примере двумерного уравнения

Запишем вспомогательное параболическое уравнение:

Выберем шаблон, показанный на рис. 90, и составим на нем чисто неявную разностную схему

1(у-у) = (Л1 + Лз)у + ф,

которую можно переписать в канонической форме:

(£ гЛ, - тЛ,) - (Лх + А,) у = ф.

(64)

Как отмечалось выше, эта схема неэко- Рис. 90.

номична, поскольку обращение оператора

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

Введем треугольные операторы