Finding the square root Newton Raphson convergence proof

Upon a time, I found a formula that converged to the square root of a certain number $x $.

Where the square root of the number you want to find is $x $, $\sqrt x $, $$a_{n+1}=\frac{\frac{x}{a_n}+a_n}{2}$$ for any $a_0$.

For example, you want to calculate $\sqrt 2$, then you would use the formula $$a_{n+1}=\frac{\frac{2}{a_n}+a_n}{2}$$ where $a_0$ is the unit guess (in this case probably $1.5$) and $\sqrt x = a_\infty $

How does this work?

This is a specific example of Newton's method. I believe the Babylonians also used this.

I'll provide more details when I am at a computer.

For a simple proof see robjohn's Proof of Convergence: Babylonian Method

(uses opposite notation than yours, with $x$ and $a$ reversed)

I want to present how the Babylonian method might be 'discovered', leading into robjohn's proof. Here we do not assume the existence of real numbers, only the rational numbers. We will also flip your notation.

You know that taking the multiplicative inverse of a positive number, not equal to one, gives you a number that is kind of 'folded over' into one of two disjoint intervals:

$(0, 1)$ or $(1, +\infty)$

And of course $1$ is right in the 'center' and is its own inverse.

As you think about the number pairs $x$ and $x^{-1}$, you wonder if taking the average will 'get you' to $1$. So you examine the function $f(x) = .5\; (x^{-1}+x)$ and start plugging in numbers. You are not surprised to see that $f(x) \ge 1\;$ -you are taking a number from an interval of infinite length and averaging it with a number from an interval of length $1$. You learn that if you iterate $f$ starting with any point you'll converge to $1$ from the right.

Now you wonder it you can make this more interesting by 'nudging' the number that is less than $1$ on each $f$ iteration, but with everything working the same, i.e. convergence to a number from the right. So you perturb your function, redefining it as

$f(x) = .5\; (a x^{-1}+x)$

So, if this works as before, you want a $k>0$ such that for all $x>0$,

$f(x) \ge k$

Solving by setting the discriminant of a quadratic equation to zero, you'll see that the inequality will be true iff $k^2 = a$.

So we have,

(1) ${f(x)}^2 \ge a$

But this is all you need in the (1) inequality of the nice proof mentioned at the top; you can proceed from that point with the @robjohn demonstration.

SUMMARY: If you ever forget the Babylonian Method, you can get it back by remembering your $(x^{-1}+x)\;$ 'game' and then the 'nudge'.

We assume that you can't possibly forget the quadratic formula and some simple facts about graphs of parabolas and taking limits.