| [ Home ] | Matrix Diagonalization. Eigensystems. | Numerical Methods. Note « 4 » |
Diagonalization. A vector v is called an eigenvector of a matrix A with an eigenvalue λ, if Av=λv}. Matrix diagonalization means finding all eigenvalues λi and (optionally) eigenvectors vi of the matrix A. If A is hermitian then its eigenvalues are real and its eigenvectors V={v1,...,vn} form a full basis in which the matrix A is diagonal VTAV=diag{λ1,...,λn}.
Orthogonal/Similarity transformations A→QTAQ, where QTQ=1, and generally similarity transformations A→S-1AS, preserve eigenvalues and eigenvectors. Therefore one of the strategies is to apply a sequence of orthogonal/similarity transformations which (iteratively) turn the matrix into diagonal or triangular form.
QR/QL algorithm. If we know QR (or QL) decomposition of real symmetric matrix A, then the orthogonal transformation A → QTAQ=RQ partly turns the matrix A into diagonal form. Successive iterations eventually make it diagonal. If there are degenerate eigenvalues there will be a corresponding block-diagonal sub-matrix. For convergence properties it is better to use shifts: instead of QR[A] we do QR[A-s1] and then A → RQ+s1. The shift s can be chosen as Ann. As soon as an eigenvalue is found the matrix is deflated, that is the corresponding row and column are crossed out.
Eigenvectors. If one accumulates the the successive transformation matrices Qi, i=1..n, into the total matrix Q=QnQn-1..Q1, such that QTAQ = diagonal matrix, then one has all the eigenvectors as columns of the Q matrix. If only one (or few) eigenvector vk is needed one can instead solve the (singular) system (A-λkx⋅1)x=0.
Tridiagonalization. Each iteration of the QR/QL is an O(n3) operation. On a tridiagonal matrix it is only O(n). Therefore the effective strategy is first to make the matrix tridiagonal and then apply the QR/QL algorithm. Tridiagonalization of a matrix is a non-iterative operation with a fixed number of steps.
Problems