Jacobi Iteration for Eigenvectors
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
Start with the real symmetric matrix . Then construct the sequence of orthogonal matrices as follows:
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
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
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 .
Example 2. Use the
cyclic Jacobi method to find all the eigenvalues and eigenvectors of
the symmetric matrix .
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.
Example 4. How fast
are our subroutines compared to Mathematica's ?
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.
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."
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