Rezolvarea Numerică a Sistemelor de Ecuații Liniare

Rezolvarea numerica a sistemelor de

ecuatii liniare

Scopul lucrarii:

1) Sa se rezolve sistemul de ecuatii liniare Ax = b, utilizînd:

- metoda eliminarii Gauss;

- metoda lui Cholesky (metoda radacinii patrate);

- metoda iterativa a lui Jacobi cu o eroare µ = 10-3;

- metoda iterativa a lui Gauss-Seidelcu o eroare µ = 10-3 si µ = 10-5;

2) Sa se determine numarul de iteratii necesare pentru aproximarea solutiei sistemului cu o eroare data µ. Sa se compare rezultatele.

3) Sa se inverseze matricea A cu ajutorul metodei Jordan-Gauss.

V - 5

Consideratii teoretice:

Metoda eliminarii a lui Gauss consta în a aduce sistemul initial la un sistem echivalent avînd matricea coeficientilor superior triunghiulara. Transformarea sistemului dat într-un sistem de forma triunghiulara, fara ca sa se modifice solutia sistemului, se realizeaza cu ajutorul urmatoarelor 3 operatii de baza :

1) rearanjarea ecuatiilor (schimbarea a 2 ecuatii între ele) ;

2) înmultirea unei ecuatii cu o constanta (diferita de zero) ;

3) scaderea unei ecuatii din alta si înlocuirea celei de-a doua cu rezultatul scaderii.

Metoda lui Cholesky de rezolvare a sistemelor de ecuatii liniare algebrice se mai numeste metoda radacinii patrate si consta în descompunerea sistemului Ax=b în doua sisiteme triunghiulare :

LTy=b, Lx=y.

unde L e o matrice superior triunghiulara, iar LT matricea transpusa ei.

În aceasta metoda se presupune ca matricea A este o matrice simetrica si pozitiv definita. Matricea L se alege astfel, încît A=LLT. Elementele lij ale matricei inferior triunghiulare L pot fi calculate în felul urmator :

Se determina prima coloana a matricei L

L11=±11 , li1= ±i1/li1 , i=2,3,…,n ;

Dupa ce s-au obtinut primele (k-1) coloane ale matricei L se calculeaza coloana k :

Lkk=akk -l2kj ,

lik=(±ik -lijlkj)/lkk , i=k+1,…n

Metode iterative de rezolvare a sistemelor de ecuatii lineare. Metodelele Jacobi si Gauss-Seidel

Metodele iterative se constuiesc utilizînd desfacerea matricei A definita prin A=S-T. Atunci sistemul Ax=b (1) e echivalent cu sistemul Sx=Qx+d, (2) sau x=Qx+d, (3)unde Q=S-1T, d=S-1b. Prin urmare putem construi sirul {x(k)}utilizînd relatia recurenta:

Sx(k+1)=Tx(k)+b, k=0,1,2... (4) sau x(k+1) =Qx(k)+d. (5)

unde x(0) , ce apartine Rn , e o aproximatie initiala a solutiei x*.

Pentru a reduce sistemul (1) la o forma (3) sau (4), potrivita pentu iteratie,

desfacerea matricei A trebuie sa satisfaca conditiile :

a) Sistemul (5) are o solutie unica x(k+1) si se rezolva usor. De aceea matricea S se alege de o forma simpla si este ireversabila.Ea poate fi diagonala sau triunghiulara.

b) Sirul {x(k) }k=1 converge catre solutia exacta x* oricare ar fi x(0).

Presupunem ca elementele diagonale aii`0, i=1,2,...n. Atunci în calitate de matrice S se poate lua matricea diagonala atasata matricei A:

S=diag(±11, ±22, …,±nn)

Avem: S-1=diag(1/±11,1/±22,…,1/±nn)

În acest caz sistemul (2) devine :

xi=1/±ii(bi-±ijxj(k)), i=1,2,…,n.

Procesul iterativ (5) este definit prin : xi(k +1)= xi(k+1), i=1,2,…n.

Astfel obtinem o metoda de rezolvare a sistemului liniar (1) numita metoda lui Jacobi.

În metoda lui jacobi e necesar de a pastra în memoria calculatorului toate componentele vectorului x(k) atît timp cît se calculeaza vectorul x(k+1). Putem modifica metoda lui Jacobi astfel încît la pasul (k+1) sa folosim în calculul componentei xi(k+1), valorile deja calculate la aceasi pas: x1(k+1), x2(k+1),…, xi-1(k+1).

Aceasta modificare a metodei lui Jacobi se numeste metoda lui Gauss-Seidel, iar sirul iterativ devine: xi(k+1)= 1/±ii(bi-±ijxj(k)- ±ijxj(k)), i =1,2,…,n.