# Iterative Matrix Techniques Based on Averages
## 4 Solution of a Linear System of Equations by an Averaged Iterative Method  
If we need to solve a linear system of equations such as  
\[AX=b, \tag{1}\]  
where \(A\in\mathcal{M}(m\times m)\), \(X\in\mathcal{M}(m\times 1)\) and \(b\in\mathcal{M}(m\times 1)\), we can transform (1) into an equation of the following type:  
\[TX=X, \tag{2}\]  
where \(TX=A_{1}X+b\), and \(A_{1}=I-A.\) It is clear that \(T\) is a Lipschitz operator:  
\[||TX_{1}-TX_{2}||\leq||A_{1}||||X_{1}-X_{2}||,\]  
\(X_{1},X_{2}\in\mathbb{R}^{m}\), and \(||\cdot||\) are a subordinate matrix norm of \(A_{1}.\) Let us note that we use the same notation for vector and subordinate matrix norms. If \(||A_{1}||\leq 1\) then \(T\) is nonexpansive. Let us assume that the system (1) has some solution \(X^{*}\). Then, for any \(X\in\mathbb{R}^{m}\),  
\[||TX-X^{*}||\leq||X-X^{*}||,\] \begin{table}
\begin{tabular}{c c c} \hline
**Iteration (\(n\))** & **Approximation \(X_{n}\)** & \(||AX_{n}-\lambda X_{n}||\) \\ \hline
1 & (0.93875, 1.06125) & 0.46138 \\ \hline
2 & (0.91877, 1.08123) & 0.15052 \\ \hline
3 & (0.91225, 1.08775) & 0.04911 \\ \hline
4 & (0.91012, 1.08988) & 0.01602 \\ \hline
5 & (0.90943, 1.09057) & 0.00523 \\ \hline
6 & (0.90920, 1.09080) & 0.00170 \\ \hline
7 & (0.90913, 1.09087) & 0.00056 \\ \hline \end{tabular}
\end{table} 
Table 4: Approximations of an eigenvector of \(\lambda=10\). and any ball \(\bar{B}(X^{*},R)\) is invariant under \(T\). If \(X\in\bar{B}(X^{*},R)\),  
\[||TX-X^{*}||\leq||X-X^{*}||\leq R.\]  
then the restriction of \(T\) to the ball \(\bar{B}(X^{*},R)\) is a continuous map on a compact set. The N-iteration is such that \(||X_{n}-TX_{n}||\to\bar{0}\) (Proposition 1). At the same time, due to the compactness of \(\bar{B}(X^{*},R)\), for \(X_{0}\in\bar{B}(X^{*},R)\) there exists a subsequence \((X_{n_{k}})\) such that \(X_{n_{k}}\to\bar{X}.\) By continuity, \((I-T)X_{n_{k}}\) tends to \((I-T)\bar{X}=\bar{0}\) and consequently \(\bar{X}\) is a fixed point of \(T\). The fact that \(||X_{n}-\bar{X}||\) is convergent (Proposition 1) implies that the whole sequence \((X_{n})\) converges to the fixed point \(\bar{X}\), that is to say, it approximates a solution of the equation \(AX=b\). **Remark 2**. : _If \(||A_{1}||<1\), \(T\) is contractive on a complete space, and there exists a unique solution which can be approximated by means of the Picard iteration. If \(||A_{1}||\leq 1\), \(T\) is nonexpansive and the N-iteration where \(0<\inf\alpha_{n}\leq\sup\alpha_{n}<1\) and \(0<\inf\gamma_{n}\leq\sup\gamma_{n}<1\) can be used to find a solution, according to the arguments exposed._  
**Remark 3**. : _The complexity of this iterative algorithm is similar to that given for the averaged power method, since the core of the procedure is the product of a matrix (which remains constant over the process) and a vector._  
**Example 7**. : _Let us consider the equation \(AX=b\), where_  
\[A= \begin{pmatrix}1&-2/3&0&-1/3\\ -1/3&1&-1/3&-1/3\\ -1/3&-1/3&1&-1/3\\ -1/3&-1/3&-1/3&1\end{pmatrix} \]  
_and \(b=(-1,0,0,1)^{T}.\) The spectral radius of \(A_{1}=I-A\) is \(1\), and the typical fixed-point method does not converge. The \(N\)-iteration has been applied to the map \(TX=A_{1}X+b\) with the values of the parameters equal to \(1/2\) and starting point \(X_{0}=(0.5,0.5,0.5,0.5)\). Table 5 collects ten approximations of the solution along with their relative errors, computed as \(E_{n}=||X_{n}-X_{n-1}||/\,||X_{n-1}||\). The stop criterion was \(E_{n}<10^{-6}.\) Figure 2 represents the number of iteration (x-axis) along with \(E_{n}\) (y-axis)_