Page 190 - Matrices theory and applications

173
10.2. The QR Method
The sequence of polynomials P j is a Sturm sequence, which allows
us to compute the number of roots of P n in a given interval (a, b). A
Sturm sequence is a finite sequence of real polynomials Q 0 ,... ,Q n,with
Q 0 a nonzero constant such that Q j (x)= 0 and 0 <j < n imply
Q j+1 (x)Q j−1 (x) < 0. In particular, Q j and Q j+1 do not share a com-
mon root. If a ∈ IR is not a root of Q n , wedenoteby V (a)the number of
sign changes in the sequence (Q 0 (a),... ,Q n (a)), with the zeros playing no
role.
Proposition 10.1.3 If Q n (a) =0 and Q n (b) =0,and if a< b, then the
number of roots of Q n in (a, b) is equal to V (a) − V (b).
Let us remark that it is not necessary of compute the polynomials P j to
apply them to this proposition. Given a ∈ IR, it is enough to compute the
sequence of values P j (a).
Once an interval (a, b)is known to containaneigenvalue λ and only that
one (by means of Proposition 10.1.3 or Theorem 4.5.1), one can compute an
approximate value of λ, either by dichotomy, or by computing the numbers
V ((a+b)/2),..., or by the secant or Newton method. In the latter case, one
must compute P n itself. The last two methods are convergent, provided that

we have a good initial approximation at our disposal, because P (λ) =0.
n
We end this section with an obvious but nevertheless useful remark.
If M is Hessenberg and T upper triangular, the products TM and MT
are still Hessenberg (that would not be true if both matrices were Hessen-
berg). For example, if M admits an LU factorization, then L is Hessenberg,
and thus has only two nonzero diagonals, because L = MU −1 . Similarly, if
M ∈ GL n (CC), then the factor Q of the factorization M = QR is again Hes-
senberg, because Q = MR −1 . An elementary compactness and continuity
argument shows that the same fact holds true for every M ∈ M n(CC).

10.2 The QR Method

The QR method is considered the most efficient one for the approximate
computation of the whole spectrum of a square matrix M ∈ M n (CC). One
employs it only after having reduced M to Hessenberg form, because this
form is preserved throughout the algorithm, while each iteration is much
cheaper than it is for a generic matrix.

10.2.1 Description of the QR Method

Let A ∈ M n(K) be given, with K = IR or CC. We construct a sequence
of matrices (A j ) j∈IN ,with A 1 = A. The induction A j → A j+1 consists
in performing the QR factorization of A j , A j = Q j R j , and then defining