next up previous contents index
Next: Konvergencija iterativne metode Up: OR (overrelaxation) metode Previous: Jacobijeva OR-metoda (JOR metoda)   Sadržaj   Indeks


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)} =
\...
...mega{}}{\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-\o...
...\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 39001
$\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_n.$  

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.

Primjer 3.11   Riješiti sustav u primjeru 3.10 OR metodama.

Rješenje. Jacobijeva OR metoda ne daje ništa bolje rezultate kad se uzme $ \omega\neq 1.$ Gauss-Seidelova OR metoda za $ \omega=1.075$ daje

$\displaystyle \{ 1,1,1\},\quad \{ 0.778175,-0.404,1.47273\},\quad
\{ 1.0168,-0.649051,1.54606\}$

$\displaystyle \{ 1.03148,-0.666804,1.5492\},\quad
\{ 1.03127,-0.666338,1.54868\},$

$\displaystyle \{ 1.03098,-0.665961,1.54853\},\quad
\{ 1.03092,-0.665897,1.54851\},$

$\displaystyle \{ 1.03092,-0.665892,1.54851\},\quad
\{ 1.03092,-0.665892,1.54851\}$

$\displaystyle \{ 1.03092,-0.665892,1.54851\}.$


next up previous contents index
Next: Konvergencija iterativne metode Up: OR (overrelaxation) metode Previous: Jacobijeva OR-metoda (JOR metoda)   Sadržaj   Indeks
2001-10-26