Matematici Asistate de Calculator

REZOLVAREA SISTEMELOR DE ECUATII LINIARE

Consideratii teoretice generale

Un sistem de „m” ecuaţii liniare cu „n” necunoscute este de forma:

a11 x1 + a12 x2 + . + a1n xn = b1

a21 x1 + a22 x1 + . + a2n x1 = b2

. . . . . . . . . . . . . . . . . . . . . . . . .

am1 x1 + am2 x2 + . + amn xn = bm

• coeficientii aij sunt reali

• termenii liberi bj sunt reali

• necunoscutele xi sunt numere reale

i=1,n , j=1,m.

Considerând matricele:

a11 a12 . a1n x1 b1

a21 a22 . a2n x2 b2

A = . . . . . . . . . . . . , x = . şi b = . ,

am1 am2 . amn xm bm

sistemul se poate scrie sub forma matriceală: A x = b .

De asemenea, sistemul se poate scrie sub formă restrânsă:

n ____ ____

∑ aij xj= bi , i=1,n; j=1,m.

i=1

Sistemele pot fi omogene, în situaţia în care matricea termenilor liberi , b, are doar elemente nule, sau neomogene, în caz contrar.Sistemele neomogene au solutie unica daca si numai daca matricea A a sistemului este nesingulara(detA≠0).Daca A este singulara (detA=0) atunci sistemul are o infinitate de solutii(compatibil nedeterminat) sau nu are nici o solutie (este incompatibil).

Un sistem se numeşte consistent dacă admite cel puţin o soluţie. Un sistem incompatibil se numeşte sistem inconsistent. Sistemele omogene sunt sisteme consistente, ele admiţând întotdeauna soluţia banală.

Un sistem se spune că este bine condiţionat dacă mici modificări ale elementelor matricelor A şi b conduc la mici modificări ale elementelor lui x.

Pentru ameliorarea gradului de condiţionare a sistemelor de ecuaţii liniare, înainte de rezolvare se recomandă: modificarea ordinii ecuaţiilor şi/sau necunoscutelor astfel încât matricea sistemului să fie diagonal dominantă; aplicarea operaţiei de scalare pentru ca necunoscutele şi termenii liberi să aibă acelaşi ordin de mărime.

După raportul dintre numărul ecuaţiilor şi numărul necunoscutelor, sistemele de ecuaţii liniare sunt de trei tipuri:

a) subdeterminate, dacă m < n, caz în care soluţia sistemului va depinde de un număr de parametrii egal cu diferenţa dintre numărul necunoscutelor, n, şi rangul matricei sistemului;

b) compatibile determinate, dacă m = n şi det(A) ≠ 0 ; dacă det(A)= 0, sistemele pot fi compatibile nedeterminate sau incompatibile;

c) supradeterminate, dacă m > n; acesta este cazul în care se pune cel mai des problema incompatibilităţii.

Sistemele de ecuaţii liniare se pot rezolva prin două tipuri de metode: metode directe, care se mai numesc şi metode exacte sau metode de eliminare, şi metode iterative.

Una din cele mai folosite si mai simpla metoda directa este metoda inversarii matriceale bazata pe inmultirea la stanga cu A-1 (X=A-1*b).

In rezolvarea sistemelor de ecuatii liniare exista cateva teorme de testare a compatibilitatii.

TEOREMA lui KRONECKER-CAPELLI:un sistem de ecuatii liniare este compatibil daca si numai daca rangul matricei sistemului este egal cu rangul matricei extinse a sistemului.

TEOREMA lui CRAMER:un sistem de ecuatii liniare neomogen este compatibil daca determinantul amtricei sistemului este nenul;pt un system omogen determinantul trebuie sa fie nul.

TEOREMA lui ROUCHE:un sistem de ecuatii liniare este compatibil daca si numai daca toti minorii caracteristici ai matricei sistemului sunt nuli.

În metodele iterative se pleacă de la o eroare iniţială, care scade cu numărul de iteraţii, ajungând, în final, sub un prag impus.

Determinarea solutiei exacte a sistemului AX = b cu ajutorul unor metode de tip iterativ este posibila numai dupa efectuarea unui numar nelimitat - teoretic infinit - de iteratii sau pasi. Deoarece nici o metoda practica nu poate cicla la infinit, rezulta ca metodele iterative determina doar o solutie aproximativa, aproximare prin trunchiere, care se abate mai mult sau mai putin fata de solutia exacta X, in functie de precizia de calcul dorita.

Mai concret, metodele iterative apeleaza la construirea unui sir de aproximatii succesive x0, x1, . , xk care, in anumite conditii, tinde catre solutia exacta X. In cazul in care pentru sirul aproximatiilor succesive nu este posibila definirea unei limite, se spune ca metoda respectiva diverge.

In cazul in care sirul aproximatiilor succesive are o limita, se spune ca metoda este convergenta. In acest caz se poate defini o relatie de recurenta intre doua aproximatii succesive xk si xk+1.

Rezolvarea sistemelor de ecuaţii liniare este o problemă foarte importantă pentru domeniul simulării numerice.