A Modification of Newton Method with Third-Order Convergence

Gentian Zavalani

  Open Access OPEN ACCESS  Peer Reviewed PEER-REVIEWED

A Modification of Newton Method with Third-Order Convergence

Gentian Zavalani

Faculty of Mathematics and Physics Engineering Polytechnic University of Tirana, Albania

Abstract

In this paper, we present a new modification of Newton method for solving non-linear equations. Analysis of convergence shows that the new method is cubically convergent. Per iteration the new method requires two evaluations of the function and one evaluation of its first derivative. Thus, the new method is preferable if the computational costs of the first derivative are equal or more than those of the function itself. Finally, we give some numerical examples to demonstrate our method is more efficient than other classical iterative methods.

Cite this article:

  • Zavalani, Gentian. "A Modification of Newton Method with Third-Order Convergence." American Journal of Numerical Analysis 2.4 (2014): 98-101.
  • Zavalani, G. (2014). A Modification of Newton Method with Third-Order Convergence. American Journal of Numerical Analysis, 2(4), 98-101.
  • Zavalani, Gentian. "A Modification of Newton Method with Third-Order Convergence." American Journal of Numerical Analysis 2, no. 4 (2014): 98-101.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

1. Introduction

Iterative methods for finding the roots of nonlinear equations , are common yet important problem in science and engineering. Analytical methods for solving such equations are difficult or almost non-existent. Solving non linear equations is an important issue in pure and applied mathematics. Researchers have developed various effective methods to find a single root of the non-linear equation , where for an open interval is a scalar function. We know that one of the fundamental algorithm for solving nonlinear equations is so-called fixed-point iteration method.

In the fixed-point iteration method for solving the nonlinear equation the equation is usually rewritten as

(1)

where

(1) there exist such that , for all ,

(2) there exist such that , for all ,

Considering the following iteration scheme:

(2)

and starting with a suitable initial approximation , we build up a sequence of approximations, say , for the solution of the nonlinear equation, say .The scheme will converge to the root , provide that the initial approximation is chosen in the interval , has a continuous derivative on , , for all , for all .

The order of convergence for the sequence of approximations derived from an iteration method is defined in the literature, as follows.

Definition 1. Let converge to . If there exist an integer constant and real positive constant such that

(3)

then is called the order and the constant of convergence.

To determine the order of convergence of the sequence , let us consider the Taylor expansion of

(4)

Using (1) and (2) in (4) we have

(5)

and we can state the following result [1]

2. Preliminaries

We firstly introduce a lemma before proposing our Newton-type iterative method for solving non-linear equations.

Lemma 1. Assume that and there is a simple root of the nonlinear equation , where is a scalar function on an open interval . If there is an iterative method with the order of convergence ( is a integer) which produces the sequence , then we have

(6)

where constant and is a neighborhood of .

Proof. Using the Taylor expansion and the definition of the convergence order of the iterative method, we know

Then, we get (6).This ends the proof.

3. Iterative Methods

Let , be times Fréchet differentiable function on an open interval and be a real zero of the non-linear equation . For any we may write the Taylor's expansion for as follows:

For , we have

(7)

Approximating the integral in (7), we have

(8)

By using (7) and (8) and , we have

This allows us to suggest the following one-step iterative method for solving the non-linear equations.

Algorithm 1. For a given , compute the approximate solution , by the iterative scheme where is the derivate at point. Algorithm 1. is known as Newton's method for the non-linear equations and has quadratic convergence.

If we approximate the integral in (7) by using the Closed-Open quadrature formula [3], then

(9)

By using (7) and (9) and , we have

Using this relation, we can suggest the following two-step iterative method for solving the nonlinear system of equation (1) as:

Algorithm 2. For a given , compute the approximate solution ,

Predictor step:

(10)

Corrector step:

(11)

Algorithm 2 is another iterative method for solving the nonlinear equation (1).

These modifications of Newton method are very important and interesting because per iteration they require one evaluation of the function and two of the first derivative , not requiring the second derivative , but they can converge cubically. Thus, the research of the third-order methods with free second derivatives becomes very active now. The efficiency of the new method is demonstrated by numerical examples.

4. Convergence Analysis

In this section, we consider the convergence criteria of the Algorithm 2 using the Taylor series technique as (4)

Theorem 1. Let , be times Fréchet differentiable function on an open interval containing the root of . The iterative method defined by Algorithm 2 has cubic convergence and satisfies the error equation

(12)

Proof. The technique is given by

Defining and from equation (11), we have

(13)

from which we have

(14)

from equation (7') with ,we have

(15)

If be the zero of the non-linear equation

(16)

Pre-multiplying equation (16) by , we have

(17)

Now, applying Taylor's expansion for at point , we have

(18)

From equation (17) and (18), we obtain

Thus

(19)

Now, from equations (14), (16) and (19)

Thus, from above equation, we have

(20)

Equation (20) shows that the Algorithm 2 has cubic convergence.

It is easy to know that per iteration the number of function evaluation of iterative method defined by (11) is three. We consider the definition of efficiency index [11] as where is the order of the method and the number of function evaluations per iteration required by the method. We have that similar to the results obtained in [4] the method defined by (11) has the efficiency index equal to which is better than the one of Newton method .Thus, the method defined by (11) is preferable if the computational costs of the first derivative are equal or more than those of the function itself.

5. Numerical Results

Now we employ the new method (10-11) obtained in this paper to solve some non-linear equations Also compared are the Newton method (NM), the method of Soheili (SM), and the method, introduced in this present paper (Algorithm 2). Table 1 presents iteration number comparison of Algorithm 2 with (NM) and (SM), in given precision. The computational results show that the cubically convergent methods, especially the new method (10-11), can compete with Newton method. Also the new method (10-11) seems to be superior in some cases where Newton method fails in convergence, as f5: We used The following stopping criteria is used for computer programs

The numerical computations listed in Table 1 are performed using Matlab© programs.

Table 1. Examples and comparison between other methods

6. Conclusions

We have obtained a new modification of Newton method for solving non-linear equations. From Theorem 1, we prove that the order of convergence of the new method is three. The numerical results in the Table 1 show that the new method is very effective and provide highly accurate results in a less number of iterations as compared with Newton method (NM) and the method of Soheili (SM) (Soheili et al., 2008). Analysis of efficiency shows that the new method is preferable to the well-known Newton method, especially in the case where the computational costs of the first derivative are equal or more than those of the function itself.

References

[1]  Burden, R. L., & Douglas Faires, J. (2001).Numerical analysis. Boston: PWS publishing company.
In article      
 
[2]  Noor, M. A. (2006 b). New iterative methods for nonlinear equations. Journal of applied mathematical and computation.
In article      
 
[3]  H.H.H. Homeier, On Newton-type methods with cubic convergence, J. Comput. Appl. Math. 176 (2005) 425-432.
In article      CrossRef
 
[4]  M. Frontini, E. Sormani, Third-order methods from quadrature formulae for solving systems of nonlinear equations, Appl. Math. Comput. 149 (2004) 771-782.
In article      CrossRef
 
[5]  Chun, C., 2005. Iterative methods improving Newton’s method by the decomposition method, Computers Math. Appl., 50: 1559-1568
In article      CrossRef
 
[6]  S. Weerakoon, T.G.I. Fernando, A variant of Newton’s method with accelerated third- order convergence, Appl. Math. Lett. 13 (2000) 87-93.
In article      CrossRef
 
[7]  F. A. Potra, V. Pta ´k, Nondiscrete induction and iterative processes, Research Notes in Mathematics, vol. 103, Pitman, Boston, 1984.
In article      
 
[8]  L. F. Shampine, R. C. Allen, S. Pruess, Fundamentals of Numerical Computing, John Wiley and Sons, New York, 1997.
In article      
 
[9]  F. Freudensten, B. Roth, Numerical solution of systems of nonlinear equations, J. ACM 10 (1963) 550-556.
In article      CrossRef
 
[10]  Soheili, A. R., Ahmadian, S. A., & Naghipoor, J. (2008). A Family of Predictor-Corrector Methods Based on Weight Combination of Quadratures for Solving Nonlinear equations. International journal of nonlinear science, 6, 29-33.
In article      
 
[11]  W. Gautschi, Numerical Analysis: An Introduction, Birkha ¨user, 1997
In article      
 
[12]  Rostam K. Saeed and Fuad W. Khthr, New third order iterative method for solving nonlinear equations, Journal of Applied Sciences Research, Vol. 7, No. 6, p. 916-921, 2011.
In article      
 
[13]  Rostam K. Saeed and Shno O. Ahmed, Modified Iterative methodfor Solving Nonlinear, equation Journal of Kirkuk University-Scientific Studies, Vol. 7, No. 1, p. 146-152, 2012.
In article      
 
comments powered by Disqus
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn