next up previous contents
Next: Konvergencija iterativne metode Up: OR (overrelaxation) metode Previous: Jacobijeva OR-metoda (JOR metoda)   Contents


Gauss-Seidelova OR-metoda (SOR metoda)

Imamo

$\displaystyle A = L + D + R.$

Neka je $ D$ regularna matrica. Stavimo

$\displaystyle B(\omega{}) = \frac{1}{\omega{}}\,D + L = \frac{1}{\omega{}}\,(D +
\omega{}L).$

Tada je

$\displaystyle B(\omega{})^{-1} = \omega{}\,(D + \omega{}L)^{-1},$

$\displaystyle C(\omega{}) = \left(\frac{1-\omega{}}{\omega{}}\right)\,D - R,$

$\displaystyle G(\omega{}) = B(\omega{})^{-1}\,C(\omega{}) = (D +
\omega{}L)^{-1}\,\left[(1 - \omega{})\,D - \omega{}\,R\right],$

$\displaystyle \boldsymbol{g}(\omega{}) = B(\omega{})^{-1}\,\boldsymbol{b} =
\omega{}\,(D + \omega{}L)^{-1}\,\boldsymbol{b}.$

Tako je

$\displaystyle \boldsymbol{x}^{(k+1)} = (D + \omega{}L)^{-1}\,\left[(1 -
\omega{...
...right]\,\boldsymbol{x}^{(k)} +
\omega{}\,(D + \omega{}L)^{-1}\,\boldsymbol{b},$

Računanje $ (D + \omega{}L)^{-1}$ nije jednostavno, pa radimo nešto drukčije. Polazimo od prethodne jednadžbe

$\displaystyle B(\omega{})\,\boldsymbol{x}^{(k+1)} =
C(\omega{})\,\boldsymbol{x}^{(k)} + \boldsymbol{b},$

odnosno

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

Pomnožimo ovu jednadžbu s $ \omega{}\,D^{-1}$

$\displaystyle (I + \omega{}D^{-1}L)\,\boldsymbol{x}^{(k+1)} =
\left[\left(1-\om...
...
\omega{}\,D^{-1}R\right]\,\boldsymbol{x}^{(k)} +
\omega{}D^{-1}\boldsymbol{b}.$

Tako imamo sljedeći algoritam

Algoritam 8   (Gauss-Seidelova OR-metoda) Proizvoljno izaberemo početnu aproksimaciju

% latex2html id marker 28601
$\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)} =
\left(1-\omega{}\right)\,\boldsymbol{x}^...
...{(k+1)} -
\omega{}D^{-1}R\,\boldsymbol{x}^{(k)} + \omega{}D^{-1}\boldsymbol{b},$

odnosno
$\displaystyle x_{1}^{(k+1)}$ $\displaystyle =$ $\displaystyle (1-\omega)\,x_{1}^{(k)} +
\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 (1-\omega)\,x_{2}^{(k)} +
\alpha_{2\,1}\,x_{1}^{(k+1)} +
\alpha_{2\,3}\,x_{3}^{(k)} + \cdots +
\alpha_{2\,n}\,x_{n}^{(k)} +
\beta_2$  
    $\displaystyle \vdots$  
$\displaystyle x_{n}^{(k+1)}$ $\displaystyle =$ $\displaystyle (1-\omega)\,x_{n}^{(k)} +
\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_,.$  

gdje je $ \alpha_{i\,j}=-\frac{\omega}{\alpha_{i\,i}}\,a_{i\,j},$ i $ \beta_i=\frac{\omega}{\alpha_{i\,i}}\,b_i.$

Primijetimo da za $ \omega{}=1$ SOR metoda postaje Gauss-Seidelova metoda.

Broj $ \omega{}$ treba uzeti tako da je $ 0<\omega{}<2.$ Optimalna vrijednost ovisi o konkretnom problemu koji se rješava.


next up previous contents
Next: Konvergencija iterativne metode Up: OR (overrelaxation) metode Previous: Jacobijeva OR-metoda (JOR metoda)   Contents
Salih Suljagic
1999-01-27