A Modification of Newton Method with Third-Order Convergence
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.
At a glance: Figures
Keywords: Newton method, third-order convergence, non-linear equations, iterative method, quadrature formulas
American Journal of Numerical Analysis, 2014 2 (4),
Received April 18, 2014; Revised May 04, 2014; Accepted May 09, 2014Copyright © 2014 Science and Education Publishing. All Rights Reserved.
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|
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) there exist such that , for all ,
(2) there exist such that , for all ,
Considering the following iteration scheme:
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
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
Using (1) and (2) in (4) we have
and we can state the following result 
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
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
Approximating the integral in (7), we have
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 , then
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 ,
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
Proof. The technique is given by
Defining and from equation (11), we have
from which we have
from equation (7') with ,we have
If be the zero of the non-linear equation
Pre-multiplying equation (16) by , we have
Now, applying Taylor's expansion for at point , we have
From equation (17) and (18), we obtain
Now, from equations (14), (16) and (19)
Thus, from above equation, we have
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  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  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.
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.
|||Burden, R. L., & Douglas Faires, J. (2001).Numerical analysis. Boston: PWS publishing company.|
|||Noor, M. A. (2006 b). New iterative methods for nonlinear equations. Journal of applied mathematical and computation.|
|||H.H.H. Homeier, On Newton-type methods with cubic convergence, J. Comput. Appl. Math. 176 (2005) 425-432.|
|||M. Frontini, E. Sormani, Third-order methods from quadrature formulae for solving systems of nonlinear equations, Appl. Math. Comput. 149 (2004) 771-782.|
|||Chun, C., 2005. Iterative methods improving Newton’s method by the decomposition method, Computers Math. Appl., 50: 1559-1568|
|||S. Weerakoon, T.G.I. Fernando, A variant of Newton’s method with accelerated third- order convergence, Appl. Math. Lett. 13 (2000) 87-93.|
|||F. A. Potra, V. Pta ´k, Nondiscrete induction and iterative processes, Research Notes in Mathematics, vol. 103, Pitman, Boston, 1984.|
|||L. F. Shampine, R. C. Allen, S. Pruess, Fundamentals of Numerical Computing, John Wiley and Sons, New York, 1997.|
|||F. Freudensten, B. Roth, Numerical solution of systems of nonlinear equations, J. ACM 10 (1963) 550-556.|
|||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.|
|||W. Gautschi, Numerical Analysis: An Introduction, Birkha ¨user, 1997|
|||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.|
|||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.|