METODE DIRECTE DE REZOLVARE A SISTEMELOR DE ECUATII LINIARE

METODE DIRECTE 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 este un vector (coloana) cu n componente .

Problema de calcul consta in determinarea unei solutii a sistemului (1), adica a unui vector care satisface egalitatile (1) .

METODELE NUMERICE DIRECTE constau in reducerea sistemului (1) la un sistem echivalent, direct rezolvabil prin mijloace elementare. Tipic, procedura de reducere are la baza o schema de eliminare succesiva a necunoscutelor, traditional atribuita lui Gauss, prin care se efectueaza triangularizarea matricii sistemului, adica aducerea matricii A la forma superior triunghiulara sau inferior triunghiulara, prin transformari de echivalenta. Ca urmare, metodele directe furnizeaza solutia exacta, , a sistemului (1), in cazurile (ideale) in care erorile de rotunjire sunt absente .

Lucrarea de fata se refera la metoda directa de rezolvare a sistemelor de ecuatii liniare cu PIVOTARE TOTALA. Procedura implica doua etape :

I. Aducerea matricii sistemului la forma superior triunghiulara, alegand, la fiecare pas, drept element necesar eliminarii inainte a necunoscutelor - elementul cu valoare maxima, in modul, al matricii reduse .

Operatia de eliminare este insotita, daca este necesar, de permutarea liniilor si/sau coloanelor implicate, pentru a aduce pivotul in pozitia (k,k). Transformarile elementare de echivalenta afecteaza si termenul liber al sistemului, in mod corespunzator.

II. Rezolvarea sistemului triunghiular obtinut prin substitutie inversa. Permutarile de coloane in etapa I afecteaza ordinea componentelor vectorului solutie, deci, in final, este necesara o reordonare a acestora. Uzual, calculele au loc 'pe loc', matricea A si termenul liber b - initiale distrugandu-se .

APLICATIE

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

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

1. Introducere parametru de control al executiei procedurii de triangularizare, in variabila EPS.

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 (a se vedea OBSERVATIA 2). Salvarea valorilor din matricea a:

ATRIBUIE aa ← a

Reluare introducere in caz de eroare.

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. Salvarea valorilor din vectorul b:

ATRIBUIE bb ← b

Reluare introducere in caz de eroare.

5. Faza I : eliminarea inainte cu pivotare totala:

_ PENTRU i=1,n EXECUTA

|_ ATRIBUIE iord(i) ← i

* Pivotare totala:

_ PENTRU k=1,n-1 EXECUTA

| ATRIBUIE [mc,imc] ← max( abs( a(k:n,k:n) ) )

| ATRIBUIE [ml,jk] ← max(mc)

| ATRIBUIE ik ← imc(jk)

| ATRIBUIE ik ← ik + (k-1)

| ATRIBUIE jk ← jk + (k-1)

| _ DACA ( ik ~= k ) ATUNCI

| | ATRIBUIE wmx ← zeros(1,n)

| | ATRIBUIE wmx ← a(k,:)

| | ATRIBUIE a(k,:) ← a(ik,:)

| | ATRIBUIE a(ik,:) ← wmx

| | ATRIBUIE t ← b(k)

| | ATRIBUIE b(k) ← b(ik)

| |_ ATRIBUIE b(ik) ← t

| _ DACA ( jk ~= k ) ATUNCI

| | ATRIBUIE zmx ← zeros(n,1)

| | ATRIBUIE zmx ← a(:,k)

| | ATRIBUIE a(:,k) ← a(:,jk)

| | ATRIBUIE a(:,jk) ← zmx

| | ATRIBUIE it ← iord(k)

| | ATRIBUIE iord(k) ← iord(jk)

| |_ ATRIBUIE iord(jk) ← it

|

| * Triangularizare

|

| _ DACA ( abs(a(k,k)) > EPS ) ATUNCI

| | ATRIBUIE a(k+1:n,k) ← a(k+1:n,k)/a(k,k)

| | ATRIBUIE a(k+1:n,k+1:n) ← a(k+1:n,k+1:n) -

| | a(k+1:n,k)*a(k,k+1:n)

| | ATRIBUIE b(k+1:n) ← b(k+1:n) - a(k+1:n,k)*b(k)

| | ATRIBUIE a(k+1:n,k) ← zeros(n-k,1)

| |ALTFEL

| | SCRIE 'pivot nul sau foarte mic'

| | SCRIE 'STOP: algoritm'

| |_ * STOP program (functia MATLAB: return)

| SCRIE 'k = ', k

| SCRIE 'a = ', a

|_ SCRIE 'b = ', b

6. Faza a-II-a : calcul solutie sistem

* Substitutia inapoi :

_ PENTRU i=1,n EXECUTA

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

|_ |_ SCRIE 'matrice prost conditionata'

ATRIBUIE b(n) ← b(n)/a(n,n)

_ PENTRU i=n-1,(pas=-1),1 EXECUTA

| ATRIBUIE sum ← a(i,i+1:n)*b(i+1:n)

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

* Ordonare solutie :

ATRIBUIE x ← zeros(n,1)

_ PENTRU i=1,n EXECUTA

|_ ATRIBUIE x(iord(i)) ← b(i)

7. Calcul solutie folosind functiile MATLAB, pentru comparatie :

ATRIBUIE x_bs ← aabb

ATRIBUIE x_inv ← inv(aa)*bb

8. Afisare solutii : x, x_bs, x_inv (mod de afisare MATLAB dat de functia : format long e;) .

9. Calcul reziduuri asociate solutiilor calculate, precum si norme Euclidiene :

ATRIBUIE r ← bb-aa*x

ATRIBUIE nr ← norm(r,2)

ATRIBUIE r_bs ← bb - aa*x_bs

ATRIBUIE nr_bs ← norm(r_bs,2)

ATRIBUIE r_inv ← bb - aa*x_inv

ATRIBUIE nr_inv ← norm(r_inv,2)

Afisare nr, nr_bs, nr_inv (mod de afisare MATLAB dat de functia : format long e;) .

10. Reluare program, daca se doreste, cu alt termen liber (punctul 4). Daca are loc reluarea, inainte de aceasta se reface matricea a:

ATRIBUIE a ← aa

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

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

13. Reluare program, daca se doreste, cu alt parametru EPS (punctul 1) .

OBSERVATII :

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

2. Se recomanda urmatoarea modalitate generala de introducere a unei matrici, pe linii (n linii, m coloane), in variabila a:

* secventa de comenzi MATLAB :

a = zeros(n,m);

for i=1:n,

fprintf('linia %g:',i);

a(i,:) = input(' ');

end;

* exemplu de introducere (n=m=3) :

linia 1:

-------

[1 2 3] <RETURN>

linia 2:

-------

[4 5 6] <RETURN>

linia 3:

-------

[7 8 9] <RETURN>

S-au subliniat mesajele afisate de catre program; <RETURN> semnifica apasarea tastei respective.

3. Programul se va rula pentru urmatoarele date de intrare (rezultatele se vor nota si comenta) :

EPS = 1.e-10

I.)

II.)

(acelasi exemplu cu scalare pe linii)

III.) ;

IV.)