QR-faktorisering

Inom linjär algebra är QR-faktorisering en matrisfaktorisering av en (reell) matris i en ortogonal matris och en triangulär matris.

Definition

En QR-faktorisering av en reell kvadratisk matris $A$ kan uttryckas:

$A=QR$

För en ortogonal matris $Q$ och en övertriangulär matris $R$. Om $A$ istället är komplex är $Q$ en unitär matris.

Detta kan generaliseras till att $A$ är en matris av format $m\times n$ där $m\geq n$, då $Q$ är en ortogonal (unitär) matris med format $m\times n$ och $R$ är en övertriangulär matris med format $n\times n$.

Beräkning

Det finns flera sätt att beräkna QR-faktoriseringen av en matris. Det vanligaste sättet är genom Gram-Schmidts ortogonaliseringsprocess.

Genom Gram-Schmidt

Om matrisen $A$ har kolonnvektorerna $\mathbf {u_{1}} ,\mathbf {u_{2}} ,...\mathbf {u_{n}}$ som är linjärt oberoende, kan man genom Gram-Schmidts ortogonaliseringsprocess bestämma vektorer $\mathbf {v_{1}} ,\mathbf {v_{2}} ,...\mathbf {v_{n}}$ som är ortogonala. De gamla $\mathbf {u}$-vektorerna kan nu skrivas som linjärkombinationer av de nya $\mathbf {v}$-vektorerna:

$\mathbf {u_{1}} =r_{11}\mathbf {v_{1}}$

$\mathbf {u_{2}} =r_{12}\mathbf {v_{1}} +r_{22}\mathbf {v_{2}}$

$...$

$\mathbf {u_{n}} =r_{1n}\mathbf {v_{1}} +...+r_{nn}\mathbf {v_{n}}$

Om vi nu placerar våra $r$-värden i en matris, $R$, och de ortogonala vektorerna i en annan matris, $Q$, kan vi uttrycka den gamla matrisen $A$ som produkten av dessa:

$A=QR={\begin{pmatrix}&&&\\\mathbf {v_{1}} &\mathbf {v_{2}} &\ldots &\mathbf {v_{n}} \\&&&\end{pmatrix}}{\begin{pmatrix}r_{11}&r_{12}&\ldots &r_{1n}\\0&r_{22}&\ldots &r_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\ldots &r_{nn}\end{pmatrix}}$

Då $\mathbf {v}$-vektorerna är ortogonala är $Q$ ortogonal (unitär om vektorerna är komplexa).

För att få $r$-värdena kan man lösa dem ur ortogonaliseringsprocessen man gör, eller så använder man sig av faktumet att:

$R=IR=Q^{H}QR=Q^{H}A\,$

Så att $R$ kan beräknas genom en enkel matrismultiplikation ($Q^{H}$ står för det hermiteska konjugatet till $Q$, som i det reella fallet är samma sak som transponat).

Med Householderreflektioner

En Householdertransformation är en linjär avbildning som reflekterar en vektor i ett hyperplan. Detta kan användas till att QR-faktorisera en matris. Denna metod är numeriskt stabilare än Gram-Schmidt-metoden och har en tidskomplexitet på $O(n^{3})$.

För beräkningen tas speciella Householdertransformationer fram. Man utgår från en vektor $\mathbf {x}$ och tar ett tal a så att $\|\mathbf {x} \|=|a|$. Om QR-faktoriseringen görs med flyttalsberäkningar och vektorn är reell bör a väljas med motsatt tecken från första elementet i vektorn $\mathbf {x}$, om vektorn är komplex bör a väljas genom:

$a=-\|x\|e^{i\arg x_{1}}.$

Sedan konstrueras Householdertransformationen Q på följande sätt ($\mathbf {e} _{1}$ är vektorn $(1,0,...,0)^{T}$):

$\mathbf {u} =\mathbf {x} -a\mathbf {e} _{1}$

$\mathbf {v} ={\frac {\mathbf {u} }{\|\mathbf {u} \|}}$

$Q=I-2\mathbf {vv} ^{H}.$

För att QR-faktorisera m×n-matrisen A, konstruerar man en Householdertransformation Q₁ enligt ovan från första kolonnen i A. Man får då

$Q_{1}A={\begin{pmatrix}a_{1}&c_{12}&\ldots &c_{1m}\\0\\\vdots &&A'\\0\end{pmatrix}}$

Man kan sedan konstruera en ny Householdertransformation $Q_{2}'$ från första kolonnen i $A'$ ($A'$ fås genom att plocka bort första kolonnen och första raden i $Q_{1}A$). Eftersom man vill verka på matrisen $Q_{1}A$ och inte $A'$ så tar man matrisen $Q_{2}'$ och fyller ut den. För ett generellt steg i QR-faktoriseringen får man matrisen:

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

Vid multiplikation med Q₂ fås alltså en matris $Q_{2}Q_{1}A$ som är lika stor som A. Ur denna matris läser man ut $A''$ som är två steg mindre än A, tar den första kolonnen och konstruerar $Q_{3}'$ varur man konstruerar Q₃ enligt ovan.

Sedan upprepas detta $k=\min(m-1,n)$ steg, då man fått

$R=Q_{k}Q_{k-1}...Q_{1}A$

där R är övertriangulär och

$Q=Q_{1}Q_{2}...Q_{k}$

är en unitär matris (eftersom Householdertransformationer är unitära). Alltså är $A=QR$ en QR-faktorisering av A.

Tillämpningar

Minsta kvadrat-lösningar

Om man ska hitta minsta kvadrat-lösningen till ett ekvationssystem givet av ekvationen $A\mathbf {x} =\mathbf {b}$ förenklas detta om $A$ är QR-faktoriserad. Lösningen ges i vanliga fall av

$A^{H}A\mathbf {x} =A^{H}\mathbf {b}$

Om $A=QR$ ger vänsterledet

$A^{H}A\mathbf {x} =(QR)^{H}QR\mathbf {x} =R^{H}Q^{H}QR\mathbf {x} =R^{H}R\mathbf {x}$

och högerledet

$A^{H}\mathbf {b} =(QR)^{H}\mathbf {b} =R^{H}Q^{H}\mathbf {b}$

så att ekvationen blir

$R^{H}R\mathbf {x} =R^{H}Q^{H}\mathbf {b} \Rightarrow R\mathbf {x} =Q^{H}\mathbf {b}$

som är ett väldigt lättlöst ekvationsysstem eftersom $R$ är triangulär.

Determinanter, egenvärden och singulärvärden

Om A är en kvadratisk matris av storlek n som är QR-faktoriserad, $A=QR$, då det ur räknelagarna för determinanten att

$\det A=\det Q\det R.\,$

Eftersom Q är unitär är $|\det Q|=1$, vilket ger:

$|\det A|=|\det R|=\left|\prod _{i}^{n}r_{ii}\right|$

där $r_{ii}$ är värdena i R:s diagonal. Då man även vet att determinanten av A är produkten av A:s egenvärden följer det att

$\left|\prod _{i=1}^{n}\lambda _{i}\right|=\left|\prod _{i=1}^{n}r_{ii}\right|$

där $\lambda _{i}$ är A:s egenvärden.

Man kan generalisera resonemanget ovan till att gälla matriser A som inte är kvadratiska, då man från egenskaper hos singulärvärdesfaktoriseringen får att:

$\prod _{i}\sigma _{i}=\left|\prod _{i}r_{ii}\right|$

där $\sigma _{i}$ är A:s singulärvärden.

Se även

• Matrisfaktorisering