Re: Induction problem ? (Atleast I think it is that :)


RobertSzefler wrote:
> Vinay wrote:
> > Hi,
> >
> > I recently came across the following code:
> >
> > const double epsilon = 1.0e-15;
> > double compute(double m) {
> > double x = m;
> > double y = 1.0;
> > while(x - y > epsilon ) {
> > x = (x+y)/2;
> > y = m/x;
> > }
> > return x;
> > }
> >
> > This function returns the square-root for given value(m). I tried
> > solving this algebraically but expression got too complex. Can anybody
> > point me how one can PROVE this to be true. I don't remember seeing any
> > expansions for square-root similar to say that of log(x), or sin(x) -
> > in case there is one please do mention it.
> >
> > Vinay
> >
> > PS: I tried looking up at recurring function solutions for square-root
> > ( of the type y/(1+y/1+y(1/...))) but drew a blank.
>
> This algorithm is elementary and widely known as the Newton formula. For
> proof, see for example:
>
> http://mathews.ecs.fullerton.edu/n2003/newtonsmethod/Newton'sMethodProof/Links/Newton'sMethodProof_lnk_3.html
>
> BTW, the method can be applied, after making appropriate substitutions,
> to computing sin and log as well.
>
> HTH

We can give a more 'elementary' proof for this particular one.

We have the sequence:

x(n+1) = (x(n) + m/x(n))/2

With x(1) > 0.

By applying AM >= GM we get x(n+1) >= sqrt(m)

Now x(n+1) - x(n) = (m-x(n)*x(n))/2

Thus x(n+1) <= x(n)

So x(n) is bounded below and decreasing. Hence it is convegent.
Also, if it is convergent, it must converge to sqrt(m).

.