The problem of finding the root of the function $f(x)$, i.e. the value of $x^{\ast}$ such that $f(x^{\ast}) = 0$, can be reformulated as $x = g(x)$, and therefore the root $x^{\ast}$ will be the value $x^{\ast} = g(x^{\ast})$. Where:
- $g(x)$ is the Iterative Function;
- $x^{\ast}$ is fixed point of $g(x)$
With this reformulation, it is possible to approximate the root $x^{\ast}$, through an iterative procedure as: $$x_{k+1} = g(x_k), \qquad k=0,1, \ldots$$ with $x_0$ assigned with an initial value.
Theorem:
If $g(x) : [a,b] → \mathbb R$ continuous and such that $a \le g(x) \le b \quad \forall x \in [a,b] \Rightarrow \exists $ a fixed point $x^{\ast} \in [a,b]$.
Also, if $g(x)$ is derivable in $[a,b]$, and $\exists \, 0 < \rho <1$ such that $|g'(x)| \le \rho \forall x \in (a,b)$ then the fixed point is unique and the succession generated from $x_{k+1} = g(x_k)$ converges to $x^{\ast}$.
Proof:
We prove only the last part, about the convergence. Since $x^{\ast}$ is a fixed point of $g(x)$, and therefore $x^{\ast} = g(x^{\ast})$, we have:
$$\begin{array}{l} |x_{k+1} - x^{\ast}| & \overset{1}{=} & |g(x_k) - g(x^{\ast})| \\ & \overset{2}{=} & |g \big (x^{\ast} + \left (x_{k} - x^{\ast} \right ) \big ) - g(x^{\ast})| \\ & \overset{3}{=} & |g'(c_k)|\cdot |x_k - x^{\ast}| \end{array} $$
we applied Taylor series, and $c_k \in I(x_k, x^{\ast})$, where $I(x_k, x^{\ast})$ is the interval containing $x_k$ and $x^{\ast}$.
Since $|g'(c_k)| \le \rho$ then we have:
$$|x_{k+1} - x^{\ast}| \le \rho|x_k - x^{\ast}|$$
and applying many times this inequality we obtain:
$$|x_k - x^{\ast}| \le \rho^k |x_0 - x^{\ast}| $$
and therefore:
$$\underset{k → \infty}{\lim} |x_k - x^{\ast}| \le \underset{k → \infty}{\lim} \rho^k |x_0 - x^{\ast}| = 0$$
and the convergence is verified. $\square$
The above is from my textbook, it is the suggested proof, but I don't understand (for now), what is the reasoning applied in the passages from $\overset{2}{=}$ to $\overset{3}{=}$.
Please, can you help me to understand? Many thanks!
edit: (Probably, it is weird a proof, so if you think a different proof is better than this, you can post it but with detailed passages. Thanks.)
Ok, I'll explain the proof. We are going to use the mean value theorem. It says that if a function $f$ is differentiable in an interval $(a,b)$ and continuous in $[a,b]$ then there exists a point $c\in (a,b)$ such that $f(b)-f(a)=f'(c)(b-a)$.
Now, in the theorem we want to prove we know that $x_{k+1}=g(x_k)$ for all $k\in\mathbb{N}$ and that $x^*$ is a fixed point of $g$. Also, $g$ is differentiable in $[a,b]$ and $|g'(x)|\leq\rho$ for all $x\in [a,b]$. So using the mean value theorem we know that for each $k\in\mathbb{N}$ there exists a point $c_k$ between $x_k$ and $x^*$ such that $g(x_k)-g(x^*)=g'(c_k)(x_k-x^*)$. Hence, for all $k\in\mathbb{N}$ we have:
$|x_{k+1}-x^*|=|g(x_k)-g(x^*)|=|g'(c_k)||x_k-x^*|\leq\rho |x_k-x^*|$
Note that this is true for every $k$. Hence we conclude that:
$|x_k-x^*|\leq\rho|x_{k-1}-x^*|\leq\rho^2|x_{k-2}-x^*|\leq...\leq\rho^k|x_0-x^*|$ for each $k\in\mathbb{N}$
Since $0<\rho<1$ we know that $\rho^k|x_0-x^*|\to 0$ when $k\to\infty$. And since $0\leq |x_k-x^*|\leq\rho^k|x_0-x^*|$ the squeeze theorem tells us that $x_k\to x^*$.