Page 186 - Matrices theory and applications

169
10.1. Hessenberg Matrices
pairwise similar, whose structure has some convergence property. Each
method is conceivedinsucha way thatthe sequence converges to a simple
form, triangular or diagonal, since then the eigenvalues can be read on the
diagonal. Such convergence is not always possible. For example, an algo-
rithm in M n (IR) cannot converge to a triangular form when the matrix
under consideration possesses a pair of nonreal eigenvalues.
There are two strategies for the choice of M (0) . One can naively take
M (0) = M. But since an iteration on a generic matrix is rather costly,
one often uses a preliminary reduction to a simple form (for example the
Hessenberg form, in the QR algorithm), which is preserved throughout the
iterations. With a few such tricks, certain methods can be astonishingly
efficient. The danger of iterative methods is the possible growth of round-
off errors and errors in the data. Typically, a procedure that doubles the
errors at each step transforms an initial error of size 10 −3 into an O(1)
after ten iterations, which is by no means acceptable. For this reason, it
is important that the passage of M (m) to M (m+1) be contracting,thatis,
that the errors be damped, or at worst not be amplified. Since M (m+1) is
conjugate to M (m) by some matrix P (which in fact depends on m), the
growth rate is approximately the number K(P):= P · P −1 , called the
condition number, which is always greater than or equal to one. Using the
induced norm · 2 , it equals 1 if and only if P is a similitude matrix; that
is, P ∈ CC · U n . For this reason, each iterative method builds sequences
of unitarily similar matrices: The conjugation matrices P (m) are unitary
(orthogonal if the ground field is IR).

10.1 Hessenberg Matrices

Definition 10.1.1 A square matrix M ∈ M n (K) is called upper Hessen-
berg (one speaks simply of a Hessenberg matrix) if m jk =0 for every pair
(j, k) such that j − k ≥ 2.
A Hessenberg matrix thus has the form
 
x ··· ···
.
 . 
 y . 
 
. .
. 
 . . .  .
 0 . . .
 
 . . . .
 . . . . . . . . . 
.
. 
0 ··· 0 z t
In particular, an upper triangular matrix is a Hessenberg matrix.
When computing the spectrum of a given matrix, we may always restrict
ourselves to the case of an irreducible matrix, using a conjugation by a
permutation matrix: If M is reducible, we may limit ourselves to a block-
triangular matrix whose diagonal blocks are irreducible. It is enough then