I LOVE METHODS: 5.5 JACOBI'S METHOD

This method had been consigned to history until the advent of parallel computing, but has now acquired a new lease of life. It uses a sequence of similarity transformations with plane rotation matrices, each one of which makes a larger than average off-diagonal element (and its transpose) zero. This unfortunately destroys previous zeros, but nevertheless reduces the sum of the off-diagonal elements, so that convergence to a diagonal matrix occurs.

The orthogonal matrix

$\begin{displaymath}P=\left[ \begin{array}{ccccccccccc} 1 & \cdots & \cdot & \cd... ...t]\begin{array}{c} \\ \\ s \\ \\ \\ \\ t \\ \\ \\ \end{array}, \end{displaymath}$

where the non-standard elements are in rows and columns s and t, and real $\phi$ is chosen so that b_st=0, with [b_ij]=B=P^TAP. The elements of AP are given for $k=1,2,\ldots ,n$ by

$\begin{eqnarray*}[AP]_{ks} & = & a_{ks}\cos \phi -a_{kt}\sin \phi \\ [0pt] [AP]_... ...{kt}\cos \phi \\ [0pt] [AP]_{kj} & = & a_{kj}, \quad j\not= s,t. \end{eqnarray*}$

Premultiplying by P^T we find in particular that

$\begin{displaymath}b_{st}=\frac{1}{2}(a_{ss}-a_{tt})\sin 2\phi +a_{st}\cos 2\phi , \end{displaymath}$

and this is zero if

$\begin{displaymath}\tan 2\phi =\frac{2a_{st}}{a_{tt}-a_{ss}}. \end{displaymath}$

We could simply compute the sum of the squares of the off-diagonal elements, but we prefer a more roundabout approach.

Lemma 10.5.3 If B=P^TAP, where P is orthogonal, then trace B= trace A and trace B^TB= trace A^TA.

Proof. The trace of a matrix is the sum of its eigenvalues, and A and B have the same eigenvalues, which proves the first part.

Also B^TB=(P^TAP)^TP^TAP=P^TA^TPP^TAP=P^T(A^TA)P, and the first result now gives the second.

Now

$\begin{displaymath}\sum _{i=1}^n\sum _{k=1}^n a_{ki}^2=\mbox{trace}~ A^TA=\mbox{trace}~ B^TB=\sum _{i=1}^n\sum _{k=1}^n b_{ki}^2. \end{displaymath}$

In the case where $A=\left[ \begin{array}{ll}a_{ss} & a_{st}\\ a_{st} & a_{tt}\end{array} \right]$ , P^TAP=B gives

a_ss²+2a_st²+a_tt²=b_ss²+b_tt².

But each of these elements is just the same as in the $n\times n$ case, so is true in this case also. Since a_ii=b_ii for all values of i except sand t, we have

$\begin{displaymath}\sum _{i=1}^na_{ii}^2+2a_{st}^2=\sum _{i=1}^nb_{ii}^2, \end{displaymath}$

so the sum of the squares of the diagonal elements is increased by the transformation by an amount 2a_st². we now see that

$\begin{displaymath}\sum _{i\not= j}b_{ij}^2=\sum _{i\not= j}a_{ij}^2-2a_{st}^2, \end{displaymath}$

where the sums are over all values of i,j which are not equal, that is over all off-diagonal elements.

If we choose a_st so that $a_{st}^2\geq \frac{\sum _{i\not= j}a_{ij}^2}{n^2-n}$ , that is, so that it is greater than average, we have

$\begin{displaymath}\sum _{i\not= j}b_{ij}^2\leq \left( 1-\frac{2}{n^2-n}\right) \sum _{i\not= j}a_{ij}^2, \end{displaymath}$

and the sum of the off-diagonal elements converges to zero with convergence factor $1-\frac{2}{n^2-n}$ . This is unfortunately close to 1 for large matrices.

Suppose the sequence of transformations is given by

$\begin{displaymath}B_{m+1}=P_m^TB_mP_m,\quad m=0,1,\ldots , \end{displaymath}$

with B₀=A, and P_m chosen as above. Then B_m converges to a diagonal matrix whose elements are the eigenvalue sof A. When we have reached a sufficient degree of convergence, say for m=M, we have

$\begin{displaymath}B_M=P_M^TP_{M-1}^T\ldots P_0^TAP_0P_1\ldots P_M=Q_M^TAQ_M, \end{displaymath}$

say, and the eigenvectors of A are approximated by the columns of Q_M.

27 julio 2010

JACOBI'S METHOD