**QR method and eigenvalues**I'm currently working on a course of numerical analysis for my students, and I've realized (using scilab software) a short animation to help them understanding how the QR method works .

**The QR method is a fast algorithm for computing matrix eigenvalues** . It is based on the QR decomposition of a matrix A : a factorization A=Q*R where R is upper-triangular and Q is orthogonal. The QR decomposition can be obtained from Gram-Schmidt process applied to column vectors of A. Then the QR method can be implemented in a very simple way :

*compute QR decomposition of A**replace A by R*Q**repeat until R be sufficiently**close to a upper-triangular matrix*In the gif below

**you can visualize the behavior of matrix coefficients : the absolute value of each cell is represented by a color (black/deep blue for low values, red/white for hight ones) and you can see that quickly the matrix tends to be upper-triangular with values sorted in decreasing order on its diagonal which are the eigenvalues of A** . The explanation is that at each step of the algorithm , the new matrix A is similar to the old one, because R*Q=Q'*A*Q, so they have the same spectrum which corresponds to diagonal values for a triangular matrix. Note also that the sequence of Q matrix tends to a diagonal matrix with +1 or -1 diagonal values, The error value is the norm || Id(i,j) - |Q(i,j)| || is close to the relative error on eigenvalues, and is a good stopping criteria for the algorithm's loop.

#mathematics #eigenvalue #matrix #scilab See also :

http://en.wikipedia.org/wiki/QR_algorithmhttp://en.wikipedia.org/wiki/QR_decomposition