Метод Якоби

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

Метод Якоби — метод простой итерации для решения системы линейных алгебраических уравнений.

Содержание

1 Постановка задачи
2 Описание метода
3 Условие сходимости
4 Условие остановки
5 Алгоритм
6 См. также

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

Возьмём систему линейных уравнений:

$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.$

[править] Описание метода

Для того, чтобы построить итеративную процедуру метода Якоби, необходимо провести предварительное преобразование системы уравнений $A\vec{x}=\vec{b}$ к итерационному виду $\vec{x}=B\vec{x}+\vec{g}$ . Оно может быть осуществлено по одному из следующих правил:

$B = E-D^{-1}A,\quad \vec{g}=D^{-1}\vec{b};$

$B = -D^{ - 1}(L + U),\quad \vec{g}=D^{-1}\vec{b}$

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

Тогда процедура нахождения решения имеет вид:

$\vec{x}^{(k+1)} = B \vec{x}^{(k)}+\vec{g},$

где $k$ счётчик итерации.

В отличие от метода Гаусса-Зейделя мы не можем заменять $x^{(k)}_i\,$ на $x^{(k+1)}_i$ в процессе итерационной процедуры, т.к. эти значения понадобятся для остальных вычислений. Это наиболее значимое различие между методом Якоби и методом Гаусса-Зейделя решения СЛАУ. Таким образом на каждой итерации придётся хранить оба вектора приближений: старый и новый.

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

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

Теорема.
Пусть $\| B \| < 1\!$ . Тогда при любом выборе начального приближения $\vec{x}^{(0)}\!$ :

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