Metode directe de rezolvări pentru

Metoda directă 1: metoda de eliminare a lui Gauss

Metoda lui Gauss de rezolvare a unui sistem de ecuaţii liniare constă în eliminarea succesivă a necunoscutelor astfel încât sistemul să se reducă la unul echivalent având matricea superior triunghiulară, iar apoi determinarea necunoscutelor prin substituţie inversă.

Metoda lui Gauss nu este întotdeauna cea mai bună alegere în rezolvarea sistemelor algebrice liniare, dar este uşor de înţeles ca principiu. Este "cea mai directă" metodă şi este deosebit de utilă pentru cazurile când rezolvarea sistemului algebric este esenţial în ansamblul rezolvării unei probleme.

Metoda directă 1: metoda de eliminare a lui Gauss

Algoritmul eliminării lui Gauss reduce o matrice dată la o matrice a cărei componente de pe diagonală şi deasupra ei rămân diferite de zero, iar în rest ea este nulă. Matricea de această formă se numeşte superior triunghiulară.

Eliminarea lui Gauss se realizează în n paşi, unde n este ordinul matricii A. Pentru a evita creşterea erorilor de rotunjire se folosesc proceduri de pivotare, care determină elementele de pe diagonală ce se folosesc în transformările Gauss. Aceste procedee se repetă la fiecare etapă a eliminării şi pot fi de două feluri:

-eliminare cu semipivot-eliminare cu pivot

Metoda directă 1: metoda de eliminare a lui Gauss

Semipivot este acel element care la etapa k se află pe poziţia elementului akk, fiind determinat dintr-o linie i0 şi o coloană k cu proprietatea că

 Pentru acest lucru s-a mutat linia i0 la linia k şi linia k la linia i0.

Operaţia se numeşte semipivotare.Pivot este acel element care la etapa k se află pe poziţia

elementului akk, fiind determinat dintr-o linie i0 şi o coloană j0 cu proprietatea 

 Pentru acest lucru s-a schimbat linia i0 cu linia k şi coloana j0 cu coloana k. Acest procedeu de permutare a liniilor în vederea aducerii elementului maxim în valoare absolută în poziţia corespunzătoare pe diagonala principală se numeşte pivotare.

a ai k kk0

a ai j kk0 0

Metoda directă 1: metoda de eliminare a lui Gauss

Fie sistemul algebric liniar: Ax=b;

Mnxn (R); Rn

Transformarea sistemului iniţial într-un sistem de formă triunghiulară se realizează cu ajutorul a trei operaţii elementare:a) interschimbarea a două ecuaţii între ele;b) înmulţirea unei ecuaţii cu o constantă nenulă;c) scăderea unei ecuaţii din alta

A

a a a a

a a a a

a a a a

n

n

n n n nn

11 12 13 1

21 22 23 2

1 2 3

...

...

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

...

nb

b

b

b

2

1

Metoda directă 1: metoda de eliminare a lui Gauss

Pasul1:Eliminarea necunoscutei x1 din ecuaţia sistemului începând cu o a doua eliminare cu semipivot.

eliminare cu semipivot.

Se înmulţeşte prima ecuaţie cu: i=2,3,...,n

şi se adună la celelalte corespunzător coeficienţiilor ecuaţiilor. Vom obţine

şi b=

niiaa

,1111 max

a

ai1

11

~

...

............................A

a a a

a a

a a

n

n

n nn

11 12 1

221

21

11 1

0

0

b

b

bn

1

21

1

.....

Metoda directă 1: metoda de eliminare a lui Gauss

a aa

aa

b ba

ab

ij iji

j

i ii

1 1

111

1 1

111

,

,

i = 2,3, ... , n; j = 1,2, ... , n

i = 2,3, ... , n

Pasul 2:Eliminarea necunoscutei x2 din ecuaţia sistemului începând cu a treia ecuaţie. Avem

Se înmulţeşte a doua ecuaţie cu: i=3,4,...,n

2

,222 max i

niaa

11

1

a

a i

Metoda directă 1: metoda de eliminare a lui Gauss

Vom obţine:

unde

2

23

12

1

223

24

243

23

233

12

123

122

1131211

......

...

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

...

...

...

...

~

n

nnn

n

n

n

n

b

b

b

b

bsi

aa

aa

aa

aaa

aaaa

A

a aa

aa

b ba

ab

ij iji

j

i ii

2 1 21

221 2

1

2 1 11

221 2

1

, i = 2,3,... , n; j = 1,2,... , n

Metoda directă 1: metoda de eliminare a lui Gauss

Pasul n: După parcurgerea tuturor paşilor de eliminiare Gauss, sistemul algebric s-a redus astfel:

)(

)2(3

)1(2

1

3

2

1

)(

)2(3

)2(33

)1(2

)1(23

)1(22

1131211

........

...000

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

...00

...0

...

nnn

nnn

n

n

n

b

b

b

b

x

x

x

x

a

aa

aaa

aaaa

Metoda directă 1: metoda de eliminare a lui Gauss

Odată procesul de eliminare încheiat, urmează substituţia inversă pentru determinarea soluţiei sistemului algebric Ax=b:

.

.

.

i = n, n-1, ..., 1

)1(1

)1(1)1(

11

1

)(

)(

1

nnnn

nnn

nn

n

nnn

nn

n

axba

x

a

bx

)(

1

)(

)(

1 iij

n

ijj

iii

ii

i axba

x

Metoda directă 1: metoda de eliminare a lui Gauss

Încercaţi să rezolvaţi prin eliminarea lui Gauss sistemul:

2X1 + 4X2 - X3 = 153X1 - 5X2 + X3 = -43X1 + 2X2 + 3X3 = 38

Metoda directă 2: metoda de eliminare a lui Gauss-Jordan

Spre deosebire de metoda lui Gauss de eliminare, metoda lui Gauss-Jordan reduce matricea sistemului la o matrice diagonală cu toate elementele nule cu excepţia diagonalei. Metoda Gauss-Jordan este foarte stabilă din punct de vedere numeric, ea particularizează eliminarea lui Gauss şi rezolvă dintr-o dată două probleme:

-determină soluţia sistemului liniar-determină matricea inversă a sistemului: A-1 .

Metoda lui Gauss poate fi considerată a fi poziţionată, din punct de vedere al aplicabilităţii, între metoda Gauss-Jordan şi metodele de descompunere triunghiulară, de tipul LU.

Metoda directă 2: metoda de eliminare a lui Gauss-Jordan

Dezavantajele principale ale acestei proceduri sunt:

1.Cere ca tot ce este în partea dreaptă să fie stocat şi manipulat în acelaşi timp.2. Atunci când matricea inversă nu este dorită procedura de eliminare a lui Gauss-Jordan este de trei ori mai înceată decât cea mai bună tehnică de rezolvare a sistemului liniar.

Principalul atuu al metodei este că este atât de stabilă ca şi oricare metodă directă, poate chiar un pic mai mult, când este folosită tehnica de pivotare totală. Ea este "foarte directă", uşor de înţeles şi reprezintă o bună garanţie (soluţie de rezervă) de fiecare dată când ceva nu merge bine şi ne-am putea gândi că poate fi vorba de metoda de rezolvare a sistemului liniar.

Metoda directă 2: metoda de eliminare a lui Gauss-Jordan

Vectorul soluţie nu se schimbă în nici un fel dacă înlocuim orice linie în A cu o combinaţie liniară de ea însăşi şi orice alte linii atâta vreme cât respectăm aceleaşi combinaţii liniare cu liniile din b. Procedura de eliminare a lui Gauss-Jordan foloseşte operaţiuni de acest tip pentru a reduce matricea A la matricea identitate de aceeaşi dimensiune.

1.Prima linie este împărţită la elementul a11.(astfel ea devine o combinaţie liniară trivială de elemente ale primei linii cu orice altă linie; bineînţeles coeficientul este zero pentru orice altă linie).2.Apoi se scade cantitatea liniei întâi din toate celelalte astfel încât toţi ai1 să devină zero. Astfel prima coloană a matricei A coincide cu prima coloană a matricei identice.

Metoda directă 2: metoda de eliminare a lui Gauss-Jordan

Acum ne ocupăm de a doua coloană şi împărţim linia a doua cu a22 şi apoi scădem linia a doua din liniile 1,3,4,... astfel încât să avem valorile zero pe a doua coloană. A doua coloană s-a redus astfel la forma coloanei a doua identitate.

Şi aşa mai departe procedura se continuă pentru toate liniile matricei A.

Evident vom ajunge să avem probleme dacă întâlnim un element nul pe diagonală când împărţim linia cu elementul diagonal al ei (pivotul).

Nu atât de evident, dar adevărat este faptul că eliminarea Gauss-Jordan fără pivotare este numeric instabilă în prezenţa unui roundoff, chiar dacă un pivot zero nu este întâlnit. Cu alte cuvinte nu se va folosi eliminarea Gauss-Jordan sau eliminarea Gauss fără pivotare.

Metoda directă 2: metoda de eliminare a lui Gauss-Jordan

În eliminarea lui Gauss Jordan, fiecare lanţ de calcul constituie o scădere şi o înmulţire, deci sunt de N3 ori executate pentru o matrice pătratică şi de N2M pentru un sistem de N ecuaţii şi M necunoscute. În cazul lanţului de calcul a lui Gauss, eliminarea se face numai 1/3 * N^3 ori deoarece se reduce numai jumătate de matrice şi numerele făcute zero reduc ordinul la o treime.

Atât eliminarea lui Gauss cât şi eliminarea lui Gauss-Jordan au dezavantajul că membrul drept trebuie cunoscut înainte. Metoda descompunerii LU nu are acest dezavantaj şi are tot un număr mic de operaţii atît pentru soluţii cu oricâte părţi drepte, cît şi pentru inversare de matrici.

Metoda directă 3: metoda factorizării LU

Fie sistemul algebric : Ax=b, unde A este matrice pătratică de dimensiune nxn.

Metoda factorizării sau a descompunerii LU are la bază ideea scrierii oricărei matrici pătrate A sub formă de produs a două matrici, una inferior triunghiulară şi cealalată superior triunghiulară. Rezolvarea sistemului realizâdu-se prin transformarea sub formă de două sisteme simplificate ce se rezolvă prin substituţie directă, respectiv prin substituţie inversă.

Există mai multe variante de descompunere a matricii A sub forma LU. Vom discuta varianta Crout a descompunerii LU. Varianta Crout are particularitatea că matricea superior triunghiulară U are pe diagonala principală elementele egale cu unitatea.

Metoda directă 3: metoda factorizării LU

Factorizarea matricii sistemului sub forma A=LU, presupune o modificare a algoritmul lui Gauss astfel: 1) La fiecare etapă k a algoritmului Gauss se copiază mai întâi elementele coloanei k din A, aflate sub diagonală (inclusiv elementele akk) în coloana k a matricei L. 2) Apoi se efectuează etapa k a algoritmului Gauss asupra matricii A (linia k se împarte la akk, se înmulţeşte pe rând cu aki, pentru i>k şi se scade din liniile următoare, pentru anularea elementelor coloanei k aflate sub pivot).

După ultima etapă a algoritmului s-a obţinut matricea L, iar matricea A adusă la forma superior triunghiulară conţine chiar elementele matricei U.

Metoda directă 3: metoda factorizării LU

matricile L şi U în varianta Crout arată astfel:

Problema determinării matricii L se regăseşte tot în paşii algoritmului Gauss de eliminare.Eliminarea poate fi privită ca o transformare a matricii A în matricea U. Să notăm cu F această transformare şi avem că: FA=U.

L

l

l l

l l l ln n n nn

11

21 22

1 2 3

0 0 0

0 0

...

...

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

...

nn

n

n

u

u

uu

UA

00

10

1

2

112

Metoda directă 3: metoda factorizării LU

Matricea transfomărilor F poate fi determinată dacă aplicăm eliminarea Gauss la o matrice identitate, deoarece matricea identitate este element neutru pentru inelul matricilor. Considerând un exemplu de matrice de dimensiune 3x3, avem:

Aplicăm întâi transformarea F matricii A, obţinând matricea U şi apoi aplicăm transformarea F matricii I pentru a obţine pe F. Rezultatele calculului sunt:

100

010

001

,

313

231

312

IA

11428.04286.1

015.0

001

,

5714.100

5.05.30

312

FU

Metoda directă 3: metoda factorizării LU

Prima matrice este aşadar F∙A=U. A doua matrice este rezultatul aplicării lui F asupra matricii identitate I, care este egală cu matricea F însăşi. Se observă că F este o matrice inferior triunghiulară.

Prin comparaţie cu expresia matriceală A=L∙U, relativă la expresia transformării A=F-1U se observă uşor că L=F-1. Aşadar L poate fi obţinută din inversa lui F.

Inversa unei matrici triunghiulare este uşor şi rapid de obţinut. Inversa unei matrici triunghiular inferioară este tot o matrice inferior triunghiulară.

Metoda directă 3: metoda factorizării LU

Problema se pune în continuare la cât de mult este afectată matricea L, respectiv matricea U de pivotare. În algoritmul lui Gauss de eliminare ordinea liniilor este schimbată prin pivotare. Dacă schimbarea ordinii este cunoscută înainte de eliminarea Gauss putem exprima efectul schimbării ordinii printr-un operator P, unde P este o matricea unitară. Înmulţind ecuaţia originală cu P obţinem:

PAx=Pysau notînd cu Ã=PA şi ў=Py:

Ãx=ў

Astfel putem aplica eliminarea lui Gauss matricii à fără a mai fi nevoie de pivotare. Matricea à poate fi descompusă la rândul ei în matricile L şi U fără a mai fi nevoie de pivotare. În algoritmul Gauss cu pivotare matricea obţintă după eliminare este U din descompunerea lui Ã.

Observatie: Matricea P poate fi obţinută prin aplicarea pivotării la o matrice unitate în acelaşi mod în care a fost făcută în eliminarea Gauss.

Metoda directă 3: metoda factorizării LU

Determinarea matricilor L şi U pentru matricea A, prin varianta Crout:

.

.

.

100

10

1

0

00

3

23

1312

333231

2221

11

333231

232221

131211

u

uu

lll

ll

l

aaa

aaa

aaa

n

11

12

11

1212121211

313121211111 ;;

a

a

l

auaul

alalal

Metoda directă 3: metoda factorizării LU

Pentru eficienţa folosirii spaţiului de memorie, vom păstra în locaţia pentru matricea A atât matricea L, cât şi matricea U (factorizare pe loc). Acest lucru este posibil deoarece se poate vedea uşor că la fiecare calcul pentru lij şi uij se foloseşte elementul aij din matricea A, fără a avea nevoie de alte elemente din A de la paşi anteriori celui curent.

Forma schemei de memorare:A=L+U-I

La fiecare etapă k se păstrează neschimbată coloana k a matricei A (elementele matricei L) şi se împart la akk doar elementele liniei k aflate la dreapta pivotului. Astfel elementele lij ale matricii L se vor găsi în A pe poziţii diagonale sau subdiagonale, iar elementele uij ale matricii U se vor găsi în A deasupra diagonalei. Elementele nule din L şi U ca şi elementele diagonale egale cu 1 nu se memorează.

nnnnn

n

n

llll

uull

uuul

A

...

__|....................

...

...

321

2232221

1131211

Metoda directă 3: metoda factorizării LU

În concluzie se poate observa că metoda LU este mai eficientă în timpul de calcul decât metoda de eliminare a lui Gauss, deoarece matricea A este descompusă o singură dată obţinând pe L şi U, în vreme ce în metoda Gauss avem de efectuat n paşi de eliminare asupra matricii A.  Metoda LU de descompunere poate fi aplicată în Matlab prin comanda lu. Sînt două formate de scriere a ei în Matlab. Primul format este:

[l, u, p]=lu(A)unde A este matricea ce urmează a fi descompusă, l, u şi p corespund matricilor L, U şi P din scrierea de mai sus.P= matrice unitara rezultata din matricea unitate careia i s-a aplicat aceasi pivotare ( intreschimbari de linii si coloane )ca si in eliminarea Gauss aplicata matricii A

Metoda directă 3: metoda factorizării LU

De exemplu:A=[2,1,-3;-1,3,2;3,1,-3]» [l,u,p]=lu(A) l = 1.0000 0 0 -0.3333 1.0000 0 0.6667 0.1000 1.0000u = 3.0000 1.0000 -3.0000 0 3.3333 1.0000 0 0 -1.1000p = 0 0 1 0 1 0 1 0 0

Metoda directă 3: metoda factorizării LU

Aici l este matricea inferior triunghiulară, u este matricea superior triunghiulară şi p este matricea unitară reprezentînd pivotarea.Matricile L şi U obţinute satisfac

PA=LUAcestea sunt mai degrabă descompuneri ale matricii PA decît ale matricii A. Aşadar ecuaţia originală lineară este scrisă prima dată în forma:

PAx=Pyşi apoi în forma

LUx=Py.Matricea originală poate fi regăsită apoi din L, U şi P prin formula P-1LU. În Matlab vom scrie:

p^(-1)*l*uans =  2 1 -3 -1 3 2 3 1 -3

Metoda directă 3: metoda factorizării LU

Al doilea format este:[l, u]=lu(A)

care producel =

  0.6667 0.1000 1.0000 -0.3333 1.0000 0 1.0000 0 0 u =  3.0000 1.0000 -3.0000 0 3.3333 1.0000 0 0 -1.1000unde l este egală cu P-1L, iar u este egală cu U asfel obţinem (P-1L)U=A.