метод Якоби

Итерационный метод, используемый для решения линейной системы уравнений

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

Описание

Пусть будет квадратной системой из n линейных уравнений, где: ${\displaystyle A\mathbf {x} =\mathbf {b} }$ $${\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}}.}$$

Когда и известны, а неизвестно, мы можем использовать метод Якоби для аппроксимации . Вектор обозначает наше первоначальное предположение для (часто для ). Мы обозначаем как k -е приближение или итерацию , а является следующей (или k +1) итерацией . ${\displaystyle A}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} ^{(0)}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} _{i}^{(0)}=0}$ ${\displaystyle i=1,2,...,n}$ ${\displaystyle \mathbf {x} ^{(k)}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} ^{(k+1)}}$ ${\displaystyle \mathbf {x} }$

Формула на основе матрицы

Тогда 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)}).}$

Формула на основе элементов

Формула на основе элементов для каждой строки выглядит следующим образом: Вычисление требует каждый элемент из, за ​​исключением самого себя. В отличие от метода Гаусса–Зейделя , мы не можем перезаписать с помощью , так как это значение понадобится для остальной части вычисления. Минимальный объем памяти составляет два вектора размера n . ${\displaystyle i}$ $${\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.}$$ ${\displaystyle x_{i}^{(k+1)}}$ ${\displaystyle \mathbf {x} ^{(k)}}$ ${\displaystyle x_{i}^{(k)}}$ ${\displaystyle x_{i}^{(k+1)}}$

Алгоритм

Вход:  начальное приближение x (0) к решению , (диагональная доминирующая) матрица A , правый вектор b , критерий сходимости Выход:  решение при достижении сходимости Комментарии: псевдокод, основанный на приведенной выше формуле на основе элементовk = 0 пока сходимость не достигнута сделать  для  i  := 1 шаг до n сделать  σ = 0  для  j  := 1 шаг до n сделать  если  j ≠ i  тогда  σ = σ + a ij  x j ( k )  конец  конец  x i ( k +1) = ( b i − σ ) / a ii  конец приращение k конец

Конвергенция

Стандартное условие сходимости (для любого итерационного метода) — когда спектральный радиус итерационной матрицы меньше 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\,.}$$

Примеры

Пример вопроса

Линейная система вида с начальной оценкой задается выражением ${\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}}.}$

Используем уравнение , описанное выше, для оценки . Сначала перепишем уравнение в более удобном виде , где и . Из известных значений определяем как Далее находится как При и вычисляется, оцениваем как : Следующая итерация дает Этот процесс повторяется до сходимости (т.е. пока не станет малым). Решение после 25 итераций имеет вид ${\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}}.}$$ ${\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}}}$$

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

Пример на Python

импортировать  numpy  как  npПРЕДЕЛ_ИТЕРАЦИИ  =  1000# инициализируем матрицуA  =  np . массив ([[ 10. ,  - 1. ,  2. ,  0. ], [ - 1. ,  11. ,  - 1. ,  3. ], [ 2. ,  - 1. ,  10. ,  - 1. ], [ 0.0 ,  3. ,  - 1. ,  8. ]])# инициализируем вектор RHSb  =  np . массив ([ 6. ,  25. ,  - 11. ,  15. ])# печатает системупечать ( "Система:" )для  i  в  диапазоне ( A . shape [ 0 ]): row  =  [ f " { A [ i , j ] } *x { j + 1 } " для j в диапазоне ( A . shape [ 1 ])]        print ( f ' { "+" . join ( row ) } = { b [ i ] } ' )печать ()x  =  np . zeros_like ( b )для  it_count  в  диапазоне ( ITERATION_LIMIT ): если  it_count  !=  0 : print ( f "Итерация { it_count } : { x } " ) x_new  =  np . zeros_like ( x ) для  i  в  диапазоне ( A . shape [ 0 ]): s1  =  np . точка ( A [ i ,  : i ],  x [: i ]) 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 ]: перерыв если  np.allclose ( x , x_new , atol = 1e- 10 , rtol = 0. ) :    перерыв х  =  х_новыйпечать ( "Решение: " )печать ( х )ошибка  =  np . точка ( A ,  x )  -  bпечать ( "Ошибка:" )печать ( ошибка )

Метод взвешенного Якоби

Взвешенная итерация Якоби использует параметр для вычисления итерации как ${\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 }$

Смотрите также

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

Ссылки

1. Саад, Юсеф (2003). Итерационные методы для разреженных линейных систем (2-е изд.). SIAM . стр. 414. ISBN 0898715342.

Внешние ссылки

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

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