Third Order Convergence for Square Roots Using Newton's Method

[Albert Chan]

(09-16-2021 05:18 PM)ttw Wrote:  To get Sqrt(S), one uses two auxiliary variables, A and B.

A=(S-X^2)/2S

B=X+A

X(new)=B-(A^2)/2B equivalent to (X+A)-(A^2)/2*(X+A)

Very compact formula
I believe there is a typo, should be A = (S-X^2)/(2X)

S = 2XA + X^2 = X*(2A+X) = (B-A)*(B+A)

Newton's from B: (B + S/B)/2 = (B^2 + (B-A)*(B+A))/(2B) = B - A^2/(2B)       QED

Using the same symbols, this is Halley's method for √S

X(new) = X + A/(1+A/(2X)) = X + A/C

C = 1 + A/(2X) = 1 + (S-X*X)/(2X)^2 = 3/4 + S/(2X)^2 ≥ 3/4

Assuming Halley's method is better than Newton's:

A > 0 → C > 1 → B > √S
A < 0 → C < 1 → B > √S

Newton's method for √S over-estimate (convergence always from the high side)

We can apply small correction to Halley's, for quartic convergence.

XCAS> simplify(subst(X + A/(1+A/(X+B)), X=B-A))

(-A^2+2*B^2)/(2*B)

(09-16-2021 01:39 PM)Albert Chan Wrote:  X(n+2) = X(n) + (N-X(n)^2)/2 * (X(n)+X(n+1)) / (N+X(n)^2)

Might as well proof this too. denominator (N+X(n)^2) = (2*X(n)*X(n+1))

X(new) = X + (X*A)*(X+B)/(2*X*B) = X + (A/B)*(X+B)/2

XCAS> simplify(subst(X + (A/B)*(X+B)/2, X=B-A))

(-A^2+2*B^2)/(2*B)