Gauss-Seidelova OR-metoda (SOR metoda)

Imamo

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

Neka je $D$ regularna matrica. Stavimo

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

Tada je

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

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

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

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

Tako je

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

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

odnosno

$$\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}$

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

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

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

$$x_{1}^{(k+1)} = (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$$

$$x_{2}^{(k+1)} = (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$$

$$\vdots$$

$$x_{n}^{(k+1)} = (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

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

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

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

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

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