Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online lexicon: Annotation to

Hessenberg Form

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
For an $ n \times n$ matrix $ A$, the entries $ a_{j,k}$ with $ j>k+1$ can be annihilated with $ n-2$ Householder similarity transformations:

$\displaystyle A \mapsto B= Q_{n-2} \cdots Q_1 A Q_1 \cdots Q_{n-2}. $

The transformation $ Q_\ell = Q_\ell^{\operatorname t}$ produces zeros below position $ (\ell +1, \ell)$.

For symmetric $ A$, $ B$ is also symmetric, hence tridiagonal. Since eigenvalues are preserved, transformation to the so-called Hessenberg form is a useful preprocessing step for any eigenvalue routine.

We proceed by induction. Before the $ \ell$-th transformation, the modified matrix has the form

$\displaystyle \tilde{A}=\left(\begin{array}{ccc\vert ccc} & & & & & \\ & H &... ...\\ \hline & & & & & \\ & 0 & x & & Z & \\ & & & & & \end{array} \right) $

where the $ \ell \times \ell$ matrix $ H$ already has Hessenberg form ($ h_{j,k}=0$ for $ j>k+1$) and $ x, \, Y, \, Z$ have dimension $ (n-\ell)\times 1$, $ \ell \times (n-\ell)$, and $ (n-\ell) \times (n-\ell)$ respectively. The transformation $ Q_\ell$, applied from the left, acts on rows $ \ell+1, \hdots,n$:

$\displaystyle \underbrace{\left(\begin{array}{ccc\vert ccc} & & & & & \\ & E... ... & 0 & 0 & & \tilde{Q}_\ell Z & \\ & & \vdots & & & \end{array} \right) $

Here, $ E$ is the $ \ell \times \ell$ unit matrix and $ \tilde{Q}_\ell$ a Householder transformation based on the vector $ x$. Applying the transformation from the right, modifies only columns $ (\ell+1)-n$, leading to

$\displaystyle \left(\begin{array}{ccc\vert ccc} & & & & & \\ & H & & & Y\til... ...\tilde{Q}_\ell Z \tilde{Q}_\ell & \\ & & \vdots & & & \end{array} \right) $

Now, the $ (\ell+1) \times (\ell+1)$ upper diagonal block has Hessenberg form, which completes the induction step.

(Authors: Höllig/Pfeil/Walter)
[Back]
  automatisch erstellt am 24.  4. 2007