# Two-Step Modified Newton Method for Nonlinear Lavrentiev Regularization

Authors: Santhosh George; Suresan Pareth
Journal: ISRN Applied Mathematics
 (2012)

---

## Abstract

A two step modified Newton method is considered for obtaining
an approximate solution for the nonlinear ill-posed equationF(x)=f when the available data are fδ with ∥f−fδ∥≤δ and the operator F is monotone. The derived error estimate under a general source condition
on x0−x^ is of optimal order; here x0 is the initial guess and x^ is the actual solution. The regularization parameter is chosen according to the adaptive method considered by Perverzev and Schock (2005). The computational results provided endorse the reliability and effectiveness of our method.


---

## Body

## 1.  Introduction

Recently George and Elmahdy [1] studied iterative methods for solving the ill-posed operator equation:(1.1)F(x)=f,
where F:D(F)⊆X→X is a nonlinear monotone operator (i.e., 〈F(x)-F(y),x-y〉≥0,forallx,y∈D(F)) and X is a real Hilbert space. The convergence analysis in [1] is based on suitably constructed majorizing sequences. Recall that a sequence (tn) in ℝ is said to be a majorizing sequence of the sequence (xn)∈X if(1.2)‖xn+1-xn‖≤tn+1-tn,∀n≥0.Throughout this paper, the inner product and the corresponding norm on the Hilbert spaceX are denoted by 〈·,·〉 and ∥·∥ respectively, D(F) is the domain of F and F′(·) is the Fréchet derivative of F.In application, usually only noisy datafδ are available, such that(1.3)‖f-fδ‖≤δ.
Then the problem of recovery of x̂ from noisy equation F(x)=fδ is ill posed, in the sense that a small perturbation in the data can cause large deviation in the solution.For monotone operators, one usually uses the Lavrentiev regularization method (see [2–5]) for solving (1.1). In this method, the regularized approximation xαδ is obtained by solving the operator equation(1.4)F(x)+α(x-x0)=fδ.
It is known (cf. [5], Theorem 1.1) that (1.4) has a unique solution xαδ∈Br(x̂)∶={x∈X:∥x-x̂∥<r}⊂D(F) for any α>0 provided that r=∥x0-x̂∥+δ/α.The optimality of the Lavrentiev method was proved in [5] under a general source condition on x0-x̂. However the main drawback here is that, the regularized equation (1.4) remains nonlinear and one may have difficulties in solving them numerically.Thus in the last few years, more emphasis was put on the investigation of iterative regularization methods (see [6–12]). In this paper, we considered a modified form of the method considered in [1], but we analyse the method as a two step modified Newton Lavrentiev method (TSMNLM). The proposed analysis is motivated by the two step directional Newton method (TSDNM) considered in [13], by Argyros and Hilout, for approximating a zero x* of a differentiable function F defined on a convex subset 𝒟 of a Hilbert space H with values in ℝ. The TSMNLM for approximating the zero xαδ of F(x)-fδ+α(x-x0)=0 is defined as(1.5)yn,αδ=xn,αδ-Rα(x0)-1[F(xn,αδ)-fδ+α(xn,αδ-x0)],(1.6)xn+1,αδ=yn,αδ-Rα(x0)-1[F(yn,αδ)-fδ+α(yn,αδ-x0)],
where x0,αδ:=x0 and Rα(x0)=F′(x0)+αI. Here the regularization parameter α is chosen from the finite set DM={αi:0<α0<α1<⋯<αM}.The organization of this paper is as follows. Convergence analysis of TSMNLM is given in Section2, error bounds under an a priori and under an adaptive choice of the regularization parameter is given are Section 3 and Section 4 deals with implementation of the adaptive choice rule. Example and results of computational experiments are given in Section 5. Finally the paper ends with conclusion in Section 6.


## 2. Convergence Analysis for TSMNLM

We need the following assumptions for the convergence analysis of TSMNLM.Assumption 2.1 (see [4]).
F possesses a locally uniformly bounded Fréchet derivative F′(·) at all x in the domain D(F).Assumption 2.2 (cf. [4], Assumption 3).
There exists a constantk0>0 such that for every x,u∈D(F) and v∈X, there exists an element Φ(x,u,v)∈X satisfying
(2.1)[F′(x)-F′(u)]v=F′(u)Φ(x,u,v),‖Φ(x,u,v)‖≤k0‖v‖‖x-u‖
for all x,u in D(F) and v∈X.Let(2.2)en,αδ∶=‖yn,αδ-xn,αδ‖,∀n≥0,δ0<3α04k0,ρ<3/2-2k0δ0/α0-1k0,(2.3)γρ∶=δ0α0+k02ρ2+ρ.
Hereafter, for convenience, we use the notations xn,yn, and en for xn,αδ,yn,αδ, and en,αδ, respectively.Remark 2.3.
Note that if∥x0-x̂∥≤ρ, then by Assumption 2.2 it follows that
(2.4)e0=‖y0-x0‖=‖Rα(x0)-1(fδ-F(x0))‖=‖Rα(x0)-1(fδ-f+F(x̂)-F(x0)-F′(x0)(x̂-x0)+F′(x0)(x̂-x0))‖≤‖Rα(x0)-1(fδ-f)‖+‖Rα(x0)-1∫01[F′(x̂+t(x̂-x0))-F′(x0)]dt(x̂-x0)‖+‖Rα(x0)-1F′(x0)(x̂-x0)‖≤δα+k02ρ2+ρ≤δ0α0+k02ρ2+ρ=γρ.Let(2.5)q=k0r.
Then γρ/(1-q)<r, if
(2.6)r∈(1-1-4k0γρ2k0,1+1-4k0γρ2k0).Theorem 2.4.
Let q and r be as in (2.5) and (2.6), respectively, and let γρ be as in (2.3). Let en be as in (2.2) and let yn and xn be as in (1.5) and (1.6), respectively, with δ∈[0,δ0) and α∈DM. Then(a)
∥xn-yn-1∥≤q∥yn-1-xn-1∥;(b)
∥yn-xn∥≤q2∥yn-1-xn-1∥;(c)
en≤q2nγρ;(d)
xn,yn∈Br(x0).Proof.
Observe that ifxn,yn∈Br(x0), then by Assumption 2.2 we have
(2.7)xn-yn-1=yn-1-xn-1-Rα(x0)-1(F(yn-1)-F(xn-1)+α(yn-1-xn-1))=Rα(x0)-1[Rα(x0)(yn-1-xn-1)-(F(yn-1)-F(xn-1))-α(yn-1-xn-1)]=Rα(x0)-1∫01[F′(x0)-F′(xn-1+t(yn-1-xn-1))]×(yn-1-xn-1)dt=Rα(x0)-1F′(x0)∫01Φ(x0,xn-1+t(yn-1-xn-1),yn-1-xn-1)dt,
and hence
(2.8)‖xn-yn-1‖≤k0r‖yn-1-xn-1‖.
Again observe that if xn,yn∈Br(x0), by Assumption 2.2 and (2.8), we have
(2.9)yn-xn=xn-yn-1-Rα(x0)-1(F(xn)-fδ+α(xn-x0))=Rα(x0)-1[Rα(x0)(xn-yn-1)-(F(xn)-F(yn-1))-α(xn-yn-1)]=Rα(x0)-1∫01[F′(x0)-F′(yn-1+t(xn-yn-1))]dt(xn-yn-1)=Rα(x0)-1F′(x0)∫01Φ(x0,yn-1+t(xn-yn-1),xn-yn-1)dt,
and hence
(2.10)‖yn-xn‖≤k0r‖xn-yn-1‖≤q2‖yn-1-xn-1‖.
Thus if xn,yn∈Br(x0), then (a) and (b) follows from (2.8) and (2.10), respectively. Now using induction we will prove that xn,yn∈Br(x0). Note that x0,y0∈Br(x0) and hence by (2.8)
(2.11)‖x1-x0‖≤‖x1-y0‖+‖y0-x0‖≤(1+q)e0≤e01-q≤γρ1-q<r,
that is, x1∈Br(x0); again by (2.10)
(2.12)‖y1-x0‖≤‖y1-x1‖+‖x1-x0‖≤q2e0+(1+q)e0≤e0(1-q)≤γρ1-q<r,
that is, y1∈Br(x0). Suppose xk,yk∈Br(x0) for some k>1. Then since
(2.13)‖xk+1-x0‖≤‖xk+1-xk‖+‖xk-xk-1‖+⋯+‖x1-x0‖,
we will first find an estimate for ∥xk+1-xk∥. Note that by (a) and (b) we have
(2.14)‖xk+1-xk‖≤‖xk+1-yk‖+‖yk-xk‖≤(q+1)‖yk-xk‖≤(1+q)q2ke0.
Therefore by (2.13) we have
(2.15)‖xk+1-x0‖≤(1+q)[q2k+q2(k-1)+⋯+1]e0≤(1+q)1-q2k+11-q2e0≤e01-q≤γρ1-q<r.
So by induction xn∈Br(x0) for all n≥0. Again by (a), (b), and (2.15) we have
(2.16)‖yk+1-x0‖≤‖yk+1-xk+1‖+‖xk+1-x0‖≤q2k+2e0+(1+q)[q2k+q2(k-1)+⋯+1]e0≤(1+q)1-q2k+31-q2e0≤e01-q≤γρ1-q<r.
Thus yk+1∈Br(x0) and hence by induction yn∈Br(x0) for all n≥0. This completes the proof of the Theorem.The main result of this section is the following theorem.Theorem 2.5.
Letyn and xn be as in (1.5) and (1.6), respectively, and assumptions of Theorem 2.4 hold. Then (xn) is Cauchy sequence in Br(x0) and converges to xαδ∈Br(x0)¯. Further F(xαδ)+α(xαδ-x0)=fδ and
(2.17)‖xn-xαδ‖≤q2nγρ(1-q).Proof.
Using the relation (b) and (c) of Theorem2.4, we obtain
(2.18)‖xn+m-xn‖≤∑i=0m-1‖xn+i+1-xn+i‖≤∑i=0m-1(1+q)en+i≤∑i=0m-1(1+q)q2(n+i)e0≤(1+q)(q2n-q2n+2m)1-q2e0≤q2n1-qe0≤q2n1-qγρ.
Thus xn is a Cauchy sequence in Br(x0) and hence it converges, say, to xαδ∈Br(x0)¯. Observe that
(2.19)‖F(xn)-fδ+α(xn-x0)‖=‖Rα(x0)(xn-yn)‖≤‖Rα(x0)‖‖(xn-yn)‖≤1αq2nγρ.
Now by letting n→∞ in (2.19), we obtain F(xαδ)-fδ+α(xαδ-x0)=0. This completes the proof.


## 3. Error Bounds under Source Conditions

The objective of this section is to obtain an error estimate for∥xn-x̂∥ under the following assumption on x0-x̂.Assumption 3.1 (see [4]).
There exists a continuous, strictly monotonically increasing functionφ:(0,a]→(0,∞) with a≥∥F′(x̂)∥ satisfying limλ→0φ(λ)=0 and v∈X with ∥v∥≤1 such that
(3.1)x0-x̂=φ(F′(x̂))v,sup⁡λ≥0⁡αφ(λ)λ+α≤cφφ(α),∀λ∈(0,a].Remark 3.2.
It can be seen that functions(3.2)φ(λ)=λν,λ>0
for 0<ν≤1 and
(3.3)φ(λ)={(ln⁡1λ)-p,0<λ≤e-(p+1),0,otherwise,
for p≥0 satisfy Assumption 3.1 (see [14]).We will be using the error estimates in the following proposition, which can be found in [5], for our error analysis.Proposition 3.3 (cf. [5], Proposition 3.1).
Letx̂∈D(F) be a solution of (1.1) and let F:D(F)⊆X→X be a monotone operator in X. Let xα be the unique solution of (1.4) with f in place of fδ and let xαδ be the unique solution of (1.4). Then
(3.4)‖xαδ-xα‖≤δα,‖xα-x̂‖≤‖x0-x̂‖.The following theorem can be found in [1].Theorem 3.4 (see, [1], Theorem 3.1).
Letxα be the unique solution of (1.4) with f in place of fδ. Let the assumptions in the Proposition 3.3 and the Assumptions 2.1, 2.2, and 3.1 be satisfied. Then
(3.5)‖xα-x̂‖≤(k0r+1)cφφ(α).Combining the estimates in Proposition3.3, Theorems 2.5, and 3.4 we obtain the following.Theorem 3.5.
Letxn be as in (1.6) and let the assumptions in Proposition 3.3, Theorems 2.5, and 3.4 be satisfied. Then
(3.6)‖xn-x̂‖≤q2nγρ(1-q)+max⁡{1,(k0r+1)cφ}(φ(α)+δα).Let(3.7)C¯∶=max⁡{γρ1-q+1,(k0r+1)cφ},
and let(3.8)nδ∶=min⁡{n:q2n≤δα}.Theorem 3.6.
Letxαδ be the unique solution of (1.4) and let xn be as in (1.6). Let the assumptions in Theorem 3.5 be satisfied. Let C¯ be as in (3.7) and let nδ be as in (3.8). Then
(3.9)‖xnδ-x̂‖≤C¯(φ(α)+δα).


### 3.1. A Priori Choice of the Parameter

Note that the error estimateφ(α)+δ/α in (3.9) is of optimal order if α:=αδ satisfies, φ(αδ)αδ=δ.Now using the functionψ(λ):=λφ-1(λ), 0<λ≤a, we have δ=αδφ(αδ)=ψ(φ(αδ)), so that αδ=φ-1(ψ-1(δ)). In view of the above observations and (3.9), we have the following.Theorem 3.7.
Letψ(λ):=λφ-1(λ) for 0<λ≤a, and let the assumptions in Theorem 3.6 hold. For δ>0, let α:=αδ=φ-1(ψ-1(δ)). Let nδ be as in (3.8). Then
(3.10)‖xnδ-x̂‖=O(ψ-1(δ)).


### 3.2. An Adaptive Choice of the Parameter

In this subsection, we will present a parameter choice rule based on the adaptive method studied in [3, 9]. Let(3.11)DM(α)∶={αi=μiα0,i=0,1,…,M},
where μ>1, α0>0, and let(3.12)ni:=min⁡{n:q2n≤δαi}.
Then for i=0,1,…,M, we have(3.13)‖xni-xαiδ‖≤δαi,∀i=0,1,…,M.Letxi:=xni,αiδ. In this paper, we select α=αi from DM(α) for computing xi for each i=0,1,…,M.Theorem 3.8 (cf. [9], Theorem 4.3).
Assume that there existsi∈{0,1,2,…,M} such that φ(αi)≤δ/αi. Let assumptions of Theorems 3.6 and 3.7 hold and let
(3.14)l∶=max⁡{i:φ(αi)≤δαi}<M,k∶=max⁡{i:‖xi-xj‖≤4C¯δαj,j=0,1,2,…,i-1}.
Then l≤k and
(3.15)‖x̂-xk‖≤cψ-1(δ),
where c=6C¯μ.


## 3.1. A Priori Choice of the Parameter

Note that the error estimateφ(α)+δ/α in (3.9) is of optimal order if α:=αδ satisfies, φ(αδ)αδ=δ.Now using the functionψ(λ):=λφ-1(λ), 0<λ≤a, we have δ=αδφ(αδ)=ψ(φ(αδ)), so that αδ=φ-1(ψ-1(δ)). In view of the above observations and (3.9), we have the following.Theorem 3.7.
Letψ(λ):=λφ-1(λ) for 0<λ≤a, and let the assumptions in Theorem 3.6 hold. For δ>0, let α:=αδ=φ-1(ψ-1(δ)). Let nδ be as in (3.8). Then
(3.10)‖xnδ-x̂‖=O(ψ-1(δ)).


## 3.2. An Adaptive Choice of the Parameter

In this subsection, we will present a parameter choice rule based on the adaptive method studied in [3, 9]. Let(3.11)DM(α)∶={αi=μiα0,i=0,1,…,M},
where μ>1, α0>0, and let(3.12)ni:=min⁡{n:q2n≤δαi}.
Then for i=0,1,…,M, we have(3.13)‖xni-xαiδ‖≤δαi,∀i=0,1,…,M.Letxi:=xni,αiδ. In this paper, we select α=αi from DM(α) for computing xi for each i=0,1,…,M.Theorem 3.8 (cf. [9], Theorem 4.3).
Assume that there existsi∈{0,1,2,…,M} such that φ(αi)≤δ/αi. Let assumptions of Theorems 3.6 and 3.7 hold and let
(3.14)l∶=max⁡{i:φ(αi)≤δαi}<M,k∶=max⁡{i:‖xi-xj‖≤4C¯δαj,j=0,1,2,…,i-1}.
Then l≤k and
(3.15)‖x̂-xk‖≤cψ-1(δ),
where c=6C¯μ.


## 4. Implementation of Adaptive Choice Rule

Following steps are involved in implementing the adaptive choice rule.(i)
Chooseα0>0 such that δ0<3α0/4k0 and μ>1.(ii)
Chooseαi:=μiα0,i=0,1,2,….Finally the adaptive algorithm associated with the choice of the parameter specified in Theorem3.8 involves the following steps.


### 4.1. Algorithm

Step 1.
Seti=0.Step 2.
Chooseni=min{n:q2n≤δ/αi}.Step 3.
Solvexi:=xni,αiδ by using the iteration (1.5) and (1.6).Step 4.
If∥xi-xj∥>4c¯δαj,j<i, then take k=i-1 and return xk.Step 5.
Else seti=i+1 and go to Step 2.


## 4.1. Algorithm

Step 1.
Seti=0.Step 2.
Chooseni=min{n:q2n≤δ/αi}.Step 3.
Solvexi:=xni,αiδ by using the iteration (1.5) and (1.6).Step 4.
If∥xi-xj∥>4c¯δαj,j<i, then take k=i-1 and return xk.Step 5.
Else seti=i+1 and go to Step 2.


## 5. Numerical Example

In this section, we consider the example considered in [4] for illustrating the algorithm considered in Section 4.1. We apply the algorithm by choosing a sequence of finite dimensional subspace (Vn) of X with dimVn=n+1. Precisely we choose Vn as the linear span of {v1,v2,…,vn+1}, where vi,i=1,2,…,n+1 are the linear splines in a uniform grid of n+1 points in [0,1].Example 5.1 (see, [4], Section 4.3).
LetF:D(F)⊆L2(0,1)→L2(0,1) defined by
(5.1)F(u)∶=∫01k(t,s)u3(s)ds,
where
(5.2)k(t,s)={(1-t)s,0≤s≤t≤1,(1-s)t,0≤t≤s≤1.
Then for all x(t),y(t):x(t)>y(t),
(5.3)〈F(x)-F(y),x-y〉=∫01[∫01k(t,s)(x3-y3)(s)ds](x-y)(t)dt≥0.
Thus the operatorF is monotone. The Fréchet derivative of F is given by
(5.4)F′(u)w=3∫01k(t,s)(u(s))2w(s)ds.
Note that foru,v>0,
(5.5)(F′(v)-F′(u))w=(3∫01k(t,s)(u(s))2ds)×[∫01k(t,s)((v(s))2-(u(s))2)w(s)ds∫01k(t,s)(u(s))2ds]∶=F′(u)Φ(v,u,w),
where Φ(v,u,w)=(∫01k(t,s)((v(s))2-(u(s))2)w(s)ds)/(∫01k(t,s)(u(s))2ds).
Observe that(5.6)Φ(v,u,w)=∫01k(t,s)((v(s))2-(u(s))2)w(s)ds∫01k(t,s)(u(s))2ds=∫01k(t,s)(u(s)+v(s))(v(s)-u(s))w(s)ds∫01k(t,s)(u(s))2ds.
So Assumption 2.2 satisfies with k0≥∥(∫01k(t,s)(u(s)+v(s))ds)/(∫01k(t,s)(u(s))2ds)∥.
In our computation, we takey(t)=(t-t11)/110 and yδ=y+δvn+1. Then the exact solutions
(5.7)x̂(t)=t3.
We use
(5.8)x0(t)=t3+356(t-t8)
as our initial guess, so that the function x0-x̂ satisfies the source condition:
(5.9)x0-x̂=φ(F′(x̂))1,
where φ(λ)=λ. Thus we expect to obtain the rate of convergence O(δ1/2).
Observe that while performing numerical computation on finite dimensional subspace(Vn) of X, one has to consider the operator PnF′(x0)Pn instead of F′(x0), where Pn is the orthogonal projection on to Vn. Thus incurs an additional error ∥PnF′(x0)Pn-F′(x0)∥=O(∥F′(x0)(I-Pn)∥).
Let∥F′(x0)(I-Pn)∥≤ɛn. For the operator F′(x0) defined in (5.4), ɛn=O(n-2) (cf. [15]). Thus we expect to obtain the rate of convergence O((δ+ɛn)1/2).
We chooseα0=(1.5)δ, μ=1.5 and q=0.51. The results of the computation (four decimal places) are presented in Table 1. The plots of the exact solution and the approximate solution obtained are given in Figures 1 and 2.Table 1nknkδ+ɛnαk∥xk-x̂∥∥xk-x̂∥/(δ+ɛn)1/28230.10160.34280.26340.826616230.10040.33880.19620.619132230.10010.33780.14290.451864230.10000.33760.10360.3275128230.10000.33750.07550.2387256230.10000.33750.05600.1772512230.10000.33750.04300.13601024230.10000.33750.03470.1096Curves of the exact and approximate solutions.
(a)(b)(c)(d)Curves of the exact and approximate solutions.
(a)(b)(c)(d)The last column of Table1 shows that the error ∥xk-x̂∥ is of O((δ+ɛn)1/2).


## 6. Conclusion

We considered a two step method for obtaining an approximate solution for a nonlinear ill-posed operator equationF(x)=f where F:D(F)⊆X→X is a monotone operator defined on a real Hilbert space X when the available data is fδ with ∥f-fδ∥≤δ. The proposed method converges to a solution of the normal equation F(x)+α(x-x0)=fδ and hence is an approximation for the solution x̂, for properly chosen parameter α. We obtained optimal order error estimate by choosing the regularization parameter α according to the adaptive method considered by Pereverzev and Schock [3]. The computational results provided endorse the reliability and effectiveness of our method.



---

*Source: 728627-2012-04-04.xml*