Descomposició QR

En àlgebra lineal, una descomposició QR (també anomenada factorització QR) d'una matriu és una descomposició d'una matriu A en el producte A=QR d'una matriu ortogonal Q per una matriu triangular superior R (de l'anglès right, dreta, ja que una matriu triangular superior té tots els seus elements no-nuls a sobre i a la dreta de la diagonal principal –inclosa–). La descomposició QR es fa servir en la resolució de problemes de mínims quadrats, i és la base per un algorisme especial pel càlcul dels valors propis d'una matriu, l'algorisme QR.

Si A té n columnes linealment independents, llavors les primeres n columnes de Q configuren una base ortonormal de l'espai de columnes d'A. Concretament, les primeres k columnes de Q formen una base ortonormal per a l'espai vectorial generat per les primeres k columnes d'A, per qualsevol 1≤k≤n. El fet que tota columna k d'A només depengui de les primeres k columnes de Q és l'argument bàsic per tal que la matriu R sigui triangular.

Definicions

Matrius quadrades

Qualsevol matriu real quadrada A es pot descompondre com a

$A=QR,$

on Q és una matriu ortogonal (les seves columnes són vectors unitaris ortogonals, la qual cosa implica que Q^TQ = I) i R és una matriu triangular superior. Aquesta definició es pot generalitzar al cas d'una matriu quadrada complexa A i una matriu unitària Q. Si A és invertible, llavors la descomposició és única si s'afegeix la hipòtesi que els elements de la diagonal de R siguin positius.

Matrius rectangulars

En un cas més general, es pot factoritzar una matriu complexa A m×n, amb m ≥ n, com el producte d'una matriu unitària Q m×m i una matriu triangular superior R m×n. Com que les últimes (m−n) files d'una matriu triangular superior m×n són entrades a zero, de vegades és útil segmentar la matriu R, o bé tant R com Q:

$A=QR=Q\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]=\left[\begin{array}{c}{Q}_1,Q_2\end{array}\right]\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]=Q_1{R}_1,$

on R₁ és una matriu triangular superior n×n, Q₁ és m×n, Q₂ és m×(m−n), i tant Q₁ com Q₂ tenen columnes ortogonals.

Plantilla:Harvtxt anomenen Q₁R₁ la factorització QR aprimada d'A; per la seva banda, Trefethen & Bau l'anomenen factorització QR reduïda.

Si A té rang complet n i s'afegeix la hipòtesi que els elements de la diagonal de R₁ siguin positius, llavors R₁ i Q₁ són úniques, però en general Q₂ no ho és. En aquest cas, R₁ és igual al factor triangular superior de la factorització de Cholesky de A^* A (= A^TA si A és real).

Descomposicions QL, RQ i LQ

Anàlogament, es poden definir descomposicions QL, RQ, i LQ, on L és una matriu triangular inferior (de l'anglès lower, inferior).

Càlcul de la descomposició QR

Existeixen diversos mètodes per calcular la descomposició QR, com ara el procés d'ortogonalització de Gram–Schmidt, les transformacions de Householder o les rotacions de Givens. Cadascun té els seus avantatges i els seus desavantatges.

Mètode de Gram–Schmidt

Considerem el procés d'ortogonalització de Gram–Schmidt aplicat a les columnes de la matriu de rang complet per columnes $A=[{𝐚}_1,\cdots ,{𝐚}_n]$, amb el producte escalar $<𝐯,𝐰>={𝐯}^T𝐰$ (o $<𝐯,𝐰>={𝐯}^{*}𝐰$ pel cas complex).

Definim la projecció

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐞}𝐚=\frac{<𝐞,𝐚>}{<𝐞,𝐞>}𝐞.$

Llavors:

$\begin{array}{cccc}{𝐮}_1& ={𝐚}_1,& {𝐞}_1& =\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }\\ {𝐮}_2& ={𝐚}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐞}_1}{𝐚}_2,& {𝐞}_2& =\frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }\\ {𝐮}_3& ={𝐚}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐞}_1}{𝐚}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐞}_2}{𝐚}_3,& {𝐞}_3& =\frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }\\ & ⋮& & ⋮\\ {𝐮}_k& ={𝐚}_k-\sum _{j=1}^{k-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐞}_j}{𝐚}_k,& {𝐞}_k& =\frac{{𝐮}_k}{\Vert {𝐮}_k\Vert }\end{array}$

Reescrivim ara les equacions anteriors de tal manera que els termes ${𝐚}_i$ apareguin a l'esquerra, emprant el fet que els vectors ${𝐞}_i$ són unitaris:

$\begin{array}{cc}{𝐚}_1& =<{𝐞}_1,{𝐚}_1>{𝐞}_1\\ {𝐚}_2& =<{𝐞}_1,{𝐚}_2>{𝐞}_1+<{𝐞}_2,{𝐚}_2>{𝐞}_2\\ {𝐚}_3& =<{𝐞}_1,{𝐚}_3>{𝐞}_1+<{𝐞}_2,{𝐚}_3>{𝐞}_2+<{𝐞}_3,{𝐚}_3>{𝐞}_3\\ & ⋮\\ {𝐚}_k& =\sum _{j=1}^k<{𝐞}_j,{𝐚}_k>{𝐞}_j\end{array}$

on $<{𝐞}_i,{𝐚}_i>=\Vert {𝐮}_i\Vert$. Això es pot escriure en forma matricial:

$A=QR$

on:

$Q=[{𝐞}_1,\cdots ,{𝐞}_n]\text{i}R=\left(\begin{array}{cccc}<{𝐞}_1,{𝐚}_1>& <{𝐞}_1,{𝐚}_2>& <{𝐞}_1,{𝐚}_3>& \dots \\ 0& <{𝐞}_2,{𝐚}_2>& <{𝐞}_2,{𝐚}_3>& \dots \\ 0& 0& <{𝐞}_3,{𝐚}_3>& \dots \\ ⋮& ⋮& ⋮& \ddots \end{array}\right).$

Exemple

Considerem la descomposició de

$A=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right).$

Recordem que una matriu ortogonal $Q$ té la propietat

$\begin{array}{c}{Q}^{T}Q=I.\end{array}$

Aleshores, podem calcular $Q$ mitjançant Gram–Schmidt de la manera següent:

$U=\left(\begin{array}{ccc}{𝐮}_1& {𝐮}_2& {𝐮}_3\end{array}\right)=\left(\begin{array}{ccc}12& -69& -58/5\\ 6& 158& 6/5\\ -4& 30& -33\end{array}\right);$

$Q=\left(\begin{array}{ccc}\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }& \frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }& \frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }\end{array}\right)=\left(\begin{array}{ccc}6/7& -69/175& -58/175\\ 3/7& 158/175& 6/175\\ -2/7& 6/35& -33/35\end{array}\right).$

Així, tenim

$\begin{array}{c}{Q}^{T}A=Q^{T}QR=R;\end{array}$

$\begin{array}{c}R=Q^{T}A=\end{array}\left(\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& 35\end{array}\right).$

Relació amb la descomposició RQ

La descomposició RQ transforma una matriu A en el producte d'una matriu triangular superior R per una matriu ortogonal Q. L'única diferència amb la descomposició QR és l'ordre d'aquestes matrius.

La descomposició QR és l'ortogonalització de Gram–Schmidt de les columnes d'A, començant des de la primera columna.

La descomposició RQ és l'ortogonalització de Gram–Schmidt de les files d'A, començant des de l'última fila.

Ús de transformacions de Householder

Transformació de Householder per una descomposició QR: l'objectiu és trobar una transformació lineal que canviï el vector $x$ en un vector de la mateixa longitud i que sigui col·lineal a $e_1$. Podríem usar una projecció ortogonal (Gram-Schmidt), però això podria ser numèricament inestable si els vectors $x$ i $e_1$ són gairebé ortogonals. En lloc d'això, la transformació de Householder calcula la reflexió per la línia de punts (que és la bisectriu de l'angle entre $x$ i $e_1$). L'angle màxim amb aquesta transformació és de 45 graus.

Una transformació de Householder és una transformació que pren un vector i en calcula la reflexió per un pla o hiperplà. Podem usar aquesta operació per calcular la descomposició QR d'una matriu $A$ m×n on m ≥ n.

Q es pot usar per reflectir un vector de tal manera que desapareguin totes les seves coordenades menys una.

Sigui $𝐱$ un vector columna real qualsevol de dimensió m d'$A$ tal que ||$𝐱$|| = |α| per un escalar α. Si l'algorisme s'implementa mitjançant aritmètica de coma flotant, llavors α haurà de tenir el signe contrari de la k-sima coordenada de $𝐱$, on $x_k$ és la coordenada «pivot»; és a dir, totes les altres coordenades de $𝐱$ seran 0 en la forma triangular superior final d'A, sense pèrdua de dígits significatius. En el cas complex, establim

$\alpha =-{\mathrm{e}}^{\mathrm{i}\arg x_k}\Vert 𝐱\Vert$

Plantilla:Harv i substituïm la transposició per la transposició conjugada en la construcció de Q que ara veurem.

Llavors, si denotem per ${𝐞}_1$ el vector (1,0,...,0)^T, ||·|| la norma euclidiana i $I$ és una matriu identitat m×m, definim:

$𝐮=𝐱-\alpha {𝐞}_1,$

$𝐯=\frac{𝐮}{\Vert 𝐮\Vert },$

$Q=I-2𝐯{𝐯}^T.$

O, si $A$ és complexa,

$Q=I-(1+w)𝐯{𝐯}^H$, amb $w={𝐱}^H𝐯/{𝐯}^H𝐱$

on ${𝐱}^H$ és la transposada conjugada de $𝐱$.

Ara, $Q$ és una matriu m×m de Householder i

$Q𝐱=(\alpha ,0,\cdots ,0{)}^T.$

Aquest procés es pot repetir per transformar gradualment una matriu A m×n en forma triangular superior. Primer, multipliquem A per la matriu de Householder Q₁ obtinguda quan escollim que x sigui la primera columna de la matriu. Això resulta en una matriu Q₁A amb zeros a la columna de l'esquerra (excepte a la primera fila).

$Q_{1}A=\left[\begin{array}{ccccc}{\alpha }_1& |& \star & \dots & \star \\ 0& |& & & \\ ⋮& |& & A^{\prime }& \\ 0& |& & & \end{array}\right]$

Això es pot repetir per A′ (obtinguda a partir de Q₁A eliminant la primera fila i la primera columna), la qual cosa resulta en una matriu de Householder Q′₂. Notem que Q′₂ és més petita que Q₁. Com que, de fet, volem que operi sobre Q₁A en comptes de sobre A′, primer necessitem ampliar-la per l'extrem superior esquerre, amb un 1, o en general:

$Q_k=\left(\begin{array}{cc}{I}_{k-1}& 0\\ 0& {Q_k}^{\prime }\end{array}\right).$

Després de $t$ iteracions d'aquest procés, on $t=\min (m-1,n)$,

$R=Q_t\cdots Q_2{Q}_{1}A$

és una matriu triangular superior. Així doncs, si denotem

$Q=Q_1^T{Q}_2^T\cdots Q_t^T,$

tenim que $A=QR$ és una descomposició QR d'$A$.

Aquest mètode té millor estabilitat numèrica que el mètode de Gram–Schmidt que hem vist abans.

La següent taula mostra el nombre d'operacions en el pas k-sim de la descomposició QR per transformacions de Householder, suposant una matriu quadrada de dimensió n.

Operació	Nombre d'operacions en el pas k-sim
multiplicacions	$2(n-k+1{)}^2$
sumes	$(n-k+1{)}^2+(n-k+1)(n-k)+2$
divisions	$1$
arrels quadrades	$1$

Sumant aquests nombres pels $(n-1)$ passos (per a una matriu quadrada de dimensió n), la complexitat de l'algorisme (en termes de multiplicacions en coma flotant) ve donada per

$\frac{2}{3}{n}^3+n^2+\frac{1}{3}n-2=O(n^3).$

Exemple

Calculem la descomposició de

$A=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right).$

Primer, hem de trobar una reflexió que transformi la primera columna d'A, el vector ${𝐚}_1=(12,6,-4{)}^T$, en $\Vert {𝐚}_1\Vert {\mathrm{e}}_1=(14,0,0{)}^T.$

Ara,

$𝐮=𝐱+\alpha {𝐞}_1,$

i

$𝐯=\frac{𝐮}{\Vert 𝐮\Vert }.$

Aquí,

$\alpha =-14$ i $𝐱={𝐚}_1=(12,6,-4{)}^T$

Per tant,

$𝐮=(-2,6,-4{)}^T=(2)(-1,3,-2{)}^T$ i $𝐯=\frac{1}{\sqrt{14}}(-1,3,-2{)}^T$, i llavors

$Q_1=I-\frac{2}{\sqrt{14}\sqrt{14}}\left(\begin{array}{c}-1\\ 3\\ -2\end{array}\right)\left(\begin{array}{ccc}-1& 3& -2\end{array}\right)$

$=I-\frac{1}{7}\left(\begin{array}{ccc}1& -3& 2\\ -3& 9& -6\\ 2& -6& 4\end{array}\right)$

$=\left(\begin{array}{ccc}6/7& 3/7& -2/7\\ 3/7& -2/7& 6/7\\ -2/7& 6/7& 3/7\end{array}\right).$

Notem ara que:

$Q_{1}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& -49& -14\\ 0& 168& -77\end{array}\right),$

de tal manera que tenim gairebé una matriu triangular. Només hem de posar a zero l'entrada (3, 2).

Prenem el menor (1, 1), i apliquem de nou el procés per

$A^{\prime }=M_{11}=\left(\begin{array}{cc}-49& -14\\ 168& -77\end{array}\right).$

Pel mateix mètode que hem vist abans, obtenim la matriu de la transformació de Householder

$Q_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& 7/25& -24/25\\ 0& -24/25& -7/25\end{array}\right)$

després de realitzar una suma directa amb 1 per assegurar que el següent pas del procés funciona correctament.

Trobem

$Q=Q_1^T{Q}_2^T=\left(\begin{array}{ccc}6/7& 69/175& -58/175\\ 3/7& -158/175& 6/175\\ -2/7& -6/35& -33/35\end{array}\right)$

Llavors

$Q=Q_1^T{Q}_2^T=\left(\begin{array}{ccc}0,8571& 0,3943& -0,3314\\ 0,4286& -0,9029& 0,0343\\ -0,2857& -0,1714& -0,9429\end{array}\right)$

$R=Q_2{Q}_{1}A=Q^{T}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& -175& 70\\ 0& 0& 35\end{array}\right).$

La matriu Q és ortogonal, i R és triangular superior; per tant, A = QR és la descomposició QR que volíem.

Ús de rotacions de Givens

Hom pot calcular també una descomposició QR mitjançant rotacions de Givens. Cada rotació fa que un element de la subdiagonal de la matriu quedi a zero, formant així la matriu R. La concatenació de totes les rotacions de Givens forma la matriu ortogonal Q.

A la pràctica, per calcular les rotacions de Givens no es construeix la matriu sencera i es realitza una multiplicació de matrius. En comptes d'això, hom utilitza un procediment que realitza l'equivalent de la multiplicació per les matrius disperses de Givens, sense la feina addicional de tenir en compte els elements dispersos. El procediment de les rotacions de Givens és útil en situacions en què només un nombre relativament petit d'elements han d'esdevinir 0, i es pot paral·lelitzar de forma més senzilla que les transformacions de Householder.

Exemple

Calculem la descomposició de

$A=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right).$

Primer, necessitem construir una matriu de rotació que posi a zero l'element de l'extrem inferior esquerre, ${𝐚}_{31}=-4$. Construïm aquesta matriu usant el mètode de rotació de Givens, i l'anomenem matriu $G_1$. Primer rotem el vector $(6,-4)$, perquè estigui alineat amb l'eix de les X. Aquest vector té un angle $\theta =\arctan \left(\frac{-(-4)}{6}\right)$. Construïm ara la matriu de rotació ortogonal de Givens, $G_1$:

$G_1=\left(\begin{array}{ccc}1& 0& 0\\ 0& \cos (\theta )& -\sin (\theta )\\ 0& \sin (\theta )& \cos (\theta )\end{array}\right)$

$\approx \left(\begin{array}{ccc}1& 0& 0\\ 0& 0,83205& -0,55470\\ 0& 0,55470& 0,83205\end{array}\right)$

I el resultat de $G_{1}A$ té ara un zero a l'entrada ${𝐚}_{31}$.

$G_{1}A\approx \left(\begin{array}{ccc}12& -51& 4\\ 7,21110& 125,6396& -33,83671\\ 0& 112,6041& -71,83368\end{array}\right)$

De forma semblant, podem crear matrius de Givens $G_2$ i $G_3$, que anul·len els elements de la subdiagonal $a_{21}$ i $a_{32}$, i formant així una matriu triangular $R$. La matriu ortogonal $Q^T$ està formada per la concatenació de totes les matrius de Givens $Q^T=G_3{G}_2{G}_1$. Així, tenim $G_3{G}_2{G}_{1}A=Q^{T}A=R$, i la descomposició QR és $A=QR$.

Relació amb el determinant i el producte dels valors propis

Podem usar la descomposició QR per trobar el valor absolut del determinant d'una matriu quadrada. Suposem que una matriu A es descompon com a $A=QR$. Aleshores tenim

$\det (A)=\det (Q)\cdot \det (R).$

Com que Q és unitària, $|\det (Q)|=1$. Per tant,

$|\det (A)|=|\det (R)|=\left|\prod _i{r}_{ii}\right|,$

on $r_{ii}$ són les entrades de la diagonal de R.

Addicionalment, com que el determinant és igual al producte dels valors propis, tenim

$\left|\prod _i{r}_{ii}\right|=\left|\prod _i{\lambda }_i\right|,$

on ${\lambda }_i$ són els valors propis d'$A$.

Podem estendre les propietats anteriors a matrius complexes no quadrades $A$, tot substituint el concepte «valor propi» per «valor singular».

Suposem que tenim una descomposició QR per una matriu no quadrada A:

$A=Q\left(\begin{array}{c}R\\ \mathrm{𝟎}\end{array}\right),Q^{*}Q=I,$

on $\mathrm{𝟎}$ és una matriu nul·la i $Q$ és una matriu unitària.

A partir de les propietats de la descomposició en valors singulars i del determinant d'una matriu, tenim

$\left|\prod _i{r}_{ii}\right|=\prod _i{\sigma }_i,$

on ${\sigma }_i$ són els valors singulars d'$A$.

Notem que els valors singulars d'$A$ i $R$ són idèntics, encara que els valors propis complexos poden ser diferents. Tot i això, si A és quadrada, es compleix que

$\prod _i{\sigma }_i=\left|\prod _i{\lambda }_i\right|.$

És a dir, la descomposició QR es pot usar de forma eficient per calcular el producte dels valors propis o els valors singulars d'una matriu.

Ús de pivot per columnes

La descomposició QR amb pivots per columnes introdueix una matriu permutació P:

$AP=QR$ o, equivalentment, $A=QR{P}^T$

El pivot per columnes és útil quan A té rang deficient (o gairebé deficient), o bé quan hom sospita que pot ser-ho. També pot millorar la precisió numèrica. Habitualment s'escull la matriu P de tal manera que els elements de la diagonal de R siguin no-creixents: $|r_{11}|\ge |r_{22}|\ge \dots \ge |r_{nn}|$. Aquest mètode es pot usar per trobar el rang (numèric) d'A amb un cost computacional menor que el d'una descomposició en valors singulars; de fet, aquesta és la base dels anomenats algorismes QR reveladors del rang.

Resolució de problemes de la inversa lineal

En comparació al càlcul directe de la inversa d'una matriu, les solucions per la inversa que utilitzen la descomposició QR són numèricament més estables, atès que tenen un nombre de condició més reduït [Parker, Geophysical Inverse Theory, Ch1.13].

Per resoldre el sistema d'equacions lineals subdeterminat ($m<n$) $Ax=b$ on la matriu A té dimensions $m\times n$ i rang $m$, primer trobem la descomposició QR de la transposada d'A: $A^T=QR$, on Q és una matriu ortogonal (és a dir, $Q^T=Q^{-1}$), i R té una forma especial: $R=\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]$. Aquí, $R_1$ és una matriu triangular superior quadrada $m\times m$, i la matriu nul·la té dimensió $(n-m)\times m$. Després d'alguns càlculs, hom pot demostrar que una solució al problema de la matriu inversa es pot expressar com:

$x=Q\left[\begin{array}{c}(R_1^T{)}^{-1}b\\ 0\end{array}\right]$

on, per trobar $R_1^{-1}$ es pot fer servir el mètode de reducció de Gauss o bé calcular directament $(R_1^T{)}^{-1}b$ per substitucions endavant. Aquesta última tècnica té major precisió numèrica i necessita menys càlculs.

Per trobar una solució, $\hat{x}$, al sistema sobredeterminat ($m\ge n$) $Ax=b$ que minimitzi la norma $\Vert A\hat{x}-b\Vert$, trobem primer la descomposició QR d'A: $A=QR$. Ara, hom pot expressar la solució com $\hat{x}=R_1^{-1}(Q_1^{T}b)$, on $Q_1$ és una matriu $m\times n$ que conté les primeres $n$ columnes de la base ortonormal completa $Q$, i on $R_1$ és com abans. De la mateixa manera que en el cas subdeterminat, hom pot fer servir substitucions enrere per calcular aquest $\hat{x}$ sense haver d'invertir $R_1$ de forma explícita.

Vegeu també

• Descomposició polar
• Descomposició en valors propis
• Descomposició espectral
• Descomposició de matrius

Bibliografia

• Plantilla:Ref-llibre
• Plantilla:Ref-llibre
• Plantilla:Ref-llibre Plantilla:Webarchive
• Plantilla:Ref-llibre

Enllaços externs

• LAPACK users manual proporciona detalls de subrutines per calcular la descomposició QR
• ALGLIB inclou un port parcial de LAPACK a C++, C#, Delphi, etc.
• Eigen::QR Inclou una implementació en C++ de la descomposició QR