next up previous contents
Next: Aproksimacija funkcije i numerička Up: Rješavanje sustava jednadžbi Previous: Gauss-Seidelova OR-metoda (SOR metoda)   Contents


Konvergencija iterativne metode

Iterativni postupci, koje smo upravo definirali, opisani su formulom

$\displaystyle \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 17   Neka je $ {A}$ simetrična matrica. Kažemo da je $ {A}$ pozitivno definitna, ako vrijedi

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

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

$\displaystyle \Vert A\,\boldsymbol{x}\Vert \leqslant{} \max{}_i \lambda{}_i(A)
\Vert\boldsymbol{x}\Vert,$

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


Dokaz. Budući da je matrica $ {A}$ 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

$\displaystyle A\,\boldsymbol{x}_i = \lambda{}_i\,\boldsymbol{x}_i.$

Zbog pozitivne definitnosti

$\displaystyle A\,\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 $ {A}$ č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.

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

Zbog linearnosti djelovanja matrice $ {A}$ na vektore

$\displaystyle A\,\boldsymbol{x} = \alpha{}_1\,A\,\boldsymbol{x}_1 +
\alpha{}_2\...
...ambda_2\,\boldsymbol{x}_2 + \cdots{} +
\alpha{}_n\,\lambda_n\,\boldsymbol{x}_n.$

Tako je

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

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

Odatle

$\displaystyle \Vert A\,\boldsymbol{x}\Vert \leqslant{}
\max{}_i\lambda{}_i\,\Vert\boldsymbol{x}\Vert.$

$ \heartsuit$

Teorem 23   Neka je $ G$ simetrična, pozitivno definitna matrica. Iterativni postupak

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

$\displaystyle \max{}_i \lambda{}_i(G) = L < 1.$


Dokaz. 1. Dokažimo najprije da iz

$\displaystyle \max{}_i \lambda{}_i(G) = L < 1$

slijedi konvergencija iterativnog postupka. Doista

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

i odatle

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

Kako to vrijedi za svaki $ k,$ imamo

$\displaystyle \Vert\boldsymbol{x}^{(k+1)} - \boldsymbol{x}^{(k)}\Vert \leqslant...
...ldots{} \leqslant{} L^k\,\Vert\boldsymbol{x}^{(1)} -
\boldsymbol{x}^{(0)}\Vert.$

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

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

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

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

Tada je

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

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

$\displaystyle \max{}_i \lambda{}_i(G) = L < 1.$

Iz

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

i

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

slijedi

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

Zbog pretpostavke

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

slijedi

$\displaystyle \lim_{k\rightarrow{}\infty{}} G^k\,(\boldsymbol{x}^{(0)} -
\bolds...
...\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 matrica $ \lim_{k\rightarrow{}\infty{}}
G^k$ mora biti nulmatrica, tj. mora biti

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

% latex2html id marker 28758
$\displaystyle G^k = X\,\left[\begin{array}{cccc}
...
...ddots & \vdots \\
0 & 0 & \cdots & \lambda_n^k(G)
\end{array}\right]\,X^{-1},$   za $\displaystyle k=1,2,\ldots\,.$

Odatle

% latex2html id marker 28761
$\displaystyle \lim_{k\rightarrow{}\infty{}} G^k= \...
...dots & \vdots \\
0 & 0 & \cdots & \lambda_n^k(G)
\end{array}\right]\,X^{-1} =$

% latex2html id marker 28763
$\displaystyle = X\,\left(\lim_{k\rightarrow{}\inft...
...vdots \\
0 & 0 & \cdots & \lambda_n^k(G)
\end{array}\right]\right)\,X^{-1} = $

% latex2html id marker 28765
$\displaystyle = X\,
\left[\begin{array}{cccc}
\li...
...s & \lim_{k\rightarrow{}\infty{}}\lambda_n^k(G)
\end{array}\right]\,X^{-1} = O.$

Budući da je $ X$ regularna matrica, slijedi

% latex2html id marker 28769
$\displaystyle \left[\begin{array}{cccc}
\lim_{k\r...
... & \cdots & \lim_{k\rightarrow{}\infty{}}\lambda_n^k(G)
\end{array}\right] = O.$

Prema tome

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

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

$\displaystyle \max{}_i \lambda{}_i(G) < 1.$

$ \heartsuit$

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

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

$\displaystyle \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(G)$ više nema smisla, jer u skupu kompleksnih brojeva nemamo prirodni uređaj. Umjesto toga imamo ovu definiciju.

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

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

$\displaystyle \nu(G) = \max{}_i \lambda{}_i(G).$

Može se dokazati sljedeći teorem

Teorem 24   Iterativni postupak

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

$\displaystyle \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.$ U nekim slučajevima je bilo

% latex2html id marker 28826
$\displaystyle g_{i\,j} =
\left\{\begin{array}{rl}...
..._{i\,i}}, & \mbox{ za\ }i\neq j, \\
0, & \mbox{ za\ }i=j.
\end{array}\right.
$

Tada je, prema 2, dovoljno da bude apsolutna vrijednost dijagonalnog elementa matrice $ {A}$ veća od sume apsolutnih vrijednosti ostalih elemenata u retku.

Primjer 3.3   Neka je matrica sustava

% latex2html id marker 28831
$\displaystyle 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

% latex2html id marker 28833
$\displaystyle G = - D^{-1}(L+R) = \left[
\begin{ar...
... & 1/2 & 0 \\
0 & 1/2 & 0 & 1/2 \\
0 & 0 & 1/2 & 0 \\
\end{array}\right].$

Njezine vlastite vrijednosti su

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

spektralni radius je

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

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

Kod Gauss-Seidelove metode je

% latex2html id marker 28839
$\displaystyle 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

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

spektralni radius je sada

$\displaystyle \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 matrica $ G$ rastu prema $ 1.$ U slučajevima kad su vrlo blizu broju $ 1,$ OR metode postaju vrlo efikasne u smislu brzine konvergencije.


next up previous contents
Next: Aproksimacija funkcije i numerička Up: Rješavanje sustava jednadžbi Previous: Gauss-Seidelova OR-metoda (SOR metoda)   Contents
Salih Suljagic
1999-01-27