METODE ITERATIVE DE REZOLVARE A SISTEMELOR DE ECUATII LINIARE

METODE ITERATIVE DE REZOLVARE A SISTEMELOR DE ECUATII LINIARE

Se considera sistemul de n ecuatii liniare cu n necunoscute, scris sub forma matriciala :

(1)

unde A este o matrice reala cu n linii si n coloane, inversabila (nesingulara), iar b este un vector (coloana) cu n componente . Problema de calcul consta in determinarea unei solutii, x, a sistemului (1), adica a unui vector care satisface egalitatile (1). METODELE NUMERICE ITERATIVE constau in constructia unui sir convergent catre solutia exacta a sistemului (1). Oprirea procesului iterativ, adica trunchierea sirului are loc la un index de iterare, [s], determinat pe parcursul calculului, in functie de precizia impusa, astfel incat termenul curent, , sa constituie o aproximatie satisfacatoare a solutiei cautate, x. Metodele iterative se utilizeaza pentru sisteme de dimensiune ridicata.

Considerand matricea A descompusa sub forma , sirul se construieste utilizand relatia de recurenta:

(2)

unde aproximatia initiala, , este un vector arbitrar ales, dar fixat. Sirul (2) converge catre solutia sistemului (1), oricare ar fi , daca si numai daca toate valorile proprii ale matricii sunt, in modul, subunitare.

Lucrarea de fata se refera la metodele iterative JACOBI si GAUSS - SEIDEL . Se considera matricea A descompusa sub forma :

(3)

unde L contine elementele de sub diagonala principala a lui A, D contine elementele de pe diagonala principala a lui A, R contine elementele de deasupra diagonalei principale a lui A, iar restul de elemente din L, D si R, respectiv, sunt nule.

Metoda JACOBI se caracterizeaza prin descompunerea (3), in care:

Metoda GAUSS-SEIDEL se caracterizeaza prin descompunerea (3), in care:

APLICATIA 1:

Sa se realizeze, in mediul de programare MATLAB, programul pentru rezolvarea unui sistem de n ecuatii liniare cu n necunoscute, prin metoda iterativa Jacobi. Programul va compara solutia gasita cu cea furnizata de mediul MATLAB, aplicand o metoda directa de rezolvare.

In rezolvarea programului se vor parcurge urmatoarele etape, descrise partial in limbajul pseudocod:

1. Introducere parametru de control al executiei procedurii iterative, in variabila EPS. Introducere numar maxim iteratii in variabila max_iter.

2. Introducere ordin sistem in variabila n, .

3. Alocare spatiu de memorie pentru matricea sistemului in variabila a, prin initializarea acesteia cu o matrice nula, de dimensiune n. Introducerea elementelor matricii sistemului se face pe linii. Se testeaza elementele de pe diagonala principala a matricii a :

_ PENTRU i=1,n EXECUTA

| _ DACA ( abs(a(i,i)) < EPS ) ATUNCI

| | SCRIE 'element pe diagonala nul sau foarte mic'

| |_ SCRIE 'Rearanjati si reintroduceti A'

Reluare introducere in cazul in care pe diagonala principala s-au gasit elemente nule sau foarte mici in modul.

4. Alocare spatiu de memorie pentru termenul liber al sistemului in variabila b, prin initializarea acesteia cu un vector coloana nul cu n componente. Introducerea elementelor termenului liber al sistemului se face pe linii.

5. Alocare spatiu de memorie pentru aproximatia initiala a solutiei in variabila xn, prin initializarea acesteia cu un vector coloana nul, cu n componente. Introducerea elementelor vectorului xn se face pe linii.

6. Studiu de convergenta :

ATRIBUIE nn ← diag( diag(a) )

ATRIBUIE p ← nn-a

ATRIBUIE g ← inv(nn)*p

ATRIBUIE valp ← eig(g)

ATRIBUIE ro ← max( abs(valp) )

SCRIE 'raza spectrala matrice convergenta, ro=', ro

_ DACA ( ro < 1 ) ATUNCI

| SCRIE 'metoda converge !'

|ALTFEL

|_ SCRIE 'metoda NU converge !!!'

7. Calcul solutie prin metoda iterativa Jacobi:

ATRIBUIE vninf ← 1

ATRIBUIE iter ← 0

* Comutare pe mod afisare: format long e;

_ CAT TIMP ( (vninf > EPS) SI (iter < max_iter) ) EXECUTA

| ATRIBUIE iter ← iter+1

| ATRIBUIE xv ← zeros(n,1)

| ATRIBUIE xv ← xn

| * Adaptare solutie metoda JACOBI:

| _ PENTRU i=1,n EXECUTA

| | ATRIBUIE sum ← 0

| | _ PENTRU j=1,i-1 EXECUTA

| | |_ ATRIBUIE sum ← sum+a(i,j)*xv(j)

| | _ PENTRU j=i+1,n EXECUTA

| | |_ ATRIBUIE sum ← sum+a(i,j)*xv(j)

| |_ ATRIBUIE xn(i) ← (b(i)-sum)/a(i,i)

| * Sfarsit adaptare solutie metoda JACOBI

| ATRIBUIE vninf ← max( abs(xn-xv) )

| SCRIE 'iter =', iter

| SCRIE 'xn =', xn

|_ SCRIE 'vninf =', vninf

8. Calcul solutie folosind facilitatile mediului MATLAB :

ATRIBUIE x <-- ab

9. Afisare rezultate: iter, xn, x. Comutare pe mod de afisare:

format short;

10. Reluare program, daca se doreste, cu alta estimatie initiala a solutiei (punctul 5).

11. Reluare program, daca se doreste, cu alt termen liber (punctul 4).

12. Reluare program, daca se doreste, cu alt sistem de acelasi ordin (punctul 3).

13. Reluare program, daca se doreste, cu alt sistem, de alt ordin n (punctul 2).

14. Reluare program, daca se doreste, cu alti parametri EPS si max_iter (punctul 1).

OBSERVATII :

1. Descrierea anterioara a programului de realizat foloseste urmatoarele functii MATLAB: abs, diag, inv, eig, max, zeros, .

2. Programul se va rula pentru urmatoarele date de intrare:

I.)

II.)

APLICATIA 2:

Sa se realizeze, in mediul de programare MATLAB, programul pentru rezolvarea unui sistem de n ecuatii liniare cu n necunoscute, prin metoda iterativa Gauss-Seidel. Programul va compara solutia gasita cu cea furnizata de mediul MATLAB, aplicand o metoda directa de rezolvare.

In realizarea programului se vor parcurge EXACT aceleasi etape ca la APLICATIA 1. Deosebirile constau in modul de calcul al matricilor nn si p ce definesc matricea de convergenta, g (punctul 6), precum si in modalitatea de adaptare a aproximatiei solutiei in cadrul procedurii iterative (punctul 7) de la APLICATIA 1.

Matricile nn si p se calculeaza astfel:

ATRIBUIE nn ← tril(a)

ATRIBUIE p ← nn - a

Portiunea: * ADAPTARE SOLUTIE metoda JACOBI:

..

* SFARSIT ADAPTARE solutie metoda JACOBI

se inlocuieste cu:

* ADAPTARE SOLUTIE metoda GAUSS-SEIDEL:

_ PENTRU i=1,n EXECUTA

| ATRIBUIE sum ← 0

| _ PENTRU j=1,i-1 EXECUTA

| |_ ATRIBUIE sum ← sum + a(i,j)*xn(j)

| _ PENTRU j=i+1,n EXECUTA

| |_ ATRIBUIE sum ← sum + a(i,j)*xv(j)

|_ ATRIBUIE xn(i) ← (b(i) - sum)/a(i,i)

* SFARSIT ADAPTARE SOLUTIE metoda GAUSS-SEIDEL

OBSERVATII :

1. Descrierea programului de realizat foloseste aceleasi functii MATLAB ca la APLICATIA 1. Deosebire: functia diag este inlocuita cu functia tril.

2. Programul se va rula pentru datele de intrare prezentate la OBSERVATIA 2/ APLICATIA 1. Rezultatele se compara cu cele obtinute utilizand metoda Jacobi.