Валях Е. Последовательно-параллельные вычисления. – М.: Мир, 1985, стр 277.

Итерационные методы

Итак, требуется решить уравнение

$\begin{displaymath} \mbox{${\rm A}$}\mbox{\boldmath${\rm\bf f}$} = \mbox{\boldmath${\rm\bf g}$} , \end{displaymath}$

(5.1)

где $\mbox{${\rm A}$}$ -- квадратная $n \times n$ матрица с элементами $a_{ij}$ , $\mbox{\boldmath${\rm\bf f}$}=(f_1,\ldots ,f_n)$ , $\mbox{\boldmath${\rm\bf g}$}=(g_1,\ldots ,g_n)$ -- -мерные векторы. Итерационные методы решения системы (5.1) позволяют строить последовательность приближений (итераций) $\{\mbox{\boldmath${\rm\bf f}$}^k\}^\infty_{k=0}$ . Если эта последовательность имеет предел, то предел называется решением системы (5.1):

$\begin{displaymath} \mbox{\boldmath ${\rm\bf f}$}=\lim_{k\to\infty}\mbox{\boldmath ${\rm\bf f}$}^k . \end{displaymath}$

Очередное приближение строится с помощью рекуррентной формулы

$\begin{displaymath} \mbox{\boldmath ${\rm\bf f}$}^{k+1}=\mbox{\boldmath ${\rm\bf... ...th ${\rm\bf f}$}^0,\ldots ,\mbox{\boldmath ${\rm\bf f}$}^k) , \end{displaymath}$

где -- номер итерации. Преимущественно используется простейшая рекуррентная формула

$\begin{displaymath} \mbox{\boldmath ${\rm\bf f}$}^{k+1}=\mbox{${\rm B}$}\mbox{\boldmath ${\rm\bf f}$}^k+\mbox{\boldmath ${\rm\bf h}$} , \end{displaymath}$

где $\mbox{${\rm B}$}$ -- квадратная $n \times n$ матрица, а $\mbox{\boldmath${\rm\bf h}$}$ -- -мерный вектор. Для организации счета по такой формуле требуется задание некоего начального приближения $\mbox{\boldmath${\rm\bf f}$}^0$ . Вид матрицы $\mbox{${\rm B}$}$ и вектора $\mbox{\boldmath${\rm\bf h}$}$ определяет тот или иной итерационный метод. Рассмотрим наиболее часто встречающиеся методы.

Метод последовательных приближений (метод Якоби).

Исходная система (5.1) преобразуется к виду

$\begin{displaymath} \mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=(\mbox{${\rm A... ...\mbox{\boldmath ${\rm\bf f}$}=\mbox{\boldmath ${\rm\bf g}$} , \end{displaymath}$

где $\mbox{${\rm I}$}$ -- единичная матрица, и далее,

$\begin{displaymath} \mbox{\boldmath ${\rm\bf f}$}=(\mbox{${\rm I}$}-\mbox{${\rm ... ...\mbox{\boldmath ${\rm\bf f}$}+\mbox{\boldmath ${\rm\bf g}$} . \end{displaymath}$

Счет организуется по формуле

$\begin{displaymath} \mbox{\boldmath${\rm\bf f}$}^{k+1}=(\mbox{${\rm I}$}-\mbox{$... ...\mbox{\boldmath${\rm\bf f}$}^k+\mbox{\boldmath${\rm\bf g}$} . \end{displaymath}$

(5.2)

Таким образом $\mbox{${\rm B}$}=\mbox{${\rm I}$}-\mbox{${\rm A}$}$ , a $\mbox{\boldmath${\rm\bf h}$}=\mbox{\boldmath${\rm\bf g}$}$ .

Метод простой итерации.

Представим матрицу $\mbox{${\rm A}$}$ в виде суммы

$\begin{displaymath} \mbox{${\rm A}$}=\mbox{${\rm L}$}+\mbox{${\rm D}$}+\mbox{${\rm R}$} , \end{displaymath}$

(5.3)

где $\mbox{${\rm D}$}$ -- диагональная матрица с элементами $a_{ii}$ , $\mbox{${\rm L}$}$ и $\mbox{${\rm R}$}$ -- нижняя и верхняя треугольные матрицы, состоящие из соответствующих элементов исходной матрицы $\mbox{${\rm A}$}$ . Система (5.1) подвергается далее следующему преобразованию:

$\begin{displaymath} \mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=(\mbox{${\rm A... ...\mbox{\boldmath ${\rm\bf f}$}=\mbox{\boldmath ${\rm\bf g}$} , \end{displaymath}$

откуда получаем

$\begin{displaymath} \mbox{\boldmath ${\rm\bf f}$}^{k+1}=\mbox{${\rm D}$}^{-1}(\m... ...f f}$}^k+\mbox{${\rm D}$}^{-1}\mbox{\boldmath ${\rm\bf g}$} , \end{displaymath}$

$\begin{displaymath} \mbox{${\rm B}$}=\mbox{${\rm D}$}^{-1}(\mbox{${\rm D}$}-\mbo... ...m\bf h}$}=\mbox{${\rm D}$}^{-1}\mbox{\boldmath${\rm\bf g}$} . \end{displaymath}$

(5.4)

Матрица $\mbox{${\rm D}$}^{-1}$ , обратная диагональной матрице $\mbox{${\rm D}$}$ , вычисляется просто, поскольку также является диагональной с элементами $1/a_{ii}$ .

Метод Гаусса-Зейделя.

Снова запишем матрицу в виде (5.3), а систему (5.1) преобразуем к виду

$\begin{displaymath} \mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=(\mbox{${\rm L... ...\mbox{\boldmath ${\rm\bf f}$}=\mbox{\boldmath ${\rm\bf g}$} . \end{displaymath}$

Отсюда получаем рекуррентную формулу

$\begin{displaymath} \mbox{\boldmath ${\rm\bf f}$}^{k+1}=-(\mbox{${\rm L}$}+\mbox... ...rm L}$}+\mbox{${\rm D}$})^{-1}\mbox{\boldmath ${\rm\bf g}$} , \end{displaymath}$

$\begin{displaymath} \mbox{${\rm B}$}=-(\mbox{${\rm L}$}+\mbox{${\rm D}$})^{-1}\m... ...rm L}$}+\mbox{${\rm D}$})^{-1}\mbox{\boldmath ${\rm\bf g}$} . \end{displaymath}$

Метод последовательной релаксации

Пусть $\tau>0$ -- число, которое мы будем называть параметром релаксации. Умножим на это число систему (5.1)

$\begin{displaymath} \tau\mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=\tau\mbox{\boldmath ${\rm\bf g}$} \end{displaymath}$

и преобразуем ее следующим образом:

$\begin{displaymath} \tau\mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=(\tau\mbox... ...box{${\rm D}$}-\mbox{${\rm D}$})\mbox{\boldmath ${\rm\bf f}$}= \end{displaymath}$

$\begin{displaymath} =(\tau\mbox{${\rm L}$}+\mbox{${\rm D}$})\mbox{\boldmath ${\r... ...x{\boldmath ${\rm\bf f}$}=\tau\mbox{\boldmath ${\rm\bf g}$} . \end{displaymath}$

В результате получаем рекуррентную формулу

$\begin{displaymath} \mbox{\boldmath ${\rm\bf f}$}^{k+1}=-(\tau\mbox{${\rm L}$}+\... ...}$}+\mbox{${\rm D}$})^{-1}\tau\mbox{\boldmath ${\rm\bf g}$} , \end{displaymath}$

$\begin{displaymath} \mbox{${\rm B}$}=-(\tau\mbox{${\rm L}$}+\mbox{${\rm D}$})^{-... ...}$}+\mbox{${\rm D}$})^{-1}\tau\mbox{\boldmath ${\rm\bf g}$} . \end{displaymath}$

Параметр релаксации используется для настройки метода на максимальную скорость сходимости и обычно подбирается эмпирически. При этом $\tau\in(0,2)$ . Если $\tau>1$ , получаем метод верхней релаксации, если $\tau<1$ -- метод нижней релаксации.