Jacobi eigenvalue algorithm

The Jacobi method ( according to Carl Gustav Jacob Jacobi ( 1846) ) is an iterative method for the computation of all eigenvalues ​​and eigenvectors (small ) symmetric matrices.

Description

Since the output matrix is assumed to be symmetric, it is orthogonally similar to a diagonal matrix

The diagonal of the eigenvalues ​​of containing and columns the corresponding eigenvectors.

The idea of ​​the Jacobi method is to bring the largest amount each off-diagonal element by means of a Givens rotation to 0, and to approach in this way more and more of a diagonal matrix. This results in the iteration

With

Stand where and are respectively in the -th and -th row and column, and is the largest off-diagonal element of amount. The components of now arise from the following consideration:

The transformation causes especially in the crossing elements following changes:

Since the rotation matrices are orthogonal and orthogonal matrices are orthogonal products again an orthogonal similarity transformation will be described in this way. It can be shown that the sequence of matrices converges to a diagonal matrix. This must be due to the similarity have the same eigenvalues.

Classic and cyclic Jacobi method

In the classical Jacobi method, the maximum absolute element is set to zero in each iteration. As the search for this the main effort of the algorithm is to apply the cyclic Jacobi method in each iteration depending Given a rotation to each element of the strict upper triangle.