A New Modification of Newton Method with Cubic Convergence

DOI: 10.4236/apm.2021.111001   PDF   HTML   XML   68 Downloads   167 Views  

Abstract

Newton’s method is used to find the roots of a system of equations f (x) = 0. It is one of the most important procedures in numerical analysis, and its applicability extends to differential equations and integral equations. Analysis of the method shows a quadratic convergence under certain assumptions. For several years, researchers have improved the method by proposing modified Newton methods with salutary efforts. A modification of the Newton’s method was proposed by McDougall and Wotherspoon [1] with an order of convergence of 1+ √2. On a new type of methods with cubic convergence was proposed by H. H. H. Homeier [2]. In this article, we present a new modification of Newton method based on secant method. Analysis of convergence shows that the new method is cubically convergent. Our method requires an evaluation of the function and one of its derivatives.

Share and Cite:

Goudjo, A. and Kouye, L. (2021) A New Modification of Newton Method with Cubic Convergence. Advances in Pure Mathematics, 11, 1-11. doi: 10.4236/apm.2021.111001.

1. Introduction

Determining zeros of scalar function f lines up with the most important problems in both theory and practice not only in mathematics but also in many other fields like engineering sciences, physics, computer science, finance. These problems lead to a well-endowed mixture of mathematics, numerical analysis and computing science. Discovering the source of non-linear equation is one of the most important challenges in science and engineering. The main concept to all root finding methods is the recurrence of successive approximation. Actually, analytical method for the non-linear Equation (1.1) is hard or nearly non existent.

f ( x ) = 0 where f : D (1.1)

In current years, researchers have been curious about modifying the Newton method which is the foundation of all algorihms for solving these problems. Current design methods tend to focus on usage of fonction evaluations and avoid usage of the derivatives. In this study, we consider a non-linear Equation (1.1) and we present a new modification of Newton method. The analysis of convergence shows that the new method is cubically convergent. In a recurrence way, our method requires an evaluation of the function and the one of its derivatives.

2. Preliminaries

The idea of the iterative method is that we make some estimate of the solution and we repeatedly improve that estimate using some well defined operations, until we end up with an approximate answer which is quite close to real answer.

Let f : D be r-times Fréchet differentiable function on an open interval D . x * be a real zero of the non linear equation

f ( x ) = 0 (2.1)

As well known, roots of Equation (2.1) can be found analytically only in some special cases. We most commonly solve (2.1) approximately, that is, we find an approximation to the zero x * by applying some iterative method of the form:

x n + 1 = φ ( x n ) (2.2)

where x n is an approximation to the zero x * . The function φ is called iteration function.

Definition 2.1. Let f ( x ) be a real valued function with root x * and let ( x n ) n be a sequence of real number from iterative method (sequence of iterate) that converge toward x * . If there exists a real number r and a nonzero constant C p such that:

lim n + x n + 1 x * ( x n x * ) p = C p 0.

Then p is called the order of convergence and C p is the factor of convergence orthe asymptotic error constant.

Definition 2.2. Let e n = x n x * be the error of the approximation in the nth iteration.

e n + 1 = C p e n p + O ( e n p + 1 ) (2.3)

is the error equation. If the error equation exists, the p is the order of convergence ofthe iterative method.

Theorem 2.3. (Schroder-Traub 1964) Let φ an iterative function such that φ ( r ) is continuous in a neighborhood of x * . Then, φ is of order p if only if

φ ( x * ) = x * , φ ( x * ) = φ ( 2 ) ( x * ) = = φ ( p 1 ) ( x * ) = 0 , φ ( p ) ( x * ) 0 (2.4)

The asymptotic error constant is given by:

lim n + | x n + 1 x * | | x n x * | p = | φ ( p ) ( x * ) p ! | (2.5)

Theorem 2.4 (Traub 1964 [3] ) Let x * be a simple zero of a function f and let φ define an iterative method of order p. Then a composite iterative function Ψ introduced by Newtons method

Ψ ( x ) = φ ( x ) f ( φ ( x ) ) f ( x ) (2.6)

defines an iterative method of order p + 1 .

Theorem 2.5 (Traub 1964 p. 28 [3] ) Let φ 1 , φ 2 , , φ s be iteration functions with the orders p 1 , p 2 , , p s respectively. Then the composition

Ψ ( s ) = φ 1 φ 2 φ s ( x ) (2.7)

defines the iterative method of order p 1 p 2 p s .

Definition 2.6. Let r be the number of function evaluations per iteration of the method. The efficiency index of the method is defined by:

I E = p r = p 1 r (2.8)

where p is the order of convergence of the method.

Definition 2.7. Suppose that x n 2 , x n 1 et x n are three successive iterative closer to the root x * . Then the computational order of convergence may be approximated by:

C O C ln ( δ n ÷ δ n 1 ) δ n 1 ÷ δ n 2 (2.9)

where δ n = f ( x n ) ÷ f ( x n ) .

3. Construction of the Methods and Convergence Analysis

In this section, we recall the modified Newton method that was proposed by Gentian Zavalani ( [4] ). To determine the order of convergence of the sequence ( x n ) n , let consider the Taylor expansion of g ( x n ) where the iterative method is x n + 1 = g ( x n ) and the function g satisfied:

1) There exist [ a , b ] such that g ( x ) [ a , b ] for all x [ a , b ]

2) There exist [ a , b ] such that | g ( x ) | L < 1 for all x [ a , b ]

g ( x n ) = g ( x ) + g ( x ) ( x n x ) + g ( x ) 2 ! ( x n x ) 2 + g ( 3 ) ( x ) 3 ! ( x n x ) 3 + + g ( l ) ( x ) l ! ( x n x ) l + (3.1)

Definition 3.1. The mapping F : n is (totally or Fréchet) differentiable at x if the Jacobian matrix ( J F ( x ) ) i j = ( i F j ) i j exists at x and

lim h 0 F ( x + h ) F ( x ) + J F ( x ) h h = 0 (3.2)

If n = 1 , this defintion reduces to the usual definition of differentiability.

Definition 3.2. For mapping F : Ω n n , a solution x * Ω of F ( x ) = 0 is simple if F is differentiable at x * and J F ( x * ) is non singular.

In this work, we assume that f admits a unique and simple solution.

Iterative Methods

For any x , x n D we may write the Taylor’s expansion for f as follows:

f ( x ) = f ( x n ) + f ( x n ) ( x x n ) + f ( x n ) 2 ! ( x x n ) 2 + f ( 3 ) ( x n ) 3 ! ( x x n ) 3 + + f ( r 1 ) ( x n ) ( r 1 ) ! ( x x n ) r 1 + + 0 1 ( 1 t ) r 1 ( r 1 ) ! f ( r ) ( x n + t ( x x n ) ) ( x x n ) r d t (3.3)

for r = 1 , we have:

f ( x ) = f ( x n ) + 0 1 f ( x n + t ( x x n ) ) ( x x n ) d t (3.4)

Approximating the integral in (3.4), we have:

0 1 f ( x n + t ( x x n ) ) ( x x n ) d t f ( x n ) ( x x n ) (3.5)

By using f(x) = 0, we have

f ( x n ) + f ( x n ) ( x x n ) = 0 (3.6)

Then

x n + 1 = x n f ( x n ) f ( x n ) (3.7)

This is known as Newton method for the non linear equations f ( x ) = 0 and has quadratic convergence when x 0 the initial guess is quite close to x * . If we approximate the integral in (3.4) by using the closed-open quadrature formula ( [5] ):

x n x f ( t ) d t Q m ( t ) = ( x x n ) j = 1 m ω j f ( x n + τ j ( x x n ) ) (3.8)

· τ j [ 0,1 ] .

· ω j weigths satisfying j = 1 m ω j = 1 and j = 1 m ω j τ j = 1 2

Then

0 1 f ( x n + t ( x x n ) ) ( x x n ) d t 1 4 [ f ( x n ) + 3 f ( x n + 2 x 3 ) ] ( x x n ) (3.9)

Thus, by using f(x) = 0, we have:

x n + 1 = x n 4 f ( x n ) f ( x n ) + 3 f ( x n + 2 x 3 ) (3.10)

x n + 1 = x n 4 [ f ( x n ) + 3 f ( x n + 2 x 3 ) ] 1 f ( x n ) (3.11)

Algorithm For a given x 0 , compute approximate solution x n + 1

· Predictor step:

ρ n = x n f ( x n ) f ( x n ) (3.12)

· Correction step:

x n + 1 = x n 4 [ f ( x n ) + 3 f ( x n + 2 x 3 ) ] 1 f ( x n ) (3.13)

This is another iterative method for solving the non linear Equation (1.1). These modifications of Newton method are very important and interesting because per iteration, they require one evaluation of the function and two evaluation of the derivative, not requiring the second derivative f but they can converge cubically.

Theorem 3.3. Let f : D be r-times Fréchet differentiable function on an open interval D . x * be a real zero of the non linear equation f ( x ) = 0 . The iterative method defined by: For given x 0 ,

{ ρ n = x n f ( x n ) f ( x n ) x n + 1 = x n 4 f ( x n ) f ( x n ) + 3 f ( x n + 2 x 3 ) (3.14)

has cubic convergence and satisfies the error equation:

[ f ( x n ) + 3 f ( x n + 2 x 3 ) ] e n + 1 = [ f ( x n ) ( f ( x n ) ) 1 f ( x n ) ] e n 3 + O ( e n 4 ) (3.15)

4. New Modified Newton Method

We consider the predictor-corrector method (3.14):

{ ρ n = x n f ( x n ) f ( x n ) x n + 1 = x n 4 f ( x n ) f ( x n ) + 3 f ( x n + 2 ρ n 3 ) (4.1)

We replace f ( x n ) by finite difference approximation

f ( x n ) f ( x n 1 ) x n x n 1 (4.2)

which is a suitable approximation which does not require new information. The predictor step becomes the secant method scheme. The scheme (3.14) becomes:

{ ρ n = x n ( x n x n 1 ) f ( x n ) f ( x n ) f ( x n 1 ) x n + 1 = x n 4 ( x n x n 1 ) f ( x n ) f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) (4.3)

Our option is motivated by the fact that the evaluation of two derivative may delay the convergence of the method. The proposed method requires only by iteration an evaluation of the function and one of its derivative which improved the index of efficiency of the method compared to those propose in many other works. It has a convergence of order p = 3 . More precisely, the algorithm of our iterative method is the following:

1) For a given x 0 ,

2) computing

x 1 = x 0 f ( x 0 ) f ( x 0 ) (4.4)

3) For n 1 ,

ρ n = x n ( x n x n 1 ) f ( x n ) f ( x n ) f ( x n 1 ) (4.5)

and

x n + 1 = x n 4 ( x n x n 1 ) f ( x n ) f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) (4.6)

Theorem 4.1. Let f : D be r-times Fréchet differentiable function on an open interval D . x * be a real zero of the non linear equation f ( x ) = 0 . The iterative method defined by (4.3) has p = 3 order convergence and the error equation is:

e n + 1 = ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) [ f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) ] 1 [ f ( x n ) ] 2 e n 3 (4.7)

Proof. Let x * the unique root simple of Equation (1.1).

Let x n an approximation of x * obtained by the Scheme (4.6).

Let e n = x * x n the approximation error.

e n + 1 = x * x n + 1 (4.8)

e n + 1 = x * x n + 4 ( x n x n 1 ) f ( x n ) f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) (4.9)

e n + 1 = e n + 4 ( x n x n 1 ) f ( x n ) f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) (4.10)

[ f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) ] e n + 1 = [ f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) ] e n + 4 ( x n x n 1 ) f ( x n ) (4.11)

By expansion, we have:

0 = f ( x * ) = f ( x n ) + f ( x n ) ( x * x n ) + f ( x n ) 2 ! ( x * x n ) 2 + f ( 3 ) ( x n ) 3 ! ( x * x n ) 3 + f ( 4 ) ( x n ) 4 ! ( x * x n ) 4 + (4.12)

Then

0 = f ( x n ) + f ( x n ) e n + f ( x n ) 2 ! e n 2 + f ( 3 ) ( x n ) 3 ! e n 3 + f ( 4 ) ( x n ) 4 ! e n 4 + (4.13)

By replacing f ( x ) by (4.2)

f ( x n ) = f ( x n ) f ( x n 1 ) x n x n 1 e n + f ( x n ) 2 ! e n 2 + f ( 3 ) ( x n ) 3 ! e n 3 + f ( 4 ) ( x n ) 4 ! e n 4 + (4.14)

x n x n 1 f ( x n ) f ( x n 1 ) f ( x n ) = e n + x n x n 1 f ( x n ) f ( x n 1 ) f ( x n ) 2 ! e n 2 + x n x n 1 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) 3 ! e n 3 + x n x n 1 f ( x n ) f ( x n 1 ) f ( 4 ) ( x n ) 4 ! e n 4 + (4.15)

By using the predictor step, we have:

ρ n x n = x n x n 1 f ( x n ) f ( x n 1 ) f ( x n ) (4.16)

ρ n x n = e n + x n x n 1 f ( x n ) f ( x n 1 ) f ( x n ) 2 ! e n 2 + x n x n 1 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) 3 ! e n 3 + x n x n 1 f ( x n ) f ( x n 1 ) f ( 4 ) ( x n ) 4 ! e n 4 +

x n + 2 ρ n 3 = x n + 2 3 ( ρ n x n ) (4.17)

Taylor expansion of f ( x n + 2 ρ n 3 ) at x n gives:

f ( x n + 2 ρ n 3 ) = f ( x n ) + 2 3 ( ρ n x n ) f ( x n ) + 1 2 ( 2 3 ) 2 ( ρ n x n ) 2 f ( 3 ) ( x n ) + (4.18)

f ( x n + 2 ρ n 3 ) = f ( x n ) f ( x n 1 ) x n x n 1 + 2 3 [ e n + x n x n 1 f ( x n ) f ( x n 1 ) f ( x n ) 2 ! e n 2 + x n x n 1 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) 3 ! e n 3 + ] f ( x n )

+ 1 2 ( 2 3 ) 2 [ e n + x n x n 1 f ( x n ) f ( x n 1 ) f ( x n ) 2 ! e n 2 + x n x n 1 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) 3 ! e n 3 + ] 2 f ( 3 ) ( x n ) + 1 6 ( 2 3 ) 3 [ e n + x n x n 1 f ( x n ) f ( x n 1 ) f ( x n ) 2 ! e n 2 + x n x n 1 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) 3 ! e n 3 + ] 3 f ( 4 ) ( x n ) + (4.19)

f ( x n + 2 ρ n 3 ) = f ( x n ) f ( x n 1 ) x n x n 1 + 2 e n 3 f ( 2 ) ( x n ) + e n 2 3 x n x n 1 f ( x n ) f ( x n 1 ) [ f ( 2 ) ( x n ) ] 2 + e n 3 9 x n x n 1 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) f ( 2 ) ( x n ) + e n 4 36 x n x n 1 f ( x n ) f ( x n 1 ) f ( 4 ) ( x n ) f ( 2 ) ( x n ) + 2 e n 2 9 f ( 3 ) ( x n ) + 2 e n 3 9 x n x n 1 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) f ( 2 ) ( x n ) + 4 e n 3 81 f ( 3 ) ( x n ) + (4.20)

3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) = 3 ( f ( x n ) f ( x n 1 ) ) + 2 e n ( x n x n 1 ) f ( 2 ) ( x n ) + e n 2 ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) [ f ( 2 ) ( x n ) ] 2 + e n 3 3 ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) f ( 2 ) ( x n ) + e n 4 12 ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) f ( 4 ) ( x n ) f ( 2 ) ( x n ) + 2 3 e n 2 ( x n x n 1 ) f ( 3 ) ( x n ) + 2 3 e n 3 ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) f ( 2 ) ( x n ) + 4 27 e n 3 ( x n x n 1 ) f ( 3 ) ( x n ) + (4.21)

f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) = 4 ( f ( x n ) f ( x n 1 ) ) + 2 e n ( x n x n 1 ) f ( 2 ) ( x n ) + e n 2 ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) [ f ( 2 ) ( x n ) ] 2 + e n 3 ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) f ( 2 ) ( x n )

+ 4 27 e n 3 ( x n x n 1 ) f ( 3 ) ( x n ) + 2 3 e n 2 ( x n x n 1 ) f ( 3 ) ( x n ) + e n 4 12 ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) f ( 4 ) ( x n ) f ( 2 ) ( x n ) + (4.22)

By using (4.14) we have,

4 ( x n x n 1 ) f ( x n ) = 4 ( f ( x n ) f ( x n 1 ) ) e n 2 e n 2 ( x n x n 1 ) f ( 2 ) ( x n ) 2 3 e n 3 ( x n x n 1 ) f ( 3 ) ( x n ) 1 6 e n 4 ( x n x n 1 ) f ( 4 ) ( x n ) + (4.23)

By using (4.22) and (4.23),

[ f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) ] e n + 4 ( x n x n 1 ) f ( x n ) = e n 3 ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) [ f ( 2 ) ( x n ) ] 2 + e n 4 ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) f ( 3 ) ( x n ) f ( 2 ) ( x n ) + ( 4 27 1 6 ) e n 4 ( x n x n 1 ) f ( 4 ) ( x n ) + (4.24)

Then

[ f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) ] e n + 1 = ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) [ f ( 2 ) ( x n ) ] 2 e n 3 + O ( e n 4 ) (4.25)

Thus

e n + 1 = ( x n x n 1 ) 2 f ( x n ) f ( x n 1 ) [ f ( 2 ) ( x n ) ] 2 [ f ( x n ) f ( x n 1 ) + 3 ( x n x n 1 ) f ( x n + 2 ρ n 3 ) ] 1 e n 3 (4.26)

5. Numerical Examples and Comparison

We will compare the performance of our method with some existing methods and use in [1]. Therefore, we will give numerical results for some functions and initial values.

From the analysis made of Table 1, we can notice that the efficiency index of the proposed method is higher than that of the secant method which was already better than the Newton method and others developed in [1]. This is explained by the fact our method even though of order three of convergence requires only two evaluations of the function by iteration whereas most of the method of order three existing in the literature use three evaluations of the function and this by supposing that the evaluation of the function and its derivative have the same numerical cost. Our method defined by 4.3 is preferable.

Table 1. Efficiency index of different numerical methods.

Table 2. f ( x ) = sin 2 ( x ) x 2 + 1 et x 0 = 1 .

Table 3. f ( x ) = x 2 exp ( x ) 3 x + 2 et x 0 = 3 .

Table 4. f ( x ) = exp ( x 2 + 7 x 30 ) 1 et x 0 = 3.5 .

Table 5. f ( x ) = 11 x 11 1 et x 0 = 0.7 .

6. Conclusion

We have presented in this paper a modified Newton method of order three of convergence, more efficient than most of the methods known in the literature. Analysis of efficiency shows that this method is preferable for solving the non-linear equations. A comparative study of the number of function evaluations and the number of iterations with convergence of some methods is indicated in Tables 2-5. The result of these tables confirms the theory.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1] McDougall, T.J. and Wotherspoon, S.J. (2014) A Simple Modification of Newtons Method to Achieve Convergence of Order 1+√2. Applied Mathematics Letters, 29, 2025.
[2] Homeier, H.H.H. (2005) On Newton-Type Methods with Cubic Convergence. Journal of Computational and Applied Mathematics, 176, 425-432.
https://doi.org/10.1016/j.cam.2004.07.027
[3] Traub, J.F. (1964) Iterative Methods for the Solution of Equations. Prentice-Hall, Englewood Cliffs, New Jersey.
[4] Zavalani, G. (2014) A Modification of Newton Method with Third-Order Convergence. American Journal of Numerical Analysis, 2, 98-101.
[5] Kincaid, D. and Cheney, W. (1991) Numerical Analysis Mathematics of Scientific Computing. Wadsworth, Inc., Belmont, California.

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.