The Deflation Method for Finding Eigenvalues and Eigenvectors

The method of deflation proceeds by finding the largest eigenvalue by iteration, then reducing the  
\[n \times n\]
  matrix to an  
\[(n-1) \times (n-1)\]
  matrix, finding the largest eigenvalue of this matrix, reducing the matrix to an  
\[(n-2) \times (n-2)\]
  matrix, and so on.
Let  
\[A\]
  be an  
\[n \times n\]
  matrix with largest eigenvalue  
\[\lambda_1\]
  and associated eigenvector  
\[\mathbf{v}_1\]
. If  
\[\mathbf{v}_1\]
  does not have 1 as the component of largest modulus, multiply  
\[\mathbf{v}_1\]
  by a permutation matrix  
\[P\]
  which interchanges the largest element and the first element. Suppose  
\[P \mathbf{v}_1 = \mathbf{w_1}\]
. We must find an elementary matrix  
\[R\]
   
\[R \mathbf{w}_1= \mathbf{e}_1\]
, the elementary vector with first component 1 and all other components 0.
Let  
\[B=RPAP^{-1}R^{-1}=RPAPR^{-1}\]

Then
 
\[\begin{equation} \begin{aligned} B \mathbf{e}_1 &= RPAPR^{-1} \mathbf{e}_1 \\ &=RPAP \mathbf{w}_1 \\ &=RPA \mathbf{v}_1 \\ &=\lambda_1 RP \mathbf{v}_1 \\ &=\lambda_1 \mathbf{e}_1 \end{aligned} \end{equation}\]

Thus  
\[\mathbf{e}_1\]
  is an eigenvector of  
\[B\]
  with eigenvalue  
\[\lambda_1\]
  and  
\[B\]
  must be upper triangular with  
\[\lambda_1\]
  as the first element on the leading diagonal.
\[B=\left( \begin{array}{ccc} \lambda_1 & \dots & x^1 \\ \vdots & \ddots & \vdots \\ 0 & \dots & x^n \end{array} \right)\]

Delete the first column and row to give an  
\[(n-1) \times (n-1)\]
  matrix  
\[B_1\]
.
\[A, \: B\]
  are similar so have the same eigenvalues  
\[\lambda_1, \: \lambda_2, \: \lambda_3, ..., \: \lambda_n\]
. The eigenvalues  
\[ \lambda_2, \: \lambda_3, ..., \: \lambda_n\]
  are eigenvalues of the  
\[(n-1) \times (n-1)\]
  matrix  
\[B_1\]
.
We can find  
\[RPA\]
  by elementary row operations on  
\[A\]
.  
\[B=RPAP^{-1}R^{-1}\]
  can then be found by applying  
\[P^{-1}\]
  and  
\[R^{-1}\]
  to the columns of  
\[RPA\]

Let  
\[A=\left( \begin{array}{ccc} 0 & 5 & -6 \\ -4 & 12 & -12 \\ -2 & -2 & 10 \end{array} \right)\]

The largest eigenvalue of  
\[B\]
  is  
\[\lambda_1=16\]
  with corresponding eigenvector  
\[\mathbf{v}_1 = \begin{pmatrix}1\\2\\-1\end{pmatrix} \]

Interchange rows 1 and 2 of  
\[A\]
, which will make 1.0 the first component of  
\[\mathbf{v}_1\]

\[\left( \begin{array}{ccc} -4 & 12 & -12 \\ 0 & 5 & -6 \\ -2 & -2 & 10 \end{array} \right)\]

Subtract half of row 1 from row 2 and add half of row 1 to row 3, transforming  
\[\mathbf{v}_1\]
  into  
\[\mathbf{e}_1\]

\[\left( \begin{array}{ccc} -4 & 12 & -12 \\ 2 & -1 & 0 \\ -4 & 4 & 4 \end{array} \right)\]

Interchange columns 1 and 2.
\[\left( \begin{array}{ccc} 12 & -4 & -12 \\ -1 & 2 & 0 \\ 4 & -4 & 4 \end{array} \right)\]

The deflated matrix is  
\[\left( \begin{array}{cc} 2 & 0 \\ -4 & 4 \end{array} \right)\]

Using the iteration method for  
\[B\]
  returns the eigenvalue  
\[\lambda_2=4\]
  and the eigenvector of  
\[A\]
  is  
\[\mathbf{v}_2= \begin{pmatrix}1\\2\\1\end{pmatrix}\]

Deflating the matrix  
\[B_1\]
  gives  
\[\left( \begin{array}{cc} 4 & -4 \\ 0 & 2 \end{array} \right)\]
  then  
\[B_2=\left( \begin{array}{c} 2 \end{array} \right)\]

The eigenvalue= is  
\[\lambda_3=2\]
  then and the eigenvector, using  
\[A\]
  is 
\[\begin{pmatrix}2\\2\\1\end{pmatrix}\]
.

Add comment

Security code
Refresh