Page 205 - Matrices theory and applications

10. Approximation of Eigenvalues
188
10.4.2 The Inverse Power Method
Let us assume that M is invertible. The standard power method, applied
−1
, furnishes the eigenvalue of least modulus, whenever it is simple, or
to M
at least its modulus in the general case. Since the inversion of a matrix is a
costly operation, we involve ourselves with that idea only if M has already
been inverted, for example if we had previously had to make an LU or a QR
factorization. That is typically the situation when one begins to implement
the QR algorithm for M. It might look strange to involve a method giving
only one eigenvalue in the course of a method that is expected to compute
the whole spectrum.
The inverse power method is thus subtle. Here is the idea. One begins
by implementing the QR method, until one gets coarse approximations
µ 1 ,... ,µ n of the eigenvalues λ 1 ,... ,λ n . If one persists in the QR method,
the proof of Theorem 10.2.1 shows that the error is at best of order σ k
with σ =max j |λ j+1 /λ j |.When n is large, σ is in general close to 1 and
this convergence is rather slow. Similarly, the method with Rayleigh trans-
lations, for which σ is replaced by σ(η):=max j |(λ j+1 −η)/(λ j −η)|,isnot
satisfactory. However, if one wishes to compute a single eigenvalue, say λ p ,
with full accuracy, the power method, applied to M − µ p I n , produces an
k
error on the order of θ ,where θ := |λ p − µ p |/ min j =p |λ j − µ p | is a small
number, since λ p − µ p is small.
In practice, the inverse power method is used mainly to compute an
approximate eigenvector, associated to an eigenvalue for which one already
has a good approximate value.

10.5 Leverrier’s Method

The method of Leverrier allows for the computation of the characteris-
tic polynomial of a square matrix. Though inserted in this Chapter, this
method is not suitable for computing approximate values of the eigenval-
ues of a matrix. First of all, it furnishes only the characteristic polynomial
which, as mentioned at the opening if this chapter, is not a good technique
for computing the eigenvalues. Its interest is purely academic. Observe,
however, that it is of great generality, applying to matrices with entries in
any field of characteristic 0.

10.5.1 Description of the Method

Let K be a field of characteristic 0 and M ∈ M n (K) be given. Let us
denote by λ 1 ,... ,λ n the eigenvalues of M, counted with multiplicity. Let
us define the two following lists of n numbers: