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 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.

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.