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

Authors: S. Amat; C. Bermúdez; S. Busquier; M. J. Legaz; S. Plaza
Journal: Abstract and Applied Analysis
 (2012)

---

## 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.


---

## Body

## 1. Introduction

This paper deals with the approximation of nonlinear equations as follows(1.1)F(x)=0,
where F:Ω⊆X→Y is a nonlinear operator between Banach spaces, using the following family of high-order iterative methods:
(1.2)&yn=xn-F′(xn)-1F(xn),&xn+1=yn-(I+LF(xn)+LF(xn)2GF(xn))F′(xn)-1F(yn),
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
(1.3)LF(x)=F′(x)-1F′′(x)F′(x)-1F(x),
assuming that F′(x)-1 exists and GF:Ω⊆X→ℒ(X,X) is a given nonlinear operator (usually depending on the operator F and its derivatives), here ℒ(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 equationsf(t)=0 in [1], for any initial scheme, Traub’s theorem reads:Theorem 1.1.
For all sufficiently smooth functiongf(x), the following iterative method
(1.4)yn=Φ(xn),xn+1=yn-(1+Lf(xn)+Lf(xn)2gf(xn))f(yn)f′(xn),
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 onx0 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 Section2 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(2.1)yn=xn-f(xn)f′(xn),xn+1=yn-(1+Lf(xn)+Lf(xn)2gf(xn))f(yn)f′(xn).Note that the method (2.1) is equivalent to iterate the function Mf given by the following
(2.2)Mf(x)=x-f(x)f′(x)-(1+Lf(x)+Lf(x)2gf(x))f(x-f(x)/f′(x))f′(x),
that is,
(2.3)xn+1=Mf(xn).Particular examples of schemes included in the family withnonsmooth functions gf(x) are(1)
Halley(2.4)xn+1=xn-(11+(1/2)Lf(xn))f(xn)f′(xn),(2)
Super-Halley(2.5)xn+1=xn-(1+Lf(xn)2(1-Lf(xn)))f(xn)f′(xn),(3)
Chebyshev(2.6)xn+1=xn-(1+12Lf(xn))f(xn)f′(xn),(4)
Chebyshev like methods. For 0≤α≤2, we consider the following α-methods
(2.7)xn+1=xn-(1+12Lf(xn)+αLf(xn)2)f(xn)f′(xn),(5)
Two-step(2.8)yn=xn-f(xn)f′(xn),xn+1=yn-f(yn)f′(xn).These methods have order of convergence three that is small than the estimate4=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 differentsmooth functions gf(x), the following schemes are also particular examples in the family.(1)
The two-step method (gf(x)=0)
(2.9)M4:{yn=xn-f(xn)f′(xn),xn+1=yn-(1+Lf(xn))f(yn)f′(xn),has order four.(2)
The two-step method (gf(x)=(1/2)((5/2)-Lf′(x)))
(2.10)M5:{yn=xn-f(xn)f′(xn),xn+1=yn-(1+Lf(xn)+12(52-Lf′(xn))Lf(xn)2)f(yn)f′(xn).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′(xn)))
(2.11)M6:{yn=xn-(1+12Lf(xn))f(xn)f′(xn),xn+1=yn-(1+Lf(xn)+12(3-Lf′(xn))Lf(xn)2)f(yn)f′(xn)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)
Letx0∈Ω such that Γ0=F′(x0)-1 exists and ∥Γ0∥≤β.(C2)
∥Γ0F(x0)∥≤η.(C3)
∥F′′(x)∥≤M for all x∈Ω.(C4)
∥F′′(x)-F′′(y)∥≤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′(t)<0, p′′(t)>0 and p′′′(t)>0 in [a,t*], with t* the unique simple solution of p(t)=0, and verifying the following hypotheses:Fort0∈[a,b] and p(t0)>0.(H1)
∥Γ0∥≤-1/p′(t0),(H2)
∥Γ0F(x0)∥≤-p(t0)/p′(t0),(H3)
∥F′′(x)∥≤p′′(t) for all x∈Ω, ∥x-x0∥≤t-t0≤t*-t0,(H4)
∥F′′(x)-F′′(y)∥≤|p′′(u)-p′′(v)|, with ∥x-y∥≤|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′(t)<0 in that interval.(2)
p(t)>0 in [a,t*[.(3)
p′(t) is increasing and p(t) is convex in [a,t*], since we have p′′(t)>0 in [a,t*].(4)
p′′(t) is increasing in [a,t*], since p′′′(t)>0 in that interval.From these properties it follows the next:(a)
The Newton map associate top(t), Np(t)=t-(p(t)/p′(t)), is increasing in [a,t*[,  Np(t*)=t* and Np′(t*)=0.(b)
The functionLp(t)=p(t)p′′(t)/p′(t)2>0 in [a,t*[, since p(t) and p′′(t) are strictly positive in that interval. Furthermore, Lp(t*)=0, since p(t*)=0 and p′(t*)≠0.In this paper, as in [21, page 43], we consider as the function p(t) the following polynomial:
(3.1)p(t):=K6t3+M2t2-1βt+ηβ,
assuming
(3.2)η≤4K+M2β-MβM2+2Kβ3βK(M+M2+2Kβ).If this last condition holds, then the cubic polynomialp(t) has two roots t* and t** (t*≤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 operatorGF and the function gp. We assume:(Hg1)
∥LF(x)2GF(x)∥≤Lp(t)2Gp(t), for ∥x-x0∥≤t-t0≤t*-t0,(Hg2)
1+Lp(t)+Lp(t)2gp(t)≥0,(Hg3)
m′(t)>0 in [a,t*[, where
(3.3)m(t)=t-p(t)p′(t)-(1+Lp(t)+Lp(t)2gp(t))p(t-(p(t)/p′(t)))p′(t).All the methods considered in the above section have associated functionsgp 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(3.4)sn=tn-p(tn)p′(tn),tn+1=sn-(1+Lp(tn)+Lp(tn)2gp(tn))p(sn)p′(tn),
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 assumex0∈Ω and t0∈[a,t*] verifying the hypotheses (H1)–(H4) and (Hg1)–(Hg3) with
(3.5)η≤4K+M2β-MβM2+2Kβ3βK(M+M2+2Kβ).
IfB(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,(3.6)‖x*-xn‖≤t*-tn,n≥0,
where
(3.7)sn=tn-p(tn)p′(tn),tn+1=sn-(1+Lp(tn)+Lp(tn)2gp(tn))p(sn)p′(tn).Proof.
By an induction process, it is possible to verify that(i)
∥F′(xn)-1∥≤-1/p′(tn),(ii)
∥F(xn)∥≤p(tn),and then,(iii)
∥LF(xn)∥≤Lp(tn),and(iv)
∥xn+1-xn∥≤tn+1-tn.
The casen=0 follows from the initial conditions on x0 and t0.
We now assume that the conditions are valid forn and we check them for n+1.(i)
(3.8)F′(xn+1)=F′(xn){I-F′(xn)-1(F′(xn)-F′(xn+1))}.Applying Taylor’s theorem:(3.9)‖F′(xn)-1(F′(xn)-F′(xn+1))‖≤‖F′(xn)-1‖(‖F′′(xn)‖+12K‖xn-xn+1‖)⋅‖xn-xn+1‖≤-1p′(tn)(p′′(tn)+12K(tn+1-tn))⋅(tn+1-tn)=-1p′(tn)(p′(tn+1)-p′(tn))=1-p′(tn+1)p′(tn)<1,because p′(t) is increasing.By applying the general invertibility criterion,F′(xn+1) is invertible, and
(3.10)‖F′(xn+1)-1‖≤‖(I-F′(xn)-1(F′(xn)-F′(xn+1)))-1‖‖F′(xn)-1‖≤‖F′(xn)-1‖1-‖F′(xn)-1(F′(xn)-F′(xn+1))‖≤-1p′(tn)[1-[1-p′(tn+1)/p′(tn)]]=-1p′(tn+1).(ii)
Using the following Taylor expansion(3.11)F(yn)=F(xn)+F′(xn)(yn-xn)+12!F′′(xn)(yn-xn)2+∫xnyn‍(F′′(x)-F′′(xn))(yn-x)dx,and by the definition of the method
(3.12)F′(xn)(yn-xn)=-F′(xn)(F′(xn)-1F(xn)),
we obtain that
(3.13)F(yn)=12!F′′(xn)(F′(xn)-1F(xn))2+∫xnyn‍(F′′(x)-F′′(xn))(yn-x)dx,
and since
(3.14)p(sn)=12!p′′(tn)(p′(tn)-1p(tn))2+∫tnsn‍(p′′(x)-p′′(tn))(sn-t)dt,
we conclude that
(3.15)‖F(yn)‖≤p(sn).
Similarly from the following expansion
(3.16)F(xn+1)=F(xn)+F′(xn)(xn+1-xn)+12!F′′(xn)(xn+1-xn)2+∫xnxn+1‍(F′′(x)-F′′(xn))(xn+1-x)dx,
the definition of the method, the main hypotheses on GF and the induction process, we obtain, using that ∥F(yn)∥≤p(sn) and that
(3.17)F′′(xn)(xn+1-xn)2=F′′(xn)F′(xn)-1F(xn)F′(xn)-1F(xn)+F′′(xn)F′(xn)-1F(xn)(I+LF(xn)+LF(xn)2GF(xn))F′(xn)-1F(yn)+F′′(xn)F′(xn)-1F(xn)(I+LF(xn)+LF(xn)2GF(xn))F′(xn)-1F(yn)+F′′(xn)((I+LF(xn)+LF(xn)2GF(xn))F′(xn)-1F(yn))2,
the desired inequality:
(3.18)‖F(xn+1)‖≤p(tn+1).
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 top 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
(4.1)∫0∞‍〈Cx(t),Cx(t)〉+u*Ru(t)dt
is minimized, where R is a positive defined matrix and the observation C∈ℒ(X,ℝd). In practice, the control is calculated through approximation. This leads to solving an algebraic Riccati equation
(4.2)A*P+PA-PBR-1B*P=-C*C
for a feedback operator
(4.3)K=-R-1B*P,
see [25, 26] for more details.In the general case, an algebraic Riccati’s equation is given by [27]
(4.4)R(X)=XDX-XA-ATX-C=0,
where D,A,C∈ℝn×n are given matrix, D symmetric and X∈ℝn×n is the unknown.In this case,(4.5)R′(X)Y=(XD-AT)Y+Y(DX-A),R′′(X)YZ=YDZ+ZDY.In particular, the second derivative is constant. In this case, the Kantorovich conditions for Newton’s methods have the compact form(4.6)‖R-1(X0)R′′(X0)‖‖R-1(X0)R(X0)‖≤12.
Moreover, this hypothesis also gives the convergence for the high-order methods [22].Then, using a matricial norm(4.7)‖R′′(X)YZ‖≤2‖D‖‖Y‖‖Z‖,‖R′′(X)‖≤2‖D‖.Given a symmetric initial guessX0∈ℝn×n, to obtain R′(X0)-1 we solve the equation
(4.8)R′(X0)Y=(X0D-AT)Y+Y(DX0-A)=Z.
This equation has solution if DX0-A is stable [27], that is, all its eigenvalues have negative real part. In this following case
(4.9)Y=R′(X0)-1Z=-∫0∞‍exp⁡((DX0-A)Tt)Zexp⁡((DX0-A)t)dt.Next, to illustrate the previous results, we consider the following algebraic Riccati equation (4.4) with matrix
(4.10)D=(100010001)=C,A=(001010100),
and the starting point
(4.11)X0=(-320100010-54).
In this case, the algebraic Riccati equation has exact solution
(4.12)X*=(-20101-2010-2).
Besides, from the aforesaid starting point it follows that DX0-A is a stable matrix.Now, considering the stopping criterion∥Xn-X*∥<10-50 in Table 1, we obtain the errors ∥Xn-X*∥. If we now analyze the following computational order of convergence [28]:
(4.13)ρ≈ln⁡‖Xn+1-X*‖‖Xn-X*‖/ln⁡‖Xn-X*‖‖Xn-1-X*‖,n∈N,
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
…
·
1
0
-
2
3.92135
…
·
1
0
-
2
8.63800
…
·
1
0
-
3
2
2.45310
…
·
1
0
-
3
1.60604
…
·
1
0
-
5
7.95704
…
·
1
0
-
14
3
2.12390
…
·
1
0
-
6
1.03568
…
·
1
0
-
15
4
1.59486
…
·
1
0
-
12
2.77730
…
·
1
0
-
46
5
8.99292
…
·
1
0
-
25
6
2.85928
…
·
1
0
-
49Table 2
The computational order of convergence for the Newton, Chebyshev and M6 methods.
n
ρ
N
ρ
CH
ρ
M
6
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 operatorF, 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(4.14)u(s)=ψ(s)+∫01‍H(s,t)f(t,u(t))dt.
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
(4.15)xi=ψ(ti)+∑j=0m‍γjH(ti,tj)f(tj,xj),i=0,1,…,m,
where 0≤t0<t1<⋯<tm≤1 are the grid points of some quadrature formula ∫01‍f(t)dt≈∑j=0m‍γjf(tj), and xi=x(ti).The second Fréchet derivative of the associated discrete system is diagonal by blocks.Let the following Hammerstein equation(4.16)x(s)=1-14∫01‍st+s1x(t)dt,s∈[0,1].The discretization of this equation verifies the Lipschitz condition of our Kantorovich theorem [4].We considerm=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
…
·
1
0
-
2
4
.
23125
…
·
1
0
-
3
5
.
00638
…
·
1
0
-
4
2
1
.
60604
…
·
1
0
-
4
1
.
06034
…
·
1
0
-
6
6
.
55602
…
·
1
0
-
15
3
3
.
30548
…
·
1
0
-
8
1
.
00158
…
·
1
0
-
17
8
.
23560
…
·
1
0
-
60
4
3
.
11276
…
·
1
0
-
16
2
.
13492
…
·
1
0
-
49
5
1
.
12645
…
·
1
0
-
32
6
2
.
89613
…
·
1
0
-
65Since the second derivative is diagonal by blocks, its application has a computational cost of orderO(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.


## 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
(4.1)∫0∞‍〈Cx(t),Cx(t)〉+u*Ru(t)dt
is minimized, where R is a positive defined matrix and the observation C∈ℒ(X,ℝd). In practice, the control is calculated through approximation. This leads to solving an algebraic Riccati equation
(4.2)A*P+PA-PBR-1B*P=-C*C
for a feedback operator
(4.3)K=-R-1B*P,
see [25, 26] for more details.In the general case, an algebraic Riccati’s equation is given by [27]
(4.4)R(X)=XDX-XA-ATX-C=0,
where D,A,C∈ℝn×n are given matrix, D symmetric and X∈ℝn×n is the unknown.In this case,(4.5)R′(X)Y=(XD-AT)Y+Y(DX-A),R′′(X)YZ=YDZ+ZDY.In particular, the second derivative is constant. In this case, the Kantorovich conditions for Newton’s methods have the compact form(4.6)‖R-1(X0)R′′(X0)‖‖R-1(X0)R(X0)‖≤12.
Moreover, this hypothesis also gives the convergence for the high-order methods [22].Then, using a matricial norm(4.7)‖R′′(X)YZ‖≤2‖D‖‖Y‖‖Z‖,‖R′′(X)‖≤2‖D‖.Given a symmetric initial guessX0∈ℝn×n, to obtain R′(X0)-1 we solve the equation
(4.8)R′(X0)Y=(X0D-AT)Y+Y(DX0-A)=Z.
This equation has solution if DX0-A is stable [27], that is, all its eigenvalues have negative real part. In this following case
(4.9)Y=R′(X0)-1Z=-∫0∞‍exp⁡((DX0-A)Tt)Zexp⁡((DX0-A)t)dt.Next, to illustrate the previous results, we consider the following algebraic Riccati equation (4.4) with matrix
(4.10)D=(100010001)=C,A=(001010100),
and the starting point
(4.11)X0=(-320100010-54).
In this case, the algebraic Riccati equation has exact solution
(4.12)X*=(-20101-2010-2).
Besides, from the aforesaid starting point it follows that DX0-A is a stable matrix.Now, considering the stopping criterion∥Xn-X*∥<10-50 in Table 1, we obtain the errors ∥Xn-X*∥. If we now analyze the following computational order of convergence [28]:
(4.13)ρ≈ln⁡‖Xn+1-X*‖‖Xn-X*‖/ln⁡‖Xn-X*‖‖Xn-1-X*‖,n∈N,
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
…
·
1
0
-
2
3.92135
…
·
1
0
-
2
8.63800
…
·
1
0
-
3
2
2.45310
…
·
1
0
-
3
1.60604
…
·
1
0
-
5
7.95704
…
·
1
0
-
14
3
2.12390
…
·
1
0
-
6
1.03568
…
·
1
0
-
15
4
1.59486
…
·
1
0
-
12
2.77730
…
·
1
0
-
46
5
8.99292
…
·
1
0
-
25
6
2.85928
…
·
1
0
-
49Table 2
The computational order of convergence for the Newton, Chebyshev and M6 methods.
n
ρ
N
ρ
CH
ρ
M
6
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 operatorF, 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(4.14)u(s)=ψ(s)+∫01‍H(s,t)f(t,u(t))dt.
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
(4.15)xi=ψ(ti)+∑j=0m‍γjH(ti,tj)f(tj,xj),i=0,1,…,m,
where 0≤t0<t1<⋯<tm≤1 are the grid points of some quadrature formula ∫01‍f(t)dt≈∑j=0m‍γjf(tj), and xi=x(ti).The second Fréchet derivative of the associated discrete system is diagonal by blocks.Let the following Hammerstein equation(4.16)x(s)=1-14∫01‍st+s1x(t)dt,s∈[0,1].The discretization of this equation verifies the Lipschitz condition of our Kantorovich theorem [4].We considerm=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
…
·
1
0
-
2
4
.
23125
…
·
1
0
-
3
5
.
00638
…
·
1
0
-
4
2
1
.
60604
…
·
1
0
-
4
1
.
06034
…
·
1
0
-
6
6
.
55602
…
·
1
0
-
15
3
3
.
30548
…
·
1
0
-
8
1
.
00158
…
·
1
0
-
17
8
.
23560
…
·
1
0
-
60
4
3
.
11276
…
·
1
0
-
16
2
.
13492
…
·
1
0
-
49
5
1
.
12645
…
·
1
0
-
32
6
2
.
89613
…
·
1
0
-
65Since the second derivative is diagonal by blocks, its application has a computational cost of orderO(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.



---

*Source: 782170-2012-08-15.xml*