09-19-2021, 04:14 PM
Inspired by Namir's thread: Third Order Convergence for Square Roots Using Newton's Method
If we define f(x) = n - 1/x, Halleys' method won't work
XCAS> f := n - 1/x
XCAS> factor(f/(f' - (f''/2)*(f/f')) → (n*x-1)/n
Correction involve division, which we can't do (otherwise, we just evaluate 1/n)
Slightly modified f work.
XCAS> f /= x
XCAS> factor(f/(f' - (f''/2)*(f/f')) → -x*(n*x-2)*(n*x-1)
Reciprocal, 3rd-order convergence: x ← x + x*(1-n*x)*(2-n*x)
Compare with 2nd-order Newton's: x ← x + x*(1-n*x)
We can estimate cost of computation: 3rd-order = 1.5× 2nd-order
But, 3rd-order run twice is 9th-order, 2nd-order run 3 times only get 8th.
XCAS> N(x) := x + x*(1-n*x)
XCAS> H(x) := x + x*(1-n*x)*(2-n*x)
XCAS> [ H(H(x)), N(N(N(x))) ] | n=5/8, x=1.
[1.59976536036, 1.59937429428]
If we try 1 Halley + 1 Newton, regardless of order, we get the same result.
XCAS> simplify( N(H(x)) - H(N(x)) )
0
If we define f(x) = n - 1/x, Halleys' method won't work
XCAS> f := n - 1/x
XCAS> factor(f/(f' - (f''/2)*(f/f')) → (n*x-1)/n
Correction involve division, which we can't do (otherwise, we just evaluate 1/n)
Slightly modified f work.
XCAS> f /= x
XCAS> factor(f/(f' - (f''/2)*(f/f')) → -x*(n*x-2)*(n*x-1)
Reciprocal, 3rd-order convergence: x ← x + x*(1-n*x)*(2-n*x)
Compare with 2nd-order Newton's: x ← x + x*(1-n*x)
We can estimate cost of computation: 3rd-order = 1.5× 2nd-order
But, 3rd-order run twice is 9th-order, 2nd-order run 3 times only get 8th.
XCAS> N(x) := x + x*(1-n*x)
XCAS> H(x) := x + x*(1-n*x)*(2-n*x)
XCAS> [ H(H(x)), N(N(N(x))) ] | n=5/8, x=1.
[1.59976536036, 1.59937429428]
If we try 1 Halley + 1 Newton, regardless of order, we get the same result.
XCAS> simplify( N(H(x)) - H(N(x)) )
0