Proceduri de triangularizare

Proceduri de triangularizare

In acest capitol vom prezenta procedurile tipice de triangularizare superioara a unei matrice A.

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,2, . ,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 demonstrat 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 construi matricele , si matricea .

Deoarece:

Din egalitatea rezulta:

iar de aici , pentru , obtinem:

Deoarece si ,din aceasta egalitate rezulta .

Teorema este demonstrata.

In Algoritmul 13 se realizeaza triangularizarea superioara a unei matrice A folosind regulile Calculele se fac in matricea A.

Algoritmul 13 Procedura de triangularizare a unei matrice A (varianta 1).

Date de intrare:

Matricea A=.

Date de iesire:

Matricea superior triunghiulara obtinuta in A

Pentru k=1,2,,n-1 executa:

Daca atunci:

Pentru i = k + 1,k + 2,,n executa:

Pentru j = k + 1,k + 2,, n executa:

Sfậrsit Pentru

Sfậrsit Pentru

altfel

Matricea A nu poate fi triangularizata prin acest algoritm.

STOP

Sfậrsit Daca

Sfậrsit Pentru

Sa presupunem acum ca in etapa k elementul . 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.

Algoritmul 14 Procedura de triangularizare a unei matrice A(varianta2).

Date de intrare :

Matricea A=

Date de iesire

Matricea superior triunghiulara obtinuta in A.

Pentru k = 1,2,,n - 1 executa

Daca atunci:

Daca atunci:

Permuta liniile p si k

Sfậrsit Daca

Pentru i=k+1,k+2,,n executa:

Pentru j= k+1,k+2,,n executa:

Sfậrsit Pentru

Sfậrsit Pentru

Sfậrsit Daca

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.

Date de intrare

Matricea A=

Date de iesire:

Matricea superior triunghiulara obtinuta In A

Pentru k=1,2,,n-1 executa:

Daca atunci:

Daca atunci:

Permuta coloanele q si k

Sfậrsit Daca

Daca atunci

Permuta coloanele q si k

Sfậrsit Daca

Pentru i = k+1, k+2,,n  executa:

Pentru j= k+1, k+2,,n executa:

Sfậrsit Pentru

Sfậrsit Pentru

altfel:

Matricea A este superior triunghiulara

STOP

Sfậrsit Daca

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.

Exemplul 2.4. Sa se triangularizeze matricea:

A = .

Solutii

a) İn cazul algoritmului obisnuit (metoda lui Gauss), fara pivotare

partiala sau totala, se parcurg urmatoarele etape:

Etapa 1.

.

Etapa 2.

b) Pivotare partiala.

Etapa 1. Avem:

Se permuta in liniile 1, 2. Se obtine matricea:

Se aplica regulile matricei Rezulta:

Etapa 2. Avem:

= ,

Nu sunt necesare permutari de linii. Se aplica regulile matricei . Rezulta:

c)Pivotare totala.

Etapa 1. Avem:

Se permuta in liniile 1, 3 si coloanele 1, 3. Se obtine matricea:

Se aplica acum regulile matricei Rezulta:

Etapa 2. Avem:

Se permuta in coloanele 2, 3. Se obtine matricea:

Se aplica acum regulile matricei Rezulta:

.

2.4.1 Metode directe bazate pe proceduri de triangularizare

Conform celor stabilite, pentru matricea A exista matricea inferior triunghiulara M' si matricele de permutare P,S astfel incat matricea R=M'PAS este superior triunghiulara.

Rezulta de aici:

    M'PA = R

Sistemul Ax = b se transforma in sistemul:

Ry =c, (2.30)

unde c = M'Pb, iar y = Sx.

Dupa rezolvarea sistemului triunghiular Ry = c se obtine solutia sistemului initial: x = Sy.

Matricea R = M'PAS si vectorul c = M'Pb se pot determina simultan aplicand procedurile de triangularizare matricei extinse (A,b), obtinand in final matricea M'P(AS,b) = (R,c).

Trebuie retinut ca procedura de pivotare totala, care conduce la aparitia matricei S= de permutare a coloanelor, (S= I daca in etapa k nu se fac permutari de coloane), trebuie aplicata numai in "blocul" care corespunde matricei A.

Fie , (r, elementele eventual nenule ale matricei R, y=(, c=( .

Sistemul 2.30 se rezolva cu urmatoarele formule:

(2.31)

Solutia sistemului Ax = b este x = Sy.

Exemplul 2.40.Sa se resolve sistemul:

Metoda 1. Metoda lui Gauss. Pentru aceasta metoda vom folosi formulele 2.2, metoda lui Gauss (regulile ), pentru matricea extinsa (A,b) (in formulele 2.2 indicele de coloana va lua valoarea n+1).

Vom nota cu Bmatricea extinsa obtinuta in etapa k. Avem:

, B=, B

Sistemul 2.30 corespunzator matricei B este:

Solutia acestui sistem este:

y=

Deoarece nu s-au efectuat permutari de coloane rezulta S=I si deci solutia sistemului dat este:

x=y=

Metoda 2. Metoda pivotarii totale. Fie:

B= (A.

Aplicand procedura de pivotare totala obtinem:

.

Se permuta liniile 1,2 si coloanele 1,2. Obtinem:

= P(A.

Se aplica regulile matricei .Rezulta:

B=M M.

Aplicam din nou procedura de pivotare totala.Avem :

.

Nu sunt necesare permutari de linii sau coloane. Se aplica regulile matricei B.Obtinem:

B=M, M.

Sistemul 2.30 corespunzator matricei Beste:

Solutia acestui sistem este:

y=.

Solutia sistemului dat este :

x=Sy=Sy=.

In algoritmul 27 se rezolva sistemul Ax = b folosind procedura de triangularizare pentru matricea extinsa (A,b) cu pivotare totala in fiecare etapa. Calculele se fac in matricea (A,b).

In algoritm matricea S este produsul matricelor de permutare de coloane S, , (S daca in etapa k nu se fac permutari de coloane).Initial vom lua S=I . Daca in etapa k se permuta in (A,b) coloanele q si k atunci vom avea S= , ceea ce este echivalent cu permutarea in S a coloanelor q si k.

ALGORITM . ..

Comentariul 2.41.In procedura de triangularizare din primul paragraf al aceastui capitol inlocuim matricele M date de formula 2.1 cu matricele:

unde:

,

Matricea A se transforma in matricea dupa urmatoarele reguli:

R:Coloanele 1,2, . k-1 nu se modifica (pentru k).

R: Coloana k este coloana k din matricea unitate.

R: Linia pivotului se imparte la pivot.

R: Elementele situate in coloanele k+1,k+2, . n si liniile 1,2, . ,k-1,k+1,.. . n se transforma cu regula dreptunghiului.

Daca a, atunci se aplica metoda pivotarii partiale sau totale.

In acest mod se calculeaza matricele A2.Matricea finala este superior triunghiulara avand elementele situate pe prima diagonala egale cu 1 sau 0.In coloanele care au numarul 1 la intersectia cu diagonala, toate celelalte elemente sunt nule.

Daca in toate cazurile in care se aplica metodele de pivotare se gasesc elemente nule, care prin permutari de linii si (sau) coloane devin elemente pivot, atunci =I.

Matricea Reste de forma R=PAS, cu:

M S=

Matricele ,sunt egale cu matricea unitate daca in etapa k nu se fac permutari de linii, respectiv coloane.

Daca matricea A a sistemului Ax = b este nesingulara, atunci, aplicand procedura precedenta matricei extinse (A,b), obtinem in final R = I. Deci, solutia sistemului 2.30 este y = c = MPb.

Aceasta procedura este aplicata in Algoritmul 28.

Exemplul 2.42.Aplicam aceasta procedura sistemului din exemplul precedent.Avem:

=

Aplicam procedura de pivotare totala.Avem:

.

Se permuta liniile 1,2 si coloanele 1,2.Obtinem matricea:

P.

Transformam matricea dupa regulile . Obtinem:

M

Aplicand din nou procedura de pivotare totala se constata ca nu sunt necesare permutari de linii sau coloane. Transformam matricea dupa regulile Obtinem:

B M.

Transformam matricea dupa regulile . Rezulta in final:

B .

Solutia sistemului Ry = c este:

y = c = .

Solutia sistemului dat este:

x = Sy = = .

Algoritmul 28 . . . . .

2.6 Metode pentru calculul determinantilor.

Metode simple pentru calculul determinantilor decurg din procedurile de triangularizare LR,QR.

Fie si:

(2.57)

Matricea superior triunghiulara obtinuta in urma aplicarii procedurii de triangularizare matricei A.

Matricele , sunt inferior triunghiulare avand elementele diagonale egale cu 1. De aceea:

, 1

Matricele sunt matrice unitate sau se obtin din matricea unitate prin permutarea a doua linii atunci cand sunt matrice de permutare de linii, respectiv coloane. De aceea determinantii acestor matrice au valoarea 1 sau -1.

Din 2.57 rezulta:

(2.58)

unde daca numarul permutarilor de linii si de coloane este par, in caz contrar, iar sunt elementele diagonale ale matricei superior triunghiulare .

Daca matricea A poate fi factorizata LR, Doolittle sau Crout , atunci din egalitatea A=L R rezulta formulele:

(2.59)

in cazul factorizarii Doolittle, si:

, (2.60)

in cazul factorizarii Crout.

Pentru o matrice oarecare A exista matricele P,S, produse de matrice de permutare de linii, respectiv coloane, astfel incat matricea poate fi factorizata LR.Cum determinantul unei matrice de permutare de linii sau coloane este -1 rezulta ca daca numarul permutarilor de linii si coloane este par si in caz contrar. Atunci , din egalitatea , rezulta formulele:

, (2.61)

in cazul factorizarii Doolittle, si

, (2.62)

in cazul factorizarii Crout, unde daca numarul permutarilor de linii si coloane este par si in caz contrar.

Apoi, pentru orice matrice Aexista matricea ortogonala Q, produs de matrice Householder, si matricea superior triunghiulara R astfel incat . Deoarece determinantul unei matrice Householder este -1 rezulta:

, (2.63)

unde daca numarul matricelor Householder este par, in caz contrar, iar sunt elementele diagonale ale matricei R obtinuta prin aplicarea procedurii de factorizare QR matricei A.