sisteme de ecuatii algebrice liniare - metode directe (ii)an.lmn.pub.ro/slides/an_s6.pdfformularea...

43
Formularea problemei Gauss - sisteme multiple Metoda factoriz ˘ arii LU Varianta Doolittle Varianta Cholesky Matrice rare Sisteme de ecua¸ tii algebrice liniare - metode directe (II) Conf.dr.ing. Gabriela Ciuprina Universitatea "Politehnica" Bucure¸ sti, Facultatea de Inginerie Electric ˘ a, Departamentul de Electrotehnic ˘ a Suport didactic pentru disciplina Algoritmi Numerici, 2012

Upload: ngothu

Post on 10-Apr-2018

258 views

Category:

Documents


3 download

TRANSCRIPT

Page 1: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Sisteme de ecuatii algebrice liniare - metodedirecte (II)

Conf.dr.ing. Gabriela Ciuprina

Universitatea "Politehnica" Bucuresti, Facultatea de Inginerie Electrica,Departamentul de Electrotehnica

Suport didactic pentru disciplina Algoritmi Numerici, 2012

Page 2: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Cuprins

Formularea problemei

Gauss - sisteme multiple

Metoda factorizarii LU

Varianta Doolittle

Varianta Cholesky

Matrice rare

Page 3: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Formularea problemei

Sistem de n ecuatii algebrice liniare cu n necunoscute:

a11x1 + a12x2 + · · ·+ a1nxn = b1,a21x1 + a22x2 + · · ·+ a2nxn = b2,· · ·an1x1 + an2x2 + · · ·+ annxn = bn.

(1)

Page 4: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Formularea problemeiSe da matricea coeficientilor

A =

a11 a12 · · · a1n

a21 a22 · · · a2n

· · ·an1 an2 · · · ann

∈ IR

n×n (2)

si vectorul termenilor liberi

b =[

b1 b2 · · · bn]T ∈ IR

n, (3)

se cere sa se rezolve sistemul

Ax = b, (4)

unde x este solutia

x =[

x1 x2 · · · xn]T ∈ IR

n. (5)

Page 5: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Buna formulare matematica

Problema este bine formulata din punct de vedere matematic(solutia exista si este unica)⇔matricea A este nesingulara (are determinantul nenul).Se scrie formal:

”x = A−1b”

trebuie citita ca:"x este solutia sistemului algebric liniar Ax = b"si NU "se calculeaza inversa matricei A care se înmulteste cuvectorul b".

Page 6: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Conditionarea problemei

κ(A) = ‖A‖‖A−1‖ (6)

numar de conditionare la inversare al matricei A.

εx ≤ κ(A)εb, (7)

• κ(A) ≥ 1:Cazul cel mai favorabil: nA = 1 si εx = εb. (matriceortogonala)

• Numarul de conditionare este o proprietate a matricei si nuare legatura nici cu metoda de rezolvare propriu-zisa, nicicu erorile de rotunjire care apar în mediul de calcul.În practica:Daca κ(A) > 1/eps problema se considera slabconditionata.

Page 7: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Clasificarea metodelor

1. Metode directe - gasesc solutia teoretica a problemeiîntr-un numar finit de pasi. (Gauss, factorizare LU)

2. Metode iterative - genereaza un sir de aproximatii alesolutiei care se doreste a fi convergent catre solutiaexacta.

• stationare: Jacobi, Gauss-Seidel, SOR, SSOR• nestationare (semiiterative): gradienti conjugati (GC),

reziduu minim (MINRES), reziduu minim generalizat(GMRES), gradienti biconjugati (BiGC), etc.

Page 8: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Formularea problemei

Fie m sisteme de ecuatii algebrice liniare

Ax (1) = b(1), Ax (2) = b(2), · · · , Ax (m) = b(m), (8)

Se dau: A ∈ IRn×n, b(k) ∈ IRn×1, k = 1,mSe cer: x(k) ∈ IRn×1,Notam

B = [b(1) b(2) · · · b(m)] ∈ IRn×m (9)

X = [x(1) x(2) · · · x(m)] ∈ IRn×m (10)

Se cere sa se rezolve sistemul

AX = B. (11)

Page 9: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Varianta I

Varianta I - aplicarea succesiv a a algoritmului GaussEfort de calcul: m(2n3/3 + n2) ≈ 2mn3/3.Etapa de eliminare este repetata inutil, de m ori.Cea mai proasta idee.

Page 10: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Varianta IIVarianta II - rezolvarea simulatan a prin adaptareaalgoritmului Gauss

procedur a Gauss_multiplu(n, m, a, B, X ); rezolva sismultan sistemele algebrice liniare aX = B prin metoda Gaussîntreg n ; dimensiunea sistemuluiîntreg m ; numarul de sistemetablou real a[n][n] ; matricea coeficientilor - indici de la 1tablou real B[n][m] ; matricea termenilor liberitablou real X [n][m] ; matricea solutieîntreg i, j, kreal p, s; etapa de eliminarepentru k = 1, n − 1 ; parcurge sub-etape ale eliminarii

; aici se poate introduce pivotareapentru i = k + 1, n ; parcurge liniile

p = −aik/akk ; element de multiplicarepentru j = k + 1, n ; parcurge coloanele

aij = aij + pakj•pentru j = 1, m ; parcurge coloanele termenilor liberi

bi j = bi j + pbkj•

••

Page 11: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Varianta II; etapa de retrosubstitutiepentru k = 1, m

xnk = bnk/annpentru i = n − 1, 1,−1

s = 0pentru j = i + 1, n

s = s + aij xjk•xik = (bik − s)/aii

••retur

Efort de calcul

Te =

n−1∑

k=1

[2(n − k) + 2m + 1](n − k) ≈n−1∑

k=1

[2(n − k)2 + 2m(n − k)] =

= 2(n − 1)n(2n − 1)

6+ 2m

n(n − 1)2

2n3

3+ mn2. (12)

Ts = mn−1∑

i=1

[2(n − i) + 2] ≈ mn−1∑

i=1

[2(n − i)] = 2mn(n − 1)

2≈ mn2. (13)

T = O(2n3/3 + 2mn2), mai mic decât în cazul variantei I.

Page 12: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Varianta IIIVarianta III - rezolvarea succesiv a a sistemelor folosindcalculul inversei

• Se calculeza A−1

• Se calculeaza x(k) = A−1b(k) imediat ce este cunoscuttermenul liber.

func¸tie invA(n, a); calculeaza inversa matricei aîntreg n ; dimensiunea matriceitablou real a[n][n] ; matricea, indici de la 1; alte declaratii....pentru i = 1, n

pentru j = 1, nBij = 0

•Bii = 1

•Gauss_multiplu(n, n, a, B, X )întoarce X ; X este inversa matricei

Complexitatea calcului inversei: 2n3/3 + 2mn2 = 8n3/3COSTISITOR!

Page 13: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Varianta III

func¸tie produs_Mv (n, M, v ); calculeaza produsul dintre o matrice patrata M si un vector coloana vîntreg n ; dimensiunea problemeitablou real M[n][n] ; matricea, indici de la 1tablou real v [n] ; vectorultablou real p[n] ; rezultatul p = Mv; alte declaratii....pentru i = 1, n

pi = 0pentru j = 1, n

pi = pi + Mij vj•

•întoarce p

Complexitatea inmultirii dintre o matrice si un vector: 2n2

Efortul total de calcul : O(8n3/3 + 2mn2).Exista o varianta mai eficienta bazata pe factorizarea matriceicoeficientilor.

Page 14: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Ideea metodei

Ax = b, (14)

A = LU, factorizare (15)

A =

∗ ∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗ ∗

L =

∗ 0 0 0 0 0∗ ∗ 0 0 0 0∗ ∗ ∗ 0 0 0∗ ∗ ∗ ∗ 0 0∗ ∗ ∗ ∗ ∗ 0∗ ∗ ∗ ∗ ∗ ∗

U =

∗ ∗ ∗ ∗ ∗ ∗0 ∗ ∗ ∗ ∗ ∗0 0 ∗ ∗ ∗ ∗0 0 0 ∗ ∗ ∗0 0 0 0 ∗ ∗0 0 0 0 0 ∗

LUx = b. (16)

Notamy = Ux, (17)

(16) ⇔Ly = b, substitutie progresivaUx = y. substitutie progresiva

(18)

Page 15: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Un exemplu simplu - pornind de la Gauss

x1 + 2x2 − x3 = −1,−2x1 + 3x2 + x3 = 0,

4x1 − x2 − 3x3 = −2.(19)

x1 + 2x2 − x3 = −1,7x2 − x3 = −2,

−9x2 + x3 = 2.(20)

x1 + 2x2 − x3 = −1,7x2 − x3 = −2,

− 2/7x3 = −4/7.(21)

x3 = (−4/7)/(−2/7) = 2,x2 = (−2 + x3)/7 = 0,x1 = −1 − 2x2 + x3 = 1.

(22)

Page 16: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Un exemplu simplu - pornind de la Gauss

Factorizare

U =

1 2 −10 7 −10 0 −2/7

. (23)

L =

1 0 0−2/1 1 0

4/1 −9/7 1

=

1 0 0−2 1 0

4 −9/7 1

. (24)

Verificare: LU = A

A =

1 2 −1−2 3 1

4 −1 −3

. (25)

Page 17: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Un exemplu simplu - pornind de la Gauss

Substitutie progresivaLy = b

1 0 0−2 1 0

4 −9/7 1

y1

y2

y3

=

−10

−2

, (26)

y1 = −1−2y1 + y2 = 0

4y1 − 9/7y2 + y3 = −2(27)

y1 = −1y2 = 2y1 = −2y3 = −2 − 4y1 + 9/7y2 = −4/7.

(28)

Page 18: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Un exemplu simplu - pornind de la Gauss

Substitutie regresivaUx = y

1 2 −10 7 −10 0 −2/7

x1

x2

x3

=

−1−2−4/7

, (29)

x1 + 2x2 − x3 = −17x2 − x3 = −2−2/7x3 = −4/7.

(30)

x3 = (−4/7)/(−2/7) = 2,x2 = (−2 + x3)/7 = 0,x1 = −1 − 2x2 + x3 = 1.

(31)

Page 19: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Variante de factorizare

Factorizare nu este unica. Variante standard:

• Doolittle: lii = 1 - se aplica la orice matrice nesingulara

• Crout: uii = 1 - se aplica la orice matrice nesingulara

• Cholesky: L = UT - se aplica doar matricelor simetrice sipozitiv definite

[3 26 1

]

=

[l11 0l21 l22

] [u11 u12

0 u22

]

. (32)

l11u11 = 3l12u12 = 2l21u11 = 6

l21u12 + l22u22 = 1

(33)

Sistemul devine determinat doar daca fixam oricare doua valori.

Page 20: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Variante de factorizare

Exemplu:

[3 26 1

]

=

[1 02 1

] [3 20 −3

]

=

[3 06 −3

] [1 2/30 1

]

.

(34)[

9 22 1

]

=

[3 0

2/3√

5/3

] [3 2/30

√5/3

]

. (35)

Page 21: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Algoritmul variantei Doolittle

A0 = A, (36)

A1 = E1A0,A2 = E2A1 = E2E1A0,· · ·An−1 = En−1An−2 = En−1En−2 · · ·E2E1A0.

(37)

U = An−1. (38)

E = En−1En−2 · · ·E2E1, (39)

U = EA. (40)

Dar E este nesingulara si:

L = E−1. (41)

Page 22: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Algoritmul variantei Doolittle

a11 a12 a13

0 a′

22 a′

230 a′

32 a′

33

= E1

a11 a12 a13

a21 a22 a23

a31 a32 a33

. (42)

E1 =

1 0 0−a21/a11 1 0−a31/a11 0 1

. (43)

E−11 =

1 0 0a21/a11 1 0a31/a11 0 1

, E−12 =

1 0 00 1 00 a′

32/a′

22 1

. (44)

E−1 = E−11 E−1

2 · · ·E−1n−2E−1

n−1. (45)

E−1 =

1 0 0a21/a11 1 0a31/a11 a′

32/a′

22 1

= L. (46)

Page 23: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Algoritmul variantei Doolittle

; etapa de eliminare din metoda Gauss cu memorarea opuselor elementelor; de multiplicare în triunghiul inferior al matriceipentru k = 1, n − 1 ; parcurge sub-etape ale eliminarii

pentru i = k + 1, n ; parcurge liniilep = −aik/akk ; element de multiplicarepentru j = k + 1, n ; parcurge coloanele

aij = aij + pakj•aik = −p

••

procedur a factorizare_LU(n, a); factorizeaza "in loc" matricea a; varianta Doolittle; declaratii· · ·pentru k = 1, n − 1 ; parcurge sub-etape ale eliminarii

pentru i = k + 1, n ; parcurge liniileaik = aik/akk ; element de multiplicarepentru j = k + 1, n ; parcurge coloanele

aij = aij − aik akj•

••retur

Factorizare "în loc" : "A = L + U − I"

Page 24: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Calculul solutiei dupa factorizare

LUx = b. (47)

Notamy = Ux, (48)

(47) ⇔

Ly = b, (49)

Ux = y. (50)

"y = L−1b" se rezolva prin substitutie progresiva:

l11y1 = b1,l21y1 + l22y2 = b2,· · ·ln1y1 + ln2y2 + · · · lnnyn = bn,

y1 = b1/l11,y2 = (b2 − l21y1)/l22,· · ·yn = (bn −∑n−1

k=1 lnkyk )/lnn.(51)

Page 25: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Calculul solutiei dupa factorizare

y1 = b1/l11, (52)

yi =

bi −i−1∑

j=1

lijyj

/lii , i = 2, . . . , n. (53)

"x = U−1y" se rezolva prin substitutie regresiva:

xn = yn/unn, (54)

xi =

yi −n∑

j=i+1

uijxj

/uii , i = n − 1, . . . , 1. (55)

Page 26: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Calculul solutiei dupa factorizare

procedur a rezolva_LU(n, a, b, x); rezolva sistemul de ecuatii ax = b prin factorizare LU; matricea este presupusa a fi deja factorizata în loc; varianta Doolittle; declaratii· · ·; substitutie progresivay1 = b1 ; formula (52), unde l11 = 1pentru i = 2, n

s = 0pentru j = 1, i − 1

s = s + aij yj; formula (53), unde L este memorat în a•yi = bi − s ; deoarce lii = 1

•; substitutie regresivaxn = yn/ann ; formula (54), unde U este memorat în apentru i = n − 1, 1,−1

s = 0pentru j = i + 1, n

s = s + aij xj•xi = (yi − s)/aii

•retur

Page 27: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Evaluarea algoritmului

Complexitate:

• Factorizarea propriu-zisa a: Tf = O(2n3/3)

• Rezolvarile: Ts = O(2n2).

• Necesarul de memorie: M = O(n2)

Erori:

• Nu exista erori de trunchiere;

• Erorile de rotunjire pot fi micsorate daca se aplica strategiide pivotare.

Page 28: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Pivotare

Matrice de permutare:

• matrice care are exact un element egal cu 1 pe fiecare liniesi pe fiecare coloana, si 0 în rest;

• inversa unei matrice de permutare este o matrice depermutare;

• produsul a doua matrice de permutare este de asemeneao matrice de permutare;

Pivotarea pe linie poate fi descrisa prin înmultirea la stânga cuo matrice de permutare notata P;Pivotarea pe coloane poate fi descrisa prin înmultirea ladreapta cu o matrice de permutare ce va fi notata cu Q.

Page 29: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Pivotare

A0 = P1A. (56)

Presupunând ca la fiecare etapa de eliminare se efectueaza opermutare partiala, relatiile (37) se scriu

A1 = E1A0 = E1P1A,A2 = E2P2A1 = E2P2E1P1A,· · ·An−1 = En−1Pn−1 · · ·E2P2E1P1A.

(57)

U = En−1Pn−1 · · ·E2P2E1P1A. (58)

U = E3P3E2P2E1P1A =

= E3︸︷︷︸

E′3

P3E2P−13

︸ ︷︷ ︸

E′2

P3P2E1P−12 P−1

3︸ ︷︷ ︸

E′1

P3P2P1A =

= E′

3E′

2E′

1︸ ︷︷ ︸

L−1

P3P2P1︸ ︷︷ ︸

P

A (59)

Page 30: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Pivotare

Factorizarea cu pivotare pe linii:

PA = LU, (60)

Factorizarea LU cu pivotare totala (rareori aplicata)

PAQ = LU, (61)

Page 31: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Cazul sistemelor multiple

Rezolvate cu factorizare: T = O(2n3/3 + 2mn2), mai mic decâtcel necesar calculului inversei.

Efort de calcul pentru rezolvarea sistemelor multiple.Nr. sisteme Metoda Complexitate T

1 Gauss 2n3/3 + n2

LU 2n3/3 + 2n2

m - simultan Gauss 2n3/3 + 2mn2

m - succesiv folosind inversa 8n3/3 + 2mn2

LU 2n3/3 + 2mn2

Page 32: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Varianta CholeskyDaca A este simetrica, atunci este de dorit ca

U = LT . (62)

Aceasta se poate realiza doar daca A este pozitiv definita. Pp.

A = LLT . (63)

fie x nenul; atunci y = LT x va fi nenul

xT Ax = xT LLT x = yT y =n∑

i=1

y2i > 0.

Teorema: Daca A este o matrice simetrica si pozitiv definita,atunci factorizarea ei Cholesky exista în mod unic, adica existaîn mod unic o matrice triunghiular inferioara L cu elementelediagonale pozitive, astfel încât A = LLT .

Page 33: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Modul de generare al matricei L

[α aT

a A

]

=

[λ 0l L

] [λ lT

0 LT

]

. (64)

λ =√α (65)

l = a/λ (66)

LLT = A− llT . (67)

Complementul Schur al lui α:

S = A− llT = A− aaT/α. (68)

Se poate demonstra ca S este simetrica si pozitiv definita si, înconsecinta LLT este factorizarea ei Cholesky.

Page 34: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Modul de generare al matricei L

A = A0 =

[λ 0l L

] [λ lT

0 LT

]

=

[λ 0l I

] [1 00 S

] [λ lT

0 I

]

= L1A1LT1 .

(69)Similar,

A1 = L2A2LT2 ,

... (70)

An−1 = LnAnLTn ,

unde An = I.

A = L1L2 · · ·Ln︸ ︷︷ ︸

L

LTn LT

n−1 · · ·LT1

︸ ︷︷ ︸

LT

(71)

Page 35: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Algoritm

lkk =

√√√√akk −

k−1∑

j=1

l2kj , k = 1, . . . ,n (72)

lik = (aik −k−1∑

j=1

lij lkj)/lkk , i = k + 1, . . . ,n. (73)

procedur a factorizare_LU_Cholesky(n, a, l); factorizeaza matricea a, presupusa simetrica si pozitiv definita; întoarce matricea triunghiular inferioara l; varianta Cholesky; declaratii· · ·pentru k = 1, n ; parcurge sub-etape ale eliminarii

pentru i = k, n ; calculeaza coloana, sub diagonalas = aikpentru j = 1, k − 1

s = s − lij lkj•dac a i = k

lkk =√

saltfel

lik = s/lkk•

••

Page 36: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Algoritm

Efortul de calcul

Te ≈n∑

k=1

[2k(n − k)] = −2n∑

k=1

[(n − k − n)(n − k)] =

= −2

[n∑

k=1

(n − k)2 − nn∑

k=1

(n − k)

]

=

= −2[(n − 1)n(2n − 1)

6− n

n(n − 1)2

]

≈ −2(

2n3

6− n3

2

)

=n3

3

Algoritmul Cholesky este întotdeauna stabil si nu are nevoie depivotare. Aceasta se datoreaza proprietatilor speciale alematricei A, care fiind pozitiv definita este si diagonal dominanta.

Page 37: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Cazul matricelor rare

Matrice rara = matrice care contine un numar foarte mare deelemente nenule.O matrice care nu este rara se numeste matrice densa sauplina.Densitatea unei matrice = raportul dintre numarul de elementenenule si numarul total de elemente al matricei.Daca, pentru o anumita matrice care are si elemente nule, sepoate elabora un algoritm care exploateaza aceasta structurasi care, este mai eficient decât algoritmul conceput pentrumatricea plina, atunci aceasta este o matrice rara.

Page 38: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Formate de memorare a matricelor rare

Matrix Market: se memoreza doar valorile nenule si"coordona-tele" lor în matrice. http://math.nist.gov/MatrixMarketExemplu: tablou bidimensional de dimensiune m × n:Mplin = 8mn BMrar ,coord = 8 ∗ nnz + 4 ∗ 2nnz = 16nnz B.

M =

4 0 0 00 0 5 12 3 0 7

val = [ 4 5 1 2 3 7 ]r_idx = [ 1 2 2 3 3 3 ]c_idx = [ 1 3 4 1 2 4 ]

Page 39: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Formate de memorare a matricelor rare

Formatul Yale (CRS - Compressed Row Storage:Mrar ,CRS = 8nnz + 4(m + 1) + 4nnz = 12nnz + 4(m + 1) B.

M =

4 0 0 00 0 5 12 3 0 7

val = [ 4 5 1 2 3 7 ]r_ptr = [ 1 2 4 7 ]c_idx = [ 1 3 4 1 2 3 ]

Similar, CCS (Compressed Column Storage)- cunoscut si sumnumele Harwell - Boeing.Mrar ,CCS = 8nnz + 4(n + 1) + 4nnz = 12nnz + 4(n + 1) B.

M =

4 0 0 00 0 5 12 3 0 7

val = [ 4 2 3 5 1 7 ]c_ptr = [ 1 3 4 5 7 ]r_idx = [ 1 3 3 2 2 3 ]

Page 40: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Formate de memorare a matricelor rare

Matricelor banda (de exemplu matrice tridiagonala):

M =

q1 r1 0 0 · · · 0 0 0p2 q2 r2 0 · · · 0 0 00 p3 q3 r3 · · · 0 0 0· · ·· · ·0 0 0 0 · · · pn−1 qn−1 rn−1

0 0 0 0 · · · 0 pn qn

Memorare cu ajutorul a trei vectori (CDS - CompressedDiagonal Storage):

Mrar =

0 p2 p3 · · · pn−1 pn

q1 q2 q3 · · · qn−1 qn

r1 r2 r3 · · · rn−1 0

Page 41: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Metode directe pentru matrice rareGauss pentru matrice tridiagonala:

∗ ∗ 0 0 0 0 0 · · · 0 00 ∗ ∗ 0 0 0 0 · · · 0 00 0 ∗ ∗ 0 0 0 · · · 0 00 0 0 qk rk 0 0 · · · 0 00 0 0 pk+1 qk+1 rk+1 0 · · · 0 00 0 0 0 pk+2 qk+2 rk+2 · · · 0 0...0 0 0 0 0 0 0 · · · pn qn

Un singur element de multiplicare m = −pk+1/qk .Singura modificare suferind-o ecuatia k + 1:qk+1 = qk+1 + m ∗ rk , si temenul liber corespunzator.Retrosubstitutie

xn = bn/qn, (74)

qixi + rixi+1 = bi ⇒ xi = (bi − rixi+1)/qi , i = n − 1, . . . , 1.(75)

Page 42: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Metode directe pentru matrice rare

procedur a Gauss_tridiag(n, p, q, r, b, x); rezolva sistemul algebric liniar ax = b prin metoda Gauss; matricea a este tridiagonala, memorata în p, q, rîntreg n ; dimensiunea sistemuluitablou real p[n], q[n], r [n] ; "matricea" coeficientilor - indici de la 1tablou real b[n] ; vectorul termenilor liberitablou real x [n] ; vectorul solutieîntreg i, k; etapa de eliminare din metoda Gausspentru k = 1, n − 1 ; parcurge sub-etape ale eliminarii

m = −pk+1/qk ; element de multiplicareqk+1 = qk+1 + mrk ; modifica element în linia k + 1bk+1 = bk+1 + mbk ; modifica termenul liber al ecuatiei k + 1

•; etapa de retrosubstitutiexn = bn/qnpentru i = n − 1, 1,−1

xi = (bi − ri xi+1)/qi•retur

T = O(8n), M = O(5n).

Page 43: Sisteme de ecuatii algebrice liniare - metode directe (II)an.lmn.pub.ro/slides/AN_s6.pdfFormularea problemei Gauss - sisteme multiple Metoda factorizarii LU˘ Varianta Doolittle Varianta

Formularea problemei Gauss - sisteme multiple Metoda factorizarii LU Varianta Doolittle Varianta Cholesky Matrice rare

Metode directe pentru matrice rare• Pentru matrice rare fara o structura particulara, algoritmii

trebuie adaptati memorarii de tip CRS sau CCS.• La eliminare matricea se poate umple, a.î. pivotarea

urmareste nu numai stabilitatea numerica, ci siminimizarea umplerilor, adica a elementelor nenule nouaparute.

• La matrice rare inversarea este practic imposibila datoritafenomen de umplere.

• Factorizarea unei matrice rare poate salva raritatea dacamatricea are o anumita structura.

A1 =

∗ 0 · · · 0 0 ∗0 ∗ · · · 0 0 ∗

· · ·0 0 · · · ∗ 0 ∗0 0 · · · 0 ∗ ∗∗ ∗ · · · ∗ ∗ ∗

A2 =

∗ ∗ ∗ · · · ∗ ∗∗ ∗ 0 · · · 0 0∗ 0 ∗ · · · 0 0· · ·∗ 0 · · · 0 ∗ 0∗ 0 · · · 0 0 ∗

Matricea A1 are factorii LU rari, în timp ce matricea A2 are factorii LU plini.

Structura matricei joaca deci un rol important în concepereaalgoritmului de rezolvare.