366 CHAPTER 15. NUMERICAL METHODS, EIGENVALUES

The output will be first P a unitary matrix, then H, a Hessenberg matrix and finally, thelast line just verifies that P∗AP = H. Then you can do the QR algorithm on H.

The reason you should use a matrix which is upper Hessenberg and similar to A in theQR algorithm is that the algorithm keeps returning a matrix in upper Hessenberg form andif you are looking for block upper triangular matrices, this will force the size of the blocksto be no larger than 2×2 which are easy to handle using the quadratic formula. This is inthe following lemma.

Lemma 15.6.4 Let {Ak} be the sequence of iterates from the QR algorithm, A−1 exists.Then if Ak is upper Hessenberg, so is Ak+1.

Proof: The matrix is upper Hessenberg means that Ai j = 0 whenever i− j ≥ 2.

Ak+1 = RkQk

where Ak = QkRk. Therefore AkR−1k = Qk and so

Ak+1 = RkQk = RkAkR−1k

Let the i jth entry of Ak be aki j. Then if i− j ≥ 2

ak+1i j =

n

∑p=i

j

∑q=1

ripakpqr−1

q j

It is given that akpq = 0 whenever p−q≥ 2. However, from the above sum,

p−q≥ i− j ≥ 2,

and so the sum equals 0. ■

Example 15.6.5 Find the solutions to the equation x4− 4x3 + 8x2− 8x+ 4 = 0 using theQR algorithm.

This is the characteristic equation of the matrix

H =

4 −8 8 −41 0 0 00 1 0 00 0 1 0

Since the constant term in the equation is not 0, it follows that the matrix has an inverse. It isalready in upper Hessenberg form. Lets apply the QR algorithm above with 100 iterations.This yields the following matrix which is similar to H.

.6761 −.7372 .0469 .15931.5344 1.3435 3.1593 10.7276

0 0.0001 −1.3435 −4.18850 0 1.5344 3.3239

