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.

Example:

[Downloads] [Links]
  automatically generated 7/ 2/2007