Third Order Convergence for Square Roots Using Newton's Method

[Albert Chan]

Using XCas pade((1+n*x)^(1/n), 3, 3), I discovered a pattern:

\(\displaystyle \sqrt[n]{1+n\,x} = 1 + x \left(
\frac {1+\left({n+1 \over 6}\right) x}
{1 + \left({2n-1 \over 3}\right) x}
\right) + O(x^4) \)

For n = 1/2 or 1, O(x^4) can be dropped.

lua> exact = function(n,x) return (1+n*x)^(1/n) end
lua> approx = function(n,x) return 1+x*(1+(n+1)/6*x) / (1+(2*n-1)/3*x) end

lua> y = 0.1 -- test approx formula for (1+y)^(1/n)
lua> for i=2,12 do n=i/4; print(n, exact(n,y/n), approx(n,y/n)) end

Code:

0.5     1.2100000000000002      1.21
0.75    1.135508127002004       1.1355072463768117
1       1.1                     1.1
1.25    1.079230345298891       1.0792307692307692
1.5     1.0656022367666107      1.0656028368794326
1.75    1.0559733623179208      1.055974025974026
2       1.0488088481701516      1.0488095238095239
2.25    1.0432700717216588      1.0432707355242568
2.5     1.0388601182540846      1.038860759493671
2.75    1.0352658433367348      1.0352664576802508
3       1.0322801154563672      1.032280701754386

As expected, for n>1, approx formula over-estimated true root.

51/49 = 1 + 2/49
sqrt(51)/7 = sqrt(1 + 2*1/49)

lua> approx(2, 1/49) * 7
7.141428571428571

51*49 / 50^2 = 1 - 1/50^2
sqrt(51)*7/50 = sqrt(1 - 2*2e-4)

lua> approx(2, -2e-4) * 50/7
7.141428428542851