A Taylor-polynomial-based Faster-converging
Generalization of Newton’s Method for
Successive Approximation of Zeros
Donald R. Burleson, Ph.D.
Copyright © 2013, 2020 by Donald R. Burleson.
This article may be reproduced in its entirety
provided original authorship is expressly
acknowledged.
It is well known that Newton’s Method, a generally
reliable algorithm for successively
approximating a zero of a continuous and
differentiable function f(x), consists of
starting with an initial estimate x0 and
computing a sequence of improving
approximations x1, x2, x3,
etc. as needed, until the successive iterates no longer differ
significantly, where each “next” approximation xn+1
is computed from the “present”
approximation xn
by the formula
provided fʹ(xn)
is not too close to 0, in which case the successive computations may
fail to converge.
In calculus courses the usual method of deriving the
formula for Newton’s
Method is to write the equation of the tangent line to
the curve y = f(x) at the point
(x0, f(x0)) and determine the
value x1 (which is then the first iterate) at which this
tangent line intersects the x-axis. One then repeats the process starting with x1
to produce the next value x2 and so on.
But it is often not mentioned (mostly because Newton’s
Method and
Taylor series are commonly covered in different
courses) that if one
truncates the Taylor series
to approximate a curve y = f(x) roughly with a
degree-one Taylor polynomial
y = f1(x) = f(x0) + fʹ(x0)(x - x0)
then under the condition y = 0 one readily verifies
that this representation
is equivalent to the usual tangent line derivation of
Newton’s formula.
I propose that a natural generalization, then, is to
start by approximating
the curve y =
f(x) with a degree-two Taylor polynomial
y = f2(x) = f(x0) + fʹ(x0)(x-x0) + (1/2)fʺ(x0)(x-x0)2
from which, solving quadratically for x-x0
under the condition y = 0
to determine the x-value at which this approximating
parabola intersects
the x-axis, we have
where x = x1 will represent the new
approximation of the zero in question.
This
approximation will generally be closer to the desired
zero of f(x) than x1
would be by a one-pass Newton’s Method computation,
since the parabola
y = f2(x) could be expected more closely to
approximate the curve y = f(x)
than does the linear y = f1(x). Algebraically rearranging the above equation
and writing xn+1 for x and xn for x0 gives our main result, an
iterative
algorithm that performs the same task as Newton’s
Method but
converges significantly faster:
where the sign is chosen to match the sign of fʹ(xn)/fʺ(xn) since this
choice of sign
clearly minimizes the absolute difference between xn and xn+1.
(Under the right circumstances, with a negative
radicand and given a
workable starting value, this generalized method may
begin to converge
to a pair of conjugate complex numbers, in which case
of course
we employ both algebraic signs in front of the square
root.)
It is understood, of course, that similarly to what
happens in Newton’s Method
when fʹ is too close to 0, this parabolic
approach could fail to perform well
if fʺ were too close to 0, in particular if one
were to choose (x0, f(x0))
too close to an inflection point of the curve y =
f(x).
One naturally could devise further generalizations
using a degree-three
Taylor polynomial and so on, but the parabolic method
described here
often produces results correct to six or seven decimal
places
in only one step, with relatively simple computations,
whereas
higher-degree Taylor polynomial approaches would
entail computations
considerably more tedious with only moderately
faster-converging results.
The following examples show only one iteration of the
parabolic
method, with error less than 10 -6. A second iteration would produce
values having error much smaller even than that.
EXAMPLE 1
To approximate the cube root of 7, i.e. to approximate
a zero of
the function
f(x) = x3-7, using the initial estimate x0 = 1.9.
For f(x) = x3-7,
with derivatives fʹ(x) = 3x2 and fʺ(x) = 6x,
the method described above gives the new estimate of
the zero as
= 1.9 - 0.95 + 0.962931380 =
1.912931380
As the actual cube root of 7 to nine decimal places is
1.912931183,
the absolute error of our one-pass computation is only
0.000000187.
By comparison, Newton’s Method for one pass gives
x1 = 1.913019391
for a larger absolute error of 0.000088208.
EXAMPLE 2
To approximate a zero of the function f(x) = sin(x) -
e -x close to x = 0.6.
The parabolic method with initial estimate x0
= 0.6 gives the next iterate to be
= 0.6 + 1.234130118 - 1.245597323 =
0.588532795
with an absolute error of only 0.000000051
since the actual zero (correct to nine places as
determined by four
passes in Newton’s Method) is 0.588532744.
Newton’s Method for one pass gives x1 =
0.588479519
with larger absolute error 0.000053225.