The Jacobi Method

The Jacobi method is probably the simplest diagonalization method that is well adapted to computers. It is limited to real symmetric matrices, but that is the only kind we will get by the formula for generating simple Huckel molecular orbital method (HMO) matrices just described. A rotation matrix is defined, for example. 

Let us follow the first few iterations for the allyl system by hand calculations. We subtract the matrix xl from the HMO matrix to obtain the matrix we wish to diagonalize, just as we did with ethylene. With the rotation block in the upper left conrer of the R matrix (we are attacking an and aai), we wish to find 

By the simple HMO procedure, it is always true that sin 6 = cos 0 = 0.7071 on the first iteration. Now, to eliminate an. 

Because both matrix A and the transformation are symmetrical, reducing the an element to zero also reduces aai to zero. We have gained the zeros we wanted, but we have sacrificed the zeros we had in the 1,3 and 3,1 positions. Other than those eliminated, the off-diagonal elements are no longer zero but they are less than one. Attacking the an = = 0.7071 element produces 

In conclusion of this section, it is remarkable that molecular orbitals are never really used in Huckel theory, that is, the integrals ot and p are not evaluated. Huckel 

---

Having filled in all the elements of the F matr ix, we use an iterative diagonaliza-tion procedure to obtain the eigenvalues by the Jacobi method (Chapter 6) or its equivalent. Initially, the requisite electron densities are not known. They must be given arbitrary values at the start, usually taken from a Huckel calculation. Electron densities are improved as the iterations proceed. Note that the entire diagonalization is carried out many times in a typical problem, and that many iterative matrix multiplications are carried out in each diagonalization. Jensen (1999) refers to an iterative procedure that contains an iterative procedure within it as a macroiteration. The term is descriptive and we shall use it from time to time. 

The conditions required by the dominant-diagonal theorem are sufficient to assure convergence of the Jacobi method. In certain important applications it happens that also A2 0. In that event all three methods converge, Jacobi the most slowly. 

The eigenvalues of A can be find by solving the characteristic equation of (1.61). It is much more efficient to look for similarity transformations that will translate A into the diagonal form with the eigenvalues in the diagonal. The Jacobi method involves a sequence of orthonormal similarity transformations, 12,... such that A(<+1 = TTkAkTk. The matrix Tk differs from the identity... 

In the Jacobi method, a series of similarity transformations is carried out. It is easily proven that similar matrices have the same eigenvalues. Let A = P, BP. The eigenvalues of A satisfy the secular equation (2.38) ... 

The Jacobi method is generally slower than these other methods unless the matrix is nearly diagonal. In SCF calculations one is faced with the non-orthogonal eigenvalue equation... 

Usually on the first iteration of an SCF calculation W is computed by the Schmidt orthogonalization method but thereafter W is chosen to be the C matrix from the previous iteration. This produces an F matrix which is nearly diagonal so the Jacobi method becomes quite efficient after the first iteration. Further, in the Jacobi method, F is diagonalized by an iterative sequence of simple plane-rotation transformations... 

The Jacobi method is traditional (first presented 1846) and simple. More efficient general methods were not found until 1954 (W. Givens, Oak Ridge), and some special features make it the first choice for many applications still today. In order to describe the method in more detail, consider the problem of finding a solution A,V to the problem... 

The Jacobi method works by successively transforming the matrices A and v in place , in a way which ensures that the non-diagonality measure... 

In the Jacobi method, we rearrange the system of equations to place the contribution due to Xj on the LHS of the fth equation and the other terms on the RHS, and we divide both sides of the equation by an. The iteration equation for the Jacobi method is written as ... 

Iterative methods are sometimes used due to ease of computer coding and lesser computational storage requirements. The Jacobi method is the simplest iterative method but has slower convergence in comparison with the Gauss-Seidel method. In the Gauss-Seidel method, the (A -tl)th iteration of the value of the unknown x, is given by... 

Another sufficient condition for the convergence of the Jacobi method of iteration follows. Let R be the set of all starting vectors X0 for which the largest Hilbert norm of any matrix B generated by the iterative process has the property that... 

Show that if the conditions given by Eq. (15-27) are satisfied, then convergence can be assured for the Jacobi method of iteration. 

Transform each pair of oif-diagonal elements to zero in turn, subsequent transformations may regenerate elements, the method is iterative the Jacobi method-... 

The processes involved in all these methods can be appreciated by a detailed look at the Jacobi method which is extremely simple in concept and implementation. 

The advantages of the Jacobi method, in addition to its simplicity are obvious ... 

The method which has been implemented to generate the eigenvalues and eigenvectors of a real symmetric matrix is not, in fact, the fastest method there are methods which have asymptotic dependence on floating point operations, while the Jacobi method depends asymptotically on m. f77 implementations of these methods (the Givens and Householder methods) are available for most computers and calls to eigen may be simply replaced by corresponding calls to the other routine. 

The implementation of the Jacobi method is straightforward all that is necessary are the steps ... 

Equations (17) and (19), with the appropriate boundary conditions, were solved numerically to determine the insulation pressure and temperature distributions. The method of solution chosen was essentially the Jacobi method, where all the derivatives of a previous iteration are used in any given iteration. Vertical variation of the effective thermal conductivity was then determined from the temperature distribution. 

While the polynomial method can be used for solving small eigenvalue problems by hand, all computational implementations rely on iterative similarity transform methods for bringing the matrix to a diagonal form. The simplest of these is the Jacobi method, where a sequence of 2 x 2 rotations analogous to eqs (16.28)-(16.30) can be used to bring all the off-diagonal elements below a suitable threshold value. 

In the Jacobi method, the iterated vector of the (k + l)th iteration is obtained based entirely on the vector of the previous iteration, that is, The Gauss-Seidel iteration method is similar to the Jacobi method, except that the component for = 1, 2,1 are used immediately in the calculation of the component The iteration equation for the Gauss-Seidel... 

Like the Jacobi method, the Gauss-Seidel method requires diagonal dominance for the convergence of iterated solutions. 

Theorem The successive overrelaxation method with optimum relaxation factor converges at least twice as fast as the Chebyshev semi-iterative method with respect to the Jacobi method, and therefore at least twice as fast as any semi-iterative method with respect to the Jacobi method. Furthermore, as the number of iterations tends to infinity, the successive overrelaxation method becomes exactly twice as fast as the Chebyshev semi-iterative method. 

It should be mentioned that the Jacobi method for diagonalizing N x N matrices is a generalization of the above procedure. The basic idea of this method is to eliminate iteratively the off-diagonal elements of a matrix by repeated applications of orthogonal transformations, such as the ones we have considered here. 

Another in the class of iterative procedure is the Jacobi method. This method is illustrated by solving the following system ... 

Notice that one difference between the Gauss-Seidel and Jacobi methods is in their use of the newly calculated x, value. In Gauss-Seidel, the newly calculated x, value is used to determine the x,+i value, but this is not so in the Jacobi method. In most cases, this leads to faster convergence of the Gauss-Seidel over the Jacobi method. Generally, iteration methods are most useful for large matrices with a substantial number of zero elements. 

---