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 ${\displaystyle A}$ kan uttryckas:

${\displaystyle A=QR}$

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

Detta kan generaliseras till att ${\displaystyle A}$ är en matris av format ${\displaystyle m\times n}$ där ${\displaystyle m\geq n}$, då ${\displaystyle Q}$ är en ortogonal (unitär) matris med format ${\displaystyle m\times n}$ och ${\displaystyle R}$ är en övertriangulär matris med format ${\displaystyle 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 ${\displaystyle A}$ har kolonnvektorerna ${\displaystyle \mathbf {u_{1}} ,\mathbf {u_{2}} ,...\mathbf {u_{n}} }$ som är linjärt oberoende, kan man genom Gram-Schmidts ortogonaliseringsprocess bestämma vektorer ${\displaystyle \mathbf {v_{1}} ,\mathbf {v_{2}} ,...\mathbf {v_{n}} }$ som är ortogonala. De gamla ${\displaystyle \mathbf {u} }$-vektorerna kan nu skrivas som linjärkombinationer av de nya ${\displaystyle \mathbf {v} }$-vektorerna:

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

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

${\displaystyle ...}$

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

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

${\displaystyle 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å ${\displaystyle \mathbf {v} }$-vektorerna är ortogonala är ${\displaystyle Q}$ ortogonal (unitär om vektorerna är komplexa).

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

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

Så att ${\displaystyle R}$ kan beräknas genom en enkel matrismultiplikation (${\displaystyle Q^{H}}$ står för det hermiteska konjugatet till ${\displaystyle 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å ${\displaystyle O(n^{3})}$.

För beräkningen tas speciella Householdertransformationer fram. Man utgår från en vektor ${\displaystyle \mathbf {x} }$ och tar ett tal a så att ${\displaystyle \|\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 ${\displaystyle \mathbf {x} }$, om vektorn är komplex bör a väljas genom:

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

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

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

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

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

${\displaystyle 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 ${\displaystyle Q_{2}'}$ från första kolonnen i ${\displaystyle A'}$ (${\displaystyle A'}$ fås genom att plocka bort första kolonnen och första raden i ${\displaystyle Q_{1}A}$). Eftersom man vill verka på matrisen ${\displaystyle Q_{1}A}$ och inte ${\displaystyle A'}$ så tar man matrisen ${\displaystyle Q_{2}'}$ och fyller ut den. För ett generellt steg i QR-faktoriseringen får man matrisen:

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

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

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

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

där R är övertriangulär och

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

är en unitär matris (eftersom Householdertransformationer är unitära). Alltså är ${\displaystyle 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 ${\displaystyle A\mathbf {x} =\mathbf {b} }$ förenklas detta om ${\displaystyle A}$ är QR-faktoriserad. Lösningen ges i vanliga fall av

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

Om ${\displaystyle A=QR}$ ger vänsterledet

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

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

så att ekvationen blir

${\displaystyle 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 ${\displaystyle R}$ är triangulär.

Determinanter, egenvärden och singulärvärden

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

${\displaystyle \det A=\det Q\det R.\,}$

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

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

där ${\displaystyle 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

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

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

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

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

Se även

• Matrisfaktorisering

Linjär algebra Grundläggande begrepp Skalär · Vektor · Noll · Ortogonalitet · Ekvationssystem · Rum · Linjärkombination · Inre produkt · Oberoende · Bas · Radrum · Kolonnrum · Nollrum · Gram-Schimdt · Egenvärde · Hölje · Linjäritet Vektoralgebra Kryssprodukt · Trippelprodukt Matriser Elementär · Block · Enhet · Determinant · Norm · Rang · Transformation · Rotation · Invers · Cramers regel · Trappstegsform · Spår · Transponat · Gausselimination · Symmetri · Addition Multilinjär algebra Geometrisk algebra · Yttre algebra · Bivektor · Multivektor · Tensor Konstruktioner Delrum · Dualrum · Funktionsrum · Kvotrum · Tensorprodukt Numerik Flyttal · Gles matris Kategori