QR-faktorigo

En lineara algebro, QR-malkomponaĵo aŭ QR-faktorigo de matrico estas matrico malkomponaĵo de la matrico en ortan kaj dekstran triangulan matricojn. QR-malkomponaĵo estas ofte uzata por solvado de lineara problemo de plej malgrandaj kvadratoj, kaj estas la bazo por aparta ejgena algoritmo, la QR-algoritmo.

Difino

Por kvadrata matrico

QR-malkomponaĵo de reela kvadrata matrico A estas malkomponaĵo de A kiel

A = QR

kie Q estas orta matrico (tio estas ke Q^TQ = I ) kaj R estas dekstra triangula matrico (ankaŭ nomata kiel supra triangula matrico).

Se A estas inversigebla matrico, tiam ĉi tiu faktorigo estas unika se postuli ke diagonalaj eroj de R estu pozitivaj.

Por kompleksa kvadrata matrico A, Q estas unita matrico Q (tio estas ke Q^*Q = I ).

Por ne-kvadrata matrico

Pli ĝenerale, oni povas faktorigu kompleksan m×n-matricon A, kun m≥n, kiel produton de unita matrico Q de dimensioj m×m kaj supra triangula matrico R de dimensioj m×n. En la malsupro (m-n-linioj) la supra triangula matrico de dimensioj m×n konsistas plene el nuloj. Estas ofte utile dispartigi matricon R, aŭ ambaŭ R kaj Q:

$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}$

kie R₁ estas supra triangula matrico de dimensioj n×n, Q₁ estas m×n, Q₂ estas m×(m-n), kaj Q₁ kaj Q₂ ambaŭ havas ortajn kolumnojn.

La Q₁R₁ estas nomata la maldika QR-faktorigo de A. Se A estas de plena rango n kaj postuli, ke la diagonalaj eroj de R₁ estu pozitivaj, tiam R₁ kaj Q₁ estas unikaj, sed ĝenerale Q₂ ne estas unika. R₁ estas tiam egala al la supra triangula faktoro de la malkomponaĵo de Cholesky de A^*A (kio estas la samo kiel A^TA se A estas reela).

QL-, RQ- kaj LQ-malkomponaĵoj

Analoge, oni povas difini QL-, RQ- kaj LQ-malkomponaĵojn, kie L estas suba triangula matrico.

Komputado de QR-malkomponaĵo

Estas kelkaj manieroj por reale komputi la QR-malkomponaĵon, per la procezo de Gram-Schmidt, transformoj de Householder aŭ turnadoj de Givens. Ĉiu havas kelke da avantaĝoj kaj malavantaĝoj.

Procezo de Gram-Schmidt

Konsideru la procezon de Gram-Schmidt aplikitan al kolumnoj de la matrico $A={\begin{bmatrix}\mathbf {a} _{1}&\cdots &\mathbf {a} _{n}\end{bmatrix}}$, kun ena produto $\langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\top }\mathbf {w}$ (aŭ $\langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{*}\mathbf {w}$ por la kompleksa okazo).

Estu la projekcio:

$\mathrm {proj} _{\mathbf {e} }\mathbf {a} ={\frac {\left\langle \mathbf {e} ,\mathbf {a} \right\rangle }{\left\langle \mathbf {e} ,\mathbf {e} \right\rangle }}\mathbf {e}$

tiam

$\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}\|}$

...

$\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}\|}$

Oni tiam reordigu la ekvaciojn pli supre tiel ke la a_i estu maldekstre, uzante tion ke la e_i estas unuoblaj vektoroj:

$\mathbf {a} _{1}=\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle \mathbf {e} _{1}$

$\mathbf {a} _{2}=\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle \mathbf {e} _{1}+\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle \mathbf {e} _{2}$

$\mathbf {a} _{3}=\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle \mathbf {e} _{1}+\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle \mathbf {e} _{2}+\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle \mathbf {e} _{3}$

...

$\mathbf {a} _{k}=\sum _{j=1}^{k}\langle \mathbf {e} _{j},\mathbf {a} _{k}\rangle \mathbf {e} _{j}$

kie $\langle \mathbf {e} _{i},\mathbf {a} _{i}\rangle =\|\mathbf {u} _{i}\|$. Ĉi tio povas esti skribita en matrica formo:

A = QR

kie:

$Q=\left[\mathbf {e} _{1},\cdots ,\mathbf {e} _{n}\right]$

$R={\begin{bmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\ldots \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\ldots \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\ldots \\\vdots &\vdots &\vdots &\ddots \end{bmatrix}}$

Ekzemplo

Estu

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

Oni povas kalkuli matricon Q per procezo de Gram-Schmidt:

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

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

Tial

A = QQ^TA = QR

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

Rilato al RQ-malkomponaĵo

La RQ-malkomponaĵo konvertas la matricon A en produton de supra triangula matrico R (ankaŭ konata kiel dekstra triangula) kaj orta matrico Q. La nura diferenco de QR-malkomponaĵo estas la ordo de ĉi tiuj matricoj.

QR-malkomponaĵo estas ortigo de Gram-Schmidt de kolumnoj de A, startigita de la unua kolumno.

RQ-malkomponaĵo estas ortigo de Gram-Schmidt de linioj de A, startigita de la lasta linio.

Uzo de reflektoj de Householder

Reflekto de Householder (aŭ transformo de Householder) estas transformo kiu prenas vektoron kaj reflektas ĝin ĉirkaŭ iu ebeno. Oni povas uzi ĉi tiun operacion por kalkuli la QR-faktorigon de m×n-matrico A kun m≥n.

Q povas esti uzata por reflekti vektoron en tia maniero ke ĉiuj koordinatoj krom unu nuliĝas.

Estu x ajna reela m-dimensia kolumna vektoro de A tia ke ||x|| = |α| por skalaro α. Se la algoritmo estas realigata per glitkoma aritmetiko, tiam α devus preni la kontraŭan signon de la unua koordinato de x por eviti malprofiton de signifeco. En la komplekso okazo

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

kaj anstataŭ transpono estas konjugita transpono en la konstruado de Q pli sube.

Tiam

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

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

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

kie e₁ estas la vektoro (1, 0, ..., 0)^T, ||·|| estas la eŭklida normo kaj I estas identa matrico de dimensio m×m

Aŭ, se A estas kompleksa

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

kie $\mathbf {x} ^{H}$ estas la transpono kaj konjugito de x

Q estas matrico de Householder de dimensio m×m kaj

Qx = (α, 0, ..., 0)^T

Ĉi tio povas esti uzata por laŭgrade konverti m×n-matricon A al supra triangula formo. Unue, oni multipliku A kun la matrico de Householder Q₁ kiun oni ricevis kiam elekti la unua matrican kolumnon por x. Ĉi tio donas matricon Q₁A kun nuloj en la maldekstra kolumno ĉie escepte de la unua linio.

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

Ĉi tio povas ripetiĝi por A′ (ricevita de Q₁A per forviŝo de la unua linio kaj unua kolumno), rezultante en matrico de Householder Q′₂. Notu, ke Q′₂ estas pli malgranda ol Q₁. Pro tio ke oni bezonas ke ĝi reale al operaciu sur Q₁A anstataŭ A′ oni bezonas elvolvi ĝin al la supro-maldekstro, enspacante per ero 1, aŭ ĝenerale per unua matrico:

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

Post t ripetoj de ĉi tiu procezo kie t = min(m-1, n),

R = Q_t ... Q₂Q₁A

estas supra triangula matrico. Do kun

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

A = QR estas QR-malkomponaĵo de A.

Ĉi tiu maniero havas pli grandan nombran stabilecon ol la maniero de Gram-Schmidt pli supre priskribita.

La kvanto de operacioj en la k-a paŝo de la QR-malkomponigado per la transformo de Householder de kvadrata n×n-matrico estas

Operacio	Kvanto
multipliko	$2(n-k+1)^{2}$
adicio	$(n-k+1)^{2}+(n-k+1)(n-k)+2$
divido	1
kvadrata radiko	1

Sumante ĉi tiujn nombrojn tra la (n-1) paŝoj por kvadrata matrico de amplekso n, la komplekseco de la algoritmo (laŭ la glit-komaj multiplikoj) estas

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

Ekzemplo

Estu same kiel supre

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

Unue, oni bezonas trovi reflekton kiu konvertas la unuan kolumnon de matrico A, vektoron $\mathbf {a} _{1}={\begin{bmatrix}12\\6\\-4\end{bmatrix}}$, al $\|\mathbf {a} _{1}\|\mathrm {e} _{1}={\begin{bmatrix}14\\0\\0\end{bmatrix}}$

Do

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

kaj

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

Ĉi tie,

α=14 kaj $\mathbf {x} =\mathbf {a} _{1}={\begin{bmatrix}12\\6\\-4\end{bmatrix}}$

Pro tio

$\mathbf {u} ={\begin{bmatrix}-2\\6\\-4\end{bmatrix}}=2{\begin{bmatrix}-1\\3\\-2\end{bmatrix}}$ kaj $\mathbf {v} ={1 \over {\sqrt {14}}}{\begin{bmatrix}-1,3\\-2\end{bmatrix}}$, kaj tiam

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

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

$={\begin{bmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{bmatrix}}$

Tiam

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

do oni jam havas preskaŭ triangulan matricon. Nun nur bezonatas nuligi la (3, 2)-elementon (de valoro 168).

Prenu la (1, 1)-minoron, kaj tiam apliku la procezon denove al

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

Per la sama maniero kiel pli supre, oni ricevas la matricon de la transformo de Householder

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

post aldono de valoro 1 je supro-maldekstro por havi taŭgan amplekson de la matrico por la sekva paŝo.

Nun

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

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

La matrico Q estas orta kaj R estas supra triangula, do A = QR estas la postulita QR-malkomponaĵo.

Uzo de turnadoj de Givens

QR-malkomponaĵo povas ankaŭ esti komputita per serio de turnadoj de Givens. Ĉiu turnado nuligas eron sub la diagonalo de la matrico, formante laŭgrade la matricon R. La kunmeto de ĉiuj turnadoj de Givens formas la ortan matricon Q.

En praktiko, turnadoj de Givens ne estas reale plenumataj per konstruado de la tuta matrico kaj faro de matrica multipliko. Turnada proceduro de Givens estas uzata anstataŭe, kiu faras la ekvivalenton de la multipliko de matrico de Givens enhavanta multajn nulojn, sen la superflua laboro. La turnada proceduro de Givens estas utila en situacioj, en kiuj estas nur relative malmultaj nenulaj nediagonalaj eroj, kaj ĝi estas pli facile paraleligebla ol transformoj de Householder.

Ekzemplo

Estu la same kiel pli supre

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

Unue, oni bezonas formi turnadan matricon kiu nuligas la plej malsupro-maldekstran eron, a₃₁ = -4. Oni formas ĉi tiu matricon G₁ uzante la turnadon de Givens. Oni unue turnas la vektoron (6, -4) al punkto laŭ la x-akso. Ĉi tiu vektoro havas angulon $\theta =\arctan \left({-4 \over 6}\right)$. Oni kreas matricon de la orta turnado de Givens:

$G_{1}={\begin{bmatrix}1&0&0\\0&\cos(\theta )&\sin(\theta )\\0&-\sin(\theta )&\cos(\theta )\end{bmatrix}}\approx {\begin{bmatrix}1&0&0\\0&0,83205&-0,55470\\0&0,55470&0,83205\end{bmatrix}}$

La produto G₁A havas nulon en la 3,1-ero:

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

Konsiderante ĉi tiun matricon, oni povas simile formi matricojn de Givens G₂ kaj poste G₃, kiuj nuligas la sub-diagonalajn erojn 2, 1 kaj 3, 2 respektive, formante triangulan matricon R. Tiam R = G₃G₂G₁A kaj do la orta matrico Q^T estas formata per produto de ĉiuj matricoj de Givens Q^T = G₃G₂G₁ kaj R=Q^TA aŭ A=QR estas la QR-malkomponaĵo.

Ligo al determinanto aŭ produto de ejgenoj

Oni povas uzi QR-malkomponaĵon por trovi la absolutan valoron de la determinanto de kvadrata matrico. Supozu ke matrico estas malkomponita kiel A=QR. Tiam

det(A)=det(Q)det(R)

Pro tio ke Q estas unita, |det(Q)|=1. Tial,

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

kie r_ii estas la elementoj en la ĉefdiagonalo de R.

Plu, ĉar la determinanto egalas al produto de la ejgenoj

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

kie λ_i estas ejgenoj de A.

Oni povas etendi la pli supre donitajn propraĵojn al ne-kvadrata kompleksa matrico A per anstataŭo de ejgenoj per singularaj valoroj.

Estu QR-malkomponaĵo de ne-kvadrata matrico A:

$A=Q{\begin{bmatrix}R\\O\end{bmatrix}}$

kie O estas nula matrico kaj Q estas unita matrico, Q^*Q = I.

De la propraĵoj de singulara valora malkomponaĵo kaj determinanto de matrico

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

kie σ_i estas singularaj valoroj de A.

Singularaj valoroj de A kaj R estas identaj, kvankam la kompleksaj ejgenoj de ili povas esti malsamaj. Tamen, se A estas kvadrata,

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

Elekto de kondukaj kolumnoj

QR-malkomponaĵo kun elekto de kondukaj kolumnoj enhavas ankaŭ la permutan matricon P:

AP = QR aŭ A = QRP^T

Elekto de kondukaj kolumnoj estas utila se A estas proksima al havo de ne plena rango, aŭ estas suspektata ĉi tia. Ĝi povas ankaŭ plibonigi nombran akuratecon. P estas kutime elektata tiel, ke la diagonalaj eroj de R estas ne-pligrandiĝantaj:

|r₁₁| ≥ |r₂₂| ≥ ... ≥ |r_nn|

Ĉi tio povas esti uzata por nombre trovi rangon de A je pli malgranda komputa kosto ol singulara valora malkomponaĵo.

Vidu ankaŭ

• Polusa malkomponaĵo
• Ejgena malkomponaĵo
• Spektra malkomponaĵo
• Matrica malkomponaĵo

Eksteraj ligiloj

• Mezzadri, Francesco (majo 2007). How to Generate Random Matrices from the Classical Compact Groups - Kiel generi hazardajn matricojn de la klasikaj kompaktaj grupoj. Notices - Rimarkoj 54 (5) 592–604. AMS. arXiv:math-ph/0609050..
• Reta matrica kalkulilo Arkivigite je 2008-12-12 per la retarkivo Wayback Machine Plenumas QR-malkomponaĵon de matricoj.
• uzanto-manlibro de LAPACK kun detaloj pri kalkulado de la QR-malkomponaĵo
• Detaloj kaj ekzemploj de proceduroj pot kalkuli QR-malkomponaĵon Arkivigite je 2009-10-30 per la retarkivo Wayback Machine
• biblioteko de proceduroj ALGLIB