Rayleigh shift failes for QR algorithm

  algorithm, linear-algebra, numerical-methods, python

I have a task of implementing QR algorithm with Rayleigh shift.
Here is the algorithm:

def qr_algorithm_reileigh(A_init, num_iter):
    """
        QR algorithm without shifts
        input: matrix A_init of size n x n to find its eigenvalues 
               num_iter number of iterations for algorithm to run 
    """
    convergence = np.empty(num_iter)
    Ak = A_init
    for i in np.arange(num_iter):
        mu = Ak[-1, -1]
        Ak = Ak - mu * np.eye(Ak.shape[0])
        Q, R = scipy.linalg.qr(Ak)
        Ak = R @ Q + mu * np.eye(Ak.shape[0])
        convergence[i] = scipy.linalg.norm(np.triu(Ak, 1), ord=np.inf)
    return Ak, convergence

When I try to use it for tridiagonal matrix with 2 on diagonal and 1’s on subdiagonals, it fails (Chebyshev norm of upper subdiagonal doesn’t decrease). What is the problem with my code?

Source: Python Questions

LEAVE A COMMENT