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

Материал из Википедии — свободной энциклопедии

У этого термина существуют и другие значения, см. метод покоординатного спуска.

Метод Гаусса—Зейделя^[1] является классическим итерационным методом решения системы линейных уравнений. Отметим, что этот метод не был известен Зейделю и презирался Гауссом как бесполезный — таковы капризы исторической точности в науке.

[править] Постановка задачи

Возьмём систему:

$A\vec{x}=\vec{b}$ , где $A=\left( \begin{array}{ccc} a_{11} & \ldots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \ldots & a_{nn} \end{array} \right),\quad \vec{b}=\left( \begin{array}{c} b_1 \\ \vdots \\ b_n \end{array} \right)$

Или $\left\{ \begin{array}{rcl} a_{11}x_1 + \ldots + a_{1n}x_n& = & b_{1} \\ & &\\ a_{n1}x_1 + \ldots + a_{nn}x_n & = & b_{n} \end{array} \right.$

И покажем, как её можно решить с использованием метода Гаусса-Зейделя.

[править] Метод

Чтобы пояснить суть метода, перепишем задачу в виде:

$\left\{ \begin{array}{lcr} a_{11}x_1 & = &-a_{12}x_2 - a_{13}x_3 -\ldots - a_{1n}x_n + b_1\\ a_{21}x_1 + a_{22}x_2 & = & -a_{23}x_3 - \ldots - a_{2n}x_n + b_2\\ \ldots & &\\ a_{n1}x_1 + a_{n2}x_2 +\ldots+ a_{(n-1)(n-1)}x_{n-1} & = & -a_{nn}x_n + b_n\\ a_{n1}x_1 + a_{n2}x_2 +\ldots+ a_{(n-1)(n-1)}x_{n-1}+ a_{nn}x_n & = & b_n \end{array} \right.$

Здесь в $j$ -м уравнении мы перенесли в правую часть все члены, содержащие $x i$ , для $i > j$ . Эта запись может быть представлена:

$(\mathrm{L} + \mathrm{D} )\vec{x} = -\mathrm{U} \, \vec{x} + \vec{b},$

где в принятых обозначениях D означает матрицу, у которой на главной диагонали стоят соответствующие элементы матрицы A, а все остальные нули; тогда как матрицы U и L содержат верхнюю и нижнюю треугольные части A, и на главной диагонали которых нули.

Итеративный процесс в методе Гаусса-Зейделя строится по формуле $(\mathrm{L} + \mathrm{D} )\vec{x}^{(k+1)} = -\mathrm{U} \vec{x}^{(k)} + \vec{b} ,\quad k = 0, 1, 2, \ldots$ после выбора соответствующего начального приближения $\vec{x}^{(0)}$ .

Метод Гаусса-Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что новые значения $\vec{x}^{(i)}$ используются здесь сразу же по мере получения, в то время как в методе Якоби они не используются до следующей итерации:

$\left\{\begin{array}{ccccccccccc} {x_{1}}^{(k+1)} &=& c_{12}{x_2^{(k)}} &+& c_{13}x_3^{(k)}&+& {\ldots}&+& c_{1n}{x_n}^{(k)} &+& d_1 \\ {x_{2}}^{(k+1)} &=& c_{21}{x_1^{(k+1)}} &+& c_{23}x_3^{(k)}&+& {\ldots}&+& c_{2n}{x_n}^{(k)} &+& d_2 \\ \ldots & & & & & & & & & & \\ {x_{n}}^{(k+1)} &=& c_{n1}{x_1^{(k+1)}} &+& c_{n2}{x_2^{(k+1)}}&+& {\ldots}&+& c_{n(n-1)}{x_{n-1}}^{(k+1)} &+& d_n \end{array}\right.,$

где $c_{ij}=-\frac{a_{ij}}{a_{ii}},\quad d_i=\frac{b_i}{a_{ii}},\quad i=1,\ldots,n$

Таким образом i-тая компонента $(k + 1)$ -го приближения вычисляется по формуле:

$x_i^{(k+1)}=\sum_{j=1}^{i-1}c_{ij}x_{j}^{(k+1)}+\sum_{j=i}^{n}c_{ij}x_{j}^{(k)}+d_i, \quad i=1,\ldots,n$

[править] Условие сходимости

Приведем достаточное условие сходимости метода.

Теорема.
Пусть $\| \mathrm{A}_2 \| < 1\!$ , где $\mathrm{A}_2 = -(\mathrm{L} + \mathrm{D})^{-1} \, \mathrm{U}, \quad (\mathrm{L} + \mathrm{D})^{-1}\!$ – матрица, обратная к $(\mathrm{L} + \mathrm{D})\!$ . Тогда при любом выборе начального приближения $\vec{x}^{(0)}\!$ :

метод Гаусса-Зейделя сходится;
скорость сходимости метода равна скорости сходимости геометрической прогрессии со знаменателем $q = \|\mathrm{A}_2\|\!$ ;
верна оценка погрешности: $\|\vec{x}^{(k)}-\vec{x}\|=q^k \, \|\vec{x}^{(0)}-\vec{x}\|\!$ .