Эти коэффициенты связаны с элементами матрицы А посредством формул

Я/.. = ж..-лЛ-ы..-1~2ар}, (6.72)

=-f-

Параметр a использован здесь для ускорения сходимости, причем значение а - 0.5 близко к оптимальному. Как указывается в работе [Schneider, Zedan, 1981], схема МСН оказывается, как правило, в два-четыре раза экономичнее, чем схема СНП, и притом не требует перенумерации узлов сетки после каждой итерации, как это имеет место в случае СНП.

Информация об использовании существенно неявных процедур, по своей формулировке аналогичных изложенному выше, имеется в работах [Rubin, Khosla, 1981; Zedan, Schneider, 1985; Lin, 1985].

6,3.4. Методы ускорения сходимости

Различные методы итераций, описываемые в п. 6.3.1-6.3.3, являются эффективными, но при решении некоторых задач обнаруживают довольно медленную сходимость после того, как невязка R испытает быстрое начальное уменьшение. Если ошибку итерационного решения е = V(*> - разложить в ряд Фурье, то быстрое начальное уменьшение невязки соответствует уменьшению амплитуды коротковолновых мод ряда Фурье. Последующее уменьшение амплитуды длинноволновых мод зачастую протекает со значительно меньшей скоростью.

Имеется, однако, возможность модифицировать уже рассмотренные нами итерационные методы для ускорения сходимости. Два наиболее эффективных для этого метода - это метод ускорения по Чебышёву и метод ускорения с сопряженными градиентами [Hageman, Young, 1981]. Здесь мы дадим описание важнейших особенностей метода ускорения с сопряженными градиентами.

Первоначально будет предполагаться, что матрица А в уравнении (6.2) является симметричной и положительно определенной. Иначе говоря, при любом выборе х будет хАх > 0.

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

Последовательность шагов при применении традиционного метода сопряженных градиентов [Hestenes, Stiefel, 1952] можно описать в следующем виде:

1) Vrt+I) = у in) я,<*)р(п)

2) R(+0 = R(n) n)u( ),

3) p< +) = (R(r+l)f R),

4) aCnP-,

5) p(n+i) an+i)p(n) (6.73)

6) Uin+\)xp{n+\)

(р( +П)Гу( +1)

Данный алгоритм оказывается сравнительно экономичным, так как он требует только одного матрично-векторного умножения на этапе (6). Можно отметить, что невязка R+i) вычисляется рекурсивно по результатам шага (2), а не из соотношения ц(п+1) В - AV<+>. За параметром р) ведется наблюдение с целью уловить приближение сходимости. В отличие от схемы ПВР (п. 6.3.1) метод сопряженных градиентов не содержит эмпирически подбираемых параметров.

В формулах (6.73) вектор Р определяет направление поиска, которое в начале итерационного процесса задается равенством Р<°> = R(°>. Выбор параметра а(*+*) в формулах (6.73) гарантирует, что направления поиска Р(> будут взаимно сопряженными (ортогональными) в смысле выполнения условия

р(ОГАр(/) = о при (6.74)

Кроме того, данный алгоритм обеспечивает, что R(>R<> = О при гф}. Все эти особенности делают алгоритм весьма эффективным и в отсутствие ошибок округления он мог бы способствовать построению решения системы из линейных алгебраических уравнений (6.2) не более чем за итераций. Параметр Хе* в формулах (6.73) выбирается так, чтобы эквивалентная квадратичная функция

F (V) = 0.5VAV - VB (6.75)

имела минимум в направлении Р( ) при V< +).

Если невязка R разлагается в ряд по собственным функциям матрицы А, то можно установить, что каждый шаг метода сопряженных градиентов воздействует таким образом, что как бы приближенно исключает вклады от каждого из собственных векторов по очереди [Jennings, 1977b]. Следовательно, если некоторые из собственных значений А собраны в единую группу, то сходимость достигается менее чем за итераций.

Если, кроме того, оказывается возможным произвести предварительное умножение отдельных членов уравнения (6.2) так, чтобы собственные значения полученной в результате матрицы были сгруппированы более тесно, чем для матрицы А, а разброс собственных значений (Хтш, Ятах) был несколько уменьшен, то последующее применение метода сопряженных градиентов к предварительно подготовленной системе обеспечивает более быструю сходимость. Наилучший вариант выбора кондиционирующего множителя состоит в умножении на А~ так как после этого решение будет тривиальным. Хорошим вариантом является множитель N- фигурирующий в формуле (6.51), соответствующей итерационному методу решения стационарных задач общего вида. На этом основании вместо (6.2) запишем

N-4V = N B. (6.76)

Чтобы можно было применять вышеописанный вариант метода сопряженных градиентов, необходимо комплекс N-A сделать симметричным. Этого можно добиться, формируя комбинацию WN-AW- где матрица W обычно выбирается так, чтобы получить WW = N. В результате вместо (6.76) получим

AV = B, (6.77)

А = WNAW-\ V = WV, В = WN B.

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

На практике уравнение (6.77) не формируется явным образом. Вместо шагов, соответствующих формулам (6.73), делается следующее:

1) \{п+1) = v -f Л< )Р<>,

2) d+i) = б) - Л< )и*>, Rt+O = W6< +i) = WN *R*+>,

3) p<+) = (R(n+i))(+i),