Proof that the babylonian method converges for any postive number c

eoins23456

We have to prove that the babylonian method converges for any postive number c.
F(x)= .5(x+c/x)

Xn+1= f(Xn)

I tried the ratio test on this and got the answer a half which proves its convergent but does this prove its convergent for any positive number c?

We are then asked to find the limit as n approaches infinity of Xn by calculating the fixed point method and also to determine the order of convergence.

My attempt at this was x= f(x) and getting x = sqrt(c). I know that the limit is sqrt(c) but dont know how to prove it.

Any help is much appreciated

MathsManiac

When doing the ratio test, you presumably found that, no matter what the value of c is, the relevant ratio is 1/2. So yes, you have shown that it converges for all positive c.

By finding the result using the fixed point method, I think you have effectively proven the limit. If the limit L exists, then it must satisfy f(L)=L. Since this latter equation has only two solutions (namely, sqrt(c) and -sqrt(c)), the limit has to be one of those. It's easy to show that if x(k) is positive, then so is x(k+1), and similarly in the negative case. Hence, if x(1) is positive, the limit must be sqrt(c), while if x(1) is negative, the limit must be -sqrt(c).

For the order of convergence, you need to consider how |x(n+1) - L| compares to |x(n) - L|, as n tends to infinity.

The Wikipedia article on it might help.

Further hints:

Try showing first that it's at least linear. The answer is that it's quadratic.

Eliot Rosewater

I'd never heard of this method -- though I see that it can be derived from Newton's method, which is interesting given the chronology. Though MathsManiac's suggestions are more direct, it might be nice to prove it converges by looking at the effect of Newton's method on a simple f(x)=x^2-c curve near the positive roots. In particular, quadratic functions are convex, which can be used to show convergence ... it's more a geometric approach than algebraic.