Newton’s Method to Approximate an ‘N’-th Root
Since Sir Isaac Newton discovered the basics of differential calculus, it is not surprising that Newton’s Method is based on differentiation.
Newton’s Method is derived from the Newton-Raphson Theorem, which starts with a function F(x); real numbers ‘a’, ‘b’, ‘p’ and positive ‘δ’; and a natural number ‘i’ to be used as a counter.
It requires F(x) to be continuous in the range [a, b] and for which F(p) = zero where ‘p’ is in the range [a, b], and also that the derivative function “f(x) is not zero at x=p”.
As well, it sets “a < (p – δ) < (p + δ) < b”.
This theorem then defines a sequence “p = p[i] – ( F(p[i]) / f(p[i]) )”.
The theorem proves that, if “p is in the range [p – δ, p + δ]”, then the sequence converges toward the value ‘p’ where “F(p) = zero”.
In short, this theorem presents an algorithm, or rule, for Newton’s Method. Finding the cube root of a number, ‘z’, begins with “F(x) = x^3 – z” and “f(x) = 3*x^2”. Next, make a guess that “x = z^(1/3)”, where ‘x’ is some specific number.
Repeatedly apply the theorem: “x = x[i] – ( F(x[i]) / f(x[i]) ) = x[i] – ( (x[i]^3 – z) / ( 3*x[i]^2) )” until F(x) is as close to zero as desired.
Two Hazards within Newton’s Paradise
Two hazards lurk in Newton’s Method for general cubic equations, however. The first is the requirement that the solution exists in the range “[a, b]”. The second is that the derivative function “f(x) is not zero”, especially at the required value. In the first case, a bad first approximation may cause the algorithm to take a long time. In the second, “division by zero” makes the calculation impossible.
Halley’s Method to Approximate a Cube Root
Edmond Halley is more famous for the comet he discovered than his improvement over Newton’s method for finding the root of an equation.
Halley’s Method refines Newton’s Method by including the second derivative, “f‘(x)”, of the original “F(x)” function.
Note that the “single quote mark” in “f‘(x)” indicates that it is the derivative of “f(x)”, which is the derivative of “F(x)”). So “f‘(x) = 6*x”.
Halley’s iteration is “x = x[i] – ( F(x[i]) / ( f(x[i]) + (0.5 * f‘(x[i]) ) ) )”. It can be more stable than Newton’s Method, provided “f‘(x)” is not close to zero in the same region as “f(x)”.
The above is also known as “Halley’s rational formula”. Like Newton’s Method, Halley’s Method depends on making a good first approximation; and it may require a number of iterations to obtain the desired precision.
Decoding Science. One article at a time.