Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag

Mathematics-Online lexicon:

QR-Factorization


A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview

After a permutation of columns (if necessary) any $ n \times m$ matrix $ A$ can be factored into a product of a unitary and a generalized upper triangular matrix

$\displaystyle A(:,I)=QR\,.
$

This can be accomplished by $ \min(m-1,n)$ Householder transformations at most:

$\displaystyle Q=\left( \cdots Q_2 Q_1 \right)^{-1}=Q_1 Q_2 \cdots \,.
$

Before the $ \ell$-th transformation the modified matrix $ Q_{\ell-1} \cdots Q_1 A(:,I)$ has the form

\begin{displaymath}
\left(
\begin{array}{ccc\vert ccc}
* & \cdots & * & * & \...
... & \\
& 0 & & & B & \\
& & & & &
\end{array}
\right).
\end{displaymath}

If $ B$ is zero, the upper triangular form is reached. Otherwise, two columns are interchanged in such a way that the first column $ c$ of $ B$ has the largest 2-norm. Then, a Householder transformation based on $ c$ is applied to $ B$, advancing the triangular structure one step further.

The permutations are recorded in the index vector $ I$, which initially is set to $ (1, \ldots,m)$. For any column interchange the corresponding indices in $ I$ are permuted.

see also:


[Downloads] [Examples]

  automatically generated 7/ 2/2007