A Taylor-polynomial-based Faster-converging

Generalization of Newton’s Method for

Successive Approximation of Zeros

Donald R. Burleson, Ph.D.

Copyright © 2013 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 x_{0} and computing a sequence of improving

approximations x_{1}, x_{2}, x_{3}, etc. as needed, until the
successive iterates no longer differ

significantly, where each “next” approximation x_{n+1} is computed from the “present”

approximation x_{n} by the formula

provided
fʹ(x_{n}) 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

(x_{0}, f(x_{0})) and determine the value x_{1}
(which is then the first iterate) at which this

tangent
line intersects the x-axis. One then
repeats the process starting with x_{1}

to
produce the next value x_{2} 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 = f_{1}(x) = f(x_{0}) + fʹ(x_{0})(x - x_{0})

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 = f_{2}(x) = f(x_{0}) + fʹ(x_{0})(x-x_{0}) + (1/2)fʺ(x_{0})(x-x_{0})^{2}

from
which, solving quadratically for x-x_{0}
under the condition y = 0

to
determine the x-value at which this approximating parabola intersects

the
x-axis, we have

where x =
x_{1} will represent the new approximation of the zero in
question. This

approximation will generally be closer to the desired zero of f(x)
than x_{1}

would be
by a one-pass Newton’s Method computation, since the parabola

y = f_{2}(x) could be expected more closely to
approximate the curve y = f(x)

than does
the linear y = f_{1}(x).
Algebraically rearranging the above equation

and
writing x_{n+1} for x and x_{n} for x_{0}
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ʹ(x_{n})/fʺ(x_{n})
since this choice of sign

clearly
minimizes the absolute difference between x_{n}
and x_{n+1}.

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 (x_{0}, f(x_{0}))

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) = x^{3}-7, using the initial
estimate x_{0} = 1.9.

For f(x) = x^{3}-7,
with derivatives fʹ(x) = 3x^{2} 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

x_{1} = 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 x_{0}
= 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 x_{1} =
0.588479519

with
larger absolute error 0.000053225.