Unshifted QR iteration, studied in two dimensions in the preceding unit, converges only linearly, at a rate set by ratios of eigenvalues, and each step on a dense matrix costs a full QR factorization of order operations. The method used in practice removes both obstacles. First the matrix is reduced once, by orthogonal similarity, to upper Hessenberg form, which is almost triangular. Second, each QR step is shifted by an estimate of an eigenvalue, which makes the last subdiagonal entry shrink very fast. Third, once that entry is negligible, the problem is split off (deflated) and the algorithm continues on a smaller matrix. This unit proves the facts that make each stage valid. It uses Householder reflectors from the unit on Householder QR, the QR iteration identity and inverse iteration from the earlier units of this chapter.
Definitions
Definition 5.6.1
(Upper Hessenberg matrix)
A real matrix is upper Hessenberg if whenever ; it may be nonzero on and above the first subdiagonal.
Definition 5.6.2
(Householder reflector and Givens rotation)
A Householder reflector is for a nonzero vector ; it is symmetric and orthogonal. A Givens rotation acting on rows is the identity except for the block
and for given with the choice , makes the second component of zero.
Definition 5.6.3
(Shifted QR step and Rayleigh shift)
A shifted QR step with shift takes a square matrix , computes a factorization with orthogonal and upper triangular, and forms
The Rayleigh shift is , the last diagonal entry.
Since , we get , so is orthogonally similar to and has the same eigenvalues.
Definition 5.6.4
(Deflation)
A matrix is deflated when a subdiagonal entry is set to zero, so that it is block upper triangular.
Hessenberg reduction
Theorem 5.6.5
(Reduction to Hessenberg form)
For every real matrix there is an orthogonal , a product of Householder reflectors, with upper Hessenberg. If is symmetric, is tridiagonal.
Proof
(Annihilating column by column)
Put and construct for , with and a Householder reflector in chosen as follows. Let be the part of column of below the diagonal. Take , where if and otherwise (this sign avoids cancellation), and when (and when ). Then .
Left multiplication by changes only rows and turns column into one whose entries in rows are zero. For columns , the entries in rows are already zero (because ), and a combination of zeros is zero, so these columns are unchanged. Right multiplication by combines only columns , so columns keep all their zeros. After every column has zeros in rows , so is upper Hessenberg and with , since each is symmetric and orthogonal. If then is symmetric; a symmetric Hessenberg matrix has zeros below the first subdiagonal and, by symmetry, above the first superdiagonal, so it is tridiagonal.
Proof X-ray
Why the reflector starts below the diagonal
The reduction rests on which rows and columns each multiplication touches. The vector is taken from column starting at row , so acts only on rows and columns . Left multiplication zeros column below row and leaves rows alone; right multiplication recombines columns and cannot reach columns , so the zeros already created survive. Had the reflector been built from column starting at the diagonal entry, the right multiplication would recombine column itself with later columns, and in general the zeros just created would be filled in again. A similarity can therefore afford to clear only the entries below the first subdiagonal; the remaining subdiagonal is what the QR iterations later drive to zero. The sign plays a separate role: since , the vector is nonzero whenever , and its first component is computed without cancellation.
The reduction costs a number of operations proportional to and is done only once.
Shifted QR steps on Hessenberg matrices
Theorem 5.6.6
(A QR step preserves Hessenberg form)
Let be upper Hessenberg and . For let be the Givens rotation on rows chosen to zero the entry of the current matrix, starting from . Then is upper triangular, is orthogonal with , and is upper Hessenberg. A step costs operations.
Proof
(Rotations to triangular form, then multiplying back)
The matrix is Hessenberg, so column has only one nonzero entry below the diagonal, in row . When is applied, the previous rotations have made columns upper triangular and have changed only rows ; row is still original, so the entry is the original one. The rotation zeroes it and does not disturb columns (whose entries in rows are zero). After rotations the matrix is upper triangular: this is . The relation follows from .
To form , multiply on the right by , then , and so on; replaces columns and by linear combinations of themselves. Let . We show by induction that column of has nonzero entries only in rows (and only in rows for ). For this is the triangularity of . In , column has entries only in rows (it is a combination of columns of or is column of ) and column is column of , with entries in rows . Their combinations in therefore have entries only in rows , which satisfies the claim for and ; other columns are unchanged. For the claim says that is upper Hessenberg, and so is . Each rotation changes two rows (on the left) or two columns (on the right), each of length at most , so it costs operations, and a step costs .
For a general dense matrix the same factorization costs , so the Hessenberg form lowers the cost of each step by a factor of order .
Theorem 5.6.7
(The last column of Q is an inverse-iteration vector)
If is nonsingular, with orthogonal and upper triangular, then the last column of satisfies , where is the last diagonal entry of . Consequently . The last subdiagonal entry of satisfies .
Proof
(The last column of the inverse transpose)
From we get . The matrix is lower triangular, so its last column is . Hence . Taking norms, gives the formula for . The last row of is , so the last row of is times the last row of , and the entry in position is with .
When is symmetric, , so is one step of inverse iteration with shift started from , and is small exactly when that step amplifies strongly, that is, when is close to an eigenvalue whose eigenvector has a nonzero last component. For a symmetric with eigenpair , , and , one has and so . The Rayleigh shift is the Rayleigh quotient of and so is a natural estimate of such an eigenvalue. We do not prove the convergence rate of the Rayleigh shift; for symmetric tridiagonal matrices it is cubic in practice, as the example below shows.
Rayleigh shifts work well in practice, but the claim that they always make progress is false.
Counterexample mode
A Rayleigh shift can leave the matrix unchanged
It is tempting to claim that every step with the Rayleigh shift shrinks the last subdiagonal entry. Take , which is already Hessenberg, so . Then , and its QR factorization with positive diagonal in (which is unique) is , . Hence : the step reproduces and the subdiagonal entry stays equal to . Practical codes use a Wilkinson shift instead, an eigenvalue of the trailing block closest to . Here the block is itself, both eigenvalues and are equally close to , and either one deflates the matrix in one step.
The algorithm and deflation
EIGENVALUES(A):
reduce A to Hessenberg form H = Q^T A Q
m = n
while m > 1:
repeat
choose a shift mu (for example h[m][m])
apply one shifted QR step to the leading m-by-m block of H
until |h[m][m-1]| is negligible
record h[m][m] as an eigenvalue; set h[m][m-1] = 0; m = m - 1
record h[1][1]
If then with square diagonal blocks, and , so the eigenvalues of are those of together with those of (counted with multiplicity). Thus when , the entry is an eigenvalue and the problem reduces to the leading block. In floating-point arithmetic, "negligible" means below a small multiple of the unit roundoff times ; setting such an entry to zero changes by a perturbation of that size. A real matrix with complex conjugate eigenvalues cannot be made triangular by a real orthogonal similarity: the iteration then ends with diagonal blocks, the stopping test on a single subdiagonal entry may never be met, and complex or double shifts are needed, which are not treated here. For symmetric matrices all eigenvalues are real.
Concept lensStructural
A zero subdiagonal entry is an invariant subspace
Write with , where holds the first columns. Then gives , and exactly when , that is, when the span of the first columns of is invariant under . Deflation therefore splits off an invariant subspace, and the eigenvalues of are those of restricted to it.
Worked examples
Worked example 5.6.8
(Hessenberg reduction of a 3-by-3 matrix)
Let
Only one reflector is needed (). The vector below the diagonal in column is with . Since take , proportional to . Then and . With ,
Checks of similarity invariants: the trace is ; the determinant of is ; and the sum of the principal minors is for both matrices. The entry is zero, so is Hessenberg.
Worked example 5.6.9
(An eigenvalue as the shift deflates in one step)
Let , with eigenvalues and , and take . Then with and , and
Both eigenvalues appear in one step. This is the degenerate case: is singular and , so the theorem on the last column does not apply as stated, but the bound is consistent with it, since the right-hand side tends to as .
Worked example 5.6.10
(Shifted QR steps on a tridiagonal matrix)
Let and use the Rayleigh shift . Then . The first rotation uses : , . After it the second column has entries in rows before the second rotation, which uses , giving the pivot , , . The result is
with . Forming gives
of trace . Repeating with gives the following (rounded) values:
| step | ||
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0.2711 | 0.5714 |
| 2 | 0.003859 | 0.53950 |
| 3 | 0.5394951 |
After three steps the subdiagonal entry is negligible, so is an eigenvalue of to about eight digits. The remaining block has the other two eigenvalues, and its trace equals , as it must. The last two reductions are consistent with cubic convergence: , against the observed .
Common mistakes and subtle points
Common mistake
(Hessenberg form is not triangular form)
Reducing to Hessenberg form is an orthogonal similarity, so eigenvalues are preserved, but the result is Hessenberg and not triangular: the first subdiagonal is in general nonzero, so the eigenvalues cannot yet be read off.
Common mistake
(Forgetting to add the shift back)
Shifted QR factors , not . Forming without adding gives a matrix whose eigenvalues are those of shifted by .
Common mistake
(Using one fixed shift)
The shift should change at every iteration; a fixed shift gives only linear convergence to the eigenvalue nearest the shift, like inverse iteration with a fixed shift.
A matrix that is already symmetric stays symmetric under each step (orthogonal similarity), so the tridiagonal structure of the Hessenberg form of a symmetric matrix is preserved as well.
Convergence of the Rayleigh shift is not guaranteed for every starting matrix, as the counterexample above shows. Cubic convergence is an observed behavior for symmetric tridiagonal matrices and is not proved in this unit.
Deflating a tiny but nonzero subdiagonal entry is a backward-stable approximation (a small perturbation of ), not an exact statement.
Exercises
Quick check
(Prove that if a symmetric matrix is reduced to Hessenberg form by an orthogonal , then is tridiagonal.)
Show first that is symmetric.
Solution · Answer
satisfies , so is symmetric. If then by the Hessenberg property, and by symmetry with , so whenever . Hence is tridiagonal.
Exercise 5.6.11
(For show that the shift , the other eigenvalue, also deflates in one step.)
Core
Compute the QR step with a Givens rotation.
Solution(3)
- 1
Form the shifted matrix
- 2
Choose the rotation that zeros the subdiagonal entry
Key step
Because: With and the rotation sends to .
- 3
Multiply back and add the shift
The subdiagonal entry is zero and both eigenvalues appear on the diagonal.
Quick check
(Prove that if for an upper Hessenberg , then the spectrum of is the union of the spectra of its leading block and trailing block.)
What shape does have when ?
Solution · Answer
If , then all entries below the diagonal in rows and columns vanish (the Hessenberg structure already gives zeros for ), so . The determinant of a block upper triangular matrix is the product of the determinants of its diagonal blocks, so , and its roots are the roots of the two factors.
Exercise 5.6.12
(For and , use the last-column formula to compute exactly, and check against the tridiagonal worked example.)
Core
Here is symmetric, so .
Solution(3)
- 1
Solve one linear system
Solve . The third equation gives ; the first, , gives ; the second, , gives .
Because: The theorem expresses through .
- 2
Apply the norm formula
Key step
which matches the last diagonal entry of the computed .
- 3
Compare with the subdiagonal entry
The entry is with , so .
Quick check
(A dense QR step on an matrix costs on the order of operations and a Hessenberg QR step on the order of . For compare the orders of magnitude, ignoring constants, and explain what is saved when each of the eigenvalues needs a few steps.)
Sum the cost over the shrinking active block.
Solution · Answer
For one has and , a ratio of . If each of the eigenvalues needs a few steps (the active block shrinks as eigenvalues deflate), the Hessenberg iteration costs of the order of in total, while dense steps would cost of the order of . The saving is a factor of order , at the price of a one-off reduction cost of order .