Factorizarea LU

Factorizarea LU

1 Breviar teoretic

Fie sistemul compatibil determinat

Ax = b. (2.4)

Factorizarea LU presupune descompunerea matricei A intr-un produs de matrice L · U , unde

, ( 2.5 )

Aceasta descompunere este posibila daca toti determinantii de colt ai matricei A sunt nenuli.

Pentru a asigura unicitatea descompunerii, trebuie precizate n elemente ale matricei L sau U. In mod traditional, se specifica λ_ii sau µ_ii; daca λ_ii = 1 atunci factorizarea LU se numeste factorizare Doolittle, iar daca µ_ii = 1 se numeste factorizare Crout.

Astfel, rezolvarea sistemului (2.4) se reduce la rezolvarea sistemelor triunghiulare

Ly = b (2.6)

cu solutia

                              (2.7)

si

Ux = y (2.8)

cu solutia

(2.9)

2 Problema rezolvata

Exercitiul 1 Sa se determine solutia sistemului urmator, folosind factorizarea LU:

Sistemul se scrie in forma matriceala:

Ax = b,

unde

, ,

Deoarece

rezulta ca matricea A este nesingulara si are toti determinantii de colt nenuli, deci se poate folosi factorizarea LU pentru rezolvarea acestui sistem.

REZOLVARE FOLOSIND FACTORIZAREA CROUT

A. Factorizarea Crout

Presupunem ca

,

si ne propunem sa determinam coeficientii l_ij , u_jk. Pentru aceasta, folosim definitia inmultirii matricelor. Astfel, avem:

a₁₁ = λ₁₁· 1 λ₁₁ = 1

Eseu: Raport de incercare Eseu: Detergenti .Sapunuri. Substante tensio-active - clasificare

a₁₂ = λ₁₁· µ₁₂ µ₁₂ = 1

a₁₃ = λ₁₁· µ₁₃ µ₁₃ = −1

a₂₁= λ₂₁· 1                     λ₂₁ = 2

a₂₂= λ₂₁· µ₁₂ + λ₂₂ · 1 λ₂₂ = −3

a₂₃ = λ₂₁ · µ₁₃ + λ₂₂ · µ₂₃                    µ₂₃ = −1

a₃₁ = λ₃₁· 1                                                        λ₃₁ = 1

a₃₂ = λ₃₁ · µ₁₂ + λ₃₂ · 1 λ₃₂ = 2

a₃₃= λ₃₁· µ₁₃ + λ₃₂ · µ₂₃ + λ₃₃ · 1                    λ₃₃ = 1

sau

B. Rezolvarea sistemelor triunghiulare

Pentru rezolvarea sistemului initial, avem de rezolvat doua sisteme triungiulare:

a carui solutie este

,

si respectiv:

,

a carui solutie este

.

REZOLVARE FOLOSIND FACTORIZAREA DOOLITTLE

A. Factorizarea Doolittle

Presupunem ca

si ne propunem sa determinam coeficientii l_ij , µ_jk , la fel ca si in exemplul precedent. Astfel avem:

a₁₁= 1 · µ₁₁                                   µ₁₁= 1

a₁₂= 1 · µ₁₂                                   µ₁₂= 1

a₁₃= 1 · µ₁₃                                   µ₁₃= −1

a₂₁= λ₂₁· µ₁₁                                λ₂₁ = 2

a₂₂= λ₂₁· µ₁₂ + 1 · µ₂₂ µ₂₂ = −3

a₂₃ = λ₂₁· µ₁₃ + 1 · µ₂₃      µ₂₃ = 3

a₃₁ = λ₃₁· µ₁₁     λ₃₁ = 1

a₃₂ = λ₃₁· µ₁₂ + λ₃₂ · µ₂₂ λ₃₂ =

a₃₃ = λ₃₁· µ₁₃ + λ₃₂ · µ₂₃ + 1 · µ₃₃           µ₃₃= 1

sau

.

B. Rezolvarea sistemelor triunghiulare

Pentru rezolvarea sistemului initial, avem de rezolvat doua sisteme triungiulare:

,

a carui solutie este

si respectiv:

,

a carui solutie este

.

3 Implementare

A. Algoritm

Date de intrare: un sistem de ecuatii.

Date de iesire: solutia sistemului

Algoritmul consta din urmatoarele etape:

1. generarea matricei A a sistemului, si a vectorului coloana b

. n = numarul de linii ale matricei A (numarul de ecuatii ale sistemului)

2. a) factorizarea Crout

pentru i =

µ_ii= 1

pentru i =

pentru j =

pentru j =

b) factorizarea Doolittle

pentru i =

λ_ii= 1

pentru i =

pentru j =

pentru j =

3. Rezolvarea celor doua sisteme triunghiulare

pentru i =

pentru i =

B. Programe MAPLE si rezultate

2.3 Sisteme tridiagonale

2.4 Factorizarea Cholesky

2.5 Factorizarea Householder

Factorizarea Householder este o metoda de rezolvare numerica a sistemelor de tip Cramer simetrice, si consta in determinarea unei matrice simetrice nesingulare U , astfel incat UAU = T sa fie o matrice tridiagonala

2.6 Metoda Jacobi

Metoda Jacobi este o metoda iterativa de rezolvare a sistemelor liniare de forma Ax = b.

2.7 Metoda Gauss-Seidel

Metoda Gauss-Seidel este o metoda de rezolvare numerica a sistemelor de tip Cramer, prin aproximatii succesive.

2.8. Metoda relaxarii succesive

Metoda relaxarii succesive este o metoda de rezolvare numerica a sistemelor

de tip Cramer, prin aproximatii succesive.