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.

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...

share|improve this question
    
What have you tried? –  Arthur Jan 4 '13 at 0:52
    
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
1  
@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

1 Answer 1

up vote 0 down vote accepted

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 \begin{equation} \|x-x_k\|\le \|x-x_{k+n}\| + \sum_{i=1}^n \|x_{k+i}-x_{k+i-1}\|.\tag{1} \end{equation} 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.

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.