Let us assume that function $g$ is defined on an interval $(a,b)$, $g(x)\in(a,b)$ in that interval, and that there is a constant $c<1$ such that for each $x,y \in (a,b)$,
\begin{equation}
\left|g(y)-g(x)\right| < c |x-y|. \tag{1}
\end{equation}
If $g$ has a derivative, this becomes $g'(x)<c$ for $x\in(a,b)$.
The fixed point iteration is defined by $x_{k+1}=g(x_k)$, where $x_0$ is an arbitrarily chosen starting point in $(a,b)$.
Let us assume that the function has a fixed point at $\hat{x}\in(a,b)$, that is $\hat{x}=g(\hat{x})$.
Now at step $k$, the absolute error of our current guess to the fixed point is $e_k = |x_k-\hat{x}|$. We get
$$
e_{k+1} = |x_{k+1}-\hat{x}| = |g(x_k)-g(\hat{x})| < c|x_k - \hat{x}| = c e_k.
$$
Therefore, the sequence $(e_k)_k$ is nonnegative and bounded above by the sequence $(c^ke_0)_k$, which converges to $0$. Therefore, $\lim_{k\to\infty}e_k=0$. This means that the fixed point iteration converges to $\hat{x}$.
For general $g:\mathbb{R}\to\mathbb{R}$, we can make following observations:
If (1) holds in $\mathbb{R}$, we can replace $(a,b)$ with $\mathbb{R}$ in the above proof. One can also see that the function has exactly one fixed point in that case (if $g$ is differentiable, the derivative of $g(x)-x$ is smaller than a negative constant, thus $g(x)-x$ has exactly one zero; if $g$ is not differentiable, a similar argument still holds).
If (1) does not hold in $\mathbb{R}$ but holds in an interval $(a,b)$ containing a fixed point, we can see that $g(a)>a$ and $g(b)<b$, so $g(x) \in (a,b)$ as required. Now the fixed point iteration converges to the fixed point if $x_0$ is chosen inside the interval.
Hint:
Note that $f'$ is continuous. Let's call the fixed point by $x_0$. So, it follows:
- $\exists \varepsilon > 0: |f'(x)| \leq q <1 \mbox{ for } x \in [x_0-\varepsilon , x_0+ \varepsilon]$.
So, for $x \in [x_0-\varepsilon , x_0+ \varepsilon]$ you have
$$\color{blue}{|f(x) - x_0|} = |f(x) - \color{blue}{f(x_0)}|= |f'(\xi)|\cdot|x-x_0| \color{blue}{\leq q\cdot |x-x_0|}$$
Best Answer
One thing to consider is whether the iteration is a contraction map in a neighborhood of the desired root. Here the derivative of the iteration function is $2x$, and this has absolute value greater than 1 near either root.
In such a case an inverse iteration often works as a contraction, i.e. here we'd assign $\sqrt{x+3}$ to $x$ repeatedly to approximate the positive root.
The contraction mapping property is that $|f(x)-f(y)|$ is less than $|x-y|$, but this is a sufficient condition rather than a necessary one for convergence of a fixed point iteration. However if the inequality goes the other way, iterates cannot converge to the fixed point.