# iteration convergence bounds with norm less than 1

Let $x_{k+1} = Bx_k + c$ where $B$ is $n \times n$ matrix $c$ is a vector.

Assume $\|B\| \le \beta <1$

$\|x_k - x_{k-1}\| \le \varepsilon$ for some $k$

Show that $\| x - x_k\| \le \dfrac{\beta\varepsilon}{1 - \beta}$

Thanks a lot...

-
The same comment I made to another question of yours applies: This kind of stuffs are pretty standard. Have you ever looked up any textbook or reference book for a proof? – user1551 Jan 4 '13 at 12:04
@user1551: is there another question regarding a similar topic? If so, a link would be nice. If not, and this is a standard question, then perhaps it should have an answer. – robjohn Jan 6 '13 at 7:03
@robjohn The question surely deserves an answer. I am not trying to discourage the others to give an answer. (I'm sorry if it turns out this way.) I only thought that the OP should spend some time to look the relevant material up in a book first. – user1551 Jan 6 '13 at 7:51
I am still trying to find some answer any body please?? – Salih Ucan Jan 8 '13 at 4:23

Observe that $\|x-x_n\| = \|(Bx+c) - (Bx_{n-1}+c)\| = \|B(x-x_{n-1})\| \le \|B\|\|x-x_{n-1}\|$. So, recursively, we get $\|x-x_n\|\le\|B\|^n\|x-x_0\|$. Since $\|B\|<1$, we see that $\lim_{n\to\infty}x_n=x$. Now, by triangle inequality, we have $$\|x-x_k\|\le \|x-x_{k+n}\| + \sum_{i=1}^n \|x_{k+i}-x_{k+i-1}\|.\tag{1}$$ Yet $$\sum_{i=1}^n \|x_{k+i}-x_{k+i-1}\| = \sum_{i=1}^n \|B^i(x_k-x_{k-1})\| \le \sum_{i=1}^n \|B\|^i \epsilon \le \sum_{i=1}^\infty \beta^i \epsilon = \frac{\beta\epsilon}{1-\beta}.$$ Therefore, by letting $n\to\infty$ on the RHS of (1), the result follows.