Wednesday, December 26, 2007

A recursion function for square roots

OK. This post is NOT a big deal. I posted a previous version on Angelfire several years ago and, after reviewing it last night, decided to polish it up just a tad.

The recursion function

Xn = (Xn-1 + C) + C

is a special case of the continuing fraction



C + 1
----------------
C + 1
------------
C + 1
--------
C + ...



which, taken to infinity, equals (C + (C2 + 4)0.5)/2.

The recursive equals that continuing fraction when X0 = 0.

However, we point out that any real, other than -C, can be used and the result in the infinite limit is a single value.

To see this, we write three iterations of the recursive thus:

((((X0 + C)-1 + C) + C)-1) + C)-1

And if you write it out in traditional form using 1/z rather than z-1, it becomes obvious that

limn->inf X0/f(X) = 0, where f(X) is the recursive function.

And note that if X0 =/= Y0, then at any step n of the recursive, the values are not equal. There is equality only in the infinite limit.

An example for C = 2, n = 4.

limn->inf Xn = 1/2(2 + 80.5) = 1 + 20.5


X0 = 1

3.0
2.333...
2.428571429
2.411764706
2.414634146

X0 = 1/2

2.5
2.4
2.41666...
2.413793103
2.414285714

X0 = 31

33.0
2.0333...
2.492537313
2.401197605
2.416458853

X0 = -31

-29.0
1.965517241
2.508771930
2.398601399
2.416909612

X0 = 1/31

2.032258065
2.492063492
2.401273885
2.416445623
2.413830955

X0 = -1/31

1.967741935
2.508196721
2.398692810
2.416893733
2.413754228

No comments: