Applied

Mathematics
Letters
PERGAMON Applied Mathematics Letters 13 (2000) 87-93
www.elsevier.nl/locate/aml

A Variant of
Newton’s Method with
Accelerated Third-Order Convergence
S. WEERAKOON AND T. G. I. FERNANDO
Department of Mathematics, University of Sri Jayewardenepura
Gangodawila, Nugegoda, Sri Lanka
sweeraQsjp.ac.lk

(Received July 1998; revised and accepted November 1998)

Abstract-In the given method, we suggest an improvement to the iteration of Newton’s method.
Derivation of Newton’s method involves an indefinite integral of the derivative of the function, and the
relevant area is approximated by a rectangle. In the proposed scheme, we approximate this indefinite
integral by a trapezoid instead of a rectangle, thereby reducing the error in the approximation. It
is shown that the order of convergence of the new method is three, and computed results support
this theory. Even though we have shown that the order of convergence is three, in several cases,
computational order of convergence is even higher. For most of the functions we tested, the order of
convergence in Newton’s method was less than two and for our method, it was always close to three.
@ 2000 Elsevier Science Ltd. All rights reserved.

Keywords-Newton’s formula, Nonlinear equations, Iterative methods, Order of convergence,

Function evaluations.

1. INTRODUCTION
Newton’s method that approximates the root of a nonlinear equation in one variable using the
value of the function and its derivative, in an iterative fashion, is probably the best known and
most widely used algorithm, and it converges to the root quadratically. In other words, after
some iterations, the process doubles the number of correct decimal places or significant digits at
each iteration.
In this study, we suggest an improvement to the iteration of Newton’s method at the expense
of one additional first derivative evaluation. Derivation of Newton’s method involves an indefinite
integral of the derivative of the function, and the relevant area is approximated by a rectangle.
Here, we approximate this indefinite integral by a trapezoid instead of a rectangle, and the result
is a method with third-order convergence.
It is shown that the suggested method converges to the root, and the order of convergence is at
least three in a neighbourhood of the root, whenever the first and higher order derivatives of the
function exist in a neighbourhood of the root; i.e., our method approximately triples the number
of significant digits after some iterations. Computed results overwhelmingly support this theory,
and the computational order of convergence is even more than three for certain functions.

0893-9659/00/$ - see front matter @ 2000 Elsevier Science Ltd. All rights reserved. Typeset by A++S-T$~
PII: SO893-9659(00)00100-2
88 S.WEERAKOON AND T. G. I.FERNANDO

2. PRELIMINARY RESULTS
Letcu E !R,z, E 92,n = O,l, 2,. . . . Then, the sequence {TC,} issaid
DEFINITION 2.1. (See [I].)
to converge to Q if
lim 15, - Q) = 0.
n-CC
If, in addition, there exists a constant c 2 0, an integer no > 0, and p > 0 such that for all
n > no,
/&I+1 - aI 5 C/h - QIP, (2.1)

then (1~~) is said to converge to QIwith q-order at least p. If p = 2 or 3, the convergence is said
to be q-quadratic or q-cubic, respectively.
When e, = X, - (Y is the error in the nth iterate, the relation

en+1 = ce”, + 0 (eE+l) (2.2)

is called the error equation. By substituting e, = zn - a: for all n in any iterative method and
simplifying, we obtain the error equation for that method. The value of p thus obtained is called
the order of this method.

DEFINITION 2.2. Let a: be a root of the function f(z) and suppose that x,+1, zn, and z,_l are
three consecutive iterations closer to the root a. Then, the computational order of convergence p
can be approximated using the formula

ln I(G+I - Q) / (2, - a)I

‘= ln((z, -(2.)/(&-1-Q)I’

STOPPING CRITERIA. We have to accept an approximate solution rather than the exact root,
depending on the precision (E) of the computer. So, we use the following stopping criteria for
computer programs:

(i) Ix,+1 - z,l < V%

(ii) If(xn+l)l < &

3. NUMERICAL SCHEMES

3.1. Newton’s Method (NM)

Newton’s algorithm to approximate the root (Y of the nonlinear equation f(z) = 0 is to start
with an initial approximation 22; sufficiently close to cy and to use the one point iteration scheme

* -- f (xi3
2?2+1= 2, (3.1)
* f’(G)’

where xc is the nth iterate.

. It is well known that Newton’s method as given above is quadratically
convergent.
It is important to understand how Newton’s method is constructed. At each iterative step we
construct a local linear model of our function f(z) at the point CC:and solve for the root (x;+~)
of the local model. In Newton’s method (Figure l), this local linear model is the tangent drawn
to the function f(z) at the current point XL.
The local linear model at XL is

A&(x) = f (g&l + f’ (G) b - x3. (3.2)

 A Variant of n’ewton’s iMethod

Figure 1. Newton’s kerative step.

Figure 2. Approximating the area by tlw rectangle fU?CU

E
f @)A

A B b

x* N h

Figure 3. Approximating the ares by the tmpezoiti A RED

90 S. WEERAKOONAND T. G. I. FERNANDO

This local linear model can be interpreted [l] in another way. From Newton’s theorem,

f(x) = f (4 + .I‘Z f’(x) dX. (3.3)

xf
In Newton’s method, the indefinite integral involved in (3.3) is approximated by the rectangle
ABCD (Figure 2), i.e.,

Z f’(x) dA M f’ (xi) (x - cc;) , (3.4)

sc
which will result in the model given in (3.2).

3..2. A Variant of Newton’s Method (VNM)

From Newton’s theorem,

f(x) = f (4 + 1X f’(x) dX. (3.5)

Z,,
In the proposed scheme, we approximate the indefinite integral involved in (3.5) by the trapez-
ium ABED (Figure 3), i.e.,

’ f’(x) dX M f (x - 4 LY(%) + f’(41. (3.6)

s 2% 0

Thus, the local model equivalent to (3.2) is

j&&r) = f(G) + ; (x - z,)[f’(z,) + f’(z)]. (3.7)

0
Note that not only the model and the derivative of the model agree with the function f(x) and
the derivative of the function f’(z), respectively, but also the second derivative of the model and
the second derivative of the function agree at the current iterate z = 5,. Even though the model
for Newton’s method matches with the values of the slope f/(x,) of the function, it does not
match with its curvature in terms of f”(z,).
We take the next iterative point as the root of the local model (3.7)

tin(zn+l) = 0, i.e.,

- &L) [f’(%) + f’(%+1)1 = 0

=+X
?f (XT4
n+l = Icn- [f’(x,) + f’(x,+1)].
Obviously, this is an implicit scheme, which requires having the derivative of the function at the
(n + l)th iterative step to calculate the (n + l)th iterate itself. We could overcome this difficulty
by making use of Newton’s iterative step to compute the (n + 1) th iterate on the right-hand side.
Thus, the resulting new scheme is

4. ANALYSIS OF CONVERGENCE
THEOREM 4.1. Let f : D -+ % for an open interval D. Assume that f has first, second, and
third derivatives in the interval D. If f(x) h as a simple root at a E D and x0 is sufficiently close
to o, then the new method defined by (3.8) satisfies the following error equation:

e,+l= (C:+iC3)ei,+O(et), (4.1)

where e, = x, - Q and C, = (l/j!)f(j)(a)/f(l)(a), j = 1,2,3,. . . .

 A Variant of Newton’s Method 91

PROOF. The suggested variant of Newton’s method (VNM) is

2.f(xn) =ot1.2,...,
x,+1 = xn - 11

f’(G) + f’ (G&+1) ’

where cr:,+r = Ic, - f(x,)/f’(~). L e t ck b e a simple root of f(z) (i.e., f(Q) = 0 and f/((U) # 0)
and 2,, = QI+ e,. We use the following Taylor expansions:

where C, = (l/j!)f(“)(~)/f(‘)(~). Furthermore, we have

f(l)(~~) = f(l)(a + e,) = f(l)(a) + fc2)(Cy)en

+ ~f(“)I~)ei
+0 (4)
= f’%) [l+fc2)(a)en
pya) +
1 f(“)(a)e2
5 f’l’(a)’+ O(4 1
(4.3)

= f(l)(a) [l + 2&e, + 3&e; + 0 (et)] .

Dividing (4.2) by (4.3),

-zz
f(xn) [e, + C2ei + C3ei + 0 (e:)] [1+ 2&e, + 3&e; + 0 (ei)]-’
f (‘)(xcn)
= [e, + C2ez + C3e: + 0 (et)]

x 1 - 2C2e, + 3Cset + 0 (ez)] + [2C Je7, + 3Caei + 0 (ex)]” - .)

{ [
= [e,+C2ei+Cae”, + 0 (et)] {l- [2Cze,+3C:~e~L+0 (e$] +4CieFL + ...} (4.4)

= [e, + C2ei + Csei + 0 (ei)] [l - 2&e,, + (4Ci - 3Ca) ei + 0 (efL)]

= e, - 2C2ez + (4C,2 - 3C3) ei + C2eFL - 2Cze3, + Csei + 0 (e:‘,)

= e, - C2ei + (2C,2 - 2Cs) e: + 0 (e:) ,

.x,:+1 = 5, - ~
“f(xn)
f(l)(xn)
=a+e, - [e, - C2ei + (2Cz - 2C3) ei + 0 (e:‘,)] , (by (4.4)) (4.5)

= N + Czei + (2Cs - 2C,2) e? + 0 (e?J] .

Again by (4.5) and the Taylor’s expansion,

f(l) (xi+1) = f(l)(cr) + [C2ei + (2C3 - 2Cz) e”, + 0 (e$)] Y2’(Q) + 0 (G)

= f(l)(~) { 1-t [2C2ei + 4 (Ca - Cz) ei + 0 (ei)] [ ~~~~/~)]} (,1.6)

= f(l)(a) [l + 2Czei + 4C2 (Ca - C.$ ei + 0 (ei)]

Adding (4.3) and (4.6),

 92 S. WEERAKOON AND T. G. I. FERNANDO

f’l’(ICn) + f(l) ($+I) = 2f’l’(cY) [ 1 + c 2en+ (C~++)e~+O(e~)]. (4.7)

From equations (4.2) and (4.7),

2.f (3%)
[f(l)(x,)+f(l) (x;+l)] = [e,+C& + c3e3, + 0 (c+l

x [I+G,e,,+ (C~++3)e2+0(e~)]-1

= [e,+Czei + Csei+O (et)]’ { 1 - [ C 2en+ (Ci+iC3)i$+O(et)]

= [e, + C2ei + C3ei + 0 ($)I [l- C2e, - %C3ei

+0 (ei)
=en - C2ez - +ei + C2ei - Czei + C3ei + 0 (e:)

=e,- (C$++)e3+0(e:).

(4.8)

Table 1

Function x0 i cot NOFE Root

f(x) NM VNM NM VNM NM VNM

(1) x3 + 4x2 - 10 -0.5 109 6 1.98 2.96 218 18 1.36523001341448

1 5 3 1.98 ND 10 9 -Do-
2 5 3 1.99 ND 10 9 -DO-
-0.3 113 6 1.99 3.05 226 18 -Do-

(2) sin2(x) - x2 + 1 1.40449164821621

NM - Newton’s method COC - Computational order of convergence

VNM - Variant of Newton’s method NOFE - Number of function evaluations
ND - Not defined i - Number of iterations to approximate the root to 15 decimal places
 A Variant of Newt,ou’s hlet.hod

‘l’hus,

( 1.9)

E(luatiou (4.9) establishes the third-order convergeme of the VNiU. I

5. CONCLUSIONS
We have shown that VNM is at least third-order convergent provided the fimt, swo~~rl. ;~utl
third derivatives of the function exist. Computed results (Table 1) ovc~r~vllelnliiigl~ support tlie
third-order convergence, and for some functions the Computational Order of Convergcnw (COC’)
is (YWI more than three. The most important characteristic of the, VN51 is t,llat unlike a11 ot,lwr
third-order or higher order methods, it is not required to comlmte seco~l or higllt~r clwivatiws
of tlit, function to carry out iterat,ions.
Apparently. the VNM needs one more function evaluation ut each iteration, IY~WII ~m11mwl
to Newton’s method. However, it is evident 1)~ the computed rrsult,s (Table 1) that tlw t,otal
numtwr of function evaluations required is less tlmn that of Ntwton’s met,hod.