# The Convergence Ball and Error Analysis of the Relaxed Secant Method

Authors: Rongfei Lin; Qingbiao Wu; Minhong Chen; Lu Liu
Journal: Advances in Mathematical Physics
 (2017)

---

## Abstract

A relaxed secant method is proposed. Radius estimate of the convergence ball of the relaxed secant method is attained for the nonlinear equation systems with Lipschitz continuous divided differences of first order. The error estimate is also established with matched convergence order. From the radius and error estimate, the relation between the radius and the speed of convergence is discussed with parameter. At last, some numerical examples are given.


---

## Body

## 1. Introduction

Many scientific problems can be concluded to the form of nonlinear systems. Finding the solutions of nonlinear systems is widely required in both mathematical physics and nonlinear dynamical systems. In this paper, we will establish the convergence ball and error analysis of the relaxed secant method of nonlinear systems. Consider(1)Fx=0,where F is a nonlinear operator defined on a convex subset Ω of a Banach space X with values in another Banach space Y. When F is nonlinear, iterative methods are generally adopted to solve the system:(2)xn+1=Ψxn,x0is  given.The most widely used iterative method is Newton’s method which can be described as(3)xn+1=xn-Fxn-1Fxn,x0is  given.This method and Newton-like methods have been studied well by many authors (see [1–12]).Newton’s method requires thatF is differentiable. Thus, when F is nondifferentiable, Newton method cannot be applied on it. We have to turn to other methods that do not need to evaluate derivatives. In their algorithms, instead of derivatives, divided differences are always used. The classical method of this type is the secant method.LetΦ(X,Y) denote the space of the bounded linear maps from X to Y. If the following equality holds,(4)X,Y;Fx-y=Fx-Fy, then, we call the operator [X,Y;F]∈Φ(X,Y), at the points x and y  (x≠y), a divided difference of order one of the nonlinear operator F.By the above definition, secant method can be generalized to Banach spaces, it is described as the following scheme:(5)xn+1=xn-xn-1,xn;F-1Fxn,n>0x0,x-1∈Ω.An interesting issue here is to estimate the radius of the convergence ball of an iterative method. Supposex∗ is a solution of the nonlinear system (1). Denote with B(x∗,r)⊂X an open ball with center x∗ and radius r. The open ball B(x∗,r)⊂X is called a convergence ball of an iteration, if the sequence generated by the iterative method converges with any initial value in the ball. Under the assumption that the nonlinear operator F has Fréchet derivatives satisfying the Hölder condition, (6)F′x∗-1x,y;F-F′z⩽Kx-zp+y-zp,∀x,y,z∈Ωfor  someK>0.Ren and Wu [13] have given the radius of the convergence ball which is rp=(1+p)/K(1+2p)p.The convergence ball, the semilocal convergence of secant method, and secant-like method have been studied by many other authors (see [13–18]). In this paper, similar to the relaxed Newton’s method in [7], we considered the relaxed secant method which can be written as the following form:(7)xn+1=xn-λxn-1,xn;F-1Fxn,x0,x-1∈Ω;here, λ∈(0,2) is called the relaxed parameter. When λ=1, it will be the normal secant method.In this paper, we will study the convergence ball of (7) under the assumption that the nonlinear operator F has Fréchet derivatives satisfying the following Lipschitz condition:(8)F′x∗-1x,y;F-v,w;F⩽Kx-v+y-w,∀x,y,v,w∈Ωfor someK>0.Under the Lipschitz condition, the radiusrλ1 of the relaxed method is proved to be λ/4K when 0<λ⩽1; and the radius rλ2 of the relaxed method is proved to be (2-λ)/4Kλ when 1<λ<2. The error estimate is also given.


## 2. Convergence Ball

Theorem 1.
SupposeF(x∗)=0, where the nonlinear operator F is Fréchet differentiable on Ω, F′(x∗)-1 exists, the Lipschitz condition (8) holds, and 0<λ<2. Denote(9)rλ1=λ4K,rλ2=2-λ4Kλ.When 0<λ⩽1, starting from any two initial points x0,x-1 in ball B(x∗,rλ1), the sequence {xn} generated by the relaxed secant method (7) converges to the solution x∗. When 1<λ<2, the sequence {xn} generated by the relaxed secant method (7) converges to the solution x∗, with any two initial points x0,x-1 in ball B(x∗,rλ2). x∗ is the unique solution in ball B(x∗,1/K), that is bigger than ball B(x∗,rλ1) and ball B(x∗,rλ2). Moreover, we have the following error estimate:(10)xn-x∗⩽2-λ1-2Kθ-1n,if0<λ⩽1,xn-x∗⩽4λ-2Kθ+λ-11-2Kθn,if1<λ<2,where θ=max⁡x0-x∗,x-1-x∗.Proof.
We will prove the above theorem by induction. Firstly, when0<λ<2, by Lipschitz condition, it is easy to get(11)I-F′x∗-1x-1,x0;F=F′x∗-1F′x∗-x-1,x0;F⩽Kx-1-x∗+x0-x∗<1. By Banach lemma, we can know [x-1,x0;F] is invertible. Since x1 is well defined and(12)F′x∗-1x-1,x0;F-1⩽11-Kx-1-x∗+x0-x∗, we can conduct(13)F′x∗-1x-1,x0;F=F′x∗-1x-1,x0;F-F′x∗+F′x∗⩽Kx-1-x∗+x0-x∗+1.
Then, we can give the estimate ofx1-x∗ when 0<λ⩽1. From F(x∗)=0, we have(14)x1-x∗=x0-x∗-λx-1,x0;F-1Fx0=F′x∗-1x-1,x0;F-1F′x∗-1x-1,x0;Fx0-x∗-λFx0-Fx∗⩽F′x∗-1x-1,x0;F-1F′x∗-1x-1,x0;Fx0-x∗-λ∫01F′tx0+1-tx∗dtx0-x∗⩽F′x∗-1x-1,x0;F-1x0-x∗λF′x∗-1x-1,x0;F-∫01F′tx0+1-tx∗dt+1-λF′x∗-1x-1,x0;F. Using Lipschitz condition with (12) and (13), we have(15)x1-x∗⩽rλ11-2Krλ1∫01λKx-1-tx0-1-tx∗+x0-tx0-1-tx∗dt+1-λKx-1-x∗+x0+x∗+1=rλ11-2Krλ1∫01λKtx-1-x0+1-tx-1-x∗+1-tx0-x∗dt+1-λKx-1-x∗+x0+x∗+1. Obviously, we have(16)x-1-x0⩽x0-x∗+x-1-x∗.From x-1,x0∈Bx∗,rλ1, together with (15), (16), and rλ1=λ/4K, we have(17)x1-x∗<rλ11-2Krλ12Kλrλ1+1-λ2Krλ1+1=rλ1.This means x1∈Bx∗,rλ1.
Similar to the procession above, when1<λ<2, we can get that(18)x1-x∗=x0-x∗-λx-1,x0;F-1Fx0⩽F′x∗-1x-1,x0;F-1x0-x∗λF′x∗x-1,x0;F-∫01F′tx0+1-tx∗dt+λ-1F′x∗-1x-1,x0;F. By (13) and (18) and Lipschitz condition we can get(19)x1-x∗≤rλ21-2Krλ2∫01λKx-1-tx0-1-tx∗+x0-tx0-1-tx∗dt+λ-1Kx-1-x∗+x0-x∗+1=rλ21-2Krλ2∫01λKtx-1-x0+1-tx-1-x∗+1-tx0-x∗dt+λ-1Kx-1-x∗+x0-x∗+1⩽rλ21-2Kλ22Kλrλ2+λ-12Krλ2+1. For x-1,x0∈B(x∗,rλ2),(20)x1-x∗⩽Krλ21-2Kλ22Kλrλ2+λ-12Krλ2+1=rλ2. This means that x1∈Bx∗,rλ2 when 1<λ<2.
Now, supposexk  k=1,2,…,n is well defined, xk∈Bx∗,rλ1, when 0<λ⩽1; xk(k=1,2,…,n) is well defined, xk∈B(x∗,rλ2), when 1<λ<2. Similar to the argumentation about x-1 and x0, when 0<λ<2,(21)I-F′x∗-1xn-1,xn;F⩽Kxn-1-x∗+xn-x∗<1. By the Banach lemma, it is obviously known that xn-1,xn;F is invertible. Hence, xn+1 is well defined. We also get(22)F′x∗-1xn-1,xn;F-1≤11-Kxn-1-x∗+xn-x∗. When 0<λ⩽1,(23)xn+1-x∗⩽xn-x∗1-Kxn-x∗+xn-1-x∗×λK∫01txn-1-xn+1-txn-1-x∗+1-txn-x∗dt+1-λKxn-1-x∗+xn-x∗+1. And when 1<λ<2, we have(24)xn+1-x∗⩽xn-x∗1-Kxn-x∗+xn-1-x∗×λK∫01txn-1-xn+1-txn-1-x∗+1-txn-x∗dt+λ-1Kxn-1-x∗+xn-x∗+1. By the assumptions that xn-1,xn∈B(x∗,rλ1) when 0<λ⩽1 and xn-1,xn∈B(x∗,rλ2) when 1<λ<2, similar to the discussions about x1, it is known that xn+1∈B(x∗,rλ1) when 0<λ⩽1 and xn+1∈B(x∗,rλ2) when 1<λ<2.
Therefore, starting from any two initial pointsx-1,x0, xn, the sequence {xn}, generated by the relaxed secant method, is well defined when 0<λ⩽1,  xn∈B(x∗,rλ1), and when 1<λ<2,  xn∈B(x∗,rλ2). It means that the following holds:(25)xn-x∗<rλ1,0<λ⩽1,n≥-1,(26)xn-x∗<rλ2,1<λ<2,n≥-1.
Denote(27)θn=xn-x∗,(28)θ=max⁡θ0,θ-1. When 0<λ⩽1, from (14) we can get(29)xn+1-x∗⩽xn-x∗1-Kxn-x∗+xn-1-x∗×λKxn-x∗+xn-1-x∗+1-λKxn-x∗+xn-1-x∗+1. Then, by (27), we have(30)θn+1⩽θn1-Kθn+θn-1λKθn+θn-1+1-λKθn+θn-1+1. By (23), we know θn<rλ1 for all n. Then by (29) and (30), we can induct(31)θn+1<θn<θn-1<⋯<θ1<θ. Then we can see(32)θn+1⩽θn1-Kθn+θn-1Kθn+θn-1+1-λ=θnKθn+θn-1-1+2-λ1-Kθn+θn-1=θn2-λ1-Kθn+θn-1-1<θn2-λ1-2Kθ-1<θ2-λ1-2Kθ-1n+1. Obviously, 0<2-λ/1-2Kθ-1<1. The sequence {xn} converges to the exact solution x∗ from (32).
When1<λ<2, from (24),(33)xn+1-x∗⩽xn-x∗1-Kxn-x∗+xn-1-x∗×λK∫01txn-1-xn+1-txn-1-x∗+1-txn-x∗dt+λ-1Kxn-1-x∗+xn-x∗+1. Then, by (27), we have(34)θn+1⩽θn1-Kθn+θn-1λKθn+θn-1+λ-1Kθn+θn-1+1=θn1-Kθn+θn-12λ-1Kθn+θn-1+λ-1. By (24) and (26), we know θn<rλ2 for all n. Then by (26) and (34), when 1<λ<2, we can induct(35)θn+1<θn<θn-1<⋯<θ1<θ. So we have(36)θn+1⩽θn22λ-1Kθ-11-2Kθ<θ4λ-2Kθ+λ-11-2Kθn+1. It is easy to proof that 0<(4λ-2)Kθ+λ-1/1-2Kθ<1. So the sequence {xn} converges to the solution x∗.
Now we show the uniqueness. Assume that there exists another solutiony∗∈B(x∗,1/K). Consider the operator A=[x∗,y∗;F]. Because A[y∗-x∗]=F(y∗)-F(x∗), we can get y∗=x∗ if the operator A is invertible. From (4), we get(37)I-F′x∗-1A=F′x∗-1F′x∗-A⩽Ky∗-x∗<1. So, we can tell that operator A is invertible by Banach lemma. From the definition of rλ and (9), it is easy to verify that ball B(x∗,1/K) is bigger than ball B(x∗,rλ1) and ball B(x∗,rλ2). Proof completes.Remark 2.
Whenλ=1, the radius of the convergence ball is 1/4K. We denote r1=1/4K. From (9), we know when 0<λ<1,  rλ1<r1, and when 1<λ<2,  rλ2<r1. So we have the biggest convergence ball when λ=1.


## 3. Numerical Examples

In this section, we applied the convergence ball result given in Section2 to solve some numerical problems.Example 1.
Let us consider(38)Fx=x2-1,x∈0,2.Then F′(x)=2x. F(x)=0 has a root x∗=1 and F′(x∗)=2. It is easy to obtain (39)F′x∗-1x,y;F-u,v;F⩽12x-u+y-v.Set λ1=0.9,  λ2=1,  λ3=1.1. Then the radius of the convergence balls is r1=9/20,  r2=1/2,  r3=9/22. Choose the initial points x-1=1.15,  x0=1.2 and they are in the convergence ball of the relaxed secant method. From Table 1, we can see the sequence {xn} converges to x∗ with different λ.Table 1
Relaxed secant method with differentλ.
λ
n
x
n
x
n
-
x
∗
CPU time
0.9
1
1.0315
0.0315
0.000877
2
1.0057
0.0057
3
1.0006
6.4804
×
1
0
-
4
4
1.0001
6.6458
×
1
0
-
5
5
1.0000
6.6652
×
1
0
-
6
6
1.0000
6.6672
×
1
0
-
7
1
1
1.0128
0.0128
0.000864
2
1.0012
0.0012
3
1.0000
7.3141
×
1
0
-
6
4
1.0000
4.2172
×
1
0
-
7
1.1
1
0.9940
0.006
0.000095
2
1.0000
1.6176
×
1
0
-
6
3
1.0000
1.6708
×
1
0
-
7As we know, whenλ=1, the relaxed secant method reduces to normal secant method. From Table 1, we can see that relaxed secant method in the case of λ=1.1 outperforms the normal secant method in the sense of iteration number and CPU time.Example 2.
Let us consider the following numerical problem which has been studied in [3, 17, 18]:(40)Fx=ex-1,D=-1,1.Then F′(x)=ex, x∗=0, and F′(x∗)=1.
Similar to the process in [17], we know |ex-ey|⩽e|x-y|. Then, (41)∫01etx+1-ty-etu+1-tvdt⩽e2x-u+y-v. For [x,y;F]=∫01etx+(1-t)ydt and F′x∗-1([x,y;F]-[u,v;F])⩽[x,y;F]-[u,v;F], we can get (42)F′x∗-1x,y;F-u,v;F⩽e2x-u+y-v.So K=e/2 in this problem. Set λ1=0.999,  λ2=1,  λ3=1.01. Then, the radius of the convergence balls is r1=999/2000e,  r2=1/2e,  r3=99/202e. Set the initial points x-1=0.08,  x0=0.1, and they are in the convergence ball of the relaxed secant method. From Table 2, we can see the sequence {xn} converges to the solution x∗.
From Table2, we can know that the relaxed scant method (λ=0.999) performs the same as the normal secant method in the sense of the iteration number and CPU time, while the solution gotten by the relaxed secant method is closer to the exact solution than that by the normal secant method.Table 2
Relaxed secant method with differentλ.
λ
n
x
n
x
n
-
x
∗
CPU time
0.999
1
0.0038
0.0038
0.000094
2
1.8245
×
1
0
-
4
1.8245
×
1
0
-
4
3
1.6290
×
1
0
-
7
1.6290
×
1
0
-
7
1
1
0.0039
0.0039
0.000094
2
1.9078×10-4
1.9078
×
1
0
-
4
3
3.7011
×
1
0
-
4
3.7011
×
1
0
-
4
1.01
1
0.0048
0.0048
0.000108
2
2.8301
×
1
0
-
4
2.8301
×
1
0
-
4
3
3.4788
×
1
0
-
6
3.4788
×
1
0
-
6
4
3.4931
×
1
0
-
8
3.4931
×
1
0
-
8Example 3.
Let us consider the nonlinear system:(43)2x1-19x12-x2=0,-x1+2x2-19x22=0. It comes from the following nonlinear boundary value problem of second order:(44)x′′+x2=0,x0=x1=0, which has been studied by many authors [5, 13, 16].
Now, define the operatorF:R2→R2 such that F=(F1,F2). We take F1(x1,x2)=2x1-1/9x12-x2=0,  F2(x1,x2)=-x1+2x2-1/9x22=0,  x=(x1,x2)∈R2. Then, notice 0<λ⩽1; it is easy to knowF is Fréchet differentiable in R2 and we get(45)F′x=2-29x1-1-12-29x2.
Letx=(x1,x2)∈R2 and x=x∞=max1⩽i⩽2xi. The corresponding norm on A∈R2×R2 is (46)A=max1⩽i⩽2⁡∑j=12aij.
It can be verified easily thatx∗=(9,9) is a solution of (24) and from (26) we get(47)F′x=0-1-10.F′(x) is invertible. Similar to [13], we can deduce that Lipschitz continuous condition is satisfied for K=1/9. Set λ1=0.9999,  λ2=1,  λ3=1.06. Then the radius of the convergence ball is r1=2.499975,  r2=9/4,  r3=326/212. Set the two initial points x-1=(9.5,9.5),  x0=(8.5,8.5) and they are in the convergence ball. For results, see Table 3.
Table3 shows the sequence {xn} generated by the relaxed secant method. From this table, it is known that the sequence {xn} converges, and also the error estimation holds. Moreover, relaxed secant method has more choices than secant method, and optimal parameter λ makes the presented method outperforms the normal secant method.Table 3
Relaxed secant method with differentλ.
λ
n
x
n
x
n
-
x
∗
CPU time
0.9999
1
(8.9732, 8.9732)
0.0277
0.000288
2
(9.0016, 9.0016)
0.0016
3
(9.0000, 9.0000)
5.2307
×
1
0
-
6
4
(9.0000, 9.0000)
4.2965
×
1
0
-
10
1
1
(8.9722, 8.9722)
0.0278
0.001643
2
(9.0016, 9.0016)
0.0016
3
(9.0000, 9.0000)
5.0744
×
1
0
-
6
4
(9.0000, 9.0000)
9.2414
×
1
0
-
10
0.8
1
(8.9455, 8.9455)
0.545
0.001608
2
(9.0000, 9.0000)
4.0974
×
1
0
-
5
3
(9.0000, 9.0000)
2.0838
×
1
0
-
6
4
(9.0000, 9.0000)
1.1794
×
1
0
-
7Example 4.
Consider the nonlinear conservative system given in [15]:(48)d2xtdt2=-ext,x0=x1=0.Applying the centered finite difference scheme, we can get the nonlinear system:(49)Fx=Mx+h2ϕx,where h=1/N+1 is the step-size and N is a prescribed positive integer. x, ϕ(x) are vectors with forms of(50)x=x1x2⋮xm,ϕx=ex1ex2⋮exm,and the matrix M has the form(51)A=-210⋯01-21⋯001-2⋯0⋮⋮⋮⋱⋮000⋯-2.Take the same parameters used in [15], N=19,  h=1/20, and the initial points x-1(t)=5/2t(1-t) and x0(t)=1/2t(1-t),  t∈[0,1]. Then, we can solve this problem by our relaxed secant method, and we compare it with normal secant method. For the results, see Table 4.Table 4
Numerical results for nonlinear conservative systems.
λ
IT
x
n
+
1
-
x
n
CPU time
0.99
75
8.7445×10-7
0.002581
1
94
1.9319×10-7
0.002931
0.001
63
9.3315×10-7
0.001471From the results, we can know that, in this example, the relaxed secant method performs better. And we list the approximation solution which is gotten by the relaxed secant method in the situationλ=0.99 in Table 5.Table 5
Approximated solution.
i
x
i
∗
1
0.026205377
2
0.049844664
3
0.070856372
4
0.089184975
5
0.104780806
6
0.117601571
7
0.127610864
8
0.134780833
9
0.139090798
10
0.140529159
11
0.139090906
12
0.134780768
13
0.127610728
14
0.117601588
15
0.104780816
16
0.089184869
17
0.070856314
18
0.049844674
19
0.026205359



---

*Source: 6976205-2017-03-08.xml*