next up previous contents
Next: OR (overrelaxation) metode Up: Rješavanje sustava jednadžbi Previous: Jacobijeva metoda   Contents


Gauss-Seidelova metoda

Gauss-Seidelova metoda je poboljšanje Jacobijeve metode u sljedećem smislu.

Pod pretpostavkom da je

% latex2html id marker 28412
$\displaystyle \boldsymbol{x}^{(k)}=\left[
\begin{array}{c}
x_1^{(k)} \\  x_2^{(k)} \\  \vdots \\  x_n^{(k)}
\end{array}\right]$

$ k$-ta aproksimacija rješenja, $ k+1$-vu nalazimo iz sustava
$\displaystyle a_{1\,1}\,x_{1}^{(k+1)} + a_{1\,2}\,x_{2}^{(k)} + \cdots +
a_{1\,n}\,x_{n}^{(k)}$ $\displaystyle =$ $\displaystyle b_1$  
$\displaystyle a_{2\,1}\,x_{1}^{(k+1)} + a_{2\,2}\,x_{2}^{(k+1)} + \cdots +
a_{2\,n}\,x_{n}^{(k)}$ $\displaystyle =$ $\displaystyle b_2$  
$\displaystyle \cdots$      
$\displaystyle a_{n\,1}\,x_{1}^{(k+1)} + a_{n\,2}\,x_{2}^{(k+1)} + \cdots +
a_{n\,n}\,x_{n}^{(k+1)}$ $\displaystyle =$ $\displaystyle b_n$  

Dakle $ x_1^{(k+1)},$ koji smo izračunali iz prve jednadžbe pomoću komponenti $ k$-te aproksimacije rješenja, koristimo odmah u drugoj, trećoj, ..., $ n$-toj jednadžbi; $ x_2^{(k+1)}$ koristimo u trećoj, četvrtoj, ..., $ n$-toj jednadžbi; itd. Taj sustav možemo zapisati u matričnom obliku

$\displaystyle (L + D)\,\boldsymbol{x}^{(k+1)} + R\,\boldsymbol{x}^{(k)} = \boldsymbol{b},$

odnosno

$\displaystyle (L + D)\,\boldsymbol{x}^{(k+1)} = -R\,\boldsymbol{x}^{(k)} + \boldsymbol{b}.$

Tako imamo formulu iterativnog postupka

$\displaystyle \boldsymbol{x}^{(k+1)} = -(L + D)^{-1}\,R\,\boldsymbol{x}^{(k)} + (L +
D)^{-1}\,\boldsymbol{b}.$

Nedostatak ove formule je u tome što treba naći inverz matrice $ L+D,$ što je općenito bitno teže nego naći inverz od $ D.$ Zato radimo malo drukčije. Pomnožimo ovu jednadžbu s $ D^{-1}.$

$\displaystyle (D^{-1}\,L + I)\,\boldsymbol{x}^{(k+1)} = -D^{-1}\,R\,\boldsymbol{x}^{(k)} +
D^{-1}\,\boldsymbol{b}.$

Odatle

$\displaystyle \boldsymbol{x}^{(k+1)} = -D^{-1}\,L\,\boldsymbol{x}^{(k+1)} -D^{-1}\,R\,\boldsymbol{x}^{(k)} +
D^{-1}\,\boldsymbol{b}.$

Tako dolazimo do sljedećeg algoritma.

Algoritam 6   (Gauss-Seidelova metoda) Izaberemo proizvoljnu početnu aproksimaciju

% latex2html id marker 28466
$\displaystyle \boldsymbol{x}^{(0)}=\left[
\begin{array}{c}
x_1^{(0)} \\  x_2^{(0)} \\  \vdots \\  x_n^{(0)}
\end{array}\right],$

i zatim računamo sljedeće aproksimacije $ \boldsymbol{x}^{(n)}$ po formuli

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

odnosno
$\displaystyle x_{1}^{(k+1)}$ $\displaystyle =$ $\displaystyle \alpha_{1\,2}\,x_{2}^{(k)} +
\alpha_{1\,3}\,x_{3}^{(k)} + \cdots + \alpha_{1\,n}\,x_{n}^{(k)} +
\beta_1$  
$\displaystyle x_{2}^{(k+1)}$ $\displaystyle =$ $\displaystyle \alpha_{2\,1}\,x_{1}^{(k+1)} +
\alpha_{2\,3}\,x_{3}^{(k)} + \cdots + \alpha_{2\,n}\,x_{n}^{(k)}+
\beta_2$  
$\displaystyle \cdots$      
$\displaystyle x_{n}^{(k+1)}$ $\displaystyle =$ $\displaystyle \alpha_{n\,1}\,x_{1}^{(k+1)} +
\alpha_{n\,2}\,x_{2}^{(k+1)} + \cdots +
\alpha_{n\,n-1}\,x_{{n-1}}^{(k+1)} + \beta_n,$  

gdje je $ \alpha{}_{ij}=-\frac{a_{ij}}{a_{ii}}, \beta{}_i=\frac{b_i}{a_{ii}}.$


next up previous contents
Next: OR (overrelaxation) metode Up: Rješavanje sustava jednadžbi Previous: Jacobijeva metoda   Contents
Salih Suljagic
1999-01-27