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^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}x^{(k)}_j\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 \ne 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{align} 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{align}

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 je další iterace

: \begin{align} x_1 & = (6 + 0 - (2 \times 0)) / 10 = 0. 6, \\ x_2 & = (25 + 0 + 0 - (3 \times 0)) / 11 = 25/11 = 2. +more2727, \\ x_3 & = (-11 - (2 \times 0) + 0 + 0) / 10 = -1. 1,\\ x_4 & = (15 - (3 \times 0) + 0) / 8 = 1. 875. \end{align}.

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

Reference

Kategorie:Lineární algebra Kategorie:Matice