C03-Rezolvarea sistemelor de ecuatii_1.pdf

Cursul 3

Rezolvarea sistemelor de

ecuaii

Rezolvarea numeric a sistemelor de

ecuaii

Rezolvarea sistemelor triunghiulare.

Eliminarea Gauss.

Eliminarea Gauss cu pivotare parial.

Eliminarea Gauss cu pivotare totala.

Factorizarea LU.

Factorizarea Cholesky.

Metoda Gauss-Jordan.

Metode aproximative. Convergenta metodelor aproximative.

Metoda iterativa a lui Jacobi, Gauss-Seidel.

Recapitulare:

Se numete matrice un tabel de elemente, cu m linii i n coloane, in care poziia fiecrui element este unic determinat printr-o combinaie de indici reprezentnd linia, respectiv coloana pe care se gsete elementul.

Recapitulare:

Adunarea matricelor se realizeaz element cu element.

Condiie: dimensiunile matricelor care se opereaz trebuie sa fie egale.

Recapitulare:

nmulirea matricelor cu un scalar se realizeaz nmulind fiecare element al matricei cu scalarul considerat.

l R, A mxn (R)

Recapitulare:

nmulirea matricelor se realieaza linii prin coloane. Nu este comutativ.

Condiie: numrul de coloane al primei matrice = numrul de linii al celei de a doua matrice.

Recapitulare:

Prin transpusa matricei A se nelege matricea At definit prin:

Recapitulare:

Matrice cu numr egal de linii i coloane, A mxn (R)

Recapitulare:

Matricea identitate, identic sau unitate de dimensiune n

este element neutru fata de nmulirea matricelor patratice de dimensiune n.

Recapitulare:

Matrice simetrice

Recapitulare:

Se consider o matrice ptratic real A de ordinul n. Numrul:

n care I(k1,k2,....kn) este numrul tuturor inversiunilor permutrii (k1,k2,....kn), se numete determinantul matricei A sau determinant de ordinul n.

O matrice real ptratic A se numete singular dac det A = 0; n cazul det A 0, se spune c matricea A este nesingular.

Recapitulare:

Recapitulare:

Matricea ptratic A de ordinul n este inversabil dac exist o matrice ptratic B de ordinul n astfel nct:

Matricea B din relaia de mai sus se numete matricea invers a matricei A i se noteaz cu A-1.

Determinantul unei matrice inversabile este nenul.

O matrice ptratic A este ortogonal dac A-1 =AT, adic dac AAT =I

Sisteme de ecuaii lineare:

Forma general (3.1):

Forma matriceal (3.2):

nnnn2n21n1

2n2n222121

1n1n212111

bxa...xaxa

...

bxa...xaxa

bxa...xaxa

nnn Rb,RA b,xA


Sistemul admite soluia unic

dac matricea este inversabil, caz n care soluia se exprim sub forma:

Metodelede rezolvare:

Metode exacte - care furnizeaz soluia exact a sistemului dac se neglijeaz erorile de rotunjire.

Metode aproximative sau iterative - care construiesc un ir, convergent ctre soluia exact a sistemului.

nRx

bAx -1


Metodele directe aduc sistemul prin transformri de echivalen, la un sistem particular (diagonal, triunghiular, etc), care se rezolv cu mijloace elementare.

Teorema: Daca si sunt matrice nesingulare, solutia sistemului 3.1 este si solutie pentru sistemul si reciproc

Metodele exacte se bazeaz pe factorizare gaussian sau pe factorizare ortogonal.

Complexitatea metodelor exacte este O(n3), motiv care le restrnge aplicabilitatea la rezolvarea sistemelor de ordin nu prea mare (n


In cazul metodelor aproximative, procesul iterative de generare a irului x(k) este oprit la un rang p, n momentul n care x(p) reprezint o aproximaie satisfctoare a soluiei.

Complexitatea metodelor iterative este O(n2) ntr-un pas, ele fiind recomandate pentru rezolvarea sistemelor mari (n>50), dac se asigur o convergen rapid.

Rezolvarea sistemelor triunghiulare:

Presupunem condiia de nesingularitate pentru un sistem triunghiular aii0.

Sistem superior triunghiular cu aij=0 pentru i>j.

nnnn

2n2n222

1n1n212111

bxa

...

bxa...xa

bxa...xaxa


Sistem inferior triunghiular cu aij=0 pentru i


Sistemul superior triunghiular se rezolv prin substituie napoi folosind relaiile

Sistemul inferior triunghiular se rezolv prin substituie nainte folosind relaiile

n

i ij jj i 1

iii

b A x

x , n:1A

i

i-1

i ij jj 1

iii

b A x

x , 1: nA

i

Eliminarea Gaussiana:

Sistemul (3.1) poate fi transformat intr-un sistem superior triunghiular echivalent folosind teorema:

Teorema: Daca

sunt nesingulare, atunci exista , nesingulara si inferior triunghiulara astfel incat matricea T.A=U este superior

triunghiulara.

p p pxpiji j,j p

A = a ,A R ,cu p=1:n

nxnT R


Matricea T se alege ca fiind un produs de matrice elementare:

in care In este matricea unitate, ep este coloana p a acesteia, iar tp este un vector coloana cu primele p componente nule, celelalte nu.

Tn-1 n-2 2 1 p n p pT T T ... T T de forma T =I -t e


Se nmulete la stnga matricea A cu matricea de transformare

avand ca efect obtinerea unei matrice transformate T.A superior triunghiulare.

Inmultirea se poate exprima prin transformarile elementare in care fiecare operatie anuleaza termenii subdiagonali din coloana p.

n-1 n-2 2 1T A T T ... T T A

1 2 1 1

p+1 p p

n n-1 n-1

A =A, A =T A

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

A =T A

A =T A


Trecerea de la sistemul A.x=b la sistemul echivalent T.A.x=T.b presupune aplicarea

transformarilor elementare si asupra termenilor liberi b.

p+1 p p 1

p+1 p p 1

A =T A pornind cu A =A

b =T b pornind cu b =b

11 1p 1n 11 1p 1n

2n 21 2p 2n

pp pp

p+1,p p+1,p

n,p n,p nn

a ... a ... a a ... a ... a1 0 0 ... 0

0 1 0 ... 0 0 ... ... ... a 0 a a ... a

0 0 1 ... 0 0 0 a ... ... 0 0 a ... ...

... ... -t ... 0 ... ... a ... 0 0 0 0 ..

0 ... -t ... 1 0 ... a ... a

nn

. ...

0 ... 0 ... a


p p p+1

p p p 1 p n p 1 p p p n

T A =A

T A T a ...a ...a T a ...T a ...T a

T Tp p n p p p p p p p p pp p

ip

p p ip pp ipip pp ip

T a = I -t e a a t e a a a t

a pentru i pT a a a t

a -a t pentru i pi


ip

pp

p

a

ip a

T Tp j n p p j j p p j j pj p

din conditia de anulare a elementelor subdiagonale rezulta t

t = pentru i=p+1:n

coloanele din dreapta lui p se vor modifica astfel

T a = I -t e a a t e a a a t

ippp

a'ij p j ij pj ip ij pj a

pj p j j

a T a a a t a a , j=p+1:n, i=p+1:n

a =0 pentru j


Transformarea Tp aplicata matricei Ap, partial

triangularizata are ca efect:

Lasa nemodificate primele p-1 coloane

Anuleaza elementele subdiagonale din coloana p

Modifica ultimele n-p elemente din coloanele j=p+1:n

Eliminarea Gaussiana cu pivotare

partiala:

Triangularizarea esueaz dac elementul diagonal actualizat app este nul sau dac submatricea Ap

a matricei initiale este nula.

Chiar si pentru valori mici, dar nenule, stabilitatea este afectata, precizia depinzand de ordinul de marime.

Stategia de pivotare partiala alege dintre liniile i=p:n acea linie q pentru care elementul conducator aqp este max. in valoare absoluta

Si permuta intre ele liniile q si p, aducand pe aqp ca

pivot

qp ipa max ap i n


partiala:

Permutarea a doua linii sau coloane se poate exprima prin inmultirea cu matricea Pqp, numita

matrice de permutare, obtinuta din matricea unitate prin permutarea liniilor sau coloanelor p si q in care:

qp

qq pp

qp pq

P i,j I i,j ; i,j p,q si

P =P =0

P =P =1


partiala:

Inmultirea are ca efect permutarea liniilor p si q din matricea A.

Inmultirea are ca efect permutarea coloanelor p si q din matricea A

pqA'=P A

pqA''=A P

p+1 p pq p

p+1 p pq p

p p

p+1 p+1

A =T P A

b =T P b

A x=b

A x=b


partiala:

Deoarece intotdeauna qp se poate obtine o

matrice de transformare inferior triunghiulara, care aplicata matricei A conduce la o matrice

superior triunghiulara.

Eliminarea Gaussiana cu pivotare partiala este echivalenta cu eliminarea Gaussiana simpla, aplicata matricei A, dupa o permutare

convenabila si adecvata a ecuatiilor.


totala:

Se obtine o stabilitate mai buna daca se alege ca pivot primul element maxim in valoare absoluta Alm din submatricea delimitata de ultimele n-p+1 linii si coloane ale matricei Ap.

Pentru ca aceasta sa ocupe pozitia p,p trebuie interschimbate liniile p si l precum si coloanele p si m.


totala:

Transformarea total stabilizata se exprima prin:

In care

inmultirea la stanga cu Ppl permuta in Ap liniile p si lp;

inmultirea la dreapta cu Ppm permuta in Ap liniile p si mp;

p+1 p pl p pmA =T P A P

p pl p pm pm p p pl pT P A P P x T P b

Exemple:

Folosind eliminarea Gauss sa se rezolve sistemele:

1 2 3

1 2 3

1 2 3

22

9

8 2 3 1

2 5 1

x x x

x x x

x x x

1 2 3

1 2 3

1 2 3

8 2 15

10 4 21

50 25 8 124

x x x

x x x

x x x

Exemplul 1:

Nu este necesara permutarea:

2

1 129

8 2 3 , 1

1 2 5 1

A b

21 1 2

9

8 2 3 1

1 2 5 1

Augmentarea matricelor:

Exemplul 1:

app=1, tip=8/1 pentru linia 2

21 1 2

9

8 2 3 1

1 2 5 1

21 1 2

9

28 1 8 2 8 3 1 8 1 2 8

9

21 1 1 2 1 5 1 1 1 2 1

9

21 1 2

9

20 11 17

9

160 6 1

9

Exemplul 1:

app=2/9

21 1 2

9

20 11 17

9

160 6 1

9

21 1 2

9

2 9 9 90 11 17

9 2 2 2

16 20 8 6 11 8 1 17 8

9 9

21 1 2

9

9 90 1 11 17

2 2

0 0 82 135

Exemplul 1:

Solutia:

3

1351,646

82x

1

135 2 8192 1

3182 9 164 0,7561 41

x

.

2

9 9 13517 11

8192 2 82 4,9941 164

x

Exemplul 2:

Matricele:

Augmentarea matricelor:

8 2 1 15

10 4 1 , 21

50 25 8 124

A b

8 2 1 15

10 4 1 21

50 25 8 124

Exemplul 2:

Permutare intre liniile 1 si 3:

50 25 8 124

10 4 1 21

8 2 1 15

Exemplul 2:

app=50, se imparte prima linie la app si se calculeaza restul elementelor:

50 25 8 124

50 50 50 50 1 0,5 0,16 2,4850 25 8 124

10 4 1 21 0 1 0,6 3,85 5 5 5

0 2 0,28 4,848 8 8 8

8 50 2 25 1 8 15 12450 50 50 50

Exemplul 2:

app=-1, se imparte a doua linie la app si se calculeaza restul elementelor:

1 0,5 0,16 2,481 0,5 0,16 2,48 1 0,5 0,16 2,481 0,6 3,8

0 1 0,6 3,8 0 0 1 0,6 3,81 1 1

0 2 0,28 4,84 0 0 0,92 2,760 2 1 2 0,28 0,6 2 4,84 3,8 2

Exemplul 2:

Solutia:

3

2,763

0,92x

1

2,48 0,16 3 0,5 21

1x

.

2

3,8 0,6 32

1x

C03-Rezolvarea sistemelor de ecuatii_1.pdf

Documents

Transcript of C03-Rezolvarea sistemelor de ecuatii_1.pdf