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
kan uttryckas:
![{\displaystyle A=QR}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7d3eb7a53055abd0e9112408dbb2423035dfc72)
För en ortogonal matris
och en övertriangulär matris
. Om
istället är komplex är
en unitär matris.
Detta kan generaliseras till att
är en matris av format
där
, då
är en ortogonal (unitär) matris med format
och
är en övertriangulär matris med format
.
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
har kolonnvektorerna
som är linjärt oberoende, kan man genom Gram-Schmidts ortogonaliseringsprocess bestämma vektorer
som är ortogonala. De gamla
-vektorerna kan nu skrivas som linjärkombinationer av de nya
-vektorerna:
![{\displaystyle \mathbf {u_{1}} =r_{11}\mathbf {v_{1}} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee1c96cd2120b7f33554e5b25cf801cfc60f973e)
![{\displaystyle \mathbf {u_{2}} =r_{12}\mathbf {v_{1}} +r_{22}\mathbf {v_{2}} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ead3655af154ce6cb7eb89a19952306685daf075)
![{\displaystyle ...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d00f2f395950e3698a46501d1e9aae8e8defa145)
![{\displaystyle \mathbf {u_{n}} =r_{1n}\mathbf {v_{1}} +...+r_{nn}\mathbf {v_{n}} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c816d9c24ab8be0d1db16221e7b06ce4b7a1eeef)
Om vi nu placerar våra
-värden i en matris,
, och de ortogonala vektorerna i en annan matris,
, kan vi uttrycka den gamla matrisen
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9ee13c867dd4b2f27ec3d11f9b0dbf97e91b5fd)
Då
-vektorerna är ortogonala är
ortogonal (unitär om vektorerna är komplexa).
För att få
-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\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b7cf9b9e60b894e89cc6e330f9725ddda9cf714)
Så att
kan beräknas genom en enkel matrismultiplikation (
står för det hermiteska konjugatet till
, 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å
.
För beräkningen tas speciella Householdertransformationer fram. Man utgår från en vektor
och tar ett tal a så att
. 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:
![{\displaystyle a=-\|x\|e^{i\arg x_{1}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/250b9a60d03965db1ce520e209a2fbc26ce3d79f)
Sedan konstrueras Householdertransformationen Q på följande sätt (
är vektorn
):
![{\displaystyle \mathbf {u} =\mathbf {x} -a\mathbf {e} _{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40d4d71ad83af6e5124bcf1cc1d25964d8d62051)
![{\displaystyle \mathbf {v} ={\frac {\mathbf {u} }{\|\mathbf {u} \|}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09f364df81064ae964e1d9d4726324c14380fbd3)
![{\displaystyle Q=I-2\mathbf {vv} ^{H}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dd587c2a5a67a01d243a65017e115a22cde76c7)
För att QR-faktorisera m×n-matrisen A, konstruerar man en Householdertransformation Q1 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab1774c5f04341fdb80d3d8e35b19eb702018feb)
Man kan sedan konstruera en ny Householdertransformation
från första kolonnen i
(
fås genom att plocka bort första kolonnen och första raden i
). Eftersom man vill verka på matrisen
och inte
så tar man matrisen
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a0e113422fe790248e2440ba71103c83fc676f4)
Vid multiplikation med Q2 fås alltså en matris
som är lika stor som A. Ur denna matris läser man ut
som är två steg mindre än A, tar den första kolonnen och konstruerar
varur man konstruerar Q3 enligt ovan.
Sedan upprepas detta
steg, då man fått
![{\displaystyle R=Q_{k}Q_{k-1}...Q_{1}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/668518c7f605647a180f0b4f6321212cb544df94)
där R är övertriangulär och
![{\displaystyle Q=Q_{1}Q_{2}...Q_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b2c7dae111b9d1fe2648c6a487cf6d17f6a086c)
är en unitär matris (eftersom Householdertransformationer är unitära). Alltså är
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
förenklas detta om
är QR-faktoriserad. Lösningen ges i vanliga fall av
![{\displaystyle A^{H}A\mathbf {x} =A^{H}\mathbf {b} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/df562dbe46b653be1924e5224f24c556e42474da)
Om
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} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/a52ca29174334949e756f2de4c12003bd8f60cce)
och högerledet
![{\displaystyle A^{H}\mathbf {b} =(QR)^{H}\mathbf {b} =R^{H}Q^{H}\mathbf {b} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8996dc2852f2d003609dc8daddc3f42aa89f2b6)
så att ekvationen blir
![{\displaystyle R^{H}R\mathbf {x} =R^{H}Q^{H}\mathbf {b} \Rightarrow R\mathbf {x} =Q^{H}\mathbf {b} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/3174a7a542b607f1ca4880b2e0c28de7a79bbefe)
som är ett väldigt lättlöst ekvationsysstem eftersom
är triangulär.
Determinanter, egenvärden och singulärvärden
Om A är en kvadratisk matris av storlek n som är QR-faktoriserad,
, då det ur räknelagarna för determinanten att
![{\displaystyle \det A=\det Q\det R.\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ef71ec2e1e18e795fa3f4b816b77f46b591eb06)
Eftersom Q är unitär är
, vilket ger:
![{\displaystyle |\det A|=|\det R|=\left|\prod _{i}^{n}r_{ii}\right|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/611ddfff284437aaf66f8e1dbeea0a62f7c3ac4d)
där
ä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|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48ff0bd98a32b124b0bdd7b4638ba454d8887327)
där
ä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|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f65e8512db2c61a6dcf5eb3bb1917c42fda7a604)
där
är A:s singulärvärden.
Se även