We can often use iteration to find an approximation for the root of the equation $f(x) = 0$.

For instance, consider $x^2 - 4x + 1 = 0$. This is equivalent to $x = 4 - \frac 1x$. Now we use the iteration formula $$x_{n+1} = 4 - \frac{1}{x_n}$$ starting with, say, $x_0 = 3$.

We iterate over and over until we get sufficiently close to the root.

Now, why does this work? What is the justification for turning the relation into a recurrence relation? Why do successive iterations get us closer to the root of the equation? I understand the path that we take in getting the approximate root:

Fig. 1

But I don't understand why this path exists. How do we know that in general, we won't just go back and forth? Or that we won't skip over the root entirely?

  • 1
    $\begingroup$ Note that this technique does not work for the other root. $\endgroup$ – copper.hat Nov 16 '17 at 5:40

By writing the equation as $x=4-\frac1x$, you wrote it in the form $$x=f(x).$$ So you are looking for a fixed point for the function $f$. A sufficient condition for a fixed point $x_0$ to be an attractor (that is, that the iteration $x_{n+1}=f(x_n)$ converges to $x_0$) is that $|f'(x_0)|<1$ and $f$ continuously differentiable.

In your example, since $f'(x)=-1/x^2$, a fixed point $x_0>1$ will be an attractor, which is why the sequence converges to the desired root.


The theoretical reason this works is the Banach fixed point theorem.

We can rewrite the iteration as $$x_{n+1}=f(x_{n}) \quad \text{where} \quad f(x)=4-1/x.$$ The Banach fixed point theorem implies that if we can find a closed subset $X$ of $\mathbb{R}$ for which $f(X)\subset X$ and $|f^{\prime}|<1$ on $X$, the iteration started at any point $x_{0}\in X$ converges to a point $x$ satisfying $x=f(x)$. Moreover, no other point $y$ in $X$ satisfies $f(y)=y$.

Can you figure out an appropriate choice of $X$? (Hint: try $X=[1+\epsilon, \infty)$ for any $\epsilon>0$)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.