🚀 go-pugleaf

Ho Yuk Ting (hytel@netvigator.com) wrote:
: 
: I don't know why if
: x(n+1)=0.5*(x(n)+a/x(n)),
: then for n->infinity, x(n)->sqrt(a)

Nice Question!
This is one of the standard algorithms for calculating a square root.
It is the square root case of "Newton's Method" from calculus.

There are three possible cases to consider:
  x(n) = sqrt(a)  ==>   a/x(n) = a/sqrt(a) = sqrt(a)
  x(n) > sqrt(a)  ==>   a/x(n) < a/sqrt(a) = sqrt(a)
  x(n) < sqrt(a)  ==>   a/x(n) > a/sqrt(a) = sqrt(a)

In every case, the square root is somewhere between x(n) and a/x(n),
  So try the average: x(n+1)=0.5*(x(n)+a/x(n)).
Now a/x(n+1) is also between x(n) and a/x(n)  [Reader check.]
  and sqrt(a) is between x(n+1) and a/x(n+1),
  so x(n+1) must be closer to sqrt(a) than x(n) was.
Every step in the sequence will get closer to the desired square root.

But will it actually get there? or will it stop short?

*IF* it stops (if there IS a limit) then:
    x = lim(n->oo) x(n) = lim(n->oo) x(n+1)
so taking the lim(n->oo) of x(n+1)=0.5*(x(n)+a/x(n)) gives:
    x = 0.5(x+a/x)
Solve for x and you get x=sqrt(a) or x=-sqrt(a).
For most people this is sufficient:
- If your sequence gives an answer then that is the correct answer.

But will it really give an answer?
Or can it bounce around and never actually settle down to a limit?
(This CAN happen with Newton's Method for other functions.)

It turns out that x(n+1)^2 is always greater than (or equal) a:
    x(n+1)^2 = (0.5*(x(n)+a/x(n)))^2
             = ((x^2+a^2/x^2)/2 + a )/2
             > (     a          + a )/2 = a
    using the Inequality of Means:  (m+n)/2 > sqrt(mn)
Therefore, the sequence (if positive) is bounded below by sqrt(a)
and is strictly decreasing.  (It is going down, but not past sqrt(a).)
However it cannot stop (converge to) anything before sqrt(a). (See above.)
So the sequence must always converge to the correct square root.
[If you start with a negative number, you will get -sqrt(a).]
[If you start from zero, of course it fails!]

Any questions?
How would you change the sequence to get the Cube Root of 'a'?

  |\/|                          ||  Burnaby South Secondary School
  |  |orewood@planeteer.com     ||    Beautiful British Columbia
Mathematics & Computer Science  ||             (Canada)