2
$\begingroup$

I tried to compute eigen values with the QR-algorithm found here (there is also a wikipedia page also)

import numpy as np

def qr_algorithm(A, tol=0.000001):
    Q, R = np.linalg.qr(A)
    previous = np.empty(shape=Q.shape)
    for i in range(500):
        previous[:] = Q
        X = R @ Q
        Q, R = np.linalg.qr(X)
        if np.allclose(X, np.triu(X), atol=tol): 
            break
    return Q

A = np.array([[0,1,-2],[0,1,0],[1,-1,3]])

result = qr_algorithm(A)

In order to compute the eigenvalues of the matrix

$A=\begin{bmatrix}0&1&-2 \\ 0&1&0\\ 1&-1&3\end{bmatrix}$

which by hand we can see are 1,1,2, however I find in the end the Q-matrix

array([[-1.00000000e+00, -2.75303331e-07,  3.89337518e-07],
       [ 2.75303418e-07, -1.00000000e+00,  2.24783835e-07],
       [ 3.89337456e-07,  2.24783942e-07,  1.00000000e+00]])

which diagonal don't correspond to the eigenvalues. What is going on here?

$\endgroup$
2
  • $\begingroup$ Can you check what happens after one iteration of the algorithm rather than 500? Are the eigenvalues preserved? $\endgroup$ Sep 9, 2022 at 15:50
  • 1
    $\begingroup$ Your break condition is only valid if all eigenvalues are real and pairwise different. In the case of multiplicities or complex pairs of eigenvalues you get diagonal blocks that do not converge and change in every iteration. Multiplicities will likely resolve due to numerical instability, but the entries of the corresponding block will only converge very very slowly. $\endgroup$ Sep 10, 2022 at 8:39

1 Answer 1

4
$\begingroup$

You are returning Q instead of X.

$\endgroup$
1
  • $\begingroup$ thanks, I am going to try this as soon as I have a grab on python $\endgroup$
    – roi_saumon
    Sep 9, 2022 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.