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\ge 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 ${𝐮}_{\mathrm{𝟏}},{𝐮}_{\mathrm{𝟐}},...{𝐮}_{𝐧}$ som är linjärt oberoende, kan man genom Gram-Schmidts ortogonaliseringsprocess bestämma vektorer ${𝐯}_{\mathrm{𝟏}},{𝐯}_{\mathrm{𝟐}},...{𝐯}_{𝐧}$ som är ortogonala. De gamla $𝐮$-vektorerna kan nu skrivas som linjärkombinationer av de nya $𝐯$-vektorerna:

${𝐮}_{\mathrm{𝟏}}=r_{11}{𝐯}_{\mathrm{𝟏}}$

${𝐮}_{\mathrm{𝟐}}=r_{12}{𝐯}_{\mathrm{𝟏}}+r_{22}{𝐯}_{\mathrm{𝟐}}$

$...$

${𝐮}_{𝐧}=r_{1n}{𝐯}_{\mathrm{𝟏}}+...+r_{nn}{𝐯}_{𝐧}$

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=\left(\begin{array}{cccc}& & & \\ {𝐯}_{\mathrm{𝟏}}& {𝐯}_{\mathrm{𝟐}}& \dots & {𝐯}_{𝐧}\\ & & & \end{array}\right)\left(\begin{array}{cccc}{r}_{11}& r_{12}& \dots & r_{1n}\\ 0& r_{22}& \dots & r_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & r_{nn}\end{array}\right)$

Då $𝐯$-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 $𝐱$ och tar ett tal a så att $\Vert 𝐱\Vert =|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 $𝐱$, om vektorn är komplex bör a väljas genom:

$a=-\Vert x\Vert e^{i\arg x_1}.$

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

$𝐮=𝐱-a{𝐞}_1$

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

$Q=I-2{𝐯𝐯}^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=\left(\begin{array}{cccc}{a}_1& c_{12}& \dots & c_{1m}\\ 0\\ ⋮& & A^{\prime }\\ 0\end{array}\right)$

Man kan sedan konstruera en ny Householdertransformation ${Q_2}^{\prime }$ från första kolonnen i $A^{\prime }$ ($A^{\prime }$ 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^{\prime }$ så tar man matrisen ${Q_2}^{\prime }$ och fyller ut den. För ett generellt steg i QR-faktoriseringen får man matrisen:

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

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}^{\prime }$ 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𝐱=𝐛$ förenklas detta om $A$ är QR-faktoriserad. Lösningen ges i vanliga fall av

$A^{H}A𝐱=A^H𝐛$

Om $A=QR$ ger vänsterledet

$A^{H}A𝐱=(QR{)}^{H}QR𝐱=R^H{Q}^{H}QR𝐱=R^{H}R𝐱$

och högerledet

$A^H𝐛=(QR{)}^H𝐛=R^H{Q}^H𝐛$

så att ekvationen blir

$R^{H}R𝐱=R^H{Q}^H𝐛\Rightarrow R𝐱=Q^H𝐛$

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

Mall:Linjär-algebra