Descompunerea QR

În matematică , în special în algebra liniară , descompunerea QR sau factorizarea QR a unei matrice pătrate cu coeficienți reali sau complexi $M.$ ${\ displaystyle M}$ $M.$ este o descompunere de tipul

M=QR,

{\ displaystyle M = QR,}

{\ displaystyle M = QR,}

unde este $Î$ ${\ displaystyle Q}$ $Î$ este o matrice ortogonală și $R.$ ${\ displaystyle R}$ $R.$ este o matrice triunghiulară superioară . Se poate arăta că toate matricile pătrate admit o descompunere QR, chiar dacă nu este unică. În cazul în care matricea $M.$ ${\ displaystyle M}$ $M.$ ambele cu coeficienți complexi, atunci $Î$ ${\ displaystyle Q}$ $Î$ este o matrice unitară .

Calcul

Factorizarea QR a unei matrice date în timp poate fi calculată explicit $O(n^{3})$ ${\ displaystyle O (n ^ {3})}$ $O (n ^ 3)$ operații aritmetice prin utilizarea transformărilor Householder sau Givens .

Aplicații

Principala aplicație a factorizării QR este soluția sistemelor liniare : odată ce matricea a fost luată în considerare $A=QR$ ${\ displaystyle A = QR}$ ${\ displaystyle A = QR}$ a unui sistem liniar $Ax=b$ ${\ displaystyle Ax = b}$ $Ax = b$ cu cost $O(n^{3})$ ${\ displaystyle O (n ^ {3})}$ $O (n ^ 3)$ , soluția sistemului este dată de

x=R^{-1}(Q^{t}b)

{\ displaystyle x = R ^ {- 1} (Q ^ {t} b)}

{\ displaystyle x = R ^ {- 1} (Q ^ {t} b)}

Calculul $c=Q^{t}b$ ${\ displaystyle c = Q ^ {t} b}$ ${\ displaystyle c = Q ^ {t} b}$ necesită $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ operațiuni, în timp ce calculul $x=R^{-1}c$ ${\ displaystyle x = R ^ {- 1} c}$ ${\ displaystyle x = R ^ {- 1} c}$ se poate face printr-un algoritm de substituție inversă întotdeauna cu $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ operațiuni. Prin urmare, costul dominant este tocmai cel al factoringului.

Complexitatea de calcul a acestei metode de rezolvare este deci aceeași cu soluția care utilizează factorizarea LU (sau algoritmul Gauss ), dar acest algoritm are o stabilitate numerică mai bună .

Mai mult, factorizarea QR poate fi utilizată pentru calculul bazelor ortonormale și pentru soluția unui sistem de cel puțin pătrate .

La baza factorizării QR există o metodă, cunoscută sub numele de metodă QR , utilizată pentru a calcula valorile proprii ale unei matrice și vectorii proprii respectivi.

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică