Metode de calcul pentru factorizarea matricelor. aplicatii

METODE DE CALCUL PENTRU FACTORIZAREA MATRICELOR. APLICATII

Capitolul I

In acest capitol vom prezenta procedee de factorizare a matricelor, metode directe si interative pentru rezolvarea sistemelor de ecuatii liniare, metode pentru calculul determinantilor si inversarea matricelor.

2.1 Proceduri de triangularizare

In acest paragraf vom prezenta procedee tipice de triangularizare tipice de triangularizare superioara a unei matrice .

Triangularizarea superioara a matricei A se realizeaza intr-un numar de etape in care se determina matricele de forma:

,

Sa presupunem ca am construit matricea si ca . Elementul il vom numi pivot.

Fie matricea :

unde :

Matricea va fi :

Elementele matricei se calculeaza asfel:

Expresia este echivalenta cu :

Cele patru elemente care intervin in aceasta expresie determina in matricea un dreptunghi cu un varf in pivot. Regula de calcul in aceasta expresie este regula dreptunghiului:

'' Din produsul de pe diagonala pivotului se scade produsul de pe cealalta diagonala, iar rezultatul se imparte la pivot".

Asadar , matricea se transforma in matricea dupa urmatoarele reguli:

Liniile 1 ,.,k si coloanele 1,2,.,k-1 (k>1), nu se modifica.

. Elementele subdiagonale din coloana k se anuleaza.

. Elementele situate in liniile si coloanele k+1, k+2, .,n se transforma dupa regula dreptunghiului.

Aceasta este metoda eliminarii a lui Gauss.

Daca , atunci matricea finala va fi o matrice superior triunghiulara.

Din si , rezulta:

Matricea este o matrice inferior triunghiulara.

Teorema 2.1. Daca matricea are proprietatea :

(2.3)

unde , atunci exista o matrice M inferior triunghiulara , nesingulara, astfel incat matricea R=MA este superior triunghiulara.

Demonstratie. Avand in vedere rationamentul precedent, mai trebuie demonstrate ca daca matricea A are proprietatea 2.3 atunci Aceasta demonstratie o vom face prin inductie.

Pentru k=1 avem Rezulta

Presupunem ca .

Atunci , conform rationamentului anterior, se pot construe matricele , si matricea .

Deoarece:

Din egalitatea rezulta:

iar de aici , pentru , obtinem:

Deoarece si , din aceasta egalitate rezulta .

Teorema este demonstrate.

Sa presupunem acum ca in etapa k elemental . In acest caz se folosesc asa numitele proceduri de pivotare partiala sau totala.

Proceduri de pivotare partiala.

Se cauta in coloana k acel element cu proprietatea:

Daca atunci A. In acest caz, teoretic, vom considera in rationamentul precedent M.

Daca si se permuta liniile k si .Aceasta permutare se poate face prin inmultirea matricei A, la stanga, cu matricea Pobtinuta din matricea unitate prin permutarea liniilor k si .Se aplica in continuare metoda lui Gauss matricei P.

Teoretic, in final se obtine matricea superior triunghiulara , unde:

In acest produs consideram atunci cand in etapa k nu se efectueaza permutari de linii.

Deoarece putem scrie:

,

unde

Deoarece matricele , , sunt inferior triunghiulare, rezulta ca matricea este de asemenea inferior triunghiulara.

Fie .

Am demonstrat astfel urmatoarea teorema:

Teorema 2.2 Pentru orice matrice exista o matrice de permutare de linii P si o matrice inferior triunghiulara astfel incat matricea este superior triunghiulara.

In Algoritmul 14 se realizeaza triangularizarea superioara a unei matrice aplicand in fiecare etapa procedura de pivotare partiala si regulile . Calculele se fac in matricea A.

2.Procedura de pivotare totala

In aceasta procedura se determina elementul cu proprietatea:

.

Daca atunci In acest caz, teoretic, in rationamentul precedent vom considera .

Daca atunci se permuta liniile k si daca , iar apoi se permuta coloanele k si daca .Permutarea liniilor se poate face prin inmultirea matricei la stanga cu matricea descrisa in procedura de pivotare partiala, iar permutarea coloanelor se poate face prin inmultirea matricei la dreapta cu matricea obtinuta din matricea unitate prin permutarea liniilor si .

Fie .

In acest produs daca in etapa k nu se fac permutari de coloane.

Teorema precedenta are acum urmatorul enunt:

Teorema 2.3. Pentru orice matrice exista o matrice inferior triunghiulara M' si doua matrice P,S de permutare de linii, respectiv coloane, astfel incat matricea R=M'PAS este superior triunghiulara.

In Algoritmul 15 se realizeaza triangularizarea superioara a unei matrice Aaplicand in fiecare etapa procedura de pivotare totala si regulile .Calculele se fac in matricea A.

ALGORITM 15....

Metodele de pivotare partiala sau totala se recomanda a fi utilizate in general, nu numai in cazul cand intr-o anumita matrice elementul este nul.Aceste metode asigura stabilitate numerica algoritmului de triangularizare si evita situatiile in care erorile de rotunjire in calculator au efecte catastrofale asupra rezultatelor finale.

Factorizarea LR

In acest paragraph vom prezenta principalele proceduri de factorizare LR a unei matrice .

Definitie 2.5. Fie . O descompunere de forma:

A=LR

unde L este o matrice inferior triunghiulara, iar R este o matrice superior triunghiulara, se numeste factorizare LR a matricei A.

Rezultatul urmator este o consecinta imediata a teoremei 2.1

Teorema 2.6 Daca matricele sunt nesingulare, atunci exista o factorizare LR a matricei A in care L este o matrice nesingulara.

Demonstratie. Fie matricea obtinuta in procedura de triangularizare a matricei A. Deoarece M este o matricei inferior triunghiulara , nesingulara, rezulta ca este inferior triunghiulara si nesingulara. Din egalitatea rezulta , unde este o matrice superior triunghiulara.

Teorema este demonstrata.

ALGORITMUL 16.

Definitia 2.11 Factorizarea LR in care elementele diagonale ale matricei L sunt egale cu 1 se numeste factorizare Doolittle.

Pentru o matrice A factorizarea Doolittle este unica.

Intr-adevar, daca sunt doua astfel de factorizari, atunci din rezulta:

Matricea este inferior triunghiulara cu elementele diagonale egale cu 1, iar matricea este superior triunghiulara. De aceea egalitatea precedenta poate avea loc daca si numai daca :

Rezulta de aici:

Definitie 2.12 Factorizarea LR in care elementele diagonale ale matricei R sunt egale cu 1 se numeste factorizare Crout.

Uncicitatea factorizarii Crout se demonstreaza analog ca in cazul precedent.

Elementele matricelor L si R care realizeaza factorizarea LR a matricei A se poate calcula direct din egalitatea: A=LR

Fie elementele eventual nenule ale matricei L, iar , elementele eventual nenule ale matricei R.

Din egalitatea A=LR rezulta:

(2.5)

Pentru factorizarea Doolittle se obtin formulele:

(2.6)

Pentru factorizarea Crout din 2.5 se obtin formulele:

(2.7)

Pentru o matrice Algoritmil 17 realizeaza o factorizare Doolittle cu formulele 2.6, iar Algoritmul 18 o factorizare Crout cu formulele 2.7. Calculele se fac in matricea A.

Teorema 2.14. Pentru orice matirce exista o matrice de permutare de linii P astfel incat matricea PA poate fi factorizata LR.

Demonstratie:

Din teorema 2.2 rezulta ce pentru orice matrice exista o matrice inferior triunghiulara M' si o matrice de permutari de linii P astfel incat R=M'PA este o matrice superior triunghiulara.

Rezulta de aici PA=LR, unde L= este o matrice inferior triunghiulara.

In descrierea procedurii de pivotare partiala am stabilit egalitatea M=M'P, unde :

,

iar matricea P este produsul matricelor de permutare de linii in A:

In acest produs avem , I fiind matricea unitate , daca in etapa k nu se fac permutari de linii.

Deci :

Teorema este astfel demonstrata.

Pentru o matrice in Algoritmul 19 se determina o matrice P de permutare de linii in maticea A, matricea inferior triunghiulara L si matricea superior triunghiulara R. Matricea initiala A se retine in matricea .

In algoritm, la final, matricea P este produsul matricelor de permutare de linii in A , I fiind matricea unitate, daca in etapa k nu se fac permutari de linii).

Initial vom lua P=I. Apoi in fiecare etapa k in care se permuta liniile p si k in A avem , ceea ce este echivalent cu permutarea in P a liniilor p si k.

Matricea se obtine din matricea unitate inlocuind elementele subdiagonale din coloana k cu elementele .

Inmultirea matricei la stanga cu matricea are ca efect permutarea in a liniilor p si k.

Astfel se obtine in algoritm matricea : .

ALGORITMUL 19.

Algoritmul de factorizare poate fi completat deasemenea cu o strategie la pivotare totala.

Din teorema 2.3 rezulta ca pentru orice matrice exista o matrice inferior triunghiulara M' si matricele P, S de permutare de linii, respective coloane, astfel incat matricea este superior triunghiulara.

Rezulta de aici , unde :

este o matrice inferior triunghiulara.

Teorema 2.18. Pentru orice matrice exista matricele P,S de permutare de linii, respective de coloane, astfel incat matricea PAS poate fi factorizata in LR.

Pentru o matrice in Algoritmul 20 se determina matricele P,S de permutare de linii, respective coloane in matricea A, matricea inferior triunghiulara L si matricea superior triunghiulara R astfel incat PAS=LR.

In A se obtine matricea R. Matricea initiala A se retine in matricea .

Modul de obtinere al matricei :

este cel descris mai sus.

Matricea este produsul matricelor de permutare de coloana in A, daca in etapa k nu se fac permutari de coloane).

Initial vom lua . Apoi, in fiecare etapa k in care se permuta coloanele q si k in A avem , ceea ce este echivalent cu permutarea in S a coloanelor q si k.

ALGORITMUL 20...

Matricele dreptunghiulare pot fi factorizate LR folosind procedurile descries anterior. In acest caz matricea L este superior triunghiulara , iar matricea R este superior trapezoidala, .

In continuare prezentam procedurile de factorizare LR pentru matricele tridiagonale si pentadiagonale.

Teorema 2.23. Fie matricea tridiagonala:

Definim sirul astfel

Atunci:

1)

Daca atunci o factorizare LR (Doolittle) a matricei A este realizata de matricele:

(2.11) Demonstratie.1)

Presupunem

Dezvoltand dupa ultima coloana, obtinem:

2) Se verifica direct prin calcul egalitatea

In teorema precedenta forma matricelor L,R este:

(2.12)

(2.13)

Daca det(A)0, atunci din egalitatea rezulta det(R)0, adica ,. De aceea, din se obtin formulele:

(2.14)