Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

3 Answers 3

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.

share|improve this answer

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,

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.