Descompunerea QR

De la Wikipedia, enciclopedia liberă

În algebra liniară, descompunerea QR (numită şi factorizarea QR) a unei matrice este o descompunere a acelei matrice într-un produs dintre o matrice ortogonală şi una triunghiulară. Descompunerea QR este adesea folosită pentru a rezolva problema celor mai mici pătrate. Descomunerea QR stă şi la baza unui algoritm de aflare a valorilor proprii, algoritmul QR.

Cuprins 1 Definiţie 2 Calculul descompunerii QR 3 Descompunerea QR prin procedeul Gram-Schmidt 3.1 Exemplu 4 Calculul QR cu ajutorul reflectorilor Householder 4.1 Exemplu 5 Bibliografie

[modifică] Definiţie

O descomunere QR a unei matrici pătrate reale A este o descompunere a lui A de forma

unde Q este o matrice ortonormală (cu proprietatea că Q^TQ = I ) şi R este o matrice superior triunghiulară. Analog, se pot defini descompunerile QL, RQ şi LQ ale lui A.

Mai general, se poate factoriza o matrice complexă m×n (cu m ≥ n) sub forma unui produs dintre o matrice unitară m×n (în sensul că Q^∗Q = I ) şi o matrice n×n superior triunghiulară.

Dacă A este nesingulară, atunci această factorizare este unică dacă se pune condiţia ca elementele diagonale ale lui R să fie pozitive.

[modifică] Calculul descompunerii QR

Există câteva metode pentru calculul efectiv al descompunerii QR, cum ar fi cele cu ajutorul procedeului Gram–Schmidt, transformărilor Householder, sau al rotaţiilor Givens. Fiecare metodă are avantaje şi dezavantaje.

[modifică] Descompunerea QR prin procedeul Gram-Schmidt

Se consideră procedeul Gram–Schmidt, unde vectorii consideraţi în procedeu sunt coloanele matricei . Se defineşte unde .

Atunci

Atunci se rearanjează ecuaţiile de mai sus astfel încât s să fie în stânga şi rezultă următoarele ecuaţii.

Se observă că deoarece sunt vectori unitate, avem următoarele.

Aceste ecuaţii pot fi scrise sub formă matriceală după cum urmează.

Dar produsul fiecărui rând şi coloană al matricelor de mai sus ne dau o coloană corespunzătoare a matricei A iniţiale, şi împreună, ne dau matricea A, deci am factorizat pe A într-o matrice ortogonală Q (matricea formată din e_k), via Gram Schmidt, şi evident, matricea superior triunghiulară este restul R.

Altfel, poate fi calculată după cum urmează:

Dat fiind că avem

Se observă că şi QQ^T = I, deci Q^T = Q ^{− 1}.

[modifică] Exemplu

Se cere descompunerea lui

Fie matricea ortogonală Q astfel încât

Atunci putem calcula Q prin Gram-Schmidt astfel:

Deci avem:

Efectuând operaţia cu ajutorul MATLAB, admiţând erorile de rotunjire datorate operaţiilor cu precizie finită, se obţine:

[modifică] Calculul QR cu ajutorul reflectorilor Householder

Un reflector Householder (sau transformare Householder) este o transformare operată asupra unui vector pe care îl reflectă faţă de un plan. Putem folosi această proprietate pentru a calcula factorizarea QR a unei matrice.

Q poate fi folosită pentru a reflecta un vector în aşa fel încât dispar toate coordonatele mai puţin una.

Fie un vector-coloană arbitrar m-dimensional cu proprietatea că |||| = |α| pentru un scalar α. Dacă algoritmul este implementat folosind aritmetica în virgulă mobilă, atunci α trebuie să aibă semnul opus primei coordonate a lui pentru a evita pierderea de semnificaţie. Dacă e un vector complex, atunci definiţia

ar trebui să fie utilizată (Stoer,Bulirsch,2002,p.225).

Atunci, unde este vectorul (1,0,...,0)^T, şi ||·|| norma euclidiană, fie

Q este o matrice Householder şi

Aceasta se poate folosi treptat pentru a transforma o matrice m-pe-n A în forma superior triunghiulară. Întâi, se înmulţeşte A cu matricea Householder Q₁ obţinută prin alegerea primei coloane pentru x. Aceasta are ca rezultat o matrice QA cu zerouri în coloana din stânga (cu excepţia primului rând).

Aceasta se poate repeta pentru A′ (obţinută din Q₁A ştergând primul rând şi prima coloană), având ca rezultat o matrice Householder Q′₂. Se observă că Q′₂ este mai mică decât Q₁. Deoarece este de dorit ca ea să opereze asupra lui Q₁A în loc de A′ trebuie să fie extinsă spre sus şi stânga, completând-o cu un 1, sau în general:

După t iteraţii ale acestui proces, t = min(m − 1,n),

este o matrice superior triunghiulară. Deci, cu

A = QR is a QR decomposition of A.

Aceasta metodă are o stabilitate numerică superioară metodei Gram-Schmidt descrisă mai sus.

Tabelul următor dă numărul de operaţii în pasul k al descompunerii QR prin transformări Householder, presupunând o matrice pătrată de dimensiune n.

Operaţie	Număr de operaţii în pasul k
înmulţiri	2(n − k + 1)2
adunări	(n − k + 1)2 + (n − k + 1)(n − k) + 2
împărţiri	1
rădăcini pătrate	1

Adunând aceste numere pe cei (n − 1) paşi (pentru o matrice pătrată de dimensiune n), complexitatea algoritmului este dată de

[modifică] Exemplu

Se va calcula descompunerea matricei

Întâi, trebuie să fie găsit un reflector care transformă prima coloană a lui A, vector , în

Acum,

şi

.

Aici,

α = 14 and

Deci

and , şi apoi

Se observă că:

deci avem deja o matrice aproape triunghiulară. Trebuie doar adusă la zero valoarea de pe poziţia (3, 2).

Se ia minorul (1, 1) minor, şi se aplică din nou procedeul pe

Prin aceeaşi metodă ca mai sus, se obţine matricea de transformare Householder

după efectuarea unei sume directe cu 1 pentru a ne asigura că următorul pas din procedeu funcţionează corect.

Se găseşte

Matricea Q este ortogonală iar R este superior triunghiulară, deci A = QR este descompunerea QR căutată.

[modifică] Bibliografie

• Horn, Roger A.; Charles R. Johnson (1985). Matrix Analysis, Cambridge University Press. ISBN 0-521-38632-2. . Section 2.8.
• Stoer, Josef; Roland Bulirsch (2002). Introduction to Numerical Analysis, 3rd, Springer. ISBN 0-387-95452-X. .