Factorizarea LU

a)simpla b)cu pivotare partiala c)cu pivotare completa

Factorizarea LU

-triangularizarea matriciala prin eliminare gaussiana

a)L . .LA=U

b)LP . LPA=U

c) LP . LPAR . .R=U

Rezultat de stabilitate numerica a triangularizarii

(similar cu factorizarea LU)prin eliminare gaussiana cu

pivotare partiala.

			P-alg. de triang.

A+E=AC

A

UL= LP . LP

UL =LP . LP

P-sau de factorizare executabil pe un calculator numeric

A-identica cu calculul unui numar cu un numar infinit de zecimale

Rezultatul care se realizeaza demonstreaza ca suma matricii de perturbatie E este mai mica decat factorul fi.

K=1 U=1

|| E ||

| A ||=||LPA||

fi(n)=an+bn+cn+d

Tehnica de programare inapoi a erorii de trunchiere(erori de reprezentari in virgula mobila)furnizeaza o imagine a matricii de perturbatie care depinde de dimensiune si natura datelor de intrare,dar si de norma unor rezultate partiale()

-la triangularizarea matricilor de reflexive:

||E|| A

(Q+E)(Q+E)=R

|| E ||

|| E ||

fi(n)=an+bn+c

Daca matricea de intrare este prost conditionata (X(A)=||A||*||A||) sau este mare,se spune ca matricea A este conditionata ( / ) matricea de perturbatie E sa aiba o norma mai mare decat cea de matrice EA=A+E nu este usoara perturbatie a lui Aalg. de triangularizare prin eliminare gaussiana cu pivotare partiala poate deveni numeric instabil vis-à-vis de alg. de triangularizare prin transformari ortogonale de reflexie (QR) care pentru aceeasi data de intrare este numeric stabil.In general,alg. de eliminare gaussiana prezinta o stabilitate numerica decat alg. orthogonal.Deci,implicatiile si raspunsul sistemului si procesare a semnalelor sunt bazate in algoritm de factorizare QR.

Marginea matricii de perturbatie are o dependenta cubica fata de dimensiune si o dependenta intrinseca de algoritm.

Triangularizarea prin eliminare gaussiana cu pivotare in-situ se bazeaza pe faptul ca daca aplicam L lui A unde L este matricea de triangularizare la pasul curent.

a

a

-

= =

Rezulta matricea in care si coloana k are sub coloana principala zero.

<linL/colA> 0 . . 0- . .0 . . . . . .0 =a

Primele k-1 elemente sunt nemodificate.

Efectul aplicarii transformarii gaussiene asupra matricii A este urmatorul:

a)primele k-1 raman neschimbate;

b)coloana k se modifica prin introducerea 0 de la k+1;

a/a

c)sunt afectate numai coloanele din spatele coloanei k si acelea de la linia k+1 n cu relatia:

k+1

a=a- ,deci matricea de la pasul k

a a

n

A= AA=PAA

liniaA

liniaA

       

a a

a a

a a

Program Matlab pentru triangularizarea prin eliminare gaussiana in-situ

Factorizarea LU bazata pe eliminare gaussiana

-se face numai cu matrice patrata

A

L

U

L-inf,U-sup a.i. A=LU=

a)     l=1,i= factorizarea Doolitle

A=

b)factorizarea cont U=1, i=

-simetrica A=A -factoriz. Cholesky x*A*x>0 ||x||

A=

c)A-pozitiv definite

A=U*U= U=sup

Factorizarea LU se obtine din rezolvarea unor sisteme de ecuatii liniare si nu din triangularizarea prin eliminare gaussiana cu pivotare.

De regula,inversarea natriceala este o implicatie a factorizarii matriceale.In Matlab inv(a)-alg. de inversare se face pe baza factorize.QR.

a)factorizarea Doolitle

-se obtine si din eliminaregaussiana cu pivotare partiala:

LP . LPA=U

A=PA

A=LA

L L) . . L

-se bazeaza pe triangularizarea gaussiana fara pivotare:

L= L=L . .L Linf si L inf l=1

k=

==L

Inversa in-situ a unei matrici superior

U R= i= V sup a.i. UV=VU=I

U==

U= UcolV==colI=

, i= j=

Uv+ i= , j=

U)/ U

Program Matlab pentru inverse unei matrici sup in-situ

Program Matlab pentru factorizarea Doolitle

La factorizarea Doolitle

PA=LU

(P . (P))) (L) . (L))U

Factorizarea CROUT

a)A=LU=corespondentul triangularizarii prin eliminare gaussiana fara ppivotare si care se obtine rezolvand sistemul de ecuatii liniare:-1)cu LU separate

-2)in-situ(in matricea A)

 

a

=

a=<linL/colU>=

<linL/colU>=a,unde k=si j=

,unde k= si j=

Program Matlab pentru factorizarea U(Crout cu L si U separate)

2)Factorizarea Crout in-situ: A=

b)Factorizarea Crout cu pivotare partiala

PA=LU

P . .PA=

Pivotarea se face dupa ce se calculeaza coloana k din l.

Rezultate de stabilitate numerica =este sa se faca permutarea de linii din A inainte de a se calcula matricea L.

Program Matlab pentru factorizarea Crout pentru L si U separate si pivotare partiala

3.Factorizarea Cholesky A pozitiv definita

A= A=A

,unde k=si j=

U=

Program Matlab pentru factorizarea Cholesky