Homework 3

1. Add shifts to the QR algorithm

Instead of factoring $A_k$ as $Q_k R_k$ (the way the pure QR algorithm without shifts does), the shifted QR algorithms:

i. Get the QR factorization $$A_k - s_k I = Q_k R_k$$ ii. Set $$A_{k+1} = R_k Q_k + s_k I$$

Choose $s_k = A_k(m,m)$, an approximation of an eigenvalue of A.

The idea of adding shifts to speed up convergence shows up in many algorithms in numerical linear algebra (including the power method, inverse iteration, and Rayleigh quotient iteration).

In [1]:
def practical_qr(A, iters=10):
    # Fill method in
    return Ak, Q
In [ ]: