On a Family of High-Order Iterative Methods under Kantorovich Conditions and Some Applications

Abstract

This paper is devoted to the study of a class of high-order iterative methods for nonlinear equations on Banach spaces. An analysis of the convergence under Kantorovich-type conditions is proposed. Some numerical experiments, where the analyzed methods present better behavior than some classical schemes, are presented. These applications include the approximation of some quadratic and integral equations.

(ProQuest: ... denotes non-US-ASCII text omitted.)

S. Amat 1 and C. Bermúdez 1 and S. Busquier 1 and M. J. Legaz 1 and S. Plaza 2

Recommended by John Rassias

1, Departamento de Matemática Aplicada y Estadística, Universidad Politécnica de Cartagena, 30203 Cartagena, Spain
2, Departamento de Matemáticas, Facultad de Ciencias, Universidad de Santiago de Chile, Casilla 307, Correo 2, Santiago, Chile

Received 23 February 2012; Revised 4 June 2012; Accepted 4 June 2012

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

This paper deals with the approximation of nonlinear equations as follows [figure omitted; refer to PDF] where F:Ω⊆X[arrow right]Y is a nonlinear operator between Banach spaces, using the following family of high-order iterative methods: [figure omitted; refer to PDF] where I is the identity operator on X and for each x∈X , _LF (x) is the linear operator on Ω⊆X defined by the following [figure omitted; refer to PDF] assuming that F[variant prime]^(x)-1 exists and _GF :Ω⊆X[arrow right][Lagrangian (script capital L)](X,X) is a given nonlinear operator (usually depending on the operator F and its derivatives), here [Lagrangian (script capital L)](X,X) denotes the space of bounded linear operators from X to X .

The second step can be interpreted as an acceleration of the initial one (in our case Newton's method). Indeed, this family was introduced for scalar equations f(t)=0 in [1], for any initial scheme, Traub's theorem reads:

Theorem 1.1.

For all sufficiently smooth function _gf (x) , the following iterative method [figure omitted; refer to PDF] has order of convergence min {p+2,2p} , where p is the order of Φ(x) .

In this paper, we consider as the function Φ(x) the classical Newton method. We have mainly three reasons. First, because we can recover many well-known high-order iterative methods. Second, because the domain of convergence of Newton's method is bigger than high order schemes [2]. Finally, since in practice it is a good strategy to start with a simple method when we are not sufficiently close to the solution [3].

On the other hand, conditions are imposed on _x0 and on F in order to assure the convergence of _{{xn }n} to a solution ^x* of F(x)=0 . This analysis, usually known as Kantorovich type , are based on a relationship between the problem in a Banach space and a single nonlinear scalar equation which leads the behavior of the problem. A priori error estimates, depending only on the initial conditions, and, hence, the order of convergence can be obtained by using Kantorovich type theorems.

A review to the amount of literature on high-order iterative methods in the two last decades (see for instance [4] and its references, or this incomplete list of recent papers [5-16]) may reveal the importance of high-order schemes. The main practical difficulty related to the classical third-order iterative methods is the evaluation of the second-order derivative. For a nonlinear system of m equations and m unknowns, the first Fréchet derivative is a matrix with ^m2 entries, while the second Fréchet derivative has ^m3 entries. This implies a huge amount of operations in order to evaluate every iteration. However, in some cases, the second derivative is easy to evaluate. Some clear examples of this case are the approximation of Hammerstein equations where the second Fréchet derivative is diagonal by blocks or quadratic equations where it is constant.

The structure of this paper is as follows: in Section 2 we present some particular examples of methods included in the family and in Section 3, we assert convergence and uniqueness theorems (Kantorovich type). Finally, some numerical experiments are presented in Section 4. These applications include quadratic (Riccati) equations and integral (Hammerstein) equations. In all these problems the proposed methods seem more efficient than second-order methods.

2. A Family of High-Order Iterative Methods

As was indicated in the introduction, we are interested in the study of the family of iterative methods as follows [figure omitted; refer to PDF]

Note that the method (2.1) is equivalent to iterate the function _Mf given by the following [figure omitted; refer to PDF] that is, [figure omitted; refer to PDF]

Particular examples of schemes included in the family with nonsmooth functions _gf (x) are

(1) Halley [figure omitted; refer to PDF]

(2) Super-Halley [figure omitted; refer to PDF]

(3) Chebyshev [figure omitted; refer to PDF]

(4) Chebyshev like methods . For 0...4;α...4;2 , we consider the following α -methods [figure omitted; refer to PDF]

(5) Two-step [figure omitted; refer to PDF]

These methods have order of convergence three that is small than the estimate 4=min {2+2,2·2} in Traub's theorem (since _gf (x) is nonsmooth). For instance the above two-step method admits _gf (x)=-1/_Lf (x) . Indeed, all these methods have the function f in the denominator.

On the other hand, considering different smooth functions _gf (x) , the following schemes are also particular examples in the family.

(1) The two-step method ( _gf (x)=0 ) [figure omitted; refer to PDF]

: has order four.

(2) The two-step method ( _gf (x)=(1/2)((5/2)-_{L^{f[variant prime]}} (x)) ) [figure omitted; refer to PDF]

: has order five.

(3) We should start with other iterative functions Φ(x) and develop a similar analysis. For instance, starting with Chebyshev's method we can consider the method ( _gf (x)=(1/2)(3-_{Lf[variant prime]} (_xn )) ) [figure omitted; refer to PDF]

: that has order six [3]. We use this scheme only in the numerical section.

3. Semilocal Convergence

Several techniques are usually considered to study the convergence of iterative methods, as we can see in the following papers [4, 17-20]. Among these, the two most common are the based on the majorant principle and on recurrence relations.

In this section, we analyze the semilocal convergence of the introduced family (1.2) under a generalization of Kantorovich conditions.

Namely, we assume that:

(C1) Let _x0 ∈Ω such that _Γ0 =^{F[variant prime](_x0 )-1} exists and ||_Γ0 ||...4;β .

(C2) ||_Γ0 F(_x0 )||...4;η .

(C3) ||^{F[variant prime][variant prime]} (x)||...4;M for all x∈Ω .

(C4) ||^{F[variant prime][variant prime]} (x)-^{F[variant prime][variant prime]} (y)||...4;K||x-y|| , K>0 , x,y∈Ω .

Under these hypotheses it is possible to find a cubic polynomial in an interval [a,b] such that p(a)>0>p(b) , ^{p[variant prime]} (t)<0 , ^{p[variant prime][variant prime]} (t)>0 and ^{p[variant prime][variant prime][variant prime]} (t)>0 in [a,^t* ] , with ^t* the unique simple solution of p(t)=0 , and verifying the following hypotheses:

For _t0 ∈[a,b] and p(_t0 )>0 .

(H1) ||_Γ0 ||...4;-1/^{p[variant prime]} (_t0 ) ,

(H2) ||_Γ0 F(_x0 )||...4;-p(_t0 )/^{p[variant prime]} (_t0 ) ,

(H3) ||^{F[variant prime][variant prime]} (x)||...4;^{p[variant prime][variant prime]} (t) for all x∈Ω , ||x-_x0 ||...4;t-_t0 ...4;^t* -_t0 ,

(H4) ||^{F[variant prime][variant prime]} (x)-^{F[variant prime][variant prime]} (y)||...4;|^{p[variant prime][variant prime]} (u)-^{p[variant prime][variant prime]} (v)| , with ||x-y||...4;|u-v| , x,y∈Ω and u,v∈[a,^t* ] .

Some immediate properties of the polynomial may be obtained from the conditions above imposed:

(1) p(t) is decreasing in the interval [a,^t* ] , since p[variant prime](t)<0 in that interval.

(2) p(t)>0 in [a,^t* [ .

(3) p[variant prime](t) is increasing and p(t) is convex in [a,^t* ] , since we have p[variant prime][variant prime](t)>0 in [a,^t* ] .

(4) ^{p[variant prime][variant prime]} (t) is increasing in [a,^t* ] , since ^{p[variant prime][variant prime][variant prime]} (t)>0 in that interval.

From these properties it follows the next:

(a) The Newton map associate to p(t) , _Np (t)=t-(p(t)/p[variant prime](t)) , is increasing in [a,^t* [ , _Np (^t* )=^t* and ^{Np[variant prime]} (^t* )=0 .

(b) The function _Lp (t)=p(t)^{p[variant prime][variant prime]} (t)/^{p[variant prime](t)2} >0 in [a,^t* [ , since p(t) and ^{p[variant prime][variant prime]} (t) are strictly positive in that interval. Furthermore, _Lp (^t* )=0 , since p(^t* )=0 and p[variant prime](^t* )...0;0 .

In this paper, as in [21, page 43], we consider as the function p(t) the following polynomial: [figure omitted; refer to PDF] assuming [figure omitted; refer to PDF]

If this last condition holds, then the cubic polynomial p(t) has two roots ^t* and ^t** ( ^t* ...4;^t** ). We can choose a and b such that 0<a<^t* and b>2/(Mβ+(^M2β2 +2Kβ)) .

Moreover, we need some extra conditions associated to the operator _GF and the function _gp . We assume:

(Hg1): ||_LF (x⁾²_GF (x)||...4;_Lp^(t)2_Gp (t) , for ||x-_x0 ||...4;t-_t0 ...4;^t* -_t0 ,

(Hg2): 1+_Lp (t)+_Lp (t⁾²_gp (t)...5;0 ,

(Hg3): ^{m[variant prime]} (t)>0 in [a,^t* [ , where [figure omitted; refer to PDF]

All the methods considered in the above section have associated functions _gp that verify the three last conditions. With the two last hypotheses on _gp and the definition of p , following [21, Corollary 2.2.2 in page 31], the next result holds.

Proposition 3.1.

The sequence [figure omitted; refer to PDF] starting from the above _t0 converges monotonically to ^t* the real simple solution of p(t)=0 in [a,b] .

We are now ready to prove the desired semilocal convergence.

Theorem 3.2.

Let us assume _x0 ∈Ω and _t0 ∈[a,^t* ] verifying the hypotheses (H1)-(H4) and (Hg1)-(Hg3) with [figure omitted; refer to PDF]

If B(_x0 ,^t* -_t0 )⊂Ω then the sequence (1.2) is well defined and converges to ^x* the unique solution of F(x)=0 in B(_x0 ,^t* -_t0 )¯ .

Moreover, [figure omitted; refer to PDF] where [figure omitted; refer to PDF]

Proof.

By an induction process, it is possible to verify that

(i) ||^{F[variant prime](_xn )-1} ||...4;-1/^{p[variant prime]} (_tn ) ,

(ii) ||F(_xn )||...4;p(_tn ) ,

: and then,

(iii): ||_LF (_xn )||...4;_Lp (_tn ) ,

: and

(iv) ||_xn+1 -_xn ||...4;_tn+1 -_tn .

The case n=0 follows from the initial conditions on _x0 and _t0 .

We now assume that the conditions are valid for n and we check them for n+1 .

(i) [figure omitted; refer to PDF]

: Applying Taylor's theorem: [figure omitted; refer to PDF]

because ^{p[variant prime]} (t) is increasing.

: By applying the general invertibility criterion, ^{F[variant prime]} (_xn+1 ) is invertible, and [figure omitted; refer to PDF]

(ii) Using the following Taylor expansion [figure omitted; refer to PDF]

and by the definition of the method [figure omitted; refer to PDF] we obtain that [figure omitted; refer to PDF] and since [figure omitted; refer to PDF] we conclude that [figure omitted; refer to PDF] Similarly from the following expansion [figure omitted; refer to PDF] the definition of the method, the main hypotheses on _GF and the induction process, we obtain, using that ||F(_yn )||...4;p(_sn ) and that [figure omitted; refer to PDF] the desired inequality: [figure omitted; refer to PDF]

In this situation, the theorem holds by applying the previous estimates directly to the formulas that describe the methods, we refer [21, page 41-42] for more details.

The estimates given in the present paper are optimal in the sense that the sequence associated to p verifies the inequalities with equalities.

4. Numerical Experiments

We consider several problems where the presented high-order methods can be considered as a good alternative to second-order methods.

4.1. Approximation of Riccati's Equations

In this first example, we consider quadratic equations, therefore the second Fréchet derivative is constant. Particular cases of this type of equations, that appear in many applications, are Riccati's equations [22-24]. For instance, if we consider the problem of calculating feedback controls for systems modeled by partial differential or delay differential equations, a classical controller design objective will be to find a control u(t) for the state x(t) such that the following objective function [figure omitted; refer to PDF] is minimized, where R is a positive defined matrix and the observation C∈[Lagrangian (script capital L)](X,^...d ) . In practice, the control is calculated through approximation. This leads to solving an algebraic Riccati equation [figure omitted; refer to PDF] for a feedback operator [figure omitted; refer to PDF] see [25, 26] for more details.

In the general case, an algebraic Riccati's equation is given by [27] [figure omitted; refer to PDF] where D,A,C∈^...n×n are given matrix, D symmetric and X∈^...n×n is the unknown.

In this case, [figure omitted; refer to PDF]

In particular, the second derivative is constant. In this case, the Kantorovich conditions for Newton's methods have the compact form [figure omitted; refer to PDF] Moreover, this hypothesis also gives the convergence for the high-order methods [22].

Then, using a matricial norm [figure omitted; refer to PDF]

Given a symmetric initial guess _X0 ∈^...n×n , to obtain ^{R[variant prime](_X0 )-1} we solve the equation [figure omitted; refer to PDF] This equation has solution if D_X0 -A is stable [27], that is, all its eigenvalues have negative real part. In this following case [figure omitted; refer to PDF]

Next, to illustrate the previous results, we consider the following algebraic Riccati equation (4.4) with matrix [figure omitted; refer to PDF] and the starting point [figure omitted; refer to PDF] In this case, the algebraic Riccati equation has exact solution [figure omitted; refer to PDF] Besides, from the aforesaid starting point it follows that D_X0 -A is a stable matrix.

Now, considering the stopping criterion ||_Xn -^X* ||<1^0-50 in Table 1, we obtain the errors ||_Xn -^X* || . If we now analyze the following computational order of convergence [28]: [figure omitted; refer to PDF] we observe that method M6 has computationally the order of convergence at least six. See Table 2, where _ρN , _ρCH and _ρM6 denote, respectively, the computational order of convergence of the three last methods.

Table 1: Errors for the Newton, Chebyshev and M6 methods.

n	Newton	Chebyshev	M6
1	8.57864...·10-2	3.92135...·10-2	8.63800...·10-3
2	2.45310...·10-3	1.60604...·10-5	7.95704...·10-14
3	2.12390...·10-6	1.03568...·10-15
4	1.59486...·10-12	2.77730...·10-46
5	8.99292...·10-25
6	2.85928...·10-49

Table 2: The computational order of convergence for the Newton, Chebyshev and M6 methods.

n	ρN	ρCH	ρM6
1	2.25751...	3.30896...	6.56567...
2	1.98391...	3.00811...
3	1.99975...	3.00000...
4	1.99999...
5	1.99999...

In comparison with the classical Newton's method, the extra computational cost per iteration of method M6, is only two new evaluations of the operator F , and two extra matrix-vector multiplications. Moreover, the same as Newton's method only a LU decomposition is necessary. Thus, M6 is more efficient.

See [29] for more details.

4.2. Approximation of Hammerstein Equations

We consider an important special case of integral equation, the following Hammerstein equation [figure omitted; refer to PDF] These equations are related with boundary value problems for differential equations. For some of them, high-order methods using second derivatives are useful for their effective (discretized) solution.

The discrete version of (4.14) is [figure omitted; refer to PDF] where 0...4;_t0 <_t1 <...<_tm ...4;1 are the grid points of some quadrature formula ^∫01 ...f(t)dt[approximate]^∑j=0m ..._γj f(_tj ) , and ^xi =x(_ti ) .

The second Fréchet derivative of the associated discrete system is diagonal by blocks.

Let the following Hammerstein equation [figure omitted; refer to PDF]

The discretization of this equation verifies the Lipschitz condition of our Kantorovich theorem [4].

We consider m=20 in the quadrature trapezoidal formula and as exact solution the obtained numerically by Newton method. In Table 3, we summarize the numerical results for different methods in the family: Newton, Halley, and M4. We consider as initial guess _x0 (s)=1.5 .

Table 3: Errors for the Newton, Halley, and M4 methods.

n	Newton	Halley	M4
1	2.35786...·10-2	4.23125...·10-3	5.00638...·10-4
2	1.60604...·10-4	1.06034...·10-6	6.55602...·10-15
3	3.30548...·10-8	1.00158...·10-17	8.23560...·10-60
4	3.11276...·10-16	2.13492...·10-49
5	1.12645...·10-32
6	2.89613...·10-65

Since the second derivative is diagonal by blocks, its application has a computational cost of order O(^m2 ) . Thus, the computational cost in each iteration of the three schemes is, for m sufficiently big, of the same order ( O(^m3 ) due to the LU decomposition). Note that we only have to do a factorization in each iteration of the three schemes. As conclusion, the scheme M4 (order four) is the most efficient for m sufficiently big.

See [30] for other-related problems.

5. Conclusions

Summing up, in this paper we have studied a family of high-order iterative methods. Mainly, the theoretical analysis we did allows to ensure convergence conditions for all these schemes. We established priori error bounds for them and consequently their order. We have presented different applications where we may add that in these cases the analyzed high-order methods are more efficient than simpler second-order methods.

Acknowledgment

S. Amat, C. Bermúdez, and S. Busquier were supported in part by MINECO-FEDER MTM2010-17508 and 08662/PI/08. S. Plaza was supported in part by Fondecyt (Grant no. 1095025).

References

[1] J. F. Traub Iterative Methods for the Solution of Equations , of Prentice-Hall Series in Automatic Computation, pp. xviii+310, Prentice-Hall, Englewood Cliffs, NJ, USA, 1964.

[2] J. A. Ezquerro, M. A. Hernández, "An improvement of the region of accessibility of Chebyshev's method from Newton's method," Mathematics of Computation , vol. 78, no. 267, pp. 1613-1627, 2009.

[3] S. Amat, M. A. Hernández, N. Romero, "A modified Chebyshev's iterative method with at least sixth order of convergence," Applied Mathematics and Computation , vol. 206, no. 1, pp. 164-174, 2008.

[4] S. Amat, S. Busquier, "Third-order iterative methods under Kantorovich conditions," Journal of Mathematical Analysis and Applications , vol. 336, no. 1, pp. 243-261, 2007.

[5] M. Dehghan, M. Hajarian, "On derivative free cubic convergence iterative methods for solving nonlinear equations," Journal of Computational Mathematics and Mathematical Physics , vol. 51, no. 4, pp. 555-561, 2011.

[6] J. Dzunic, M. S. Petkovic, L. D. Petkovic, "Three-point methods with and without memory for solving nonlinear equations," Applied Mathematics and Computation , vol. 218, no. 9, pp. 4917-4927, 2012.

[7] J. A. Ezquerro, M. Grau-Sánchez, A. Grau, M. A. Hernández, M. Noguera, N. Romero, "On iterative methods with accelerated convergence for solving systems of nonlinear equations," Journal of Optimization Theory and Applications , vol. 151, no. 1, pp. 163-174, 2011.

[8] L. Fang, "A cubically convergent iterative method for solving nonlinear equations," Advances and Applications in Mathematical Sciences , vol. 10, no. 2, pp. 117-119, 2011.

[9] M. Grau-Sánchez, À. Grau, M. Noguera, "Frozen divided difference scheme for solving systems of nonlinear equations," Journal of Computational and Applied Mathematics , vol. 235, no. 6, pp. 1739-1743, 2011.

[10] M. Grau-Sánchez, À. Grau, M. Noguera, "On the computational efficiency index and some iterative methods for solving systems of nonlinear equations," Journal of Computational and Applied Mathematics , vol. 236, no. 6, pp. 1259-1266, 2011.

[11] Y. I. Kim, Y. H. Geum, "A cubic-order variant of Newton's method for finding multiple roots of nonlinear equations," Computers & Mathematics with Applications , vol. 62, no. 4, pp. 1634-1640, 2011.

[12] W. Li, H. Chen, "A unified framework for the construction of higher-order methods for nonlinear equations," Open Numerical Methods Journal , vol. 2, pp. 6-11, 2010.

[13] M. S. Petkovic, J. Dzunic, B. Neta, "Interpolatory multipoint methods with memory for solving nonlinear equations," Applied Mathematics and Computation , vol. 218, no. 6, pp. 2533-2541, 2011.

[14] F. Sha, X. Tan, "A class of iterative methods of third order for solving nonlinear equations," International Journal of Nonlinear Science , vol. 11, no. 2, pp. 165-167, 2011.

[15] P. Wang, "A third-order family of Newton-like iteration methods for solving nonlinear equations," Journal of Numerical Mathematics and Stochastics , vol. 3, no. 1, pp. 13-19, 2011.

[16] X. Zhou, X. Chen, Y. Song, "Constructing higher-order methods for obtaining the multiple roots of nonlinear equations," Journal of Computational and Applied Mathematics , vol. 235, no. 14, pp. 4199-4206, 2011.

[17] I. K. Argyros, "Improving the order and rates of convergence for the super-Halley method in Banach spaces," The Korean Journal of Computational & Applied Mathematics , vol. 5, no. 2, pp. 465-474, 1998.

[18] I. K. Argyros, "The convergence of a Halley-Chebysheff-type method under Newton-Kantorovich hypotheses," Applied Mathematics Letters , vol. 6, no. 5, pp. 71-74, 1993.

[19] J. A. Ezquerro, M. A. Hernández, "New Kantorovich-type conditions for Halley's method," Applied Numerical Analysis and Computational Mathematics , vol. 2, no. 1, pp. 70-77, 2005.

[20] M. A. Hernández, M. A. Salanova, "Modification of the Kantorovich assumptions for semilocal convergence of the Chebyshev method," Journal of Computational and Applied Mathematics , vol. 126, no. 1-2, pp. 131-143, 2000.

[21] N. Romero http://dialnet.unirioja.es/ Familias paramétricas de procesos iterativos de alto orden de convergencia [Ph.D. thesis] , 2006.

[22] S. Amat, S. Busquier, J. M. Gutiérrez, "An adaptive version of a fourth-order iterative method for quadratic equations," Journal of Computational and Applied Mathematics , vol. 191, no. 2, pp. 259-268, 2006.

[23] C.-H. Guo, N. J. Higham, "Iterative solution of a nonsymmetric algebraic Riccati equation," SIAM Journal on Matrix Analysis and Applications , vol. 29, no. 2, pp. 396-412, 2007.

[24] C.-H. Guo, A. J. Laub, "On the iterative solution of a class of nonsymmetric algebraic Riccati equations," SIAM Journal on Matrix Analysis and Applications , vol. 22, no. 2, pp. 376-391, 2000.

[25] I. Lasiecka, R. Triggiani Control Theory for Partial Differential Equations: Continuous and Approximation Theories, Part 1 , Cambridge University Press, 2000.

[26] I. Lasiecka, R. Triggiani Control Theory for Partial Differential Equations: Continuous and Approximation Theories, Part 2 , Cambridge University Press, 2000.

[27] P. Lancaster, L. Rodman Algebraic Riccati Equations , pp. xviii+480, The Clarendon Press, New York, NY, USA, 1995.

[28] M. Grau, M. Noguera, "A variant of Cauchy's method with accelerated fifth-order convergence," Applied Mathematics Letters , vol. 17, no. 5, pp. 509-517, 2004.

[29] S. Amat, M. A. Hernández, N. Romero, "Semilocal convergence of a sixth order iterative method for Riccati's equations," to appear in Applied Numerical Mathematics

[30] S. Amat, S. Busquier, J. M. Gutiérrez, "Geometric constructions of iterative functions to solve nonlinear equations," Journal of Computational and Applied Mathematics , vol. 157, no. 1, pp. 197-205, 2003.