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.^[1] 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.^[1]

Definicions

Matrius quadrades

Qualsevol matriu real quadrada A es pot descompondre com a

${\displaystyle 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:

${\displaystyle A=QR=Q{\begin{bmatrix}R_{1}\\0\end{bmatrix}}={\begin{bmatrix}Q_{1},Q_{2}\end{bmatrix}}{\begin{bmatrix}R_{1}\\0\end{bmatrix}}=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.

Golub & Van Loan (1996, §5.2) anomenen Q₁R₁ la factorització QR aprimada d'A; per la seva banda, Trefethen & Bau l'anomenen factorització QR reduïda.^[1]

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 ${\displaystyle A=[\mathbf {a} _{1},\cdots ,\mathbf {a} _{n}]}$, amb el producte escalar ${\displaystyle <\mathbf {v} ,\mathbf {w} >=\mathbf {v} ^{T}\mathbf {w} }$ (o ${\displaystyle <\mathbf {v} ,\mathbf {w} >=\mathbf {v} ^{*}\mathbf {w} }$ pel cas complex).

Definim la projecció

${\displaystyle \mathrm {proj} _{\mathbf {e} }\mathbf {a} ={\frac {<\mathbf {e} ,\mathbf {a} >}{<\mathbf {e} ,\mathbf {e} >}}\mathbf {e} .}$

Llavors:

${\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {a} _{1},&\mathbf {e} _{1}&={\mathbf {u} _{1} \over \|\mathbf {u} _{1}\|}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\mathrm {proj} _{\mathbf {e} _{1}}\,\mathbf {a} _{2},&\mathbf {e} _{2}&={\mathbf {u} _{2} \over \|\mathbf {u} _{2}\|}\\\mathbf {u} _{3}&=\mathbf {a} _{3}-\mathrm {proj} _{\mathbf {e} _{1}}\,\mathbf {a} _{3}-\mathrm {proj} _{\mathbf {e} _{2}}\,\mathbf {a} _{3},&\mathbf {e} _{3}&={\mathbf {u} _{3} \over \|\mathbf {u} _{3}\|}\\&\vdots &&\vdots \\\mathbf {u} _{k}&=\mathbf {a} _{k}-\sum _{j=1}^{k-1}\mathrm {proj} _{\mathbf {e} _{j}}\,\mathbf {a} _{k},&\mathbf {e} _{k}&={\mathbf {u} _{k} \over \|\mathbf {u} _{k}\|}\end{aligned}}}$

Reescrivim ara les equacions anteriors de tal manera que els termes ${\displaystyle \mathbf {a} _{i}}$ apareguin a l'esquerra, emprant el fet que els vectors ${\displaystyle \mathbf {e} _{i}}$ són unitaris:

${\displaystyle {\begin{aligned}\mathbf {a} _{1}&=<\mathbf {e} _{1},\mathbf {a} _{1}>\mathbf {e} _{1}\\\mathbf {a} _{2}&=<\mathbf {e} _{1},\mathbf {a} _{2}>\mathbf {e} _{1}+<\mathbf {e} _{2},\mathbf {a} _{2}>\mathbf {e} _{2}\\\mathbf {a} _{3}&=<\mathbf {e} _{1},\mathbf {a} _{3}>\mathbf {e} _{1}+<\mathbf {e} _{2},\mathbf {a} _{3}>\mathbf {e} _{2}+<\mathbf {e} _{3},\mathbf {a} _{3}>\mathbf {e} _{3}\\&\vdots \\\mathbf {a} _{k}&=\sum _{j=1}^{k}<\mathbf {e} _{j},\mathbf {a} _{k}>\mathbf {e} _{j}\end{aligned}}}$

on ${\displaystyle <\mathbf {e} _{i},\mathbf {a} _{i}>=\|\mathbf {u} _{i}\|}$. Això es pot escriure en forma matricial:

${\displaystyle A=QR}$

on:

${\displaystyle Q=\left[\mathbf {e} _{1},\cdots ,\mathbf {e} _{n}\right]\qquad {\text{i}}\qquad R={\begin{pmatrix}<\mathbf {e} _{1},\mathbf {a} _{1}>&<\mathbf {e} _{1},\mathbf {a} _{2}>&<\mathbf {e} _{1},\mathbf {a} _{3}>&\ldots \\0&<\mathbf {e} _{2},\mathbf {a} _{2}>&<\mathbf {e} _{2},\mathbf {a} _{3}>&\ldots \\0&0&<\mathbf {e} _{3},\mathbf {a} _{3}>&\ldots \\\vdots &\vdots &\vdots &\ddots \end{pmatrix}}.}$

Exemple

Considerem la descomposició de

${\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}.}$

Recordem que una matriu ortogonal ${\displaystyle Q}$ té la propietat

${\displaystyle {\begin{matrix}Q^{T}\,Q=I.\end{matrix}}}$

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

${\displaystyle U={\begin{pmatrix}\mathbf {u} _{1}&\mathbf {u} _{2}&\mathbf {u} _{3}\end{pmatrix}}={\begin{pmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{pmatrix}};}$

${\displaystyle Q={\begin{pmatrix}{\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}&{\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}&{\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\end{pmatrix}}={\begin{pmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{pmatrix}}.}$

Així, tenim

${\displaystyle {\begin{matrix}Q^{T}A=Q^{T}Q\,R=R;\end{matrix}}}$

${\displaystyle {\begin{matrix}R=Q^{T}A=\end{matrix}}{\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}.}$

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

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 ${\displaystyle 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 ${\displaystyle \mathbf {x} }$ un vector columna real qualsevol de dimensió m d'${\displaystyle A}$ tal que ||${\displaystyle \mathbf {x} }$|| = |α| 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 ${\displaystyle \mathbf {x} }$, on ${\displaystyle x_{k}}$ és la coordenada «pivot»; és a dir, totes les altres coordenades de ${\displaystyle \mathbf {x} }$ seran 0 en la forma triangular superior final d'A, sense pèrdua de dígits significatius. En el cas complex, establim

${\displaystyle \alpha =-\mathrm {e} ^{\mathrm {i} \arg x_{k}}\|\mathbf {x} \|}$

(Stoer & Bulirsch 2002, p. 225) i substituïm la transposició per la transposició conjugada en la construcció de Q que ara veurem.

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

${\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},}$

${\displaystyle \mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|},}$

${\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{T}.}$

O, si ${\displaystyle A}$ és complexa,

${\displaystyle Q=I-(1+w)\mathbf {v} \mathbf {v} ^{H}}$, amb ${\displaystyle w=\mathbf {x} ^{H}\mathbf {v} \mathbf {/} \mathbf {v} ^{H}\mathbf {x} }$

on ${\displaystyle \mathbf {x} ^{H}}$ és la transposada conjugada de ${\displaystyle \mathbf {x} }$.

Ara, ${\displaystyle Q}$ és una matriu m×m de Householder i

${\displaystyle Q\mathbf {x} =(\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).

${\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\vline &\star &\dots &\star \\\hline 0&\vline &&&\\\vdots &\vline &&A'&\\0&\vline &&&\end{bmatrix}}}$

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:

${\displaystyle Q_{k}={\begin{pmatrix}I_{k-1}&0\\0&Q_{k}'\end{pmatrix}}.}$

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

${\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A}$

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

${\displaystyle Q=Q_{1}^{T}Q_{2}^{T}\cdots Q_{t}^{T},}$

tenim que ${\displaystyle A=QR}$ és una descomposició QR d'${\displaystyle 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	${\displaystyle 2(n-k+1)^{2}}$
sumes	${\displaystyle (n-k+1)^{2}+(n-k+1)(n-k)+2}$
divisions	${\displaystyle 1}$
arrels quadrades	${\displaystyle 1}$

Sumant aquests nombres pels ${\displaystyle (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

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

Exemple

Calculem la descomposició de

${\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}.}$

Primer, hem de trobar una reflexió que transformi la primera columna d'A, el vector ${\displaystyle \mathbf {a} _{1}=(12,6,-4)^{T}}$, en ${\displaystyle \|\mathbf {a} _{1}\|\;\mathrm {e} _{1}=(14,0,0)^{T}.}$

Ara,

${\displaystyle \mathbf {u} =\mathbf {x} +\alpha \mathbf {e} _{1},}$

i

${\displaystyle \mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|}.}$

Aquí,

${\displaystyle \alpha =-14}$ i ${\displaystyle \mathbf {x} =\mathbf {a} _{1}=(12,6,-4)^{T}}$

Per tant,

${\displaystyle \mathbf {u} =(-2,6,-4)^{T}=({2})(-1,3,-2)^{T}}$ i ${\displaystyle \mathbf {v} ={1 \over {\sqrt {14}}}(-1,3,-2)^{T}}$, i llavors

${\displaystyle Q_{1}=I-{2 \over {\sqrt {14}}{\sqrt {14}}}{\begin{pmatrix}-1\\3\\-2\end{pmatrix}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}}$

${\displaystyle =I-{1 \over 7}{\begin{pmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{pmatrix}}}$

${\displaystyle ={\begin{pmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{pmatrix}}.}$

Notem ara que:

${\displaystyle Q_{1}A={\begin{pmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{pmatrix}},}$

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

${\displaystyle A'=M_{11}={\begin{pmatrix}-49&-14\\168&-77\end{pmatrix}}.}$

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

${\displaystyle Q_{2}={\begin{pmatrix}1&0&0\\0&7/25&-24/25\\0&-24/25&-7/25\end{pmatrix}}}$

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

Trobem

${\displaystyle Q=Q_{1}^{T}Q_{2}^{T}={\begin{pmatrix}6/7&69/175&-58/175\\3/7&-158/175&6/175\\-2/7&-6/35&-33/35\end{pmatrix}}}$

Llavors

${\displaystyle Q=Q_{1}^{T}Q_{2}^{T}={\begin{pmatrix}0,8571&0,3943&-0,3314\\0,4286&-0,9029&0,0343\\-0,2857&-0,1714&-0,9429\end{pmatrix}}}$

${\displaystyle R=Q_{2}Q_{1}A=Q^{T}A={\begin{pmatrix}14&21&-14\\0&-175&70\\0&0&35\end{pmatrix}}.}$

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

${\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}.}$

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

${\displaystyle G_{1}={\begin{pmatrix}1&0&0\\0&\cos(\theta )&-\sin(\theta )\\0&\sin(\theta )&\cos(\theta )\end{pmatrix}}}$

${\displaystyle \approx {\begin{pmatrix}1&0&0\\0&0,83205&-0,55470\\0&0,55470&0,83205\end{pmatrix}}}$

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

${\displaystyle G_{1}A\approx {\begin{pmatrix}12&-51&4\\7,21110&125,6396&-33,83671\\0&112,6041&-71,83368\end{pmatrix}}}$

De forma semblant, podem crear matrius de Givens ${\displaystyle G_{2}}$ i ${\displaystyle G_{3}}$, que anul·len els elements de la subdiagonal ${\displaystyle a_{21}}$ i ${\displaystyle a_{32}}$, i formant així una matriu triangular ${\displaystyle R}$. La matriu ortogonal ${\displaystyle Q^{T}}$ està formada per la concatenació de totes les matrius de Givens ${\displaystyle Q^{T}=G_{3}G_{2}G_{1}}$. Així, tenim ${\displaystyle G_{3}G_{2}G_{1}A=Q^{T}A=R}$, i la descomposició QR és ${\displaystyle 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 ${\displaystyle A=QR}$. Aleshores tenim

${\displaystyle \det(A)=\det(Q)\cdot \det(R).}$

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

${\displaystyle |\det(A)|=|\det(R)|={\Big |}\prod _{i}r_{ii}{\Big |},}$

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

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

${\displaystyle {\Big |}\prod _{i}r_{ii}{\Big |}={\Big |}\prod _{i}\lambda _{i}{\Big |},}$

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

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

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

${\displaystyle A=Q{\begin{pmatrix}R\\\mathbf {0} \end{pmatrix}},\qquad Q^{*}Q=I,}$

on ${\displaystyle \mathbf {0} }$ és una matriu nul·la i ${\displaystyle Q}$ és una matriu unitària.

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

${\displaystyle {\Big |}\prod _{i}r_{ii}{\Big |}=\prod _{i}\sigma _{i},}$

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

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

${\displaystyle {\prod _{i}\sigma _{i}}={\Big |}{\prod _{i}\lambda _{i}}{\Big |}.}$

É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:

${\displaystyle AP=QR}$ o, equivalentment, ${\displaystyle A=QRP^{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: ${\displaystyle |r_{11}|\geq |r_{22}|\geq \ldots \geq |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 (${\displaystyle m<n}$) ${\displaystyle Ax=b}$ on la matriu A té dimensions ${\displaystyle m\times n}$ i rang ${\displaystyle m}$, primer trobem la descomposició QR de la transposada d'A: ${\displaystyle A^{T}=QR}$, on Q és una matriu ortogonal (és a dir, ${\displaystyle Q^{T}=Q^{-1}}$), i R té una forma especial: ${\displaystyle R={\begin{bmatrix}R_{1}\\0\end{bmatrix}}}$. Aquí, ${\displaystyle R_{1}}$ és una matriu triangular superior quadrada ${\displaystyle m\times m}$, i la matriu nul·la té dimensió ${\displaystyle (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:

${\displaystyle x=Q{\begin{bmatrix}(R_{1}^{T})^{-1}b\\0\end{bmatrix}}}$

on, per trobar ${\displaystyle R_{1}^{-1}}$ es pot fer servir el mètode de reducció de Gauss o bé calcular directament ${\displaystyle (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ó, ${\displaystyle {\hat {x}}}$, al sistema sobredeterminat (${\displaystyle m\geq n}$) ${\displaystyle Ax=b}$ que minimitzi la norma ${\displaystyle \|A{\hat {x}}-b\|}$, trobem primer la descomposició QR d'A: ${\displaystyle A=QR}$. Ara, hom pot expressar la solució com ${\displaystyle {\hat {x}}=R_{1}^{-1}(Q_{1}^{T}b)}$, on ${\displaystyle Q_{1}}$ és una matriu ${\displaystyle m\times n}$ que conté les primeres ${\displaystyle n}$ columnes de la base ortonormal completa ${\displaystyle Q}$, i on ${\displaystyle R_{1}}$ és com abans. De la mateixa manera que en el cas subdeterminat, hom pot fer servir substitucions enrere per calcular aquest ${\displaystyle {\hat {x}}}$ sense haver d'invertir ${\displaystyle R_{1}}$ de forma explícita.

Referències

Vegeu també

• Descomposició polar
• Descomposició en valors propis
• Descomposició espectral
• Descomposició de matrius
• Producte de Zappa–Szép

Bibliografia

• Golub, Gene H.; Van Loan, Charles F. Matrix computations. 3. ed.. Baltimore, Md. [u.a.]: Johns Hopkins Univ. Press, 1996. ISBN 978-0-8018-5414-9. 
• Johnson, Roger A. Horn; Charles R.. «Secció 2.8». A: Matrix analysis. 19. print.. Cambridge [u.a.]: Cambridge Univ. Press, 2005. ISBN 0-521-38632-2. 
• al.], William H. Press ... [et. «Secció 2.10.». A: Numerical recipes : the art of scientific computing. 3rd ed.. Cambridge, UK: Cambridge University Press, 2007. ISBN 978-0-521-88068-8.  Arxivat 2012-03-19 a Wayback Machine.
• Stoer, Josef; Bartels, R. Bulirsch; translated by R.; Gautschi,, W.; Witzgall, C.. Introduction to numerical analysis. 3rd ed.. Nova York: Springer, 2002. ISBN 0-387-95452-X. 

Enllaços externs

• Online Matrix Calculator Arxivat 2008-12-12 a Wayback Machine. Calcula la descomposició QR de matrius
• LAPACK users manual proporciona detalls de subrutines per calcular la descomposició QR
• Mathematica users manual Arxivat 2006-11-22 a Wayback Machine. proporciona detalls i exemples de rutines 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
• Into Arxivat 2010-07-09 a Wayback Machine. conté una implementació de codi obert en C++ per la descomposició QR