Rezolvarea iterativa a sistemelor de ecuatii liniare

Rezolvarea iterativa a sistemelor de ecuatii liniare

Tematica lucrarii: 1. Principiul de lucru al metodelor iterative;

2. Metoda lui Jacobi;

3. Metoda lui Gauss-Seidel;

4. Programarea in MathCad;

5. Probleme de rezolvat;

6. Concluzii.

1. Principiul de lucru al metodelor iterative

Rezolvarea sistemelor de ecuatii liniare prin metode deterministe se realizeaza intr-un numar finit de pasi, cunoscut dinainte, in functie de dimensiunea sistemului si metoda aplicata (de exemplu metoda lui Gauss). Spre deosebire de acestea, metodele iterative calculeaza aproximatii ale solutiei, pas cu pas, pana se obtine o eroare acceptabila. Trebuie mentionat ca aceste metode pot fi aplicate numai daca sistemul de ecuatii indeplineste anumite conditii, corespunzatoare metodei. O alta particularitate este dificultatea de a defini apriori (adica inainte de pornirea procesului iterativ) o eroare a solutiei aproximative, fata de solutia exacta. De obicei se considera ca procesul iterativ poate fi oprit atunci cand variatiile solutiei de la o iteratie la alta sunt nesemnificative. Trebuie subliniat insa ca gradul de stabilizare a solutiei este puternic dependent de numarul de cifre semnificative disponibil si de viteza de convergenta. O metoda lenta si un numar redus de cifre semnificative duce la o stabilizare rapida a solutiei aproximative, chiar daca aceasta este departe de solutia exacta. Cu toate acestea metodele iterative au calitati incontestabile privind simplitatea algoritmului, necesitatile de memorie si in anumite cazuri, chiar viteza de lucru. Superioritatea lor se afirma net atunci cand trebuie rezolvate sisteme de dimensiuni foarte mari. In acest caz, datorita numarului foarte mare de operatii, metodele deterministe sunt afectate de erori de trunchiere cumulate care degradeaza calitatea solutiei.

Eficienta metodelor de rezolvare iterativa este puternic dependenta de proprietatile sistemului de ecuatii si de valorile initiale ale solutiei date la prima aproximatie. Situatia optima este atunci cand in cadrul constructiei metodei sunt luate in consideratie proprietatile problemei de rezolvat. Astfel pentru o clasa destul de larga de sisteme de ecuatii liniare, rezultate in urma discretizarii problemelor diferentiale (cum cazul problemelor de camp, de exemplu) se pot construi metode iterative eficiente.

Daca este dat un sistem de ecuatii liniare in forma explicita:

a x +a x ++a_1nx_n = b

a x +a x ++a_2nx_n = b (1)

a_n1x +a_n2x ++a_nnx_n = b_n

acesta este reprezentat in forma matriceala (vectoriala):

Ax = b (2)

cu:       A = b = x = (3)

unde: A reprezinta matricea coeficientilor;

b reprezinta vectorul termenilor liberi;

x reprezinta vectorul solutiei sistemului de ecuatii;

Ax reprezinta aplicarea operatorului A asupra vectorului x.

Ecuatia recursiva generala a unei metode iterative oarecare este:

x^k+1 := T(x^k (4)

unde k este numarul pasului de iteratie, iar T operatorul de tranzitie corespunzator.

Metodele iterative prezentate mai jos (metoda lui Jacobi si lui Gauss-Seidel) sunt convergente numai daca sunt indeplinite anumite conditii privind structura matricei sistemului de ecuatii. Astfel o conditie suficienta este ca matricea sistemului sa fie simetrica si pozitiv definita. O conditie suficienta mai usor de verificat este ca matricea A sa fie diagonal dominanta, adica elementele diagonale ale matricei sa fie mai mari decat suma celorlalte elemente de pe linia respectiva :

i = 1N (5)

Criteriul de oprire al unei metode iterative se poate baza pe gradul de stabilizare a solutiei aproximative, adica pe norma diferentei dintre doua solutii la doi pasi succesivi:

(6)

unde x^k+1 si x^k reprezinta vectorii solutie obtinuti respectiv la pasul k+1 si la pasul k.

2. Metoda lui Jacobi

Metoda lui Jacobi poate fi reprezentata de urmatorul proces iterativ:

i := 1N (7)

unde:      x_j^k - este componenta j a vectorului solutie la pasul k+1 al iteratiei;

x_i^k+1 - este componenta j a vectorului solutie la pasul k al iteratiei.

La fiecare pas al iteratiei se calculeaza pentru fiecare ecuatie necunoscuta corespunzatoare termenului diagonal in finctie de celelelte necunoscute calculate la pasul precedent.

3. Metoda lui Gauss-Seidel

Metoda Gauss-Seidel este asemanatoare cu metoda Jacobi deosebirea ca la fiecare pas al iteratiei sunt utilizate necunoscutele calculate pana atunci in cadrul aceluiasi proces iterativ.

i := 1N (8)

Metodele Iacobi si Gauss-Seidel sunt caracterizate printr-un procedeu foarte simplu, cu putine operatii la un pas de iteratie. Datorita faptului ca suma se face dupa toti termenii care au coeficienti nenuli, fara sa aiba importanta pozitia acestora in matricea sistemului, metoda este deosebit de comoda in cazul matricilor rare (cu putine elemente diferite de zero) rezultate in special la rezolvarea ecuatiilor cu derivate partiale.

Dezavantajele principale ale metodelor Jacobi si Gauss-Seidel constau in criterii de convergenta destul de restrictive si viteza de convergenta redusa. Viteza de convergenta creste cu cat caracterul dominant diagonal al matricii este mai puternic. Din fericire insa o clasa destul de larga de metode de rezolvare a ecuatiilor cu derivate partiale duc la matrici diagonal dominante.

Viteza de convergenta redusa poate pune serioase probleme in aprecierea criteriului de oprire al procesului iterativ. Daca eroarea relativa data de o anumita norma nu variaza semnificativ sau este comparabila cu eroarea de trunchiere este greu de spus cand se stabilizeaza procesul de aproximatie si cat de departe ne aflam de solutia exacta.

Avantajul metodei este o buna stabilitate in cazul sistemelor de ecuatii foarte mari si o autostabilizare fata de eroarea de trunchiere. Totusi eroarea de trunchiere poate reprezenta un handicap serios in cazul vitezei de convergenta foarte redusa. Atunci variatia unei necunoscute de la o iteratie la alta poate deveni comparabila cu eroarea de trunchiere. Daca se intampla acest lucru atat proprietatile de convergenta cat si cele de stabilitate sunt afectate.

4. Programarea in MathCad

Matricele de forma A = [a_{ij i=1,N;j=1,N} sunt operatori in spatiul vectorial. Matricea A poate fi descompusa conform relatiei:

A = D + L + U (9)

unde matricile D, L si U au semnificatia urmatoarea:

matricea D are toate elementele nule, exceptand diagonala identica cu diagonala matricei A .

matricea L are diagonala nula, submatricea superioara diagonalei nula si submatricea       inferioara identica cu cea a lui A .

matricea U are diagonala nula, submatricea inferioara diagonalei nula si submatricea       superioara identica cu cea a lui A .

In cadrul progaramului MathCad pot fi rezolvate ecuatii recursive atat scalare cat si vectoriale. Implementarea metodelor Jacobi si Gauss-Seidel poate fi realizata printr-o ecuatie vectoriala. Pentru a putea calcula la un pas toate componentele vectorului solutie relatia trebuie pusa sub forma matriceala. Daca aplicam un operator matriceal M asupra unui vector v cu N componente fiecare componenta i a vectorului rezultant este data de relatia:

(10)

Rezulta ca termenii suma din ecuatiile de mai sus pot fi exprimati in functie de matricile partiale D, L si U astfel:

(11)

Daca amplificam ecuatia corespunzatoare metodei Jacobi cu a_ii , rezulta:

i := 1N (12)

Aceasta poate fi exprimata matriceal utilizand relatiile de mai sus astfel:

Dx^k+1 := - (L + U)x^k + B (13)

Daca amplificam ecuatia cu inversa matricei D obtinem ecuatia recursiva in limbaj MathCad:

x^<k+1> := - D (L + U)x^<k+1>+ D B (14)

Analog procedam si pentru metoda lui Gauss-Seidel. Amplificam ecuatia recursiva corespunzatoare cu a_ii si obtinem:

i := 1N (15)

Aceasta poate fi exprimata matriceal utilizand aceleasi relatii ca mai sus astfel:

Dx^k+1 + Lx^k+1 := - Ux^k + B (16)

Daca amplificam ecuatia cu inversa matricei (D + L) obtinem ecuatia recursiva in limbaj MathCad corespunzatoare metodei lui Gauss-Seidel:

x^<k+1> := - (D + L) Ux^<k+1>+ (D + L) B (17)

5. Probleme de rezolvat

Rezolvarea unei probleme abstracte

Fie sistemului de ecuatii liniare de forma AX = B unde A este matricea sistemului si B vectorul termenilor liberi. In notatie MathCad cu X^<0> notam aproximatia initiala a solutiei.

(18)

Construim matricea diagonala D si matricile triunghiulare inferioara si superioara, respectiv L si U in care poate sa fie descompusa matricea A a sistemului de ecuatii:

(19)

Consideram numarul maxim de iteratii, de exemplu, N := 50 si variabila sir k, definita astfel:

k := 1..N (20)

Pentru metoda Jacobi se utilizeaza ecuatia recursiva:

(21)

Pentru metoda Gauss-Seidel se utilizeaza ecuatia recursiva:

(22)

Observatie: Convergenta rapida a celor doua metode se bazeaza pe structura simetrica si pozitiv definita a matricii sistemului si pe forma diagonal dominanta a acesteia.

Se cere:

* Implementarea algoritmilor de rezolvare in limbaj MathCad;

* Stabilirea numarului de iteratii pana la stabilizarea solutiei aproximative;

* Analiza rezultatelor si vitezei de convergenta pentru cele doua metode prezentate;

* Comparatia cu solutia exacta calculabila imediat prin evaluarea expresiei A B , care pentru cazul nostru are forma:

(23)

Rezolvarea unui circuit electric

Se considera un circuit electric de forma unei punti de masura in regim de curent continuu(fig.1). Principiul de functionare este urmatorul. Puntea este alimentata la sursa de tensiune modelata cu generatorul ideal E si rezistenta interna Rs. Rezistentele R1, R2, R3, R4 formeaza ramurile puntii, iar Ro este rezistenta interna a aparatului de masura, detector de nul. Atunci cand prin acesta nu circula curent, rezulta ca tensiunea intre punctele 2 si 3 este nula si inseamna ca puntea este echilibrata. In acest caz rezistentele R1, R2, R3, R4 se afla intr-o anumita relatie. Astfel daca sunt cunoscute trei dintre acestea (considerate ca etaloane fixe sau reglabile) se poate determina cea de-a patra. Puntea de masura este utilizata pentru masurarea rezistentelor, folosind un aparat de masura sensibil dar fara caracteristici de precizie.

Pentru determinarea numerica a valorilor potentialului electric in nodurile 1, 2, 3 (nodul 0 fiind considerat nod de referinta) se poate utiliza metoda potentialelor la noduri. Aceasta are avantajul ca permite aplicarea metodelor clasice iterative clasice, descrise mai sus, deoarece matricea sistemului de ecuatii care rezulta este simetrica si pozitiv definita. Ecuatiile metodei potentialelor la noduri se construiesc astfel:

pentru fiecare nod (exceptand cel de referinta) se scrie cate o ecuatie.

coeficientul potentialului nodului respectiv este suma admitantelor convergente in nod;

coeficientii potentialelor nodurilor vecine sunt sumele cu semnul schimbat ale       admitantelor de legatura cu nodul principal;

termenul liber este dat de suma tensiunilor surselor convergente in nodul principal, inmultite cu admitantele ramurilor respective.

Fig.1. Schema circuitului electric in punte

Rezulta ca matricea sistemului si vectorul termenilor liberi sunt:

(24)

Se observa ca matricea A este simetrica, pozitiv definita si diagonal principala. Rezulta ca putem aplica atat metoda Jacobi cat si metoda Gauss-Seidel.

Se cere:

Scrierea matricilor corespunzatoare sistemului de ecuatii pentru circuitul dat, considerand ca elementele schemei au valori date mai jos;

Stabilirea numarului de iteratii pana la stabilizarea solutiei aproximative;

Analiza rezultatelor si vitezei de convergenta pentru cele doua metode prezentate;

Comparatia cu solutia exacta (data mai jos) pentru vectorul potentialelor V,       calculabila prin evaluarea expresiei A B.

E = 10 (V) Rs = 10 ( Ro = 10000 ( (25)

R1 = 1000 ( R2 = 50 ( R3 = 75 ( R4 = 1500 ( (26)

Pentru care se obtine solutia exacta: (25)

6. Concluzii

Metodele iterative sunt mai avantajoase din punctul de vedere al erorii de trunchiere       cumulate.

Acestea pot fi aplicate numai atunci cand matricea sistemului are anumite proprietati (simetrica si pozitiv definita, diagonal dominanta, etc.).

Eficienta criteriilor de oprire este dependenta de tipul de norma utilizat si de viteza de convergenta a procesului iterativ.

Viteza de convergenta depinde de caracteristicile sistemului de ecuatii (si implicit de cele ale problemei fizice care l-a generat) si de aproximatia initiala a solutiei.