Introducere#

În acest subcapitol, voi introduce câteva noțiuni matematice utile în descrierea metodelor iterative, pornind de la concepte precum acuratețea și convergența și culminând cu descrierea generalizată a metodelor pe care le vom discuta.

Concepte fundamentale#

În contextul metodelor iterative de rezolvare a sistemelor de ecuații liniare, se definesc două noțiuni foarte importante:

• Acuratețea. Face referire strict la numărul de zecimale corecte obținut în calcule;

• Convergența. Se referă la pasul de iterație când o anumită acuratețe a fost atinsă.

Motorul metodelor#

Metodele iterative utilizează diverse relații de recurență care, prin apelare succesivă (repetată, iterativă), furnizează aproximări cu precizie controlată a soluției sistemului.

În acest scop, să considerăm sistemul \(A\bm{x}=\bm{b}\), unde \(A\in\mathbb{R}^{n\times n}\), \(\bm{x},\bm{b}\in\mathbb{R}^n\) și \(n\in\mathbb{N}^*\). Totodată, vom încerca să scriem matricea \(A\) ca o diferență de alte două matrice, \(N,P\in\mathbb{R}^{n\times n}\), momentan luate aparent din aer. Așadar:

\[ \boxed{\begin{cases} A\bm{x}&=\bm{b}\\ A&=N-P \end{cases}} \]

Înlocuim valoarea lui \(A\) în prima ecuație și obținem \((N-P)\bm{x}=\bm{b}\), deci \(N\bm{x}=P\bm{x}+\bm{b}\). Dacă matricea \(N\) este nesingulară (inversabilă), putem înmulți ecuația cu \(N^{-1}\) la stânga, adică:

\[ \bm{x}=N^{-1}P\bm{x}+N^{-1}\bm{b} \]

Într-adevăr, aparent, nu s-a întâmplat mare lucru. Cu toate acestea, în urma operațiilor noastre, am reușit să scriem vectorul \(\bm{x}\) ca o funcție față de el însuși, deci se poate concepe un algoritm recursiv.

Folosind aceste notații, ne putem imagina următorul algoritm recursiv ce definește a \((p+1)\)-a iterație drept îmbunătățirea:

\[ \boxed{\bm{x^{(p+1)}}=G\bm{x^{(p)}}+\bm{c}} \]

unde considerăm definite:

• \(\bm{x^{(0)}}, \bm{x^{(1)}}, \dots, \bm{x^{(p)}}, \bm{x^{(p+1)}}, \dots\) - aproximările soluției la un anumit pas;

• \(G\) - matricea de iterație, definită drept \(G = N^{-1}P\);

• \(\bm{c}\) - vectorul de iterație, egal cu \(c=N^{-1}\bm{b}\).

Metodele Jacobi, Gauss-Seidel și suprarelaxarea - toate folosesc acest motor. Diferența între acestea este în general dată de modul în care se definesc matricele \(N\) și \(P\).

Descompunerea lui \(A\)#

Suplimentar, vom considera următoarea descompunere unică a matricei \(A\):

\[ \boxed{A=D-L-U} \]

unde \(D,L,U\) au fost alese astfel încât să reprezinte:

• \(D\) - o matrice diagonală;

• \(L\) - o matrice inferior triunghiulară, cu elementele de pe diagonala principală nule;

• \(U\) - o matrice superior triunghiulară, cu elementele de pe diagonala principală nule.

Este trivial motivul pentru care această descompunere este unică. Descompunerea va fi folosită în toate metodele iterative discutate.

Condiția de convergență#

Din nefericire, noțiunile matematice prin care se exprimă condiția de convergență nu au fost încă explicate, acestea fiind parte din subcapitolul dedicat valorilor proprii.

Așa cum am mai menționat, este imposibilă parcurgerea materiei necesară metodelor numerice într-o manieră liniară, așadar vom ruga cititorii fie să lectureze de acum subcapitolul atașat, fie să aibă răbdare și să revină la această noțiune abia după ce se încheie capitolul dedicat matricelor.

Pentru ca o metodă iterativă să conveargă, este absolut necesar ca \(\rho(G)\lt 1\), unde prin \(\rho(G)\) se înțelege raza spectrală a matricei de iterație \(G\).

Acesta este unul dintre dezavantajele metodelor iterative.

Licență#

The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0