# Iterative Matrix Techniques Based on Averages
## 2 Averaged Power Method for Finding Eigenvalues and Eigenvectors of a Matrix
A useful criterion to stop the algorithm is to check that \(||AX_{n+1}-\lambda_{n+1}X_{n+1}||<\varepsilon\) for some tolerance \(\varepsilon\), or \(|\lambda_{n+1}-\lambda_{n}|<\varepsilon\). The last value \(\lambda_{k}\) is an approximation of an eigenvalue of \(A\) and \(X_{k}\) is the corresponding eigenvector. In order to justify the suitability of the algorithm, we will consider the simplest case of the Krasnoselskii iteration:  
\[A^{k}(x,y)=(x,-y),\]1  
for \(0<\alpha<1\). Let us denote \(B:=(1-\alpha)I+\alpha A\). It is easy to check that  
\[A^{k}(x,y)=(x,-y),\]2  
and the eigenvectors of \(B\) and \(A\) agree, that is to say, \(X\) is an eigenvector of \(A\) with respect to an eigenvalue \(\lambda\), if and only if \(X\) is an eigenvector of \(B\) with eigenvalue \((1-\alpha)+\lambda\alpha\). Let us assume that \(A\) has positive and negative eigenvalues with the same absolute value. Then, \(|(1-\alpha)+\alpha\lambda|\leq(1-\alpha)+\alpha\lambda^{*}\) for the positive eigenvalue \(\lambda^{*}\). For a negative eigenvalue \(\lambda:|(1-\alpha)+\alpha\lambda|<(1-\alpha)+\alpha\lambda^{*}\) and, consequently, \((1-\alpha)+\alpha\lambda^{*}\) is a dominant eigenvalue of \(B\). Hence, the power method applied to the matrix \(B\) will converge to an eigenvector of \(B\) (and thus of \(A\)), if the component of \(X_{0}\) with respect to this eigenvector is non-null. The power method is based on the product of a matrix \(A\in\mathcal{M}(m\times m)\) and a vector. This operation has a complexity \(\mathcal{O}(m^{2})\). If the number of iterations is \(n_{max}\), the complexity is \(\mathcal{O}(n_{max}m^{2})\). For a large matrix, the averaging operations of the N-algorithm proposed are negligible, and the complexity is \(\mathcal{O}(2n_{max}m^{2})\). Though the operations involved are about twice as many as in the original power method, the type of convergence (polynomial of degree 2) is not modified. If one wishes to reduce the total number of operations, the use of constant weight coefficients is advisable, and the algorithm is able to be conveniently optimized. The speed of convergence of the power method (and consequently the number of iterations required to give a good approximation) depends on the ratio \(|\lambda_{2}|/|\lambda_{1}|\), where \(\lambda_{1},\lambda_{2}\) are the greatest eigenvalues in magnitude. The smaller is this quotient, while the faster is the convergence. In the averaged Mann-Krasnoselskii method, this \"spectral gap\" is \(|1-\alpha-\alpha\lambda^{*}|/(1-\alpha+\alpha\lambda^{*})\), where \(\lambda^{*}\) is the positive eigenvalue. For instance, if \(\alpha=1/2\), minimum quotients are reached for values of \(\lambda^{*}\) close to 1. **Example 2**. : _Considering the matrix of Example 1,_  
\[A= \begin{pmatrix}1&0\\ 0&-1\end{pmatrix} \]  
_we obtain that for \(X_{0}=(x,y)\), \(x\
eq 0\), the Krasnoselskii method with \(\alpha=1/2\) gives as first approximation_  
\[X_{1}=(X_{0}+AX_{0})/2=(x,0),\]  
_and the rest of iterations agree with the eigenvector \((x,0)\). The positive eigenvalue is computed as \(\lambda_{1}=<AX_{k},X_{k}>/<X_{k},X_{k}>=x^{2}/\ x^{2}=1\)._  
**Example 3**. : _The spectrum of the matrix_  
\[A= \begin{pmatrix}0&2\\ 2&0\end{pmatrix} \]  
_is \(\sigma(A)=\{2,-2\}\). The N-iteration, with \(\alpha_{n}=\beta_{n}=\gamma_{n}=1/2\) starting at \(X_{0}=(2,-3)\), with Euclidean scaling produces the sequence of approximations collected in Table 1._ \begin{table}
\begin{tabular}{c c c} \hline \hline
**Iteration (\(n\))** & \(\mathbf{X_{n}}\) & \(||\mathbf{X_{n}}-\mathbf{X_{n-1}}||\) \\ \hline
1 & (\(-0.894427\), \(-0.447214\)) & 3.85933 \\ \hline
2 & (\(-0.691223\), \(-0.722642\)) & 0.342276 \\ \hline
3 & (\(-0.708154\), \(-0.706058\)) & 0.023699 \\ \hline
4 & (\(-0.707037\), \(-0.707177\)) & 0.001580 \\ \hline
5 & (\(-0.707111\), \(-0.707102\)) & 0.000105 \\ \hline
6 & (\(-0.707106\), \(-0.707107\)) & 0.000007 \\ \hline
7 & (\(-0.707107\), \(-0.707107\)) & 0.000000 \\ \hline \hline \end{tabular}
\end{table}