How does this numerical method of root approximation work?

Question

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:

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?

Answer 1

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.

Answer 2

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$)