SISTEME DE ECUATII ALGEBRICE

Fie sistemul de n- ecuatii algebrice:

0),.....,,(

.

.

0),.....,,(

0),.....,,(

21

212

211

nn

n

n

xxxf

xxxf

xxxf

(4.1)

Sisteme algebrice liniare

Daca ecuatille sunt liniare, spunem ca avem un sistem algebric liniar:

nnnnnn

nn

nn

bxaxaxa

bxaxaxa

bxaxaxa

.....

.

.

.....

.....

2211

22222121

11212111

(4.2)

unde ija şi ib nji ,..,2,1, , sunt coeficieţi constanţi, iar nxxx ...,,, 21 sunt

necunoscutele.

Sistemul (4.2) se poate scrie în forma matriceală:

nnnnnn

n

n

b

b

b

x

x

x

aaa

aaa

aaa

..

..

.....

..

..

2

1

2

1

21

22221

11211

(4.3)

Introducem notaţiile:

nnnn

n

n

aaa

aaa

aaa

A

..

.....

..

..

21

22221

11211

;

nb

b

b

b.

2

1

;

nx

x

x

x.

2

1

(4.4)

Cu aceste notaţii rescriem sistemul (4.3) :

bxA (4.5)

Inversa unei matrice

Dacă matricea [A] este nesingulară, adică valoarea determinantului este diferită

de zero

0]det[ A ; det

nnnn

n

n

aaa

aaa

aaa

A

..

.....

..

..

21

22221

12111

(4.6)

matricea este inversabilă.

Inversa matricei se calculează astfel:

]det[

][][

*1

A

AA

(4.7)

unde matricea ][][ *ijAA este matricea adjunctă a matricei ][A . Elementele

matricei adjuncte se obţin înlocuind fiecare element al matricei transpuse

(schimbăm linile în coloane), ][][ jiT aA , cu complementul sau algebric:

ijji

ij MA )1(

(4.8)

unde ijM sunt minorii elementului ija ai matricei transpuse, adică determinaţii

obţinuţi din determinantul matricei transpuse prin suprimarea liniei i şi coloanei

j.

Exemplu 4.1 Calculul matricei inverse.

Fie matricea

111

012

111

][A

Pasul 1: Calculăm determinantul:

2)3(2111

12)1)(1(

11

02)1(1

11

01)1(1][det 312111

A

Pasul 2: obţinem matricea transpusă

101

111

121

][ TA

Pasul 3: calculăm complemenţii algebrici

...011

11)1(;1

10

11)1( 21

1211

11

AA

Pasul 4: obţinem matricea adjunctă:

123

222

101*

A

Pasul 5: obţínem matricea inversă

2

11

2

3111

2

10

2

1

det

*1

A

AA

(4.9)

Aceste calcule se pot obţine cu ajutorul programului MATLAB.

Obţinem inversa:

inv(A)=

0.5000 0.0000 0.5000

-1.0000 1.0000 -1.0000

-1.5000 1.0000 -0.5000

Rezultatul produsului dintre o matrice şi inversa sa este matricea unitate de

acelaşi ordin

(4.10) IAA

1 >>I=A*inv(A) I = 1 0 0

IAA 1

0 1 0

0 0 1

>> A=[1 1 -1;2 1 0;1 -1 1]; % introducem matricea

>> d=det(A) % calculăm determinantul

>> inv(A) % comanda de calcul a inversei

Metode de rezolvarea a sistemelor liniare

Soluţia cu matricea inversă

Fie sistemul (4.3) ȋn forma matriceală (4.5)

bxA

O cale formală, dar nu foarte efcicientă, pentru a determina soluţia sistemului

este sa înmulţim ambele părţi ale ecuaţiei (4.5) cu inversa 1][ A . Obţinem:

bAxAA11 ][][

şi folosind (4.10) rezultă soluţia:

bAx1

(4.11)

Soluţia cu regula lui Cramer

A

A

A

Ax

kk

k

]det[

]det[, nk ,...,2,1 (4.12)

unde ][k

A este matricea obţinută din matricea [A] prin ȋnlocuirea elementelor

coloanei k cu elementele coloanei termenilor liberi.

Sisteme triunghiulare. Soluţia unui sistem triunghiular

spunem că o matrice nnRL este inferior triunghiulară dacă toate

elementele matricei de deasupra diagonalei sunt egale cu zero, adică

0ij

l pentru j > i.

spunem că o matrice nnRU este superior triunghiulară dacă toate

elementele matricei de sub diagonală sunt egale cu zero, adică

0ij

l pentru i > j.

Un sistem liniar cu matricea A superior triunghiulară se poate rezolva prin

metoda substituţiei "ȋnapoi" - substituţie regresivă sau inversă.

Exemplu. Fie sistemul

33

12

22

3

32

321

x

xx

xxx

(4.13)

bxU

9

1

2

300

210

121

3

2

1

x

x

x

Rezolvarea se face prin substituţie regresivă (inversă), pornind de la ecuaţia a

treia, din care rezultă 3

x , apoi din ecuaţia a doua rezultă 2

x şi ȋn final, din prima

ecaţie se determină 1

x :

11352222

;5)1/()321()1/()21(

;33/9

321

32

3

xxx

xx

x

Metode numerice de rezolvarea a sistemelor algebrice liniare

Avem doua tipuri de metode numerice pentru rezolvarea a sistemelor liniare :

1. Metode dirtecte - soluţia se determină ȋntr-un număr finit de paşi:

metoda Gauss

metode Cholevsky

metoda Householder

Prin metodele directe sistemul este transformat ȋntr-un sistem triunghiular

echivalent şi care se rezolvă prin metoda descrisă mai sus.

Metodele directe dau rezultate bune daca nu avem erori de rotunjire. Numărul

operaţiilor aritmetice efectuate este de ordinul 3n , astfel că pentru un număr

mare de ecuaţii )100( n erorile de rotunjire vor altera soluţia.

2. Metode indirecte:

metoda Jacobi

metoda Gauss-Seidel

metodele de relaxare

Exemplu numeric - Metoda Gauss

Metoda Gauss numită şi metodea de eliminare Gauss se bazează pe aducerea

sistemului prin transformări elementare la un sistem triunghiular superior

echivalent (având matricea de formă triunghiulară superior).

Transformările elementare prin care se obţine acest sistem echivalent sunt:

ȋnlocuirea unei ecuaţii cu suma dintre această ecuaţii şi altă ecuaţie

ȋnmulţită cu un scalar;

schimbarea locului a două ecuaţii;

ȋnmulţirea unei ecuaţii cu un număr.

Aceste transformări se vor aplica matricei extinse, adică matricei obţinută prin

adăugarea la matricea sistemului a coloanei termenilor liberi ][ bA .

Fie sistemul liniar:

1

2

0

221

012

121

3

2

1

x

x

x

(4.14)

Construim matricea extinsă:

(4.15)

Pasul 1 Eliminăm necunoscuta 1

x din liniile doi şi trei:

a. linia (1) rămâne neschimbată -elementul 111a este numit pivot;

b. pentru a face zero pe poziţia 21

a vom ȋnmulţi linia unu (1) cu -2 şi o vom

aduna cu linia doi (2) : (2) ← (2) - 2*(1)

c. pentru a face zero pe poziţia 31

a vom ȋnmulţi linia unu (1) cu 1 şi o vom

aduna cu linia trei (3) : (3) ← (3) + 1*(1)

Obţinem:

Pasul 2. Facem zero şi elementul 32

a :

(1)

(2)

(3) ← (3) + 4/3*(2)

1|140

2|230

0|121

1|221

2|012

0|121

311|31100

2|230

0|121

3

11

3

11

223

02

3

32

321

x

xx

xxx

(4.16)

Astfel, am obţinut un sistem triunghiular superior a cărui soluţie se determină

prin metoda substituţiei regresive (inverse):

1,0,1123 xxx .

Observaţia 1.

Folosind

2

)12)(1(

1

2

nnnk

n

k

putem aproxima, pentru valori mari ale lui n (sistem cu multe ecuaţii), numărul

operaţiilor aritmetice efectuate ȋn metoda Gauss cu 3/2 3n .

Observaţia 2.

Pivotarea - rearanjarea liniilor pentru a avea la fiecare pas al eliminării un pivot

maxim. Astfel se ȋmbunătăţeşte stabilitatea numerică a metodei Gauss, se

minimizează erorile de rotunjire şi se evită ȋmpărţirile cu zero.

Pivotul se va alege astfel: ȋn pasul i, găsim linia j > i astfel ȋncât kiji aa pentru

toţi k > i şi apoi schimbăm liniile i şi j; pivotul va fi ales coeficientul jia .

Metoda Gauss

Vom exemplifica metoda, pentru simplitate, pe cazul unui sistem cu trei ecuaţii

şi trei necunoscute, matricea [A] nesingulară de tip 3x3

3333232131

2323222121

1313212111

bxaxaxa

bxaxaxa

bxaxaxa

(4.17)

Folosim observaţiile de mai sus pentru alegerea pivotului.

Matricea extinsă este:

3333231

2232221

1131211

|

`|

|

baaa

baaa

baaa

(4.18)

Pasul 1: Presupunem că pivotul este 11a ; vom elimina pe 1x din ecuaţiile doi şi

trei:

ȋmpărţim prima linie la elementul pivot 11a ;

scădem prima linie ȋnmulţită cu primul element din celelalte linii:

)1(3

)1(33

)1(32

)1(2

)1(23

)1(22

)1(1

)1(13

)1(12

|0

|0

|1

baa

baa

baa

(4.19)

unde

)1(11

)1(

)1(11

)1(11

1)1(1

11

1)1(1

3,2;3,2,1,

3,2,1,

babb

ijaaaa

a

bb

ja

aa

iii

jiijij

j

j

(4.20)

Pasul 2: eliminăm pe 2x din ecuaţia a treia:

)2(3

)2(33

)2(2

)2(23

)1(1

)1(13

)1(12

|00

|10

|1

ba

ba

baa

(4.21)

unde:

)2(2

)1(2

)1()2(

)2(2

)1(2

)1()2(

)1(22

)1(2)2(

2

)1(22

)1(2)2(

2

3;3,2,

3,2,

babb

ijaaaa

a

bb

ja

aa

iii

jiijij

j

j

(4.22)

Pasul 3: ȋmpărţim linia trei din (4.21) cu )2(

33a şi obţimem:

)2(

33

)2(

3

)2(

2

)2(

23

)1(

1

)1(

13

)1(

12

/|100

|10

|1

ab

ba

baa

. (4.23)

Sistemul date de relaţia (4.23) este sistem triunghiular echivalent cu sistemul

iniţial (4.17). Soluţia lui obţinută prin metoda substituţiei invers este:

).( 3

)1(

132

)1(

12

)1(

11

3

)2(

23

)2(

22

)3(

33

xaxabx

xabx

bx

(4.24)

Aplicaţie numerică în Matlab

Fie sistemul algebric liniar:

27243

1833

1723

102422

4321

4321

4321

4321

xxxx

xxxx

xxxx

xxxx

Solutia x = {2.8603 5.8897 0 3.5294}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% %

% ex_Gauss_1.m %

% %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% matricea extinsa a=[2 2 4 -2 10;1 3 2 -1 17;3 1 3 1 18;1 3 4 2 27] 'Pasul1:determinam linia pivot (linia 3) si eliminarea necunoscutei x1'

% pivotarea -aleg pivot maxim ==> interschimbam linile 1 cu linia 3 % Se înmulþeºte pe rând linia pivot cu elementele (-1/3); (-2/3); (-

1/3) si se adunã la linia 2, apoi 3 si respectiv 4. pivt=a(1,:); a(1,:) = a(3,:); a(3,:)=pivt; a(2,:) = a(2,:) - a(1,:)*a(2,1) / a(1,1); a(3,:) = a(3,:) - a(1,:)*a(3,1) / a(1,1); a(4,:) = a(4,:) - a(1,:)*a(4,1) / a(1,1); % Matricea P s-a transfomat în matricea urmãtoare: a 'Pasul 2: eliminam necunoscuta x2' % Nu avem in acest caz nevoie de pivotare si vom înmulti linia pivot,

linia a doua rând pe rând cu elementele (-4/3 . 3/8) = (-1/2); (-1) si o vom aduna la linia 3, respectiv 4. a(3,:) = a(3,: )-a(2,:)*a(3,2)/a(2,2); a(4,:) = a(4,:)-a(2,:)*a(4,2)/a(2,2); %Matricea a s-a transfomat în matricea urmãtoare: a 'Pasul 3: eliminam necunoscuta x3' % Nu avem nevoie de pivotare. Vom înmulþi linia pivot, linia 3, cu % elementul (-3) 2 . 2=(-3/4) si apoi o vom aduna la linia 4. a(4,:) = a(4,:) - a(3,:)*a(4,3) / a(3,3); a % Determinþia prin metoda substitutiei inverse începând cu ultima

ecuatie: x(4)=a(4,5)/a(4,4); x(3)=(a(4,5)-a(4,4)*x(4))/a(3,3); x(2)=(a(2,5)-a(2,3)*x(3)-a(2,4)*x(4))/a(2,2); x(1)=(a(1,5)-a(1,2)*x(2)-a(1,3)*x(3)-a(1,4)*x(4))/a(1,1); x=[x(1); x(2); x(3); x(4)]