Performing a fixed point Iteration upon $f(x)$

Question

Let us say we have the function $f(x) = (e^x - 1)^2$. I want to perform a fixed-point iteration upon this function, such that $x_{n+1} = g(x_n)$. How can I transform this particular function into a fixed point iteration that converges at the root of $f(x)$? How can this idea be extended to general functions? I am slightly confused at the understanding behind knowing how to transform a given function to a fixed-point iteration method.

EDIT: After trying $g(x) = f(x) + x$, the iterations diverge.

Answer 1

In general, a fixed-point iteration will converge if the map you're iterating is locally a contraction around the fixed-point. Denoting the fixed-point by $z$, an easy way to check if the fixed-point iteration of a continuously differentiable function will converge is to check if $|f'(z)| < 1$. If $|f'(z)| > 1$ you have an instable fixed-point, which means that no matter how close to $z$ you start your iteration, you can not expect the iteration to converge. The intuition behind this is the following first-order linearization:

$$x_{n+1}-x_{n} = f(x_n) - f(x_{n-1}) \approx f'(x_n)(x_n - x_{n-1}) $$ So if $x_n$ is close enough to $z$ such that $f'(x_n) < 1$, you will have that $|x_{n+1}-x_{n}| < |x_{n}-x_{n-1}|$, while in the case where $f'(x_0) > 1$ you're gonna have $|x_{n+1}-x_{n}| > |x_{n}-x_{n-1}|$ which means that you cannot expect your sequence to converge (although it still might).

EDIT: Corrected this paragraph thanks to @PierreCarre. So what happens in our example? We have $g(x) = f(x) + x = (e^{x}-1)^2 + x$ whose only fixed-point is $z = 0$,and $g'(x) = 2e^{x} +1 > 1$. We therefore cannot expect the fixed-point iteration to converge. Indeed, for any $x_0 \geq 0$ we have $g(x_n) > x_n$, such that in the iteration we get $x_{n+1} > x_{n}$, and therefore the iteration will diverge to $+\infty$. A more well-behaved function whose fixed-points are the roots of $f$ is given by $g(x) = x - (e^{x}-1)^2$.

If you want to practice this kind of reasoning, try finding the fixed-points of $f(x) = x^2$ via fixed-point iteration. Find the derivative of the function and try to predict for which starting values the iterations should converge to which fixed-point, and for which starting values the iteration will diverge, and then try and see if your predictions are correct.

Answer 2

You can write the equation $f(x)=0$ in the form $g(x)=x$ in countless ways. If the equations are equivalent, the roots of $f$ will be the fixed points of $g$. The fixed point method is used to obtain the fixed point(s) of $g$ and takes the form $x_{n+1}=g(x_n)$, for some initial approximation $x_0$.

This recursive sequence may or may not converge, and this totally depends on your choice of $g$ (not all are good) and initial approximation. The fixed point theorem establishes sufficient conditions for the convergence of the sequence $(x_n)$: If $g$ is contractive and invariant in some closed non-empty interval $\Omega$, the fixed point iterations will converge regardless of the choice of $x_0 \in\Omega$. The answer by @user159517 focuses on the contractivity condition, and this is ok because you can show that if $g$ is contractive in some neighbourhood $V_{\varepsilon}(z)$ of the fixed point, it satisfies the fixed point theorem conditions in some $V_{\delta}(z)$, $\delta \leq \varepsilon$.

So, if at first you don't succeed... Try to understand why some particular choice of $g$ does not work (for instance plotting its derivative near the fixed point), and rewrite the equation in a different way (other $g$)