Metode și modele de calcul

Tema: Rezolvarea numerica a sistemelor de ecuatii liniare

Scopul lucrarii :

1) Sa se rezolve sistemul de ecuatii liniare Ax = b, utilizind:

- Metoda lui Cholesky

- Metoda iterativa a lui Jacobi cu o eroare ϵ = 10-3

- Metoda iterativa a lui Gauss-Seidel cu o eroare ϵ = 10-3 si ϵ = 10-5

2) Sa se determine numarul de iteratii necesare pentru aproximarea solutiei sistemului cu eroarea data ϵ. Sa se compare rezultatele.

Notiuni teoretice:

Metoda lui Cholesky. Metoda lui Cholesky de rezolvare a sistemelor de ecuații liniare algebrice se mai numește metoda rădăcinii pătratice și constă în descompunerea sistemului Ax=b în două sisteme triunghiulare.

In aceasta metoda se presupune ca matricea A este o matrice simetrica si pozitiv definite.

Matricea L se alege astfel, incit A=LTL. Aceasta descompunere a matricei A se numeste factorizarea Choleskly.

Teorema: Daca matricea A este simetrica si pozitiva definite, atunci exista o unica matrice inferior triunghiulara LT cu elementele diagonale pozitive, astfel incit A=LT .

Factorizarea LU presupune descompunerea matricei sistemului (A) intr-un produs de doua matrice L*U. Matricea L trebuie sa fie inferior triunghiulară,in timp ce matricea U trebuie sa fie superior triunghiulară.

Forma factorizarii LU pentru un exemplu 3x3

Din această forma nu se pot calcula coeficienții matricelor L și U. Pentru ca acest lucru sa fie posibil se adaugă câteva constrângeri,astfel rezultând factorizarea Cholesky.

Daca sistemul A*x=b devine L*U*x=b, putem nota cu d=U*x. Astfel:

Pentru a rezolva sistemul de ecuații se determină mai întâi d din L*d=b prin rezolvarea unui sistem inferior triunghiular. Ulterior se rezolvă și sistemul d=U*x ca un sistem superior triunghiular.

Dacă matricea sistemului este simetrica și pozitiv definita, A se poate descompune astfel:

A=L*L’ (L’ fiind matricea L transpusa)

L este o matrice inferior triunghiulară.

Pentru determinarea elementelor matricei L se folosesc relațiile:

Metoda iterației și metoda Gauss-Seidel. Metoda iterației reprezintă o extindere a metodei aproximațiilor succesive folosite în cazul ecuațiilor de o singură necunoscută și metoda Jacobi pentru rezolvarea sistemelor de ecuații liniare. Acestă metodă permite rezolvarea sistemelor de ecuații neliniare de forma:

Plecând de la sistemului A*x=b, descompunem A=N-P, unde N este o matrice ușor de inversat. În continuare: