Rev. Anal. Num´er. Th´eor. Approx., vol. 42 (2013) no. 2, pp. 103–114 ictp.acad.ro/jnaat
ON AN ITERATIVE ALGORITHM OF UˇLM-TYPE FOR SOLVING EQUATIONS
IOANNIS K. ARGYROS∗and SANJAY K. KHATTRI†
Abstract. We provide a semilocal convergence analysis of an iterative algorithm for solving nonlinear operator equations in a Banach space setting. This algo- rithm is of order 1.839. . ., and has already been studied in [3, 8, 18, 20]. Using our new idea of recurrent functions we show that a finer analysis is possible with sufficient convergence conditions that can be weaker than before, and under the same computational cost. Numerical examples are also provided in this study.
MSC 2000. 65G99; 65H10; 65B05; 47H17; 49M15.
Keywords. Banach space, iterative algorithm, semilocal convergence, divided difference of operator, Fr´echet-derivative.
1. INTRODUCTION
In this study, we are concerned with the problem of approximating a locally unique solutionx? of equation:
(1) F(x) = 0,
where F is a nonlinear operator defined on an open subset D of a Banach space X with values in a Banach space Y. Many problems in computational mathematics can be written in the form (1) [8, 14, 16]. Potra in [18] used the Uˇlm-type method [20] (UTM):
xn+1 =xn−A−1n F(xn) (n≥0) (x−2, x−1, x0∈D), (2)
where,
An= [xn, xn−1;F] + [xn−2, xn;F]−[xn−2, xn−1;F], (3)
to provide a local as well as a semilocal convergence analysis under hypotheses on the first [·,·;F] and second [·,·,·;F] order divided differences of operator F.
Here, an operator belonging to the space L(X, Y) (the Banach space of linear and bounded operators from X intoY) is called a divided difference of
∗Department of Mathematical Sciences, Cameron University, Lawton, Oklahoma 73505- 6377, USA, email: [email protected].
†Department of Engineering, Stord Haugesund University College, Norway, email:
order one for the operator F :X→Y on the points x, y∈X if the following properties hold:
[x, y;F](y−x) =F(y)−F(x) for x6=y;
(4)
ifF is Fr´echet-differentiable atx∈X, then [x, x;F] =F0(x).
(5)
An operator belonging to the space L(X, L(X, Y)) denoted by [x, y, z;F] is called a divided difference of order two for the operator F : X → Y on the pointsx, y, z ∈X if:
[x, y, z;F](z−x) = [y, z;F]−[x, y;F], (6)
for the distinct pointsx, y, zifF is twice Fr´echet-differentiable atx∈X, then [x, x, x;F] = 12F00(x).
(7)
Potra showed that theR−order of the method is given by the positive solution of the scalar equations:
(8) t3−t2−t−1 = 0,
which is approximately 1.839. . .. Other methods using divided differences of order can be found in [1-21], and references therein.
Here, we are motivated by optimization considerations, and we show that it is possible to provide under the same computational cost an analysis with the following advantages:
Semilocal case:
(a) finer error bounds on he distances kxn+1−xnk,kxn−x?k (n≥0), (b) weaker sufficient convergence conditions and,
(c) an at least as precise information on the location of the solution x?. Local case:
(a) finer error bounds on the distances involved, (b) and at least as large radius of convergence.
The semilocal convergence is provided in§2 followed by local in§3. Numerical examples are also provided in§4.
2. SEMILOCAL CONVERGENCE ANALYSIS FOR (UTM)
We need the following result on majorizing sequence for (UTM).
Lemma 1. Let α, φ, γ, a, b, c, p, and q be given non-negative constants. As- sume:
φ+γ < p+q c, (9)
then, the polynomial g given by
g(s) = (qc+α+φ)s2+ (p+α+γ)s+φ+γ−p−qc, (10)
has a unique positive rootδ ∈(0,1);
moreover, suppose
α(b+c) +φ(a+c) +γ(a+b)<1;
(11)
δ0 ≤δ;
(12)
f2(δ)≤0;
(13) where,
δ0 = 1−[α(b+c)+φ(a+c)+γ(a+b)]pc+qb(a+b) , (14)
and
f2(s) =psc+q(s+ 1)s2+α
(1 +s+s2)c+ (1 +s)c+b +φ
(1 +s+s2)c+a+b+c
+γ[(1 +s)c+a+ 2b+c]−1.
Then, scalar sequence {tn} (n≥ −2)given by
t−2= 0, t−1=a, t0 =a+b, t1=a+b+c, tn+2 =tn+1+Mn+1(tn+1−tn),
where
Mn+1 = p(tn+1−tn)+q(tnµ−tn−2)(tn−tn−1)/µn
n+1 ,
(15)
is non-decreasing, bounded from above by
(16) t??= 1−δc +a+b,
and converges to its unique least upper bound t? such that t∈[0, t??]. More- over, the following estimates hold for alln≥0 :
0≤tn+2−tn+1≤δ(tn+1−tn)≤δn+1c (n≥0) (17)
and
0≤t?−tn≤δ1−δnc (n≥1), (18)
where,
µn+1 =1−[α(tn+1+tn−2a−b) +φ(tn+1+tn−1−a−b) (19)
+γ(tn+tn−1−a−b−c)].
Proof. We shall show using induction that Mn+1 ≤δ (20)
and
µn+1 <1, (21)
hold for alln. It will then follow that (2.9) also holds. Estimates (20) and (21) hold true forn= 0, by (2.3) and (2.4), respectively. Let us assume (17), (20) and (21) hold for all k≤n. It then follows from the induction hypotheses:
tk+2≤tk+1+δ(tk+1−tk)≤tk+δ(tk−tk−1) +δ(tk+1−tk)
≤t1+δ(t1−t0) +· · ·+δ(tk+1−tk)
≤a+b+c+δc+· · ·+δk+1c
=a+b+1−δ1−δk+2c < a+b+1−δc =t??. Estimates (20) and (21) will be true if
pδkc+qδk−1c
δk−1+δk−2
c≤δ−δ[α(tk+1+tk−t0−t−1) +φ(tk+1+tk−1−t0−t−2) +γ(tk+tk−1−t−1−t−2)]
or
(22) pδkc+qδk−1
δk−1+δk−2
c2+δh α
1−δk+1
1−δ c+1−δ1−δkc+b + +φ
1−δk+1
1−δ c+1−δ1−δk−1 +a+b +γ
1−δ
1−δc+1−δ1−δk−1c+a+ 2bi
−δ ≤0.
Estimate (22) motivates us to introduce functions fk (k ≥ 2) on [0,∞) (for δ =s) by:
(23) fk(s) =pcsk−1+qc2sk−1(s+ 1) +αh
(1 +s+· · ·+sk)c +(1 +s+· · ·+sk−1)c+bi
+φh
(1 +s+· · ·+sk)c +(1 +s+· · ·+sk−2)c+a+b
i
+γ h
(1 +s+· · ·+sk−1)c+ (1 +s+· · ·+sk−2)c+a+ 2b i
−1.
We shall show instead of (20) and (21) that
(24) fk(δ)≤0.
We need a relationship between two consecutive functionsfk : fk+1(s) =pcsk+pcsk−1−pcsk−1+qc2sk(s+ 1)
+qc2sk−1(s+ 1)−qc2sk−1(s+ 1) +α
h
(1 +s+· · ·+sk+sk+1)c+ (1 +s+· · ·+sk−1+sk)c+b i
+φ h
(1 +s+· · ·+sk+sk+1)c
+(1 +s+· · ·+sk−2+sk−1)c+a+bi +γh
(1 +s+· · ·+sk+sk+1)c
+(1 +s+· · ·+sk−2+sk−1)c+a+ 2bi
−1
=fk(s) +g(s)sk−1c, (25)
where, function g is given by (10). In view of (10) and (25) we get
(26) fk(δ) =f2(δ) (k≥2).
Hence, (24) is true if f2(δ)≤0, which is true by (13).
Define function f∞ on [0,1) by
(27) f∞(s) = lim
n→∞fn(s).
Then, we have by (24) and (27):
(28) f∞(∞) = lim
n→∞fn(δ)≤ lim
n→∞0 = 0.
The induction for (17), (20) and (21) is completed. Hence, we showed sequence {tn} is non-decreasing, bounded above by t?? and as such it converges to t?. Finally, estimate (18) follows from
0≤tk+m−tn= (tk+m−tk+m−1)
+ (tk+m−1−tk+m−2) +· · ·+ (tk+1−tk)
≤
δk+m−1+δk+m−2+· · ·+δk
c= 1−δ1−δk+mδkc, (29)
by letting m→ ∞. That completes the proof of the lemma.
We can show the main semilocal convergence result for (UTM).
Theorem 2. Let F be a nonlinear operator defined on an open subset D of a Banach space X with values in a Banach space Y. Let[·,·;F], [·,·,·;F] be divided differences of first and second order of F on D, respectively. Let x−2, x−1, x0∈Dbe three given points fromD, and assumeA0 is invertible. Let
a, b, c, p, q, α, φ, γ be non-negative numbers such that for all x, y, z, u, v∈D: kx−1−x0k ≤a, kx−2−x−1k ≤b,
A−10 F(x0) ≤c, (30)
A−10 ([x, y;F]−[u, v;F])
≤p(kx−uk+ky−vk), (31)
A−10 ([x, y, z;F]−[u, v, z;F])
≤qkx−uk, (32)
A−10 ([x, y;F]−[x0, x−1,;F])
≤α(kx−x0k+ky−x−1k), (33)
A−10 ([x, y;F]−[x−2, x0;F])
≤φ(kx−x−2k+ky−x0k), (34)
A−10 ([x, y;F]−[x−2, x−1;F])
≤γ(kx−x−2k+ky−x−1k), (35)
hypotheses of Lemma 1 hold and
(36) U(x0, t?):={x∈X :kx−x?k ⊆t?} ⊆D.
Then, sequence{xn}(n≥ −2)generated by (UTM) is well defined, remains in U(x0, t?) for all n≥0 and converges to a solution x? ∈U(x0, t?) of equation F(x) = 0. Moreover, the following estimates hold for all n≥0 :
kxn+2−xn+1k ≤Ln+1kxn+1−xnk ≤tn+2−tn+1, (37)
kxn−x?k ≤t?−tn, (38)
where
Ln+1 = pkxn+1−xnk+qkxn−xn−2k kxn−xn−1k dn+1
,
dn+1 = 1−[α(kxn+1−x0k+kxn−x−1k)+φ(kxn−1−x−2k+kxn+1−x0k) +γ(kxn−1−x−2k+kxn−x−1k)].
(39)
Furthermore, if there exists r≥t? such that
U(x0, r)⊆D (40)
and
φ(t?+r) + (φ+γ)(a+b)≤1, (41)
then, the solution x? is unique in U(x0, r).
Proof. We shall show using induction onk≥0 : (42) ktk+1−tkk ≤tk+1−tk.
Estimate (42) holds for k = −2,−1,0 by (14), and (30). We also have have x−2, x−1, x0 ∈U(x0, t?). Let us assume (42), and xk ∈ U(x0, t?) hold for all
n≤k+ 1. We have using (33)-(35):
A0−1
(Ak+1−A0) =
=
A−10 ([xk+1, xk;F]−[x0, x−1;F])
+A−10 ([xk−1, xk+1;F]−[x−2, x0;F]) +A−10 ([xk−1, xk;F]−[x−2, x−1;F])
≤α(kxk+1−x0k+kxk−x−1k) +φ(kxk−1−x−2k+kxk+1−x0k) +γ(kxk−1−x−2k+kxk−x−1k)
≤α(tk+1+tk−2a−b) +φ(tk+1+tk−1−a−b) + +γ(tk+1+tk−1−a−b−c)<1 (by(22)).
(43)
It follows from (43) and the Banach lemma on invertible operators [8, 14] that A−1k+1 exists and
A−1k+1A0
≤d−1k+1
≤
1−[α(tk+1+tk−2a−b) +φ(tk+1+tk−1−a−b) +γ(tk+1+tk−1−a−b−c)] −1
(44)
In view of (2), (44), (45), we have:
kxk+2−xk+1k=
A−1k+1A0
A−10 F(xk+1)
≤
A−1k+1A0
A−10 F(xk+1)
≤Lk+1kxk+1−xkk ≤tk+2−tk+1,
which shows (37) and (42) for all n. By Lemma 2.1, sequence{xn}is Cauchy in a Banach space X and as such it converges to some x? ∈ U(x0, t?) (since U(x0, t?) is a closed set). Estimate (38) follows from (37) by using standard majorization techniques [8, 14, 16].
Using (31), (32) and the induction hypotheses, we obtain in turn A−10 ([xk, xk+1;F]−Ak)
=
=
A−10 ([xk, xk+1;F]−[xk, xk;F] + [xk, xk;F]−Ak)
=
A−10 {[xk, xk+1;F]−[xk, xk;F]−([xk, xk, xk−1;F]
−[xk−2, xk, xk−1;F]) (xk−xk−1)}
≤pkxk+1−xkk+qkxk−xk−2k kxk−xk−1k
≤p(tk+1−tk) +q(tk−tk−2) (tk−tk−1). (45)
We also need the estimate:
kxk+2−xk+1k=
A−1k+1A0
A−10 F(xk+1)
=
A−1k+1A0
A−10 (F(xk+1)−F(xk)−Ak(xk+1−xk))
≤
A−1k+1A0
A−10 ([xk, xk+1;F]−Ak)
kxk+1−xkk. (46)
The fact that x? is a solution of equationF(x) = 0 follows by letting k→ ∞ in the estimate:
A−10 F(xk+1) =
A−10 ([xk,k+1;F]−Ak) (xk+1−xk)
≤pkxk+1−xkk2+qkxk−xk−2k kxk−xk−1k kxk+1−xkk. (47)
Finally, to show the uniqueness part, lety?∈U(x0, r) be a solution of equation F(x) = 0. We can write forL= [y?, x?;F] :
(48) F(y?)−F(x?) =L(y?−x?).
We shall show linear operator Lis invertible. Using (33)-(35), (40) and (41), we have:
A−10 ([x0, x−2;F] + [x−1, x0;F]−[y?, x?;F]−[x−2, x−1;F]) ≤
≤
A−10 ([x0, x−2;F]−[y?, x?;F]) +
A−10 ([x−1, x0;F]−[x−2, x−1;F])
≤φ(kx0−y?k+kx−2−x?k) +γ(kx−1−x−2k+kx0−x−1k)
< φ(r+t?+b+a) +γ(b+a)≤1.
(49)
In view of (49) and the Banach lemma on invertible operators,L−1 exists. We deduce from (48) thatx? =y?.That completes the proof of the Theorem.
Remark 3. (a) A similar existence Theorem (without a uniqueness result) was provided in [18, p.91] using conditions (30)-(31), a decreasing majoriz- ing sequence, and some different sufficient convergence conditions. Therefore a direct comparison is not possible. However, in §4, we show that the re- sults obtained in Theorem 2.2 can be weaker than the corresponding ones of Theorem 5.1 in [18, p.91].
(b) Note that t?? given by (16) can replace t? in hypotheses (36) and (41)
of Theorem 2.2.
3. LOCAL CONVERGENCE OF (UTM)
We can show the local convergence result for (UTM).
Theorem 4. Let F:D⊆X →Y and let x? ∈ D be such that F0(x?)−1 exists. Assume that for all x, y, u, v, z∈D:
F0(x?)−1([x?, x?;F]−[x, x?;F])
≤p0kx?−xk, (50)
F0(x?)−1([z, x?;F]−[z, x;F])
≤p1kx?−xk, (51)
F0(x?)−1([x, x?, y;F]−[z, x?, y;F])
≤q0kx−zk, (52)
F0(x?)−1([u, x, y;F]−[v, x, y;F])
≤q?ku−vk (53)
and
U(x?, r?)⊆D, (54)
where
r? = 2
p0+2p1+
√
(p0+2p1)2+16(q0+q?). (55)
Then, sequence{xn}generated by (UTM) is well defined, remains inU(x?, r?) for all n≥0 and converges tox?, provided that x0 ∈U(x?, r?). Moreover, the following estimates hold:
(56) kxn+1−x?k ≤ hen
nkxn−x?k, where
(57) en=p1kxn−x?k+q?kxn−xn−2k kxn−xn−1k and
(58) hn= 1−(p0+p1)kxn−x?k −q0kxn−xn−2k kxn−1−x?k.
Proof. It follows as the proof of Theorem 4.1 in [8, p.87] but uses the needed conditions (50)-(53) instead of:
F0(x?)−1([x, y;F]−[u, v;F])
≤p?(kx−uk+ky−vk) (59)
and
F0(x?)−1([u, x, y;F]−[v, x, y;F])
≤q?ku−vk. (60)
Remark 5. (a) Clearly
p0 ≤p?, (61)
p1 ≤p?, (62)
q0 ≤q?, (63)
hold in general, and p?/p0, p?/p1 and q?/q0 can be arbitrarily large [7, 8].
If equality holds in (61)-(63), then our results reduce to the ones in [18].
Otherwise they constitute an improvement with advantages as noted in the Introduction of this study. (b) The radius of convergencer? obtained in Theo- rem 3.1 is smaller in general than the corresponding one of Newton’s method.
Indeed from the hypotheses (59) it follows thatF is Fr´echet-differentiable on D and its Fr´echet derivative satisfies
F0(x?)−1 F0(x)−F0(y)
≤2p?kx−yk (64)
and
F0(x?)−1 F0(x)−F0(x?)
≤2p2kx−x?k. (65)
The radius of convergencer? is then given for q0 =q? = 0 : r?A= 2p1
2+p?
(66) for
p2≤p?, (67)
whereas the one obtained by Theorem 4.1 in [18] is given by rR? = 3p1
?, (68)
found by Rheinboldt in [16]. Note that
(69) r?R≤r?A.
If strict inequality holds in (67), then so does in (69).
4. A NUMERICAL EXAMPLE
We provide a numerical example to show that Theorem 2.2 can be used to solve equation (1) but not corresponding Theorem 5.1 in [18]. LetX=Y =R2 be equipped with the max-norm, x0 = (1,1)T, D=U(x0,1−λ), λ∈[0,1/2) and define functionF onD forx= (µ1, µ2) by
(70) F(x) = µ31−λ, µ32−λT
. Using (70) we obtain the Fr´echet-derivative
(71) F0(x) =
3µ21 0 0 3µ22
. Define
(72) [x, y;F] =
Z 1 0
F0(y+t(x−y))dt.
Let x−2 = (1.02,1.02)T, x−1 = (1.01,1.01), λ = 0.49. Using (30)-(35) and (72), we get
a=b= 0.1, c= 0.170011334, A0−1
= 0.33335557, p= 3
A−10
(2−λ), q = 3 A−10
, α= 12(1−λ+a+kx0+x−1k)
A−10 , φ= 12(1−λ+ 2kx0k+kx−2−x0k)
A−10 , γ = 12(1−λ+b+kx0+x−1k)
A−10 ,
so
p= 1.510100673, q= 1.000066671, α=φ=γ = 0.42169478.
Moreover, using (10)-(13) and (16), we obtain (9), (11) become 0.84338956<1.680123342,
0.160253576<1, respectively,
δ0 = 0.305966463, δ = 0.310470973> δ0, f2(δ) =−0.310669379<0 and
t??= 0.267566675.
That is, the hypotheses of Theorem 2.2 are satisfied. Moreover, using Remark 2.3(b) and (41), we see that we can set r = 1−λ= 0.51. Hence, there exists a unique solution:
x?=
√3
0.49,√3 0.49T
= (0.788373516,0.78373516)T
of equationF(x) = 0 inU(x0, r), which can be obtained as the limit of (UTM).
However, hypotheses of Theorem 5.1 in [18] do not hold. The sufficient con- vergence condition corresponding to (11) is given by
c≤λ= 13 p+qa+2λ0
(p+qa+λ0)2 [1−qa(a+b)]2, (73)
where
λ0= n
(p+qa)2+ 3q(1−qa(a+b)) o1/2
. We have
λ0 = 1.520496025, λ= 0.08533979 and, so (73) is violated, since
c= 0.170011334> λ= 0.08533979.
Hence, there is no guarantee that (UTM) starting atx0 converges tox?.
REFERENCES
[1] S. AmatandS. Busquier,A modified secant method for semismooth equations, Appl.
Math. Lett.,16(2003) no. 6, pp. 877–881.
[2] S. Amatand S. Busquier, On a higher order Secant method, Appl. Math. Comput., 141(2003), pp. 321–329.
[3] S. Amat, S.Busquierand V. F. Candela,A class of quasi-Newton generalized Stef- fensen methods on Banach spaces, J. Comput. Appl. Math.,149(2002), no. 2, pp. 397–
406.
[4] S. Amat,S. Busquierand J. M. Guti´errez,On the local convergence of secant-type methods, Int. J. Comput. Math.,81(2004), pp. 1153–1161.
[5] N. Andersonand˚A. Bj¨orck,A new high order method of regula falsi type for computing a root of an equation, BIT,13(1973), pp. 253–264.
[6] I. K. ArgyrosThe secant method in generalized Banach spaces, Appl. Math. Comput., 39(1990), pp. 111–121.
[7] I. K. ArgyrosA unifying local–semilocal convergence analysis and applications for two- point Newton-like methods in Banach space, J. Math. Anal. Appl.,298(2004), pp. 374–
397.
[8] I. K. Argyros,Newton Methods, Nova Science Publ. Inc., New York, 2005.
[9] R. P. Brent,Algorithms for Minimization without Derivatives, Prentice Hall, Engle- wood Cliffs, New Jersey, 1973.
[10] E. C˘atinas¸, On some iterative methods for solving nonlinear equations, Rev. Anal.
Num´er. Th´eor. Approx.,23(1994), pp. 47–53.
[11] J. A. Ezquerro andM. A. Hern´andez,Multipoint super-Halley type approximation algorithms in Banach spaces, Numer. Funct. Anal. Optim.,21(2000), no. 7-8, pp. 845–
858.
[12] M. A. Hern´andez,M. J. RubioandJ. A. Ezquerro,Secant-like methods for solving nonlinear integral equations of the Hammerstein type, J. Comput. Appl. Math., 115 (2000), pp. 245–254.
[13] M. A. Hern´andezandM. J.Rubio,Semilocal convergence of the secant method under mild convergence conditions of differentiability, Comput. Math. Appl.,44(2002), pp. 277- 285.
[14] L. V. KantorovichandG. P. Akilov,Functional Analysis, Pergamon Press, Oxford, 1982.
[15] M. A. Mertvecova,An analog of the process of tangent hyperbolas for general func- tional equations(Russian), Dokl. Akad. Navk. SSSR,88(1953), pp. 611–614.
[16] J. M. Ortega, andW. C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York 1970.
[17] I. P˘av˘aloiu, A convergence theorem concerning the method of chord, Rev. Anal.
Num´er. Th´eor. Approx.,22(1993), no. 1, pp. 93–95.
[18] F. A. Potra, An iterative algorithm of order 1.839. . .for solving nonlinear operator equations, Numer. Funct. Anal. Optim.,7(1984–85), no. 1, pp. 75–106.
[19] W. C. Rheinboldt,An adaptive continuation process for solving systems of nonlinear equations, Polish Academy of Science, Banach Ctr. Publ.,3(1977), pp. 129–142.
[20] S. Uˇlm,Iteration methods with divided differences of the second order, (Russian), Dokl.
Akad. Nauk SSSR,158(1964), pp. 55–58,Soviet Math. Dokl.,5, pp. 1187–1190.
[21] J. Vandergraft, Newton’s method for convex operators in partially ordered spaces, SIAM J. Numer. Anal.,4(1967) pp. 406–432.
Received by the editors: September 12, 2012.