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 *QTQ = 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 *R1* estas supra triangula matrico de dimensioj *n×n*, *Q1* estas *m×n*, *Q2* estas *m×(m-n)*, kaj *Q1* kaj *Q2* ambaŭ havas ortajn kolumnojn.

La *Q1R1 estas nomata la **maldika QR-faktorigo** de *A*.
Se *A* estas de plena rango *n* kaj postuli, ke la diagonalaj eroj de *R1* estu pozitivaj, tiam *R1* kaj *Q1* estas unikaj, sed ĝenerale *Q2* ne estas unika. *R1* estas tiam egala al la supra triangula faktoro de la malkomponaĵo de Cholesky de *A*A* (kio estas la samo kiel *ATA* 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 = QQTA = 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**1* 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

: *Q**x** = (α, 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 *Q1* kiun oni ricevis kiam elekti la unua matrican kolumnon por **x**. Ĉi tio donas matricon *Q1A'' kun nuloj en la maldekstra kolumno ĉie escepte de la unua linio.

:Q_1A = \begin{bmatrix}
 \alpha_1&\star&\dots&\star\\
 0 & & & \\
 \vdots & & A' & \\
 0 & & & \end{bmatrix}

Ĉi tio povas ripetiĝi por *A&prime;* (ricevita de *Q1A* per forviŝo de la unua linio kaj unua kolumno), rezultante en matrico de Householder *Q&prime;2*. Notu, ke *Q&prime;2* estas pli malgranda ol *Q1*. Pro tio ke oni bezonas ke ĝi reale al operaciu sur *Q1A* anstataŭ *A&prime;* 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 = Qt ... Q2Q1A*

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

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_1A = \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_2Q_1A=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, *a31 = -4*. Oni formas ĉi tiu matricon *G1* 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 *G1A* havas nulon en la 3,1-ero:

:G_1A \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 *G2* kaj poste *G3*, kiuj nuligas la sub-diagonalajn erojn 2, 1 kaj 3, 2 respektive, formante triangulan matricon *R*. Tiam *R = G3G2G1A* kaj do la orta matrico *QT* estas formata per produto de ĉiuj matricoj de Givens *QT = G3G2G1* kaj *R=QTA* 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 *rii* 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 = QRPT*

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:

: *|r11| ≥ |r22| ≥ ... ≥ |rnn|*

Ĉ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 
* .
* Reta matrica kalkulilo  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 
* biblioteko de proceduroj ALGLIB

Kategorio:Cifereca lineara algebro
Kategorio:Matrica teorio