# iteration convergence

When soloving the linear equation $x=Ax+b$ (where $x$ is an unknown vector, $A$ is a matrix, and $b$ is a constant vector), one often use the follow iteration:

$x_{k+1}=Ax_k +b$.

Does the above $x_k$ is convergent to $x$ when the spectral radius of $A$ is less than 1? If yes, would you give a reason. Thanks!

-
Consider the situation that it is one dimension.In that case, y=Ax+b and y=x has one intersection,since A<1, it is the fixed point.Thus, under this situation, the answer is yes. – 89085731 Mar 31 '12 at 1:49

Existence and uniqueness has been shown above; so what follows will show that the iteration converges irrespective of the diagonizability of $A$. It is simply the proof of the Banach fixed point theorem (proved in Rainer Kress's Numerical Analysis) applied to situation at hand. Let $||A||_{2}:=\sup_{||x||_{2}=1} ||Ax||_{2}$, where $||x||_{2}^{2}:=x_{1}^{2}+x_{2}^{2}+\cdots + x_{n}^{2}$. This defines a norm on the space of matrices. Moreover, there is well-known proof (again found in Kress) that $$||A||_{2}^{2} = \rho(A^{*}A)$$ If $\mu\in \mathbb{C}$ is an eigenvalue of $A$, then $|\mu|^{2}$ is an eigenvalue of $A^{*}A$. So if each eigenvalue of $A$ is $<1$, then each eigenvalue of $A^* A$ is also $<1$. Hence $\rho(A)<1$ implies $||A||_{2}= \sqrt{\rho(A^{*}A)} <1$. Then $$||x_{n+1}-x_{n}||_{2} = ||Ax_{n}+b-(Ax_{n-1}+b)||_{2} = ||A(x_{n}-x_{n-1})||_{2} \le ||A||_{2}||x_{n}-x_{n-1}||_{2}$$ We can do this same thing to $||x_{n}-x_{n-1}||_{2}$, and so on, to get $$||x_{n+1}-x_{n}||_{2}\le ||A||_{2}^{n}||x_{1}-x_{0}||_{2}.$$ Since $||A||_{2}<1$, $||x_{n+1}-x_{n}||_{2}\to 0$, which is not sufficient to prove that $x_{n}\to x$. We need the stronger condition that $\{x_{n}\}_{n=1}^{\infty}$ is a Cauchy sequence, namely that $||x_{n}-x_{m}||_{2}\to 0$ for $n,m\to \infty$. So assume $m>n$. Then \begin{align*} ||x_{n}-x_{m}||_{2} &= ||x_{n}-x_{n+1}+x_{n+1} -x_{n+2}+x_{n+2} +\cdots +x_{m-1}-x_{m}||_{2}\\ &\le ||x_{n}-x_{n+1}||_{2}+||x_{n+1}-x_{n+2}||_{2} + \cdots ||x_{m-1}-x_{m}||_{2}\\ &\le ||A||_{2}^{n}||x_{1}-x_{0}||_{2} + ||A||_{2}^{n+1}||_{2}||x_{1}-x_{0}|| + \cdots +||A||_{2}^{m-1}||x_{1}-x_{0}||_{2}\\ &\le \frac{||A||_{2}^{n}}{1-||A||_{2}} ||x_{1}-x_{0}||_{2} \to 0 \end{align*} as $n\to \infty$. So indeed it does form a Cauchy sequence. The space $\mathbb{R}^{n}$ is complete, so there exists a unique $x \in \mathbb{R}^{n}$ such that $x_{n}\to x$.

I remember battling this theorem for a long time in graduate school, and what I've given you here is a poorly written version of what Kress writes. So hopefully this helps.

-
@ChristianBlatter. The post says: $\rho(A) < 1$ implies $\|A\|_2 < 1$. Correct me if I am mistaken, but I think this does not hold in general. For example, consider $A = 0.99 \left[ \begin{array}{cc} 1 & 0 \\ 1 & 0 \end{array} \right]$ – ziutek Mar 7 '15 at 14:19
@ziutek: This is not my post. I don't know Kress' book and the notations used therein. – Christian Blatter Mar 7 '15 at 14:27

The proof of this result is often shown in elementary numerical analysis book. Here is a sketch.

You first show there exists a unique fixed point for $x = g(x) = Ax + b$. The fixed point $x$ satisfies $x = g(x)$ if and only if $(I-A)x = b$, which gives you existence and uniqueness if $I-A$ is invertible. The eigenvalues $\mu$ of $I-T$ satisfies $$\det((I-T) - \mu I) = 0 \quad \Longleftrightarrow \quad \det(T - (1-\mu) I) = 0$$ so that $\rho(T) = \max_{i=1}^n |\lambda_i| < 1$ implies $|1-\mu| < 1$, and we're done.

Now that we have existence and uniqueness, $x_{k+1} = Ax_k + b$ means $x_{k+1} - x = A(x_k - x)$. Suppose at this point that $A$ is diagonalizable, so that the error can be written as $$x_0 - x = \sum_{i=1}^n \gamma_i v_i$$ which means $$x_{k+1} - x = A(x_k - x) = \sum_{i=1}^n \gamma_i \lambda_i^k v_i$$ by induction on $k$. Therefore since $|\lambda_i^k| = |\lambda_i|^k \to 0$ as $k \to \infty$ (because $|\lambda_i| < 1$), we know that the "error term" $x_k - x$ goes to $0$, thus your algorithm converges.

I must say though I have no proof when $A$ is not diagonalizable.

Hope that helps,

-
Your proof is what I think, I just prove the case of one dimension, but I think it is the same with you for A is diagonalizable. For general case, I think G-S iteration may help. – 89085731 Mar 31 '12 at 1:55
The one dimensional case is very "simple", because there is not much to do in one dimension. G-S stands for Gauss-Seidel I believe? I am not a numerical analyst, I just took one course once and I read stuff off my notes. – Patrick Da Silva Mar 31 '12 at 2:08

Here is a pedestrian way for this problem: As $x$ is somehow related to the "world" generated by $A$ and by $b$ we make the "Ansatz" $$x=\sum_{k=0}^\infty c_k\ A^k\, b$$ with undetermined coefficients $c_k$. The given equation requires $$\sum_{k=0}^\infty c_k\ A^k\, b=\sum_{k=0}^\infty c_k\ A^{k+1}\, b = \sum_{k=1}^\infty c_{k-1}\ A^k\, b +b\ ,$$ or $$c_0 b+\sum_{k=1}^\infty(c_k-c_{k-1})\ A^k\, b = b\ .$$ This is solved for whatever $A$ and $b$ by putting $c_k=1$ $\ (k\geq 0)$, assuming the infinite series is convergent. Therefore we have $$x=\sum_{k=0}^\infty A^k\ b\ ,$$ which indeed makes sense when the spectral radius of $A$ is $<1$. But we can say more: Under this assumption there exists the map $B:=(I-A)^{-1}\$, and the solution we have found is nothing else but the development of $x=B\, b$ into a geometric series.

-