Monday, February 1, 2010

Jacobi 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
[Graphics:Images/JacobiMethodMod_gr_1.gif]. Then construct the sequence of orthogonal matrices [Graphics:Images/JacobiMethodMod_gr_2.gif] as follows:

[Graphics:Images/JacobiMethodMod_gr_3.gif]
and
[Graphics:Images/JacobiMethodMod_gr_4.gif] for j = 1, 2, ... .

It is possible to construct the sequence [Graphics:Images/JacobiMethodMod_gr_5.gif] so that

[Graphics:Images/JacobiMethodMod_gr_6.gif].

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

[Graphics:Images/JacobiMethodMod_gr_7.gif].


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.

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). ...

No comments:

Post a Comment

Introductory Methods of Numerical Analysis