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!
 A: 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.
A: 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,
A: 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.
