View of Newton type iterative methods with higher order of convergence

J. Numer. Anal. Approx. Theory, vol. 45 (2016) no. 1, pp. 14–26 ictp.acad.ro/jnaat

NEWTON TYPE ITERATIVE METHODS WITH HIGHER ORDER OF CONVERGENCE

PANKAJ JAIN^∗, CHET RAJ BHATTA^„and JIVANDHAR JNAWALI^∗∗

Abstract. Newton type iterative methods with higher order of convergence are obtained. The order of convergence is further increased by amalgamating these methods with the standard secant method. The methods are compared to the similar recent methods.

MSC 2010. 65H05.

Keywords. Newton method, secant method, iterative method, nonlinear equa- tion, order of convergence.

1. INTRODUCTION

Quite often, we come across numerous nonlinear equations which need to be solved. If the equation is not a polynomial equation, then it is not always easy to deal with such equations. To this end, one or the other numerical iterative method is employed. One such classical standard method is the Newton method

x_n+1=x_n−_f^f0^(x(xⁿn⁾)

which is quadratically convergent. Over the years, a lot of methods have appeared, each one claims to be better than the other in some or the other aspect. We mention here the method given by Weerakoon and Fernando [8]

which is based on the Newton’s theorem f(x) =f(x_n) +

Z x xn

f⁰(λ)dλ

and the integral involved is approximated by the trapezoidal rule,i.e., Z x

xn

f⁰(λ)dλ= ^(x−x₂ ⁿ⁾ f⁰(x) +f⁰(xn).

∗Department of Mathematics, South Asian University, Akbar Bhawan, Chanakya Puri, New Delhi-110021, India, e-mail:[email protected]and[email protected].

„Central Department of Mathematics, Tribhuvan University, Kirtipur Kathmandu, Nepal, e-mail: [email protected].

∗∗Central Department of Mathematics, Tribhuvan University, Kirtipur Kathmandu, Nepal, e-mail: [email protected].

As a result, Weerakoon and Fernando obtained the following iterative method for solving the nonlinear equationf(x) = 0 :

(1) x_n+1 =x_n− _f0(xn^2f)+f^(x0n(z⁾n+1), wherezn+1=xn−_f^f0^(x(xⁿn⁾).

The method so obtained is of third order. In the present paper, the aim is to modify method (1). In fact, in (1), f⁰ is a function of the previously calculated iterate. In our modification, f⁰ would be a function of some other convenient point. It is proved that the corresponding method has order of convergence 5.1925. We follow the technique of McDougall and Wotherspoon [7] who modified Newton’s method in a similar way yielding the order of convergence of their method as 1 +√

2.

Further, in [3], it was proved that if any method for solving nonlinear equa- tion is used in conjunction with the standard secant method then the order of the resulting method is increased by 1. We shall show, in this paper (see Theorem 3.2), that this order can be increased by more than 1. In fact, we prove that if our own method (which is of order 5.1925) is combined with the secant method than the new method is of order 7.275.

2. THE METHOD AND THE CONVERGENCE

We propose the following method:

Ifx₀ is the initial approximation, then

(2)

x^∗₀ =x₀

x₁ =x^∗₀−_f0(x^2f(x∗₀)+f^∗00)(z1), where z₁ =x₀−_f^f(x0(x⁰0⁾)

x^∗₁ =x₁−_f0(x^2f1)+f^(x10)(z^∗₁), with z₁^∗ =x₁− ^f(x1)

f⁰[1

2(x0+x^∗₀)] =x₁−_f^f0^(x(x¹0⁾).



























Subsequently, for n≥1, the iterations can be obtained as follows:

(3)

x^∗_n=x_n− _f0(x^2fn)+f^(xn0)(z^∗_n), where z^∗_n=x_n− ^f(xn)

f⁰[1

2(xn−1+x^∗_n−1)]

x_n+1 =x^∗_n− _f0(x^∗_n^2f)+f^(x0∗n(z⁾n+1), with z_n+1 =x_n− ^f(xn)

f⁰[1

2(xn+x^∗_n)].























Below, we prove the convergence result for the method (2)–(3).

Theorem 1. Let α be a simple zero of a function f which has sufficient number of smooth derivatives in a neighborhood ofα. Then the method(2)–(3) is convergent and has the order of convergence 5.1925.

Proof. Lete_nand e^∗_n denote respectively the errors in the termsx_nandx^∗_n. Also, we denote c_j = _j!f^fj0^(α)(α), j = 2,3,4..., which are constants. The error equation for the method (1) as obtained by Weerakoon and Fernando [8] is given by

e_n+1 =ae³_n,

where a = c²₂ + ¹₂c3 and we have neglected higher power terms of en. In particular, the errore₁ inx₁ in the equations (2) is given by

(4) e1=ae³₀.

We now proceed to calculate the errore^∗₁ inx^∗₁. By using Taylor series expan- sion and binomial expansion, we get

f(x1)

f⁰(x0) = _f^f0^(α+e(α+e¹0⁾)

= e₁+c₂e²₁+c₃e³₁+O(e⁴₁) 1 + 2c₂e₀+ 3c₃e²₀+O(e³₀)⁻¹

=e₁−2c₂e₀e₁+O(e⁵₀) so that

x₁− _f^f(x0(x¹0⁾) =α+ 2c₂e₀e₁+O(e⁵₀).

Consequently, by Taylor series expansion, it can be calculated that f⁰(z₁^∗) =f⁰(α) 1 + 4c²₂e0e1+O(e⁵₀).

Also

f⁰(x₁) =f⁰(α) 1 + 2c²₂e₁+ 3c₃e²₁+O(e³₁) so that

(5) f⁰(x1) +f⁰(z₁^∗) = 2f⁰(α) 1 +c2e1+ 2c²₂e0e1+O(e⁵₀).

Now, using (4) and (5), the errore^∗₁ inx^∗₁ in the equation (2) can be calculated as

e^∗₁ =e₁− e₁+c₂e²₁+O(e³₁) 1 +c₂e₁+ 2c²₂e₀e₁+O(e⁵₀)⁻¹

= 2c²₂e₀e²₁

=ba²e⁷₀,

whereb= 2c²₂. Usinge^∗₁, we now compute the error e₂ in the term x₂ =x^∗₁−_f0(x^2f∗₁)+f^(x∗1)0(z2),

where

z₂=x₁− ^f(x1)

f⁰ x1+x^∗₁ 2

.

Now

f^{0 x1+x}₂ ^∗1=f⁰ α+^e1+e₂ ^∗1

=f⁰(α) 1 +c₂e₁+c₂e^∗₁+³₄c₃e²₁+O(e⁹₀) so that

f(x1) f^{0 x1+x}

∗ 1 2

= e1+c2e²₁+O(e³₁) 1 +c2e1+c2e^∗₁+³₄c3e²₁+O(e⁹₀)⁻¹

=e₁+ ¹₄c₃e³₁−c₂e₁e^∗₁ and therefore

z2 =α−¹₄c3e³₁+c2e1e^∗₁, where the higher power terms are neglected. Thus

f⁰(z2) =f⁰(α) 1−¹₂c2c3e³₁+ 2c²₂e1e^∗₁ and

f⁰(x^∗₁) =f⁰(α) 1 + 2c₂e^∗₁+ 3c₃e^∗₁². Using the above considerations, the errore₂ inx₂ is given by

e₂=e^∗₁− e^∗₁+c₂e^∗₁²+c₃e^∗3₁ 1 +c₂e^∗₁− ¹₄c₂c₃e³₁⁻¹

=−¹₄c2c3e³₁e^∗₁

=ce³₁e^∗₁,

wherec=−¹₄c₂c₃. In fact, it can be worked out that for n≥1, the following relation holds:

(6) en+1=ce³_ne^∗_n.

In order to computeen+1 explicitly, we need to computee^∗_n. We already know e^∗₁. We now computee^∗₂. We have

x^∗₂ =x₂−_f0(x^2f2)+f^(x20)(z₂^∗), where

z₂^∗ =x₂− ^f(x2)

f⁰ x1+x^∗₁ 2

.

Like above, it can be calculated that the errore^∗₂ is given by e^∗₂=de₁e²₂,

where d = c²₂ and, again, it can be checked that in general, for n ≥ 2, the following relation holds:

(7) e^∗_n=den−1e²_n.

In the view of (6) and (7), the error at each stage inx^∗_nandxn+1are calculated which are tabulated below:

n en e^∗_n

0 e0 e0

1 ae³₀ a²be⁷₀

2 a⁵bce¹⁶₀ a¹¹b²c²de³⁵₀ 3 a²⁶b⁵c⁶de⁸³₀ a⁵⁷b¹¹c¹³d³e¹⁸²₀ 4 a¹³⁵b²⁶c³²d⁶e⁴³¹₀ a²⁹⁶b⁵⁷c⁷⁰d¹⁴e⁹⁴⁵₀ 5 a⁷⁰¹b¹³⁵c¹⁶⁷d³²e²²³⁸₀

... ... ...

Table 1. Successive errors.

It is observed that the powers of e₀ in the errors at each iterate form a sequence

(8) 3, 16, 83, 431, 2238, ...

and the sequence of their successive ratios is

16

3, ⁸³₁₆, ⁴³¹₈₃, ²²³⁸₄₃₁, ...

or,

5.3334, 5.1875, 5.1927, 5.1925, ...

This sequence seems to converge to the number 5.1925 approximately. Indeed, if the terms of the sequence (8) are denoted by{α_i}, then it can be seen that (9) α_i = 5αi−1+αi−2, i= 2,3,4...

If we set the limit

αi

αi−1 = ^α_αⁱ⁻¹

i−2 =R, Then dividing (9) byαi−1, we obtain

R²−5R−1 = 0 which has its positive root as R = ⁵⁺

√ 29

2 ≈ 5.1925. Hence the order of

convergence of the method is at least 5.1925.

Next, we give two variants of the method (2)–(3). Note that, in (2)–(3), the arithmetic average of the points xn, x^∗_n, n = 0,1,2... has been used. We propose methods in which the arithmetic average is replaced by harmonic as well as geometric averages. With harmonic average, we propose the following

method: Ifx0 is the initial approximation, then

(10)

x^∗₀=x0

x₁=x^∗₀−_f0(x^2f(x∗₀)+f^∗00)(z1), where z1=x0− ^f(x0)

f⁰

_2x0x^∗

0

x0+x^∗₀

=x0−_f^f0^(x(x⁰0⁾)

x^∗₁=x₁−_f0(x^2f(x1)+f¹⁰⁾(z^∗₁), with z₁^∗=x1− ^f(x1)

f⁰

_2x0x^∗

0

x0+x^∗₀

=x1−_f^f0^(x(x¹0⁾).

































 Subsequently, for n≥1, the iterations can be obtained as follows:

(11)

x^∗_n=x_n−_f0(x^2f(xn)+fⁿ⁰⁾(z^∗_n), where z_n^∗ =x_n− ^f(xn)

f⁰

2xn−1x^∗_n−1 xn−1+x^∗_n−1

x_n+1=x^∗_n−_f0(x^∗_n^2f(x)+f^∗n0(z⁾n+1), with z_n+1=x_n− ^f(xn)

f⁰

_2x

nx^∗_n xn+x^∗_n

.































For the geometric average of the points xn, x^∗_n, n = 0,1,2..., the following method is proposed:

(12)

x^∗₀ =x0

x₁ =x^∗₀−_f0(x^2f(x∗₀)+f^∗00)(z1), where z1 =x0− ^f(x0)

f⁰(√

x0x^∗₀) =x0−_f^f(x0(x⁰0⁾)

x^∗₁ =x1−_f0(x^2f1)+f^(x10)(z₁^∗), with z₁^∗ =x1− ^f(x1)

f⁰(√

x0x^∗₀) =x1−_f^f(x0(x¹0⁾).





























 Subsequently, for n≥1, the iteration can be obtained as follows:

(13)

x^∗_n=xn−_f0(x^2f(xn)+fⁿ⁰⁾(z_n^∗), where z_n^∗ =xn− ^f(xn)

f⁰(√

xn−1x^∗_n−1) x_n+1=x^∗_n−_f0(x^∗_n^2f(x)+f^0∗n(z⁾n+1), with z_n+1=x_n− ^f(xn)

f⁰(√ xnx^∗_n).























The convergence of the methods (10)–(11) and (12)–(13) can be proved on the similar lines as those in Theorem 1. We only state the results below:

Theorem 2. Let α be a simple zero of a function f which has sufficient number of smooth derivatives in a neighborhood of α. Then for solving non- linear equation f(x) = 0, the method (10)–(11) is convergent with order of convergence 5.1925.

Theorem 3. Let α be a simple zero of a function f which has sufficient number of smooth derivatives in a neighborhood of α. Then for solving non- linear equation f(x) = 0, the method (12)–(13) is convergent with order of convergence 5.1925.

3. METHODS WITH HIGHER ORDER CONVERGENCE

In this section, we obtain a new iterative method by combining the iterations of method (2)–(3) with secant method and prove that the order of convergence is more than 5.1925. Precisely, we propose the following method: Ifx₀ is the initial approximation, then

(14)

x^∗₀ =x0

x^∗∗₀ =x^∗₀−_f0(x^2f∗₀)+f^(x∗0)0(z1), where z1 =x0−_f^f0^(x(x⁰0⁾)

x₁ =x^∗∗₀ −_f(x^x∗∗^{∗∗0 −x∗0}

0 )−f(x^∗₀)f(x^∗∗₀ ).



















Subsequently, for n≥1, the iterations can be obtained as follows:

(15)

x^∗_n=xn−_f0(x^2f(xn)+fⁿ⁰⁾(z_n^∗), where z_n^∗ =xn− ^f(xn)

f⁰ xn−1+x^∗_n−1 2

x^∗∗_n =x^∗_n−_f0(x^∗_n^2f)+f^(x0∗n(z⁾n+1), where z_n+1=x_n− ^f(xn)

f⁰ xn+x^∗_n 2

xn+1=x^∗∗₁ −_f(x^x∗∗^{∗∗n −x∗n}

n )−f(x^∗_n)f(x^∗∗_n).































Remark4. In [3], it was proved that if the iterations of any method of order p for solving nonlinear equations are used alternatively with secant method, then the new method will be of order p+ 1. Thus, in view of that result, the method (14)–(15) is certainly of order at least 6.1925. However, we prove below that the order is more.

Theorem 5. Let f be a function f having sufficient number of smooth derivatives in a neighborhood ofαwhich is a simple root of the equationf(x) = 0. Then method (14)–(15) to approximate the root α is convergent with order of convergence 7.275.

Proof. We argue on the lines of that of Theorem 1 and the error equa- tion of the standard secant method. In particular, the errors e^∗₀, e^∗∗₀ and e₁, respectively, in x^∗₀, x^∗∗₀ and x1 in equations (14) are given by

e^∗₀ =e0

e^∗∗₀ =ae³₀, wherea=c²₂+¹₂c₃ e1 =λae⁴₀, whereλ=c2. Also, the errorse^∗₁ in x^∗₁ in equation (15) is given by

e^∗₁ = 2c²₂e₀e²₁

=λ²a²be⁹₀, whereb= 2c²₂ and the errore^∗∗₁ inx^∗∗₁ in equation (15) is given by

e^∗∗₁ =−¹₄c₂c₃e³₁e^∗₁

=ce³₁e^∗₁,

wherec=−¹₄c₂c₃. In fact, it can be worked out that for n≥1, the following relation holds:

(16) e^∗∗_n =ce³_ne^∗_n.

In order to compute e^∗∗_n explicitly, we need to compute en and e^∗_n. We have already computede₁ and e^∗₁. From the proof of Theorem 1

e^∗₂=de₁e²₂,

whered=c²₂ and, again, it can be checked that the following relation holds:

(17) e^∗_n=den−1e²_n.

Also from (15), it can be shown that

e₂ =λe^∗₁e^∗∗₂ .

Thus, for n ≥ 1, it can be shown that error en+1 in xn+1 in the method (14)–(15) satisfies the following recursion formula

(18) e_n+1 =λe^∗_ne^∗∗_n

Using the above information, the errors at each stage in x^∗_n, x^∗∗_n and x_n are obtained and tabulated as follows:

We do the analysis of Table 2 as done in the proof of Theorem 1 for Table 1. Note that the powers ofe0 in the error at each iterate from the sequence (19) 4, 30, 218, 1586, 11538, ....

and the sequence of their successive ratios is

30

4 , ²¹⁸₃₀, ¹⁵⁸⁶₂₁₈, ¹¹⁵³⁸₁₅₈₆, ...

or

7.5, 7.2667, 7.2752, 7.2749, ....

n en e^∗_n e^∗∗_n

0 e0 e0 ae³₀

1 λae⁴₀ λ²a²be⁹₀ λ⁵a⁵bce²¹₀

2 λ⁸a⁷b²ce³⁰₀ λ¹⁷a¹⁵b⁵c²e⁶⁴₀ λ⁴²a³⁶b¹¹c⁶e¹⁵⁴₀ 3 λ⁶⁰a⁵¹b¹³c⁸e²¹⁸₀ λ¹²⁸a¹⁰⁹b²⁹c¹⁷e⁴⁶⁶₀ λ³⁰⁸a²⁶⁰b⁶⁸c⁴²e¹¹²⁰₀ 4 λ⁴³⁷a³⁶⁹b⁹⁷c⁵⁹e¹⁵⁸⁶₀ λ⁹³⁴a⁷⁸⁹b²⁰⁸c¹²⁶e³³⁹⁰₀ λ²²⁴⁵a¹⁸⁹⁶b⁴⁹⁹c³⁰⁴e⁸¹⁴⁸₀ 5 λ³¹⁸⁰a²⁶⁸⁵b⁷⁰⁷c⁴³⁰e¹¹⁵³⁸₀

... ... ... ...

Table 2. Successive errors.

If the terms of the sequence (19) are denoted by{N_i}, then it can be seen that N_i = 7Ni−1+ 2Ni−2, i= 2,3,4, ....

Thus, as in Theorem 1, the rate of convergence of method (14)–(15) is at least

7.275.

It is natural to consider the variants of the method (14)–(15), where in the expression of z_n and z^∗_n, the arithmetic mean is replaced by harmonic mean as well as geometric mean as done in methods (10)–(11) and (12)–(13), respectively. Precisely, with harmonic mean, we propose the following method:

(20)

x^∗₀ =x₀

x^∗∗₀ =x^∗₀−_f0(x^2f(x∗₀)+f^∗00)(z1), where z₁ =x₀− ^f(x0)

f⁰

_2x0x^∗

0

x0+x^∗₀

=x₀−_f^f(x0(x⁰0⁾)

x₁ =x^∗∗₀ −_f(x^x∗∗^{∗∗0 −x∗0}

0 )−f(x^∗₀)f(x^∗∗₀ )























followed by (forn≥1)

(21)

x^∗_n=x_n−_f0(x^2f(xn)+fⁿ⁰⁾(z^∗_n), where z_n^∗ =x_n− ^f(xn)

f⁰

2xn−1x^∗_n−1 xn−1+x^∗_n−1

x^∗∗_n =x^∗_n−_f0(x^∗_n^2f(x)+f^∗n0(z⁾n+1), where z_n+1=x_n− ^f(xn)

f⁰

_2x

nx^∗_n xn+x^∗_n

xn+1=x^∗∗₁ −_f(x^x∗∗^{∗∗n−x∗n}

n)−f(x^∗_n)f(x^∗∗_n )



































and with the geometric mean, we propose the following :

(22)

x^∗₀ =x0

x^∗∗₀ =x^∗₀−_f0(x^2f∗₀)+f^(x∗0)0(z1), where z1 =x0− ^f(x0)

f⁰(√

x0x^∗₀) =x0−_f^f0^(x(x⁰0⁾)

x₁ =x^∗∗₀ −_f(x^x∗∗^{∗∗0 −x∗0}

0 )−f(x^∗₀)f(x^∗∗₀ )



















followed by (forn≥1)

(23)

x^∗_n=xn−_f0(x^2f(xn)+fⁿ⁰⁾(z_n^∗), where z_n^∗ =x_n− ^f(xn)

f⁰(√

xn−1x^∗_n−1) x^∗∗_n =x^∗_n−_f0(x^∗_n^2f)+f^(x0∗n(z⁾n+1), where z_n+1=x_n− ^f(xn)

f⁰(√ xnx^∗_n)

x_n+1=x^∗∗₁ −_f(x^x∗∗^{∗∗n −x∗n}

n )−f(x^∗_n)f(x^∗∗_n).



























The convergence of the methods (20)–(21) and (22)–(23) can be proved by using the arguments as used in the proof of Theorem 5. We skip the details for conciseness.

4. ALGORITHMS AND NUMERICAL EXAMPLES

We give below an algorithm to implement the method (2)–(3):

Algorithm 6. Step 1 : For the given tolerance ε > 0 and iteration N, choose the initial approximation x0 and set n= 0.

Step 2 : Follow the sequence of expressions:

x^∗₀ =x₀

x₁ =x^∗₀−_f0(x^2f(x∗₀)+f^∗00)(z1), where z₁ =x₀−_f^f0^(x(x⁰0⁾)

x^∗₁ =x₁−_f0(x^2f1)+f^(x10)(z₁^∗), where z₁^∗ =x1− ^f(x1)

f⁰ x0+x^∗₀ 2

=x1− _f^f(x0(x¹0⁾)

Step 3 : For n= 1,2,3, . . ., calculate x2, x3, x4, . . . by the following sequence of expressions:

x^∗_n=xn−_f0(x^2fn)+f^(xn0)(z^∗_n), where z_n^∗ =xn− ^f(xn)

f⁰ xn−1+x^∗_n−1 2

x_n+1 =x^∗_n−_f0(x^∗_n^2f)+f^(x0∗n(z⁾n+1), where z_n+1 =x_n− ^f(xn)

f⁰ xn+x^∗_n 2

Step 4 : Stop if either |x_n+1−xn|< ε or n > N. Step 5 : Set n=n+ 1 and repeat Step 3.

Example 7. We apply method (2)–(3) on the nonlinear equation

(24) cosx−xe^x+x² = 0.

This equation has a simple root in the interval (0,1). Taking initial approx- imation as x0 = 1, Table 3 shows the iterations of McDougall-Wotherspoon method, a third order method (1) and our method (2)–(3).

n W-F Method (1) M-W method (2)–(3) method 1. 1.1754860092539474 0.89033621746836966 0.64406452481689269 2. 0.7117526001461193 0.66469560530044569 0.63915407608296659 3. 0.63945030188514695 0.63928150457301036 0.63915411559451774 4. 0.63915408656045591 0.63915408990276223 0.6391540955014231 5. 0.63915410631623149 0.63915410965853769 0.63915407540832936 6. 0.63915412607200606 0.6391540698096656 0.6391541149198805 7. 0.63915408622313585 0.63915408956544117 0.63915409482678587 8. 0.63915410597891142 0.63915410932121663 0.63915407473369212 9. 0.639154125734686 0.63915406947234454 0.63915411424524327 10. 0.63915408588581579 0.63915408922812 0.63915409415214863 11. 0.63915410564159136 0.63915410898389557 0.63915407405905489 12. 0.63915412539736594 0.63915406913502348 0.63915411357060603 13. 0.63915408554849573 0.63915408889079894 0.6391540934775114 14. 0.63915410530427119 0.63915410864657451 0.63915407338441765 15. 0.63915412506004576 0.63915406879770231 0.6391541128959688 16. 0.63915408521117556 0.63915408855347788 0.63915409280287416 17. 0.63915410496695113 0.63915410830925345 0.63915407270978042 18. 0.6391541247227257 0.63915406846038125 0.63915411222133156 19. 0.6391540848738555 0.63915408821615682 0.63915409212823693 20. 0.63915410462963107 0.63915410797193239 0.63915407203514318

Table 3. Numerical results for different methods.