Konvergencija iterativne metode

Iterativni postupci, koje smo upravo definirali, opisani su formulom

$$\boldsymbol{x}^{(k+1)} = G\,\boldsymbol{x}^{(k)} + \boldsymbol{g},$$

gdje je $G$ matrica tipa $(n,n),$ definirana od slučaja do slučaja na različite načine pomoću matrice $A.$ Razmotrimo sada probleme konvergencije navedenih metoda.

Definicija 16   Neka je $A$ simetrična matrica. Kažemo da je $A$ pozitivno definitna, ako vrijedi

$$A\,\boldsymbol{x} \cdot{} \boldsymbol{x} > 0,\hspace{1cm} \forall{}\boldsymbol{x} \neq{} \textbf{0}.$$

Lema 3   Neka je $G$ simetrična pozitivno definitna matrica tipa $(n,n).$ Tada su vlastite vrijednosti $\lambda{}_i,\,i=1,2,\ldots{},n$ od matrice $G$ pozitivne, i vrijedi

$$\Vert G\,\boldsymbol{x}\Vert \leqslant{} \max_i\, \lambda{}_i \Vert\boldsymbol{x}\Vert,$$

za svaki $\boldsymbol{x} \in {\cal R}_{n}.$

Dokaz. Budući da je matrica $G$ simetrična, postoji $n$ međusobno okomitih i jediničnih vektora $\boldsymbol{x}_1,\boldsymbol{x}_2,\ldots{},\boldsymbol{x}_n$ u ${\cal R}_{n},$ i brojevi $\lambda{}_1,\lambda{}_2,\ldots{},\lambda{}_n$ takvih, da je

$$G\,\boldsymbol{x}_i = \lambda{}_i\,\boldsymbol{x}_i.$$

Zbog pozitivne definitnosti

$$G\,\boldsymbol{x}_i \cdot{} \boldsymbol{x}_i = \lambda{}_i\,\boldsymbol{x}_i \cdot{} \boldsymbol{x}_i = \lambda{}_i > 0,\hspace{1cm}\forall{}i.$$

Dokažimo sada drugu tvrdnju. Primijetimo najprije da vlastiti vektori $\boldsymbol{x}_1,\boldsymbol{x}_2,\ldots{},\boldsymbol{x}_n$ matrice $G$ čine ortonormiranu bazu u ${\cal R}_{n}.$ To znači da se bilo koji vektor $\boldsymbol{x}\in{\cal R}_{n}$ može prikazati kao njihova linearna kombinacija.

$$\boldsymbol{x} = \alpha{}_1\,\boldsymbol{x}_1 + \alpha{}_2\,\boldsymbol{x}_2 + \cdots{} + \alpha{}_n\,\boldsymbol{x}_n.$$

Zbog linearnosti djelovanja matrice $G$ na vektore

$$G\,\boldsymbol{x} = \alpha{}_1\,G\,\boldsymbol{x}_1 + \alpha{}_2... ...mbda_2\,\boldsymbol{x}_2 + \cdots{} + \alpha{}_n\,\lambda_n\,\boldsymbol{x}_n.$$

Tako je

$$\Vert G\,\boldsymbol{x}\Vert^2 = G\,\boldsymbol{x} \cdot{} G\,\b... ...lambda_1^2 + \alpha{}_2^2\,\lambda_2^2 + \cdots{} + \alpha{}_n^2\,\lambda_n^2$$

$$\leqslant{} \left(\max_i\,\lambda{}_i\right)^2\, \left(\alpha{}_... ...}_n^2\right) = \left(\max_i\,\lambda{}_i\right)^2\,\Vert\boldsymbol{x}\Vert^2.$$

Odatle

$$\Vert G\,\boldsymbol{x}\Vert \leqslant{} \max_i\,\lambda{}_i\,\Vert\boldsymbol{x}\Vert.$$

$\heartsuit$

Teorem 25   Neka je $G$ simetrična, pozitivno definitna matrica, i neka su $\lambda_1,$ $\lambda_2,$ $\ldots$ $\lambda_n,$ njezine vlastite vrijednosti. Iterativni postupak

$$\boldsymbol{x}^{(k+1)} = G\,\boldsymbol{x}^{(k)} + \boldsymbol{g},\hspace{1cm}k=0,1,2,\ldots{}$$

konvergira za bilo koju početnu aproksimaciju $\boldsymbol{x}^{(0)},$ ako i samo ako je

$$\max_i\, \lambda{}_i = L < 1.$$

Dokaz. 1. Dokažimo najprije da iz

$$\max_i\, \lambda{}_i = L < 1$$

slijedi konvergencija iterativnog postupka. Doista

$$\boldsymbol{x}^{(k+1)} - \boldsymbol{x}^{(k)} = G\,(\boldsymbol{x}^{(k)} - \boldsymbol{x}^{(k-1)}),$$

i odatle

$$\Vert\boldsymbol{x}^{(k+1)} - \boldsymbol{x}^{(k)}\Vert = \Vert ... ...{x}^{(k-1)}\Vert = L\,\Vert\boldsymbol{x}^{(k)} - \boldsymbol{x}^{(k-1)}\Vert.$$

Odatle možemo, na isti način kao kod računanja apriorne ocjene greške kod metode iteracije (v. 3.2.2), zaključiti

$$\Vert\boldsymbol{x}^{(m)}-\boldsymbol{x}^{(n)}\Vert \leqslant{} \frac{L^n}{1-L}\,\Vert\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(0)}\Vert.$$

Budući da je $0<L<1,$

$$\lim_{k\rightarrow{}\infty{}} L^k = 0,$$

pa niz $(\boldsymbol{x}^{(k)})$ konvergira. Neka je

$$\lim_{k\rightarrow{}\infty{}} \boldsymbol{x}^{(k)} = \boldsymbol{s}.$$

Tada je

$$\lim_{k\rightarrow{}\infty{}} \boldsymbol{x}^{(k+1)} = \lim_{k\rightarrow{}\infty{}} (G\,\boldsymbol{x}^{(k)} + \boldsymbol{g}),$$

$$\boldsymbol{s} = G\,\boldsymbol{s} + \boldsymbol{g},$$

i prema tome niz konvergira k rješenju $\boldsymbol{s}.$
2. Dokažimo obrat, tj. da iz konvergencije postupka slijedi

$$\max_i\, \lambda{}_i = L < 1.$$

Iz

$$\boldsymbol{x}^{(k)} = G\,\boldsymbol{x}^{(k-1)} + \boldsymbol{g}$$

i

$$\boldsymbol{s} = G\,\boldsymbol{s} + \boldsymbol{g}$$

slijedi

$$\boldsymbol{x}^{(k)} - \boldsymbol{s} = G\,(\boldsymbol{x}^{(k-1... ...} - \boldsymbol{s}) = \cdots{} = G^k\,(\boldsymbol{x}^{(0)} - \boldsymbol{s}).$$

Zbog pretpostavke

$$\lim_{k\rightarrow{}\infty{}} (\boldsymbol{x}^{(k)} - \boldsymbol{s}) = 0,$$

slijedi

$$\lim_{k\rightarrow{}\infty{}} G^k\,(\boldsymbol{x}^{(0)} - \bold... ...rightarrow{}\infty{}} G^k\right)\,(\boldsymbol{x}^{(0)} - \boldsymbol{s}) = 0.$$

Ako se to događa za svaku početnu aproksimaciju $\boldsymbol{x}^{(0)},$ onda mora biti

$$\lim_{k\rightarrow{}\infty{}} G^k = O.$$

Budući da je $G$ simetrična matrica, ona se može dijagonalizirati, tj. postoji regularna matrica $X$ takva, da vrijedi

$$G^k = X\,\left[\begin{array}{cccc} ... ... \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n^k \end{array}\right]\,X^{-1},$$   za $$k=1,2,\ldots\,.$$

Odatle

$$\lim_{k\rightarrow{}\infty{}} G^k= \... ...\ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n^k \end{array}\right]\,X^{-1} =$$

$$= X\,\left(\lim_{k\rightarrow{}\inft... ... \vdots \\ 0 & 0 & \cdots & \lambda_n^k \end{array}\right]\right)\,X^{-1} =$$

$$= X\, \left[\begin{array}{cccc} \l... ...ots & \lim_{k\rightarrow{}\infty{}}\lambda_n^k \end{array}\right]\,X^{-1} = O.$$

Ako pomnožimo s lijeva s $X^{-1},$ i s desna s $X$, slijedi

$$\left[\begin{array}{cccc} \lim_{k\r... ... 0 & \cdots & \lim_{k\rightarrow{}\infty{}}\lambda_n^k \end{array}\right] = O.$$

Prema tome

$$\lim_{k\rightarrow{}\infty{}}\lambda_i^k = 0,\hspace{1cm} i=1,2,\ldots{},n.$$

Zbog $\lambda_i >0,$ to je moguće samo ako je

$$\max_i\, \lambda{}_i < 1.$$

$\heartsuit$

Na isti način kao kod metode iteracije prilikom traženja nultočke funkcije možemo naći apriornu ocjenu greške

$$\Vert\boldsymbol{x}^{(k)} - \boldsymbol{s}\Vert \leqslant{} \frac{L^k}{1-L}\,\Vert\boldsymbol{x}^{(1)} - \boldsymbol{x}^{(0)}\Vert,$$

i aposteriornu ocjenu greške

$$\Vert\boldsymbol{x}^{(k)} - \boldsymbol{s}\Vert \leqslant{} \frac{L}{1-L}\,\Vert\boldsymbol{x}^{(k)} - \boldsymbol{x}^{(k-1)}\Vert.$$

Ovi rezultati su dobiveni uz pretpostavku da je $G$ simetrična pozitivno definitna matrica. To je važan slučaj, koji se pojavljuje prilikom približnog rješavanja rubnih i rubno-početnih problema varijacijskim metodama. Međutim, može se dogoditi da $G$ ne ispunjava ovaj uvjet. Ipak, dobiveni rezultati vrijede i tada uz neke modifikacije.

Prije svega, budući da u općem slučaju vlastite vrijednosti mogu biti kompleksni brojevi, broj $L=\max_i\,\lambda{}_i$ više nema smisla, jer u skupu kompleksnih brojeva nemamo prirodni uređaj. Umjesto toga imamo ovu definiciju.

Definicija 17   Neka je $G$ matrica tipa $(n,n),$ i neka su $\lambda{}_1,\lambda{}_2,\ldots{},\lambda{}_n$ njezine vlastite vrijednosti. Broj

$$\nu(G) = \max_i\,\,\vert\lambda{}_i\vert$$

se zove spektralni radius matrice $G.$

Očito je u slučaju simetričnosti i pozitivne definitnosti matrice $G$

$$\nu(G) = \max_i\, \lambda{}_i.$$

Može se dokazati sljedeći teorem

Teorem 26   Iterativni postupak

$$\boldsymbol{x}^{(k+1)} = G\,\boldsymbol{x}^{(k)} + \boldsymbol{g},\hspace{1cm}k=0,1,2,\ldots{}$$

konvergira za bilo koju početnu aproksimaciju $\boldsymbol{x}^{(0)},$ ako i samo ako je

$$\nu(G) < 1.$$

Tako se problem konvergencije iterativnog postupka svodi na problem ocjene spektralnog radiusa, odnosno najveće po modulu (apsolutnoj vrijednosti) vlastite vrijednosti matrice, i to ocjene odozgo. Ima raznih ocjena te vrste. Navedimo neke od njih. Neka je $G=[g_{i\,j}].$ Tada vrijedi

1. $\nu(G)\leqslant \left[\sum_{i=1}^n\sum_{j=1}^n\vert g_{ij}\vert^2\right]^{\frac{1}{2}},$
2. $\nu(G)\leqslant \max{}\{\sum_{j=1}^n\vert g_{ij}\vert;\;i=1,2,\ldots,n\},$
3. $\nu(G)\leqslant \max{}\{\sum_{i=1}^n\vert g_{ij}\vert;\;j=1,2,\ldots,n\},$

Ako je bilo koji od ovih brojeva na desnoj strani manji od $1,$ spektralni radius je nužno manji od $1.$ Naglasimo da se ovdje ne radi o spektralnom radiusu matrice $A$ već matrice $G.$

Primjer 3.12   Ispitati konvergenciju Jacobijeve i Gauss-Seidelove metode u primjeru 3.10.

Rješenje. Kod Jacobijeve metode imamo

$$G_J = - D^{-1}(L+R),$$

a kod Gauss-Seidelove

$$G_S = -(L + D)^{-1}\,R.$$

Matrica sustava, kako je na početku napisan, je

$$A = \left[ \begin{array}{rrr} 1.00... ...3.72 \\ 3.15 & - 0.20 & - 1.97 \\ 4.43 & 5.84 & 1.79 \end{array} \right].$$

Ako primijenimo Jacobijevu metodu, imamo

$$G_J = \left[\begin{array}{rrr} 0 & ... ... -3.72 \\ 15.75 & 0 & -9.85 \\ -2.47486 & -3.26257 & 0 \end{array}\right].$$

Vlastite vrijednosti su $5.18447,-2.59224 + 4.28355\,i, -2.59224 - 4.28355\,i,$ pa je spektralni radius $\nu(G_J)=5.18447.$

Kod Gauss-Seidelove metode imamo još lošiji rezultat

$$G_S = \left[\begin{array}{rrr} 0 & ... ...3.72 \\ 0 & -39.5325 & -68.44 \\ 0 & 135.189 & 232.497 \end{array}\right].$$

Vlastite vrijednosti su $192.647,0.317614,0,$ pa je spektralni radius $\nu(G_S)=192.647.$

Kad prvu jednadžbu stavimo na treće mjesto, Jacobijeva metoda daje

$$G_J = \left[ \begin{array}{rrr} 0 ... ...-0.758562 & 0 & -0.306507 \\ -0.268817 & -0.674731 & 0 \end{array} \right],$$

zatim vlastite vrijednosti su $-0.341587 + 0.599596\,i,$ $-0.341587 - 0.599596\,i,$ $0.683174,$ pa je spektralni radius $\nu(G_J)=0.69007.$

$$G_S = \left[ \begin{array}{rrr} 0 & ... ...\\ 0 & -0.0481626 & -0.780909 \\ 0 & 0.0154291 & 0.358786 \end{array}\right],$$

zatim vlastite vrijednosti su $0.326639,-0.0160158,0,$ pa je spektralni radius $\nu(G_S)=0.326639.$ Ako se radi Gauss-Seidelovom OR metodom, spektralni radius postaje $\nu(G_S)=0.126947$ za $\omega=1.075.$

Primjer 3.13   Neka je matrica sustava

$$A = \left[ \begin{array}{rrrr} 2 &... ... 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 2 \\ \end{array} \right].$$

Treba ispitati da li Jacobijev i Gauss-Seidelov postupak konvergiraju.

Rješenje. U Jacobijevom postupku je

$$G = - D^{-1}(L+R) = \left[ \begin{a... ... 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 1/2 & 0 \\ \end{array} \right].$$

Njezine vlastite vrijednosti su

$$-0.809017,\;\;-0.309017,\;\;0.309017,\;\;0.809017,$$

spektralni radius je

$$\nu(G) = 0.809017 < 1,$$

i prema tome Jacobijeva metoda konvergira za svaku početnu aproksimaciju.

Kod Gauss-Seidelove metode je

$$G = -(L + D)^{-1}\,R = \left[ \begin... ... & 0 \\ 0 & 1/8 & 1/4 & 1/2 \\ 0 & 1/16 & 1/8 & 1/4 \\ \end{array} \right].$$

Njezine vlastite vrijednosti su^3.2

$$0,\hspace{1cm}0,\hspace{1cm}0.0954915,\hspace{1cm}0.654508,$$

spektralni radius je sada

$$\nu(G) = 0.654508 < 1,$$

pa prema tome Gauss-Seidelova metoda također konvergira za svaku početnu aproksimaciju, i to brže nego Jacobijeva.

S porastom reda matrice, uz isti tridijagonalni oblik, vlastite vrijednosti matrice $G$ rastu prema $1.$ U slučajevima kad su vrlo blizu broju $1,$ OR metode postaju vrlo efikasne u smislu brzine konvergencije.