Gauss-Seidelova metoda

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

Pod pretpostavkom da je

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

$$a_{1\,1}\,x_{1}^{(k+1)} + a_{1\,2}\,x_{2}^{(k)} + \cdots + a_{1\,n}\,x_{n}^{(k)} = b_1$$

$$a_{2\,1}\,x_{1}^{(k+1)} + a_{2\,2}\,x_{2}^{(k+1)} + \cdots + a_{2\,n}\,x_{n}^{(k)} = b_2$$

$$\cdots$$

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

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

odnosno

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

Tako imamo formulu iterativnog postupka

$$\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 teže nego naći inverz od $D.$ Zato radimo malo drukčije. Pomnožimo jednadžbu (3.11) s $D^{-1}.$

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

Odatle

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

$$\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)} = -D^{-1}\,L\,\boldsymbol{x}^{(k+1)} -D^{-1}\,R\,\boldsymbol{x}^{(k)} + D^{-1}\,\boldsymbol{b},$$

odnosno

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

$$\cdots$$

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

Primjer 3.10   Riješiti sljedeći sustav jednadžbi

$$1.00\,x + 2.51\,y + 3.72\,z = 5.12$$

$$3.15\,x - 0.20\,y - 1.97\,z = 0.33$$

$$4.43\,x + 5.84\,y + 1.79\,z = 3.45$$

Rješenje. Radi jednostavnosti ćemo radije vektorstupac rješenja pisati u obliku $\{x,y,z\}.$ Ako počnemo s $\{1,1,1\},$ Jacobijeva metoda daje sustav

$$x^{(k+1)} = - 2.51\,y^{(k)} - 3.72\,z^{(k)} + 5.12$$

$$y^{(k+1)} = 15.75\,x^{(k)} - 9.85\,z^{(k)} - 1.65$$

$$z^{(k+1)} = - 2.47486\,x^{(k)} - 3.2625698\,y^{(k)} + 1.9273743$$

odakle dobivamo redom sljedeće aproksimacije.

$$\{ 1,1,1\},\quad \{ -1.11,4.25,-3.81006\},\quad \{ 8.62591,18.3966,-9.19145\},$$

$$\{ -6.86314,224.744,-79.4406\},\quad \{ -263.468,672.745,-714.33\},$$

$$\{ 973.837,2884.88,-1540.9\},\quad \{ -32614.,92744.1,-95831.1\},$$

$$\{ 123709.,430265.,-221867.\},\quad \{ -254614.,4.13381\times {{10}^6},-1.70993\times {{10}^6}\},$$

$$\{ -4.01492\times {{10}^6},1.28326\times {{10}^7}, -1.28567\times {{10}^7}\}.$$

Gauss-Seidelova metoda daje sustav

$$x^{(k+1)} = - 2.51\,y^{(k)} - 3.72\,z^{(k)} + 5.12$$

$$y^{(k+1)} = 15.75\,x^{(k+1)} - 9.85\,z^{(k)} - 1.65$$

$$z^{(k+1)} = - 2.47486\,x^{(k+1)} - 3.2625698\,y^{(k+1)} + 1.9273743$$

i aproksimacije su redom

$$\{ 1,1,1\},\quad \{ -1.11,-28.9825,99.2319\},\quad \{ -291.277,-5566.69,18884.5\},$$

$$\{ -56272.9,-1.07231\times {{10}^6},3.63776\times {{10}^6}\},$$

$$\{ -1.0841\times {{10}^7},-2.06577\times {{10}^8}, 7.00802\times {{10}^8}\}.$$

Međutim, ako se promijeni poredak jednadžbi, tako da prva jednadžba dođe na treće mjesto, druga na prvo, a treća na drugo, tj. ako sustav napišemo u obliku

$$3.15\,x - 0.20\,y - 1.97\,z = 0.33$$

$$4.43\,x + 5.84\,y + 1.79\,z = 3.45$$

$$1.00\,x + 2.51\,y + 3.72\,z = 5.12$$

onda Jacobijevom metodom dobivamo sustav

$$x^{(k+1)} = 0.063492\,y^{(k)} + 0.625397\,z^{(k)} + 0.104762$$

$$y^{(k+1)} = - 0.758562\,x^{(k)} - 0.306507\,z^{(k)} + 0.590753$$

$$z^{(k+1)} = - 0.268817\,x^{(k)} - 0.674731\,y^{(k)} + 1.376344$$

$$\{ 1,1,1\},\quad \{ 0.793651,-0.474315,0.432796\},\quad \{ 0.345316,-0.143934,1.48303\},$$

$$\{ 1.02311,-0.125749,1.38063\},\quad \{ 0.960222,-0.60851,1.18616\},$$

$$\{ 0.807949,-0.501201,1.5288\},\quad \{ 1.02905,-0.490713,1.49733\},$$

$$\{ 1.01003,-0.648784,1.43082\},\quad \{ 0.958398,-0.613973,1.54259\},$$

$$\{ 1.03051,-0.609064,1.53298\},$$

a Gauss-Seidelovom sustav glasi

$$x^{(k+1)} = 0.063492\,y^{(k)} + 0.625397\,z^{(k)} + 0.104762$$

$$y^{(k+1)} = - 0.758562\,x^{(k+1)} - 0.306507\,z^{(k)} + 0.590753$$

$$z^{(k+1)} = - 0.268817\,x^{(k+1)} - 0.674731\,y^{(k+1)} + 1.376344$$

i dobivamo

$$\{ 1,1,1\},\quad \{ 0.793651,-0.317786,1.37742\},\quad \{ 0.946018,-0.549047,1.4925\},$$

$$\{ 1.0033,-0.627776,1.53022\},\quad \{ 1.0219,-0.653441,1.54254\},$$

$$\{ 1.02797,-0.661825,1.54656\},\quad \{ 1.02996,-0.664563,1.54788\},$$

$$\{ 1.0306,-0.665458,1.54831\},\quad \{ 1.03082,-0.66575,1.54845\},$$

$$\{ 1.03088,-0.665845,1.54849\}.$$

Inače, rješenje na pet decimala točno, je

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