Decomposition QR

In Linear algebra, the decomposition QR (also called, decomposition qu) of a matrix $A$ is a decomposition of the form

$A\; =\; QR$

where $Q$ is a orthogonal Matrice ($QQ^T\; =\; I$), and $R$ a triangular Matrice higher.

There exist several methods to carry out this decomposition:

• the method of Householder where $Q$ is obtained by successive products of elementary orthogonal matrices
• the method of Givens where $Q$ is obtained by successive products of matrices of rotation planes
• the method of Schmidt

Each one of them has its advantages and its disadvantages. (Decomposition QR not being single, the various methods will produce different results).

Method of Householder

That is to say X an arbitrary vector column of dimension m and length |α| (For reasons of stability of calculation, α must be sign first element of X and length being the sum of all the elements of X ). However, several versions seem to exist in connection with α, here, to you is presented the version of the English article. Others use the standard || ||₂ rather than the length.

That is to say E ₁ the vector (1,0,…, 0) ^T, and || || the Euclidian norm, let us define

$\backslash \; mathbf\; \{U\}\; =\; \backslash \; mathbf\; \{X\}\; -\; \backslash \; alpha\; \backslash \; mathbf\; \{E\}\; \_1,$

$\backslash \; mathbf\; \{v\}\; =\; \{\backslash \; mathbf\; \{U\}\; \backslash \; over||\backslash \; mathbf\; \{U\}||\},$

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

$Q$ is the matrix of Householder or elementary orthogonal matrix and

$Qx\; =\; (\backslash \; alpha\; \backslash ,\; 0,\; \backslash \; cdots,\; 0)\; ^T$.

We can use these properties to transform a matrix has dimension m * N in a higher triangular matrix. First of all, one multiplies has by the matrix of Householder Q ₁ while having taken the care to choose for X the first column of has . The result is a matrix QA with zeros in the first column except first element which will be worth α.

$Q\_1A\; =\; \backslash \; begin\; \{bmatrix\}$

\ alpha_1& \ star& \ dots& \ star \ \ 0 & & & \ \ \ vdots & & A' & \ \ 0 & & & \ end {bmatrix}

This must be reiterated for A' which will be multiplied by Q'₂ (Q'₂ is smaller than Q ₁). If however, you would wish to use Q ₁ has rather than A', you must fill the matrix with Householder with 1 in the left higher corner:

$Q\_k\; =\; \backslash \; begin\; \{pmatrix\}$

I_ {k-1} & 0 \ \ 0 & Q_k' \ end {pmatrix}

After $t$ iterations, $t\; =\; min\; (M-1,\; N)$,

$R\; =\; Q\_t\; \backslash \; cdots\; Q\_2Q\_1A$

is a higher triangular matrix. If $Q\; =\; Q\_1Q\_2\; \backslash \; cdots\; Q\_t$ then $A\; =\; QR$ is decomposition QR of $A$.

Example

Let us calculate decomposition QR of

$A\; =\; \backslash \; begin\; \{pmatrix\}$

12 & -51 & 4 \ \ 6 & 167 & -68 \ \ -4 & 24 & -41 \ end {pmatrix}

One thus chooses the vector $\backslash \; mathrm\; \{has\}\; \_1\; =\; (12,\; 6,-4)\; ^T$. There is thus $\backslash |\; a\_1\; \backslash |\; =\; \backslash \; sqrt\; \{12^2+6^2+\; (-\; 4)\; ^2\}\; =14$. What leads us to write $\backslash |a\_1\; \backslash |\; e\_1\; =\; (14,\; 0,0)\; ^T$.

Calculation us ammene with $u\; =\; (-\; 2,\; 6,-4)\; ^T$ and $v\; =\; 14^\; \{-\; \{1\; \backslash \; over\; 2\}\}\; (-\; 1,\; 3,-2)\; ^T$. The first matrix of Householder is worth

$=\; I\; -\; \{1\; \backslash \; over\; 7\}\; \backslash \; begin\; \{pmatrix\}$

1 & -3 & 2 \ \ -3 & 9 & -6 \ \ 2 & -6 & 4 \ end {pmatrix} = \ begin {pmatrix} 6/7 & 3/7 & -2/7 \ \ 3/7 &-2/7 & 6/7 \ \ -2/7 & 6/7 & 3/7 \ \ \end{pmatrix}

Let us observe that:

$Q\_1A\; =\; \backslash \; begin\; \{pmatrix\}$

14 & 21 & -14 \ \ 0 & -49 & -14 \ \ 0 & 168 & -77 \ end {pmatrix} We have now under the diagonal only of the zeros in the 1st column.

To reiterate the process, one takes under principal matrix

$A\text{'}\; =\; M\_\; \{11\}\; =\; \backslash \; begin\; \{pmatrix\}$

-49 & -14 \ \ 168 & -77 \ end {pmatrix} Consequently method, one obtains the 2nd matrix of Householder

$Q\_2\; =\; \backslash \; begin\; \{pmatrix\}$

1 & 0 & 0 \ \ 0 & -7/25 & 24/25 \ \ 0 & 24/25 & 7/25 \ end {pmatrix}

Finally, one obtains

$Q=Q\_1Q\_2=\; \backslash \; begin\; \{pmatrix\}$

6/7 & -69/175 & 58/175 \ \ 3/7 & 158/175 & -6/175 \ \ -2/7 & 6/35 & 33/35 \ end {pmatrix}

$R=Q^\; \backslash \; signal\; A=\; \backslash \; begin\; \{pmatrix\}$

14 & 21 & -14 \ \ 0 & 175 & -70 \ \ 0 & 0 & -35 \end{pmatrix} The matrix Q is orthogonal and R is triangular higher, consequently, one obtains the decomposition has = QR .

Cost and advantages

The cost of this method for a matrix n*n is in: $\backslash \; frac\; \{4\}\; \{3\}\; \backslash \; times\; n^3$ This cost is relatively high (the method of Cholesky, for the positive definite symmetrical matrices is in $\backslash \; frac\; \{1\}\; \{3\}\; \backslash \; times\; n^3$). However, the method of Householder has the considerable advantage to be much more stable numerically, by limiting divisions by small numbers. The method of Givens, in spite of a cost still higher than this one, will offer still more stability.

See too

• Method of Cholesky
• Decomposition LU

Random links:

Gold mount (cheese) | Samurai Éditions | Elimäki | William Birdwood | David Fiegen | Wes_Linster

© 2007-2008 speedlook.com; article text available under the terms of GFDL, from fr.wikipedia.org