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ť

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

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

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

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

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

tj.

\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

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

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

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ů:

\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

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

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

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

$x_{1}$	$x_{2}$	$x_{3}$	$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.