Jacobiho metoda

V lineární algebře je Jacobiho metoda (též Jacobiova metoda) iteračním algoritmem pro numerické řešení soustavy lineárních rovnic. Je založena na rozkladu matice soustavy na součet dvou komponent, z nichž jedna je diagonální a je díky tomu snadné určit její inverzní matici. V nematicové formulaci postup odpovídá tomu, že v každé iteraci se použitím přibližných hodnot řešení z každé rovnice vypočítá diagonální prvek, který představuje novou iteraci a přesnější odhad řešení. Metoda je pojmenována po Carlu Gustavu Jacobim.

Princip metody

Nechť

${\displaystyle A\mathbf {x} =\mathbf {b} }$

je soustava n lineárních rovnic o n neznámných, kde:

${\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}}.}$

Potom lze A rozložit na diagonální složku D a složku N s nulami v hlavní diagonále.

${\displaystyle A=D+N\qquad {\text{kde}}\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{ a }}N={\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}}}$

Rovnici je potom možno přepsat do tvaru

${\displaystyle D\mathbf {x} =\mathbf {b} -N\mathbf {x} ,}$

tj.

${\displaystyle \mathbf {x} =D^{-1}(\mathbf {b} -N\mathbf {x} ).}$

Řešení této úlohy je potom možno v některých případech (viz níže podmínka konvergence) získat iterací vztahu

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

kde ${\displaystyle \mathbf {x} ^{(k)}}$ je k-tá iterace ${\displaystyle \mathbf {x} }$ a ${\displaystyle \mathbf {x} ^{(k+1)}}$ je další iterace ${\displaystyle \mathbf {x} }$. Po rozepsání na jednotlivé prvky mají iterace tvar

${\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.}$

Konvergence metody

Postačující podmínkou pro konvergenci metody je, že matice A je řádkově ostře diagonálně dominantní. To znamená, že pro každý řádek je absolutní hodnota diagonálního členu větší než součet absolutních hodnot ostatních členů:

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

Tato podmínka není nutná. Jacobiho metoda může konvergovat i pro matice, které tuto podmínku nesplňují.

Příklad v nematicové formulaci

Řešení soustavy

${\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}}}$

spočívá v nalezení hodnoty ${\displaystyle x_{1}}$ z první rovnice, přičemž ostatní neznámé nabývají hodnoty zvolené počáteční iterací. Z druhé rovnice se podobně určí hodnota ${\displaystyle x_{2}}$ atd.

Pro počáteční iteraci (0, 0, 0, 0) je další iterace

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

Toto je další odhad řešení. Postup se opakuje a v tabulce jsou shrnuta přibližná řešení po pěti iteracích.

${\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

Přesné řešení soustavy je (1, 2, −1, 1) .

Reference

V tomto článku byl použit překlad textu z článku Jacobi method na anglické Wikipedii.