Programming assignment 10
The shifted QR algorithm
In class, we saw a version of the QR algorithm that started with a symmetric, tridiag-
onal matrix A and successively found Ak = QkAk−1QT
k so that the off-diagonal elements
of Ak converge to 0. The eigenvalues of A then appear on the diagonal.
In this assignment, we’re going to speed up the convergence of the sequence Ak. Let’s
assume we have the tridiagonal matrix
A =
a1 b2 0 0 . . . 0 0
b2 a2 b3 0 . . . 0 0
0 b3 a3 b4 . . . 0 0
… … … … . . . … …
0 0 0 0 . . . an−1 bn
0 0 0 0 . . . bn an
So ak = Ak,k and bk = Ak−1,k. If bn = 0, then the matrix has the form
A =
[A′ 0
0 an
]
which shows us that an is an eigenvalue and that we can focus on finding the eigenvalues
of the (n − 1) × (n − 1) matrix A′. So our goal will be to perform QR steps to make bn = 0.
We will use λ1, λ2, . . . , λn to denote the eigenvalues of A. With some work, we could
see that the rate at which bn → 0 in the QR algorithm is proportional to
∣
∣
∣ λn
λn−1
∣
∣
∣. To speed up
convergence, we will form an estimate of λn, which we call σ, and then consider A − σI,
whose eigenvalues are λj − σ. In this matrix, bn converges to 0 at a rate proportional to∣
∣
∣ λn−σ
λn−1−σ
∣
∣
∣. If σ ≈ λn, then λn − σ is close to zero, which means the convergence will be
rapid. To recover the eigenvalues of A, we add σ to the eigenvalues of A − σI.
Here’s how we form σ, our estimate to λn. An easy way to estimate λn is just using the
entry an = An,n. But a better estimate would be to consider the 2 × 2 matrix in the lower
right corner: [an−1 bn
bn an
]
and find its eigenvalues, which are
(an−1 + an) ± √(an−1 − an)2 + 4b2
n
2 .
Choose σ to be the eigenvalue of the 2 × 2 matrix that is closest to an.
Here’s how the algorithm works then. We input an n×n symmetric, tridiagonal matrix
A and a tolerance .1. Set a variable shift = 0.
2. Find σ using the recipe above.
3. Redefine A = A − σI and shift = shift + sigma.
4. Perform one step of the QR method redefining A = QAQT using your previous
code.
5. If |bn| < , then an is an eigenvalue of the shifted matrix. Recursively, find the
eigenvalues of A′, the (n − 1) × (n − 1) matrix in the upper left corner of A and
combine them with an. Add shift to all the eigenvalues and return.
6. If |bn| ≥ , go back to step 2 and repeat.
Goal: Your goal is to write a function QR(A, tolerance) whose input parameters are
an n × n symmetric, tridiagonal matrix A and a desired tolerance for the off-diagonal
elements. Your function should return a list of eigenvalues of A.
Some things to take note of:
• A[:k, :k] will give you the k × k matrix in the upper left corner of A.
• The last entry in a list l is l[-1] and the second to last is l[-2]. That means that
A[-1,-1] is the entry in the lower right corner.
• How do you find the eigenvalue of a 1 × 1 matrix? This is the final step in the
recursion.
A good example to test is the 9 × 9 matrix that computes a discrete approximation
to the second derivative of a function (2’s on the diagonal and -1’s on the tridiagonal).
Check your results against np.linalg.eig(A)[0].
If you count the number of steps, you should find convergence is incredibly fast. For
instance, with a tolerance of 10−4 and using the 9 × 9 second-derivative matrix A, about
15 total steps are required, which is amazing.
Remember when we looked at rates of convergence earlier and saw that fixed point
iteration is linear and Newton’s method is quadratic? This method is cubic, which is very
rare and very wonderful. Due to its rapid convergence, this algorithm was named one of
the 10 most important algorithms of the 20th century.
http://pi.math.cornell.edu/ ̃ajt/presentations/TopTenAlgorithms.pdf
ASSIGNMENT COMPLETED AT CapitalEssayWriting.com
MAKE YOUR ORDER AND GET THE COMPLETED ORDER
CLICK HERE TO ORDER THIS PAPER AT CapitalEssayWriting.com ON input an n×n symmetric, tridiagonal matrix