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}](http://www.maths.lancs.ac.uk/~gilbert/m306c/img259.gif)
where the non-standard elements are in rows and columns s and t, and real


![\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*}](http://www.maths.lancs.ac.uk/~gilbert/m306c/img261.gif)
Premultiplying by PT we find in particular that

and this is zero if

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=PTAP, where P is orthogonal, then trace B= trace A and trace BTB= trace ATA.
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 BTB=(PTAP)TPTAP=PTATPPTAP=PT(ATA)P, and the first result now gives the second.
Now
In the case where
![$A=\left[ \begin{array}{ll}a_{ss} & a_{st}\\ a_{st} &
a_{tt}\end{array} \right]$](http://www.maths.lancs.ac.uk/~gilbert/m306c/img265.gif)
But each of these elements is just the same as in the


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

where the sums are over all values of i,j which are not equal, that is over all off-diagonal elements.
If we choose ast so that
, that is, so that it is greater than average, we have


and the sum of the off-diagonal elements converges to zero with convergence factor

Suppose the sequence of transformations is given by

with B0=A, and Pm chosen as above. Then Bm 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

say, and the eigenvectors of A are approximated by the columns of QM.
No hay comentarios:
Publicar un comentario