Wednesday, July 1, 2009

Rational Approximation to Roots Continued...

This morning I was able to complete the symbolic expression for the limit of the series.  For large x, the expression (1 + a(bx-c))x can be expanded using the binomial theorem to 1 + x ⋅ a(bx-c) + 12 x (x-1) (a(bx-c))2 + 16 x (x-1) (x-2) (a(bx-c))3 + … ; only keeping the highest power of x in both the numerator and the denominator, they cancel and it becomes ∑ 1n! (ab)n

This is where I was last night, but this morning I realized that it could be a MacLaurin series.  A little browsing in the CRC book and sure enough, it is the series for ey, with y=ab.  So, the actual limit is eab, or solving for ab, we want ab = ln N; indeed, ln 2 is around .693, and 9/13 is a good approximation for it.  Now that I know exactly what irrational number I am trying to have for the ratio ab to converge to any given N, I can use continued fractions to choose good a and b to approximate that ratio.

By the way, to get an exact result at x=1, c should be set to b - aN-1.

However, using Excel to plot the actual values as a function of x, it becomes clear that the convergence becomes slow for even N around 10.  (7, 10, 3) gives values within .015 of 2, but the first few terms when converging to 10 are as low as 8!  One can mitigate this somewhat by raising c such that the values for x=1 and x=2 are poor (do we really need an approximation to the 1st root?), bringing the errors for the next terms down, but this only reduces the error by about half.

So, if you happen to need very high roots, like the 200th root of 10, then this is still an interesting technique.  On the other end, for roots of numbers less than 3, all the approximations are very good.  Since this is not limited to integers, should you need to generate roots of, say, 1.2, this technique will give extremely close approximations.

I did realize that the convergence can be greatly improved by raising the order of x in both the numerator and denominator, effectively creating additional terms which only have an effect for small x.  But, since I started this exploration with the observation that there was a sequence which was easy to remember and compute in my head, I decided to stay with that theme and stop here, rather than create much more complicated expressions.  (At this point, were any of the non-math-interested folks still reading, they would go "What, you mean the previous equations weren't complicated?!" :-)

No comments:

Post a Comment