next up previous
Next: 2.2.3 LU Decomposition Up: 2.2 Exact Methods Previous: 2.2.1 Gauss Elimination and


2.2.2 Householder Transformation

Task: Strip column and/or row vectors of some of their rear elements.

Given $\mbox{${\bf A}$}$ $\longrightarrow$ $\mbox{${\bf A}$}'$ triangular, tridiagonal, or otherwise simple.



Let $\vec{a}$ be a vector (such as a matrix column vector), and $\vec{e}_{1}$ a unit vector. Define an auxiliary vector $\vec{b} \equiv \vec{a}\pm \vert\vec{a}\vert \,\vec{e}_{1}$ and normalize it.

Householder matrix:

\begin{displaymath}
\mbox{${\bf P}$} \equiv \mbox{${\bf 1}$}-2 \, \vec{b}_{0} \cdot \vec{b}_{0}^{T}
\end{displaymath}

See for yourself that in the transformed vector $ \vec{a}' \equiv \mbox{${\bf P}$} \cdot \vec{a}$ all elements but the first are equal to zero.

Apply this transformation successively to simplify a matrix.

EXAMPLE: Let

\begin{displaymath}
\mbox{${\bf A}$}=\mbox{$\left( \begin{array}{ccc}1&2&3\\ \vspace{-9pt}\\ 4&5&6 \\ \vspace{-9pt}\\ 7&8&9\end{array} \right)$}
\end{displaymath}

From $\vec{a} \equiv (1,4,7)^{T}$ construct the auxiliary vector $\vec{b}=(-7.124, 4, 7)^{T}$, normalize to $\vec{b}_{0}=(-0.662, 0.372, 0.651)^{T}$. The Householder matrix is

\begin{displaymath}
\mbox{${\bf P}$}_{1}=\mbox{$\left( \begin{array}{ccc}0.123&0...
...484 \\ \vspace{-9pt}\\ 0.862&-0.484&0.153\end{array} \right)$}
\end{displaymath}

Check: Multiplying $\mbox{${\bf A}$}$ by $\mbox{${\bf P}$}_{1}$ we have

\begin{displaymath}
\mbox{${\bf P}$}_{1} \cdot \mbox{${\bf A}$}=
\mbox{$\left( \...
...2&1.464 \\ \vspace{-9pt}\\ 0&-0.696&1.062\end{array} \right)$}
\end{displaymath}

Next step: treat the lower right $2 \times 2$ submatrix of $\mbox{${\bf P}$}_{1} \cdot \mbox{${\bf A}$}$. From $\vec{a} = (4.602, -0.696)^{T}$ construct a $2 \times 2$ Householder matrix which is promoted to a $3 \times 3$ matrix by adding a trivial first line and column:

\begin{displaymath}
\mbox{${\bf P}$}_{2} = \mbox{$\left( \begin{array}{ccc}1&0&0...
...-0.149 \\ \vspace{-9pt}\\ 0&-0.149&-0.989\end{array} \right)$}
\end{displaymath}

Result:

\begin{displaymath}
\mbox{${\bf P}$}_{2} \cdot \mbox{${\bf P}$}_{1} \cdot \mbox{...
...4.655&1.289 \\ \vspace{-9pt}\\ 0&0&-1.269\end{array} \right)$}
\end{displaymath}



next up previous
Next: 2.2.3 LU Decomposition Up: 2.2 Exact Methods Previous: 2.2.1 Gauss Elimination and
Franz J. Vesely Oct 2005
See also:
"Computational Physics - An Introduction," Kluwer-Plenum 2001