# Why does Fixed Point Iteration work?

I have searched online for an answer, but everyone gave the method, and no one explained why is it working.
I'll first write what I do understand.

Let $f(x)$ be a continuous function at $[a,b]$.
suppose $f$ has a root at $[a,b]$, and we want to find it. meaning, we want to find $x_0$ which satisfies $f(x_0)=0$. so we rewrite $f$ as $g(x)=x$, and now the problem of finding the root for $f$, reduced to finding the fixed point for $g$.
For example: let $f(x)=x^2-x-1$, so we're interested in $x^2-x-1=0$. rewriting it, we get $x=\frac{1}{x-1}$.
now define $g(x)=\frac{1}{x-1}$, and now the problem was reduced to finding a fixed point of $g$, meaning finding $x_0$ which satisfies $g(x_0)=x_0$.
Now, to find that $x_0$, the method states that one should pick some point $x_1$, evaluate $g(x_1)$, and then evaluate $g(g(x_1))$, and so on, or in other words, we evaluate:
$x_{n+1}=g(x_n)$ for $n=1,2,3...$ until we get the desired accuracy.
What I don't get is; why does it work?
And more specifically; Why is evaluating $g(g(g(...g(x))))$ yields the fixed point of $g$?
I know there are some circumstances in which this doesn't work (whatever they are, I don't know...), but I'm referring to those that it does.
Another (related?) question is: why is $g$ undefined at $x=1$? does it just happen to be this way, or does it have some implications regarding $f$'s root?

Thanks.

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)$, $$\left|g(y)-g(x)\right| < c |x-y|. \tag{1}$$ 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.

This method of finding fixed points requires that the function under consideration fulfills some rather stringent conditions, e.g. it maps the domain of definition into itself and is contracting (which means $$|f(x)-f(y)| \le C|x-y|$$ for some $$0).

You seem to be under the impression that it is common that this approach will give you a solution. This is incorrect. Usually these assumptions are not fulfilled. You are just lucky if they are and then the method yields the desired result. Why this is true can be seen best by looking at a proof (by iterating k times, the constant $$C$$ will come into play with a power of $$k$$, and since $$C<1$$, $$C^k$$ tends to $$0$$. You will find the details in analysis textbooks, search for Banach's fixed point theorem).

Also, this method is usually (at least classically) not used to calculate the fixed point/zero, but mostly to show that such a point actually exists. This may have changed during the last decades due to the availability of computing power.

• Is this really true? If your contraction condition is satisfied, then we can expect convergence to a fixed point. What if the function mapping a closed interval to itself is nowhere continuous but differentiable? We certainly expect a fixed point. – Mark McClure Mar 21 '14 at 20:57
• @MarkMcClure I do not get what you ask for. What exactly is it you want to know when you are asking 'is really true'?. But: nowhere continuous but differentiable? How do you achieve that? Differentiability implies Continuity. The contraction condition already implies Lipschitz continuity, btw. – Thomas Mar 21 '14 at 21:05
• You said that the iterative technique for finding fixed points requires that the function be contractive. I'm saying that's not necessarily true. I only happen to know this since I've been studying the iteration of the Takagi function recently. It turns out, that for almost every initial seed, the orbit converges to the fixed point 2/3. So, in this case, we might say that the technique works in the absence of a contraction condition. On the other hand, your comment is certainly apropos in the differentiable case. +1! – Mark McClure Mar 21 '14 at 21:13
• @MarkMcClure No, I did not say that it is required to be contractive. You may have missed the 'e.g.'. My point is simply that the iteration principle is nothing you should expect to work in general. The contraction hypothesis is only one possible assumption which will imply the claim. Apart from that, note that the OP did not ask for the existence of a fixed point, but for the iteration method to produce one. Which is something else entirely. – Thomas Mar 21 '14 at 21:18
• Oh, I guess I misunderstood the word "requires". My bad!! – Mark McClure Mar 21 '14 at 21:20

Suppose that $\lim_{n\to \infty} x_{n}$ exists. Call it $a$. Then $$a=\lim_{n\to\infty} x_{n+1}=\lim_{n\to\infty} g(x_n)=g(a).$$ The $\lim_{n\to\infty}g(x_n)=g(a)$ part follows from the assumption that $g$ is continuous.

Remark: We have shown that if the limit exists, then it is a root. The limit may not exist, or it may not be the particular root we are looking for. And some ways of rewriting $f(x)=0$ may give quick convergence to a root, while other ways do not.