1. General Iteration Method Proof

We are doing norms in my numerical analysis class, and I'm having a lot of trouble. We have to prove

||x^(k) - x|| <= ||T||^(k)*||x^(1) - x^(0)||/(1 - ||T||), where T is a nxn matrix and ||T||<1.

He gave us a hint, and so so far I have it down to

<= ||T||^(k)(||x^(1) - x^(0)|| + ||x^(1) - x||)

but I'm really not sure what to do next. Can anyone help? And maybe explain as you go, because I'm very new at this stuff, and my book doesn't have much on this topic. Also, do you know any sites that talk about it?

I know x = Tx + c and x^(k) = Tx^(k-1) + c but that's about it.

2. Originally Posted by gummy_ratz
We are doing norms in my numerical analysis class, and I'm having a lot of trouble. We have to prove

$\displaystyle \|x^{(k)} - x\| \leqslant \|T\|^k\|x^{(1)} - x^{(0)}\|/(1 - \|T\|)$, where $\displaystyle T$ is a nxn matrix and $\displaystyle \|T\|<1$.

He gave us a hint, and so so far I have it down to

$\displaystyle \leqslant \|T\|^k(\|x^{(1)} - x^{(0)}\| + \|x^{(1)} - x\|)$

but I'm really not sure what to do next. Can anyone help? And maybe explain as you go, because I'm very new at this stuff, and my book doesn't have much on this topic. Also, do you know any sites that talk about it?

I know $\displaystyle x = Tx + c$ and $\displaystyle x^{(k)} = Tx^{(k-1)} + c$ but that's about it.
It looks as though you have already shown that $\displaystyle \|x^{(k)} - x\| \leqslant \|T\|\|x^{(k-1)} - x\|$, and hence (by induction) $\displaystyle \|x^{(k)} - x\| \leqslant \|T\|^k\|x^{(0)} - x\|$. To complete the proof, you need to show that $\displaystyle \|x^{(0)} - x\|\leqslant \dfrac{\|x^{(1)} - x^{(0)}\|}{1-\|T\|}.$

For that, notice that

\displaystyle \begin{aligned}\|x^{(0)} - x\|&\leqslant \|x^{(0)} - x^{(1)}\| + \|x^{(1)} - x\|\quad\text{\footnotesize (triangle inequality)}\\ &\leqslant \|x^{(0)} - x^{(1)}\| + \|T\|\|x^{(0)} - x\|,\end{aligned}

and hence $\displaystyle (1-\|T\|)\|x^{(0)} - x\|\leqslant \|x^{(0)} - x^{(1)}\|.$