Metode variationale pentru rezolvarea sistemelor de ecuatii liniare - Metoda pantei maxime

Metode variationale pentru rezolvarea sistemelor de ecuatii liniare

Tematica lucrarii: 1. Principiul metodelor variationale;

2. Metoda pantei maxime;

3. Metoda gradientilor conjugati;

4. Rezolvarea numerica in MathCad;

5. Problema de rezolvat;

6. Concluzii.

1. Principiul metodelor variationale

Metodele variationale transforma problema data intr-o problema de extremum a unei functionale. Un sistem de ecuatii liniar reprezinta o ecuatie vectoriala. Solutia ei este vector, adica un punct cu coordonatele x , x x_n in spatiu vectorial.

Functionala este o aplicatie definita in spatiul vectorial si ia valori reale .

Problema de extremum consta in determinarea minimului finctionalei. Vectorul pentru care se realizeaza acest minim trebuie sa coincida cu solutia sistemului de ecuatii. Metodele variationale indica modul de costructie al functionalei.

In cazul sistemelor de ecuatii liniare cu matrice simetrica si pozitiv definita aceasta poate avea forma:

F(x) = (Ax,x) - 2(b,x) (1)

Procedeele de minimizare ale functionalelor pot fi iterative sau pseudo-deterministe atunci cand numarul de pasi pentru care este garantata eficienta metodei este apropiat de numarul de ecuatii.

2. Metoda pantei maxime

Functionala poate fi privita ca o functie de mai multe variabile. Fara a reduce generalitatea problemei sa consideram cazul a doua necunoscute. Atunci reprezentarea grafica este o suprafata al carei inaltime minima reprezinta minimul functionalei. Curbele de nivel unesc punctele cu aceeasi inaltime. Atunci metoda pantei maxime are o reprezentare geometrica intuitiva si consta in cautarea solutiilor aproximative, ca puncte in spatiul vectorial, aflate la capatul unor segmente perpendiculare pe curbele de nivel ale graficului functionalei in punctele determinate la iteratia precedenta.

Fara a reduce gradul de generalitate consideram procesul iterativ al metodei pantei maxime pentru cazul a doua dimensiuni (sistem de doua ecuatii cu doua necunoscute). Atunci vectorul x are numai doua componente si poate fi reprezentat ca un punct in plan. Functionala va fi o functie de doua variabile. Graficul lui F(x) in spatiul tridimensional real reprezinta o suprafata. Atunci solutia la pasul k+1 este exprimata in functie de solutia la pasul k prin relatia vectoriala:

x^k+ = x^k grad[F(x^k (2)

unde grad[F(x^k)] reprezinta operatorul gradient aplicat functionalei F in punctul x^k

Operatorul gradient este definit de relatia:

(3)

unde i, j, k reprezinta versorii unitari paraleli cu axele spatiului tridimensional, iar derivatele partiale sunt calculate in punctul x^k . Geometric, grad[F(x^k)] reprezinta un vector avand componente vitezele de variatie ale functionalei F dupa cele doua axe. El este orientat dupa directia de variatie maxima (panta maxima) a lui F si este perpendicular pe curba de nivel care trece prin punctul x . Se poate demonstra ca in cazul functionalei definita de relatia (1), gradientul lui F(x) este dat de relatia:

grad F = 2(Ax - b) (4)

Daca facem substitutia, relatia (2) poate fi pusa sub forma:

(5)

Daca notam cu _k produsul 2_{k k k} (6)

relatia (5) se poate rescrie sub forma:

x^k+ = x^k _k (Ax^k - b) (7)

Numarul (scalarul) _k trebuie ales astfel incat procesul iterativ sa covearga catre solutie. Sa notam cu r^k 'restul':

r^k = Ax^k - b (8)

Se poate arata ca procesul converge daca punem conditia de ortogonalitate (produse scalare nule) a resturilor r^k si r^k+1 la doi pasi consecutivi:

(r^k,r^k+1 (9)

Atunci _k este determinat de relatia:

(10)

Rezulta ca procesul iterativ de aproximare a solutiei sistemului poate fi exprimat prin relatia:

(11)

3. Metoda gradientilor conjugati

In cazul metodei pantei maxime, solutia la pasul k+1 se exprima in functie de solutia la pasul k prin relatia (2). Acesta este un proces iterativ propriu-zis in care solutia aproximativa se apropie de solutia exacta pe masura ce numarul iteratiei este mai mare (daca se face abstractie de eroarea produsa prin trunchierea reprezentarii numerice).

Metoda gradientilor conjugati este caracterizata printr-un ordin de aproximare sporit, deci are o viteza de convergenta mult mai mare, utilizand la fiecare pas al procesului iterativ valori ale solutiei calculate cu doi pasi in urma. Nu numai atat, este foarte important de mentionat ca metoda gradientilor conjugati este una de tip pseudo-determinist. Aceasta inseamna ca daca se face abstractie de eroarea de trunchiere, eroarea de aproximare minima se obtine dupa un numar de pasi egal cu numarul de ecuatii ale sistemului. Rezulta astfel o viteza de convergenta maxima. Caracterul pseudo-determinist este datorat procesului de ortogonalizare pe care se bazeaza metoda. Astfel la fiecare pas, vectorul corespunzator erorii de aproximare este liniar independent fata de vectorii de eroare obtinuti la pasii precedenti. Rezulta ca dupa terminarea procesului de ortogonalizare eroarea ar trebui sa fie nula. In realitate nu este asa datorita erorii de trunchiere care actioneaza si se poate cumula la fiecare pas. Din aceasta cauza solutia iterativa este perturbata, si este posibil ca in cadrul unor sisteme mari, cu caracteristici de conditionare modeste, solutia obtinuta dupa numarul maxim de iteratii sa fie mai departe de solutia exacta decat in cazul cand numarul de iteratii ar fi mai redus. Metoda clasica, care se bazeaza pe o metoda de ortogonalizare apriori, care nu tine seama de valorile calculate pe parcurs, poate fi imbunatatita prin aplicarea unui proces de ortogonalizare aposteriori, care tine seama de calculele realizate la fiecare pas. In acest cz numarul optim de iteratii poate depasi numarul de ecuatii ale sistemului. Desi mai performanta ca precizie, metoda imbunatatita necesita o cantitate sporita de calcule numerice.

Se poate demonstra ([2]) ca metoda gradientilor conjugati are la baza urmatoarea ecuatie recursiva:

(12)

unde variabila de lucru este data de expresia:

(13)

Daca explicitam variabila x^k+1 in partea stanga, rezulta urmatorul procesul iterativ:

(14)

4. Rezolvarea numerica in MathCad

Metoda pantei maxime

Daca definim restul la fiecare pas de aproximare ca o functie de variabila generica t :

(15)

si consideram variabila sir: k := 0..10

metoda pantei maxime poate fi exprimata in limbaj MathCad prin urmatorul proces iterativ :

(16)

unde notatia cu paranteze ascutite x^<k> reprezinta vectorul x obtinut la iteratia k, iar produsele notate cu (.) reprezinta produse scalare intre vectori.

Metoda gradientilor conjugati

In cadrul limbajului MathCad notatia cu indice inferior este utilizata pentru sirurile de variabile (variabile indexate), iar notatia cu indice superior, plasat intre paranteze ascutite, este utilizata pentru sirurile de vectori. Daca o variabila scalara este definita cu doi indici, atunci programul o va trata ca pe o matrice. In aceeasi ordine de idei, un sir de vectori este tratat ca o matrice. Variabila de lucru este un scalar, dar depinde de doua numere k si m. Acestia reprezinta de fapt indici pentru vectorii rest r^k sau r^m . Rezulta ca trebuie sa fie definita ca o functie de doua variabile vectoriale u si v, astfel:

(17)

unde Au - b si Av - b reprezinta vectorii rest, corespunzatori vectorilor u si v, iar notatia (.) reprezinta, de la caz la caz, fie aplicatia matricii A asupra vectorului argument (inmultirea intre matrice si vector), fie produsul scalar intre doi vectori. Corespondenta dintre notatiile si (u,v) poate fi realizata in modul urmator. Tinand seama ca:

r^k = Ax^k - b si (18)

rezulta (19)

In aceste conditii metoda gradientilor conjugati poate fi reprezentata sub forma unei singure ecuatii recursive, de forma:

(20)

5. Problema de rezolvat

Pentru a exemplifica modul de functionare a metodelor expuse in cadrul limbajului MathCad, consideram sistemul de ecuatii de ordinul patru defunit de matricea A si vectorul termenilor liberi b, astfel:

(21)

Pentru aproximatia initiala a vectorului solutiei consideram valori nule: (22)

Dupa 10 iteratii se obtin urmatoarele rezultate, respectiv pentru metoda pantei maxime (MPM) si pentru metoda gradientilor conjugati (MGC) :

MPM : x = (0.768, 0.208, 0.205, 0.234) ; MGC : x = (0.773, 0.204, 0.201, 0.228)

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 metodele prezentate mai sus;

Comparatia cu solutia calculata iterativ, utilizand rezolvitorul disponibil in cadrul programului MathCad.

6. Concluzii

Metodele variationale pentru rezolvarea sistemelor de ecuatii liniare au urmatoarele caracteristici:

sunt metode iterative (calculeaza aproximatii succesive ale solutiei sistemului);

au viteza de convergenta maxima datorita caracterului pseudo-determinist;

simplifica problema criteriului de oprire a procesului iterativ (din acelasi motiv);

impun anumite restrictii asupra proprietatilor matricii sistemului de ecuatii (sa fie simetrica si pozitiv definita);

sunt caracterizate de o complexitate sporita a calculelor numerice;

sunt mai usor afectate de erorile de trunchiere, fata de metodele mai simple (Jacobi si Gauss-Seidel) care de regula duc la stabilizarea acestui tip de eroare;

Trebuie remarcat ca desi par a fi destul de departe de perfectiune, metodele variationale in anumite situatii au performante greu de egalat de alte metode. Desi aparent, se pot aplica unei clase relativ restranse de sisteme de ecuatii, exista o categorie foarte larga de probleme modelare matematica care se pot conforma restrictiilor impuse (utilizand metoda elementului finit).