Метод Якоби

В числовой линейной алгебре , то метод Якоби представляет собой итерационный алгоритм для определения решений строго по диагонали доминирующей системы линейных уравнений . Решается для каждого диагонального элемента и подставляется приблизительное значение. Затем процесс повторяется до тех пор, пока он не сойдется. Этот алгоритм является урезанной версией метода диагонализации матриц с преобразованием Якоби . Метод назван в честь Карла Густава Якоба Якоби .

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

Позволять

${\ Displaystyle А \ mathbf {x} = \ mathbf {b}}$

- квадратная система из n линейных уравнений, где:

${\ displaystyle A = {\ begin {bmatrix} a_ {11} & a_ {12} & \ cdots & a_ {1n} \\ a_ {21} & a_ {22} & \ cdots & a_ {2n} \\\ vdots & \ vdots & \ ddots & \ vdots \\ a_ {n1} & a_ {n2} & \ cdots & a_ {nn} \ end {bmatrix}}, \ qquad \ mathbf {x} = {\ begin {bmatrix} x_ {1} \\ x_ {2} \\\ vdots \\ x_ {n} \ end {bmatrix}}, \ qquad \ mathbf {b} = {\ begin {bmatrix} b_ {1} \\ b_ {2} \\\ vdots \ \ b_ {n} \ end {bmatrix}}.}$

Тогда A можно разложить на диагональный компонент D , нижнюю треугольную часть L и верхнюю треугольную часть U :

${\displaystyle A=D+L+U\qquad {\text{where}}\qquad D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}}{\text{ and }}L+U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\a_{21}&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}}.}$

Затем решение итеративно получается через

${\displaystyle \mathbf {x} ^{(k+1)}=D^{-1}(\mathbf {b} -(L+U)\mathbf {x} ^{(k)}),}$

где - k- е приближение или итерация, а - следующая или k + 1 итерация . Таким образом, формула на основе элементов:${\displaystyle \mathbf {x} ^{(k)}}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {x} ^{(k+1)}}$${\displaystyle \mathbf {x} }$

${\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\neq i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n.}$

Для вычисления требуется каждый элемент в x ^{( k ),} кроме самого себя. В отличие от метода Гаусса-Зейделя , мы не можем переписать с , так как это значение будет необходимо в остальной части вычисления. Минимальный объем памяти - два вектора размера n .${\displaystyle x_{i}^{(k+1)}}$${\displaystyle x_{i}^{(k)}}$${\displaystyle x_{i}^{(k+1)}}$

Алгоритм [ править ]

Вход:  начальное предположение решения${\displaystyle x^{(0)}}$ , (диагональная доминантная) матрица , вектор правой части , критерий сходимости. Выход: решение при достижении сходимости. Комментарии: псевдокод, основанный на приведенной выше формуле на основе элементов.${\displaystyle A}$${\displaystyle b}$  ${\displaystyle k=0}$в то время как сходимость не достигнута не делать  для I: = 1 шаг до п сделать  для J: = 1 шаг , пока п не делать , если J ≠ я тогда положить конец конец конец конец${\displaystyle \sigma =0}$   ${\displaystyle \sigma =\sigma +a_{ij}x_{j}^{(k)}}$   ${\displaystyle x_{i}^{(k+1)}={{\frac {1}{a_{ii}}}\left({b_{i}-\sigma }\right)}}$  ${\displaystyle k=k+1}$

Конвергенция [ править ]

Стандартное условие сходимости (для любого итерационного метода) - это когда спектральный радиус итерационной матрицы меньше 1:

${\displaystyle \rho (D^{-1}(L+U))<1.}$

Достаточным (но не необходимым) условием сходимости метода является то, что матрица A строго или неприводимо диагонально доминантна . Строгое диагональное преобладание строки означает, что для каждой строки абсолютное значение диагонального члена больше, чем сумма абсолютных значений других членов:

${\displaystyle \left|a_{ii}\right|>\sum _{j\neq i}{\left|a_{ij}\right|}.}$

Метод Якоби иногда сходится, даже если эти условия не выполняются.

Обратите внимание, что метод Якоби не сходится для каждой симметричной положительно определенной матрицы . Например

${\displaystyle A={\begin{pmatrix}29&2&1\\2&6&1\\1&1&{\frac {1}{5}}\end{pmatrix}}\quad \Rightarrow \quad D^{-1}(L+U)={\begin{pmatrix}0&{\frac {2}{29}}&{\frac {1}{29}}\\{\frac {1}{3}}&0&{\frac {1}{6}}\\5&5&0\end{pmatrix}}\quad \Rightarrow \quad \rho (D^{-1}(L+U))\approx 1.0661\,.}$

Примеры [ править ]

Пример 1 [ править ]

Линейная система вида с начальной оценкой дается формулой${\displaystyle Ax=b}$${\displaystyle x^{(0)}}$

${\displaystyle A={\begin{bmatrix}2&1\\5&7\\\end{bmatrix}},\ b={\begin{bmatrix}11\\13\\\end{bmatrix}}\quad {\text{and}}\quad x^{(0)}={\begin{bmatrix}1\\1\\\end{bmatrix}}.}$

Для оценки мы используем уравнение , описанное выше . Сначала перепишем уравнение в более удобном виде , где и . Из известных ценностей${\displaystyle x^{(k+1)}=D^{-1}(b-(L+U)x^{(k)})}$${\displaystyle x}$${\displaystyle D^{-1}(b-(L+U)x^{(k)})=Tx^{(k)}+C}$${\displaystyle T=-D^{-1}(L+U)}$${\displaystyle C=D^{-1}b}$

${\displaystyle D^{-1}={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}},\ L={\begin{bmatrix}0&0\\5&0\\\end{bmatrix}}\quad {\text{and}}\quad U={\begin{bmatrix}0&1\\0&0\\\end{bmatrix}}.}$

мы определяем как${\displaystyle T=-D^{-1}(L+U)}$

${\displaystyle T={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}\left\{{\begin{bmatrix}0&0\\-5&0\\\end{bmatrix}}+{\begin{bmatrix}0&-1\\0&0\\\end{bmatrix}}\right\}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}.}$

Далее находится как${\displaystyle C}$

${\displaystyle C={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}{\begin{bmatrix}11\\13\\\end{bmatrix}}={\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}.}$

Имея и рассчитав, мы оцениваем как :${\displaystyle T}$${\displaystyle C}$${\displaystyle x}$${\displaystyle x^{(1)}=Tx^{(0)}+C}$

${\displaystyle x^{(1)}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}{\begin{bmatrix}1\\1\\\end{bmatrix}}+{\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}={\begin{bmatrix}5.0\\8/7\\\end{bmatrix}}\approx {\begin{bmatrix}5\\1.143\\\end{bmatrix}}.}$

Следующая итерация дает

${\displaystyle x^{(2)}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}{\begin{bmatrix}5.0\\8/7\\\end{bmatrix}}+{\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}={\begin{bmatrix}69/14\\-12/7\\\end{bmatrix}}\approx {\begin{bmatrix}4.929\\-1.714\\\end{bmatrix}}.}$

Этот процесс повторяется до схождения (т. Е. До тех пор, пока не станет маленьким). Решение после 25 итераций:${\displaystyle \|Ax^{(n)}-b\|}$

${\displaystyle x={\begin{bmatrix}7.111\\-3.222\end{bmatrix}}.}$

Пример 2 [ править ]

Предположим, нам дана следующая линейная система:

${\displaystyle {\begin{aligned}10x_{1}-x_{2}+2x_{3}&=6,\\-x_{1}+11x_{2}-x_{3}+3x_{4}&=25,\\2x_{1}-x_{2}+10x_{3}-x_{4}&=-11,\\3x_{2}-x_{3}+8x_{4}&=15.\end{aligned}}}$

Если мы выберем (0, 0, 0, 0) в качестве начального приближения, то первое приближенное решение будет иметь вид

${\displaystyle {\begin{aligned}x_{1}&=(6+0-(2*0))/10=0.6,\\x_{2}&=(25+0+0-(3*0))/11=25/11=2.2727,\\x_{3}&=(-11-(2*0)+0+0)/10=-1.1,\\x_{4}&=(15-(3*0)+0)/8=1.875.\end{aligned}}}$

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

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle x_{4}}$
0,6	2,27272	-1,1	1,875
1,04727	1,7159	-0,80522	0,88522
0,93263	2,05330	-1,0493	1,13088
1.01519	1,95369	-0,9681	0,97384
0,98899	2,0114	-1,0102	1,02135

Точное решение системы - (1, 2, −1, 1) .

Пример Python [ править ]

импортировать  numpy  как  npITERATION_LIMIT  =  1000# инициализируем матрицуА  =  np . массив ([[ 10. ,  - 1. ,  2. ,  0. ], [ - 1. ,  11. ,  - 1. ,  3. ], [ 2. ,  - 1. ,  10. ,  - 1. ], [ 0.0 ,  3. ,  - 1. ,  8. ]])# инициализировать вектор RHSб  =  нп . массив ([ 6. ,  25. ,  - 11. ,  15. ])# печатает системуprint ( "Система:" )для  я  в  диапазоне ( A . формы [ 0 ]): row  =  [ " {} * x {} " . Формат ( [ я , J ], J + 1 ) для J в диапазоне ( . форма [ 1 ])]         print ( "+" . join ( строка ),  "=" ,  b [ i ])печать ()х  =  нп . zeros_like ( b )для  it_count  в  диапазоне ( ITERATION_LIMIT ): если  it_count  ! =  0 : print ( "Итерация {0} : {1} " . format ( it_count ,  x )) x_new  =  np . zeros_like ( x ) для  я  в  диапазоне ( A . формы [ 0 ]): s1  =  np . Точка ( [ я , : я ], х [: я ])   s2  =  np . точка ( A [ i ,  i  +  1 :],  x [ i  +  1 :]) x_new [ i ]  =  ( b [ i ]  -  s1  -  s2 )  /  A [ i ,  i ] если  x_new [ i ]  ==  x_new [ i - 1 ]: перемена если  нп . allclose ( x ,  x_new ,  atol = 1e-10 ,  rtol = 0. ): перемена x  =  x_newprint ( "Решение:" )печать ( х )ошибка  =  нп . точка ( A ,  x )  -  bprint ( "Ошибка:" )печать ( ошибка )

Взвешенный метод Якоби [ править ]

Взвешенная итерация Якоби использует параметр для вычисления итерации как${\displaystyle \omega }$

${\displaystyle \mathbf {x} ^{(k+1)}=\omega D^{-1}(\mathbf {b} -(L+U)\mathbf {x} ^{(k)})+\left(1-\omega \right)\mathbf {x} ^{(k)}}$

с обычным выбором. ^[1] Исходя из соотношения , это также может быть выражено как${\displaystyle \omega =2/3}$${\displaystyle L+U=A-D}$

${\displaystyle \mathbf {x} ^{(k+1)}=\omega D^{-1}\mathbf {b} +\left(I-\omega D^{-1}A\right)\mathbf {x} ^{(k)}}$.

Сходимость в симметричном положительно определенном случае [ править ]

В случае, если матрица системы имеет симметричный положительно определенный тип, можно показать сходимость. ${\displaystyle A}$

Позвольте быть итерационной матрицей. Тогда сходимость гарантирована для${\displaystyle C=C_{\omega }=I-\omega D^{-1}A}$

${\displaystyle \rho (C_{\omega })<1\quad \Longleftrightarrow \quad 0<\omega <{\frac {2}{\lambda _{\text{max}}(D^{-1}A)}}\,,}$

где - максимальное собственное значение.${\displaystyle \lambda _{\text{max}}}$

Спектральный радиус может быть минимизирован для конкретного выбора следующим образом${\displaystyle \omega =\omega _{\text{opt}}}$

${\displaystyle \min _{\omega }\rho (C_{\omega })=\rho (C_{\omega _{\text{opt}}})=1-{\frac {2}{\kappa (D^{-1}A)+1}}\quad {\text{for}}\quad \omega _{\text{opt}}:={\frac {2}{\lambda _{\text{min}}(D^{-1}A)+\lambda _{\text{max}}(D^{-1}A)}}\,,}$

где - номер обусловленности матрицы .${\displaystyle \kappa }$

См. Также [ править ]

• Метод Гаусса – Зейделя
• Последовательное чрезмерное расслабление
• Итерационный метод § Линейные системы
• Распространение гауссовской веры
• Расщепление матрицы

Ссылки [ править ]

Внешние ссылки [ править ]

• Эта статья включает текст из статьи Jacobi_method на CFD-Wiki , находящейся под лицензией GFDL .

• Блэк, Ноэль; Мур, Ширли и Вайсштейн, Эрик В. «Метод Якоби» . MathWorld .
• Метод Якоби с сайта www.math-linux.com