Jacobi’s Method

    Jacobi’s method is an easily understood algorithm for finding all eigenpairs for a symmetric matrix. It is a reliable method that produces uniformly accurate answers for the results. For matrices of order up to 10×10, the algorithm is competitive with more sophisticated ones. If speed is not a major consideration, it is quite acceptable for matrices up to order 20×20. A solution is guaranteed for all real symmetric matrices when Jacobi’s method is used. This limitation is not severe since many practical problems of applied mathematics and engineering involve symmetric matrices. From a theoretical viewpoint, the method embodies techniques that are found in more sophisticated algorithms. For instructive purposes, it is worthwhile to investigate the details of Jacobi’s method.  

Jacobi Series of Transformations

    Start with the real symmetric matrix  . Then construct the sequence of orthogonal matrices    as follows:

        
    and
           for   j = 1, 2, ...  .

It is possible to construct the sequence   so that

        .  

In practice we will stop when the off-diagonal elements are close to zero. Then we will have

        .  

Proof  Jacobi's Method   Jacobi's Method   

Remark.  Current research by James W. Demmel and Kresimir Veselic (1992) indicate that Jacobi's method is more accurate than QR.  You can check out their research by following the link in the list of internet resources.  The abstract for their research follows below.

Abstract.  We show that Jacobi's method (with a proper stopping criterion) computes small eigenvalues of symmetric positive definite matrices with a uniformly better relative accuracy bound than QR, divide and conquer, traditional bisection, or any algorithm which first involves tridiagonalizing the matrix. In fact, modulo an assumption based on extensive numerical tests, we show that Jacobi's method is optimally accurate in the following sense: if the matrix is such that small relative errors in its entries cause small relative errors in its eigenvalues, Jacobi will compute them with nearly this accuracy. In other words, as long as the initial matrix has small relative errors in each component, even using infinite precision will not improve on Jacobi (modulo factors of dimensionality). ...

Computer Programs Jacobi's Method   Jacobi's Method   

Mathematica Subroutine (Jacobi iteration for eigenvectors).  To compute the full set of eigen-pairs    of the  n by n  real symmetric matrix  A.  Jacobi iteration is used to find all eigenvalue-eigenvector pairs.  

Example 1.  Use the classic Jacobi method to find all the eigenvalues and eigenvectors of the symmetric matrix  .  
Solution 1.

Example 2.  Use the cyclic Jacobi method to find all the eigenvalues and eigenvectors of the symmetric matrix  .  
Solution 2.

Example 3.  Determine which method is faster: the original Jacobi method or the cyclic Jacobi method.
The statement in the text says that the search for the maximum element becomes time consuming.
However, it might be the computation of    for each step which is time consuming.  
Solution 3.

Example 4.  How fast are our subroutines compared to Mathematica's ?
Solution 4.

Example 5.  Since the cyclic Jacobi method seems faster, we should mention that calling the subroutine costs time.
We could put it all together in one part and it will be faster.  
However, Mathematica, Maple, Matlab are all in some sense interpreted languages such as BASIC.  
Because the instruction code we write is not compiled.  Complied languages such as FORTRAN and C will always be the fast ones.
Solution 5.

Example 6.  An eigenvalue movie.  Cleve Moler, inventor of the software used graphs to illustrate convergence of eigenvalues.  In Matlab, eigmovie(A), shows a "movie" that depicts the computation of the eigenvalues of a symmetric matrix.  (Cleve Moler is chairman and cofounder of The MathWorks.)   The following Mathematica animation has the "spirit" of Cleve "eigmovie."
Solution 6.

Research Experience for Undergraduates

Jacobi's Method   Jacobi's Method  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Jacobi Iteration for Eigenvectors

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004