The implicit midpoint rule for nonexpansive mappings

Abstract

The implicit midpoint rule (IMR) for nonexpansive mappings is established. The IMR generates a sequence by an implicit algorithm. Weak convergence of this algorithm is proved in a Hilbert space. Applications to the periodic solution of a nonlinear time-dependent evolution equation and to a Fredholm integral equation are included.

MSC:47J25, 47N20, 34G20, 65J15.

1 Introduction

The implicit midpoint rule (IMR) is one of the powerful numerical methods for solving ordinary differential equations (in particular, the stiff equations) [1–6] and differential-algebra equations [7].

For the ordinary differential equation

$$y^{\prime }=f(y),y(0)=y_0,$$

(1.1)

IMR generates a sequence $\{y_n\}$ by the recursion procedure

$$y_{n+1}=y_n+hf\left(\frac{y_n+y_{n+1}}{2}\right),n\ge 0,$$

(1.2)

where $h>0$ is a stepsize. It is known that if $f:{\mathbb{R}}^k\to {\mathbb{R}}^k$ is Lipschitz continuous and sufficiently smooth, then the sequence $\{y_n\}$ converges to the exact solution of (1.1) as $h\to 0$ uniformly over $t\in [0,\overline{t}]$ for any fixed $\overline{t}>0$.

If we write the function f in the form $f(y)=y-g(y)$, then differential equation (1.1) becomes

$$y^{\prime }=y-g(y),y(0)=y_0,$$

(1.3)

and the process (1.2) is rewritten as

$$y_{n+1}=y_n+h[\frac{y_n+y_{n+1}}{2}-g\left(\frac{y_n+y_{n+1}}{2}\right)],n\ge 0.$$

(1.4)

The equilibrium problem associated with differential equation (1.3) is the fixed point problem

$$y=g(y).$$

(1.5)

This motivates us to transplant IMR (1.4) to the solving of the fixed point equation

$$x=Tx,$$

(1.6)

where T is, in general, a nonlinear operator in a Hilbert space. We below introduce our implicit midpoint rule (IMR) for the fixed point problem (1.6) in two iterative algorithms. The first algorithm generates a sequence $\{x_n\}$ in the following manner.

Algorithm I Initialize $x_0\in H$ arbitrarily and iterate

$$x_{n+1}=x_n-t_n[\frac{x_n+x_{n+1}}{2}-T\left(\frac{x_n+x_{n+1}}{2}\right)],n\ge 0,$$

(1.7)

where $t_n\in (0,1)$ for all n.

Our second IMR is an algorithm that generates a sequence $\{x_n\}$ as follows.

Algorithm II Initialize $x_0\in H$ arbitrarily and iterate

$$x_{n+1}:=(1-t_n)x_n+t_{n}T\left(\frac{x_n+x_{n+1}}{2}\right),n\ge 0,$$

(1.8)

where $t_n\in (0,1)$ for all n.

We observe that Algorithm I is equivalent to Algorithm II since it is easy to rewrite (1.7), by partially solving for $x_{n+1}$, as

$$x_{n+1}=(1-s_n)x_n+s_{n}T\left(\frac{x_n+x_{n+1}}{2}\right),$$

(1.9)

where

$$s_n=\frac{2t_n}{2+t_n}.$$

(1.10)

Consequently, we may concentrate on Algorithm II.

The purpose of this paper is to study the convergence of two IMR (1.7) and (1.8) in the case where the mapping T is a nonexpansive mapping in a general Hilbert space H, that is,

$$\parallel Tx-Ty\parallel \le \parallel x-y\parallel ,x,y\in H.$$

(1.11)

The iterative methods for finding fixed points of nonexpansive mappings have received much attention due to the fact that in many practical problems, the governing operators are nonexpansive (cf. [8, 9]). Two iterative methods are basic and they are Mann’s method [10, 11] and Halpern’s method [12–16]. An implicit method is also proposed in [17].

2 Convergence analysis

Throughout this section we always assume that H is a Hilbert space with the inner product $〈\cdot ,\cdot 〉$ and the norm $\parallel \cdot \parallel$ and that $T:H\to H$ is a nonexpansive mapping with a fixed point. We use $Fix(T)$ to denote the set of fixed points of T. Namely, $Fix(T)=\{x\in H:Tx=x\}$. It is not hard to find that both IMR (1.7) and (1.8) are well defined. As a matter of fact, for each fixed $u\in H$ and $t\in (0,1)$, the mapping

$$x\mapsto T_{u}x:=u-t[\frac{u+x}{2}-T\left(\frac{u+x}{2}\right)]$$

(2.1)

is a contraction with coefficient $\frac{1+t}{2}\in (0,1)$. That is,

$$\parallel T_{u}x-T_{u}y\parallel \le \frac{1+t}{2}\parallel x-y\parallel ,x,y\in H.$$

(2.2)

This is immediately clear due to the nonexpansivity of T.

It is also easily seen that the mapping

$$x\mapsto T^{u}x:=(1-t)u+tT\left(\frac{u+x}{2}\right)$$

(2.3)

is a contraction with coefficient $t/2$.

2.1 Properties of Algorithm II

We first discuss the properties of Algorithm II.

Lemma 2.1 Let $\{x_n\}$ be the sequence generated by Algorithm II. Then

• (i) $\parallel x_{n+1}-p\parallel \le \parallel x_n-p\parallel$ for all $n\ge 0$ and $p\in Fix(T)$.

• (ii) ${\sum }_{n=1}^{\mathrm{\infty }}{t}_n{\parallel x_n-x_{n+1}\parallel }^2<\mathrm{\infty }$.

• (iii) ${\sum }_{n=1}^{\mathrm{\infty }}{t}_n(1-t_n){\parallel x_n-T(\frac{x_n+x_{n+1}}{2})\parallel }^2<\mathrm{\infty }$.

Proof Let $p\in Fix(T)$. We deduce that

$$\begin{array}{rcl}{\parallel x_{n+1}-p\parallel }^2& =& {\parallel (1-t_n)(x_n-p)+t_n[T\left(\frac{x_n+x_{n+1}}{2}\right)-p]\parallel }^2\\ =& (1-t_n){\parallel x_n-p\parallel }^2+t_n{\parallel T\left(\frac{x_n+x_{n+1}}{2}\right)-p\parallel }^2\\ -t_n(1-t_n){\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel }^2\\ \le & (1-t_n){\parallel x_n-p\parallel }^2+t_n{\parallel \frac{x_n+x_{n+1}}{2}-p\parallel }^2-t_n(1-t_n){\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel }^2\\ =& (1-t_n){\parallel x_n-p\parallel }^2\\ +t_n(\frac{1}{2}{\parallel x_n-p\parallel }^2+\frac{1}{2}{\parallel x_{n+1}-p\parallel }^2-\frac{1}{4}{\parallel x_n-x_{n+1}\parallel }^2)\\ -t_n(1-t_n){\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel }^2.\end{array}$$

It turns out that

$$\begin{array}{rcl}(1-\frac{t_n}{2}){\parallel x_{n+1}-p\parallel }^2& \le & (1-\frac{t_n}{2}){\parallel x_n-p\parallel }^2-\frac{t_n}{4}{\parallel x_n-x_{n+1}\parallel }^2\\ -t_n(1-t_n){\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel }^2\end{array}$$

and

$$\begin{array}{rcl}{\parallel x_{n+1}-p\parallel }^2& \le & {\parallel x_n-p\parallel }^2-\frac{t_n}{2(2-t_n)}{\parallel x_n-x_{n+1}\parallel }^2\\ -\frac{2t_n(1-t_n)}{2-t_n}{\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel }^2.\end{array}$$

(2.4)

It is then immediately evident that

$$\parallel x_{n+1}-p\parallel \le \parallel x_n-p\parallel ,n\ge 0.$$

(2.5)

Moreover, since $t_n\in (0,1)$, (2.4) also implies that

$$\sum _{n=1}^{\mathrm{\infty }}{t}_n{\parallel x_n-x_{n+1}\parallel }^2<\mathrm{\infty }$$

(2.6)

and

$$\sum _{n=1}^{\mathrm{\infty }}{t}_n(1-t_n){\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel }^2<\mathrm{\infty }.$$

(2.7)

The proof of the lemma is complete. □

Lemma 2.2 Let $\{x_n\}$ be the sequence generated by Algorithm II. Suppose that $t_{n+1}^2\le a{t}_n$ for all $n\ge 0$ and some $a>0$. Then

$$\underset{n\to \mathrm{\infty }}{lim}\parallel x_{n+1}-x_n\parallel =0.$$

(2.8)

Proof By definition (1.8) of Algorithm II, we derive that

$$\begin{array}{rcl}\parallel x_{n+2}-x_{n+1}\parallel & =& t_{n+1}\parallel x_{n+1}-T\left(\frac{x_{n+1}+x_{n+2}}{2}\right)\parallel \\ \le & t_{n+1}\parallel x_{n+1}-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel \\ +t_{n+1}\parallel T\left(\frac{x_n+x_{n+1}}{2}\right)-T\left(\frac{x_{n+1}+x_{n+2}}{2}\right)\parallel \\ \le & t_{n+1}(1-t_n)\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel \\ +t_{n+1}\parallel \frac{x_n+x_{n+1}}{2}-\frac{x_{n+1}+x_{n+2}}{2}\parallel \\ \le & t_{n+1}(1-t_n)\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel \\ +t_{n+1}(\frac{1}{2}\parallel x_{n+1}-x_n\parallel +\frac{1}{2}\parallel x_{n+2}-x_{n+1}\parallel ).\end{array}$$

Hence

$$\begin{array}{rcl}\parallel x_{n+2}-x_{n+1}\parallel & \le & \frac{t_{n+1}}{2-t_{n+1}}\parallel x_{n+1}-x_n\parallel +\frac{2t_{n+1}(1-t_n)}{2-t_{n+1}}\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel \\ \le & t_{n+1}\parallel x_{n+1}-x_n\parallel +2t_{n+1}(1-t_n)\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel .\end{array}$$

Using the assumption that $t_{n+1}^2\le a{t}_n$, we further derive that

$$\begin{array}{rcl}{\parallel x_{n+2}-x_{n+1}\parallel }^2& \le & 2t_{n+1}^2{\parallel x_{n+1}-x_n\parallel }^2+4t_{n+1}^2{(1-t_n)}^2{\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel }^2\\ \le & 2a{t}_n{\parallel x_{n+1}-x_n\parallel }^2+4a{t}_n(1-t_n){\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel }^2.\end{array}$$

Now (2.6) and (2.7) imply that

$$\sum _{n=1}^{\mathrm{\infty }}{\parallel x_{n+2}-x_{n+1}\parallel }^2<\mathrm{\infty }.$$

This in turn implies (2.8). □

2.2 Convergence of Algorithms I and II

As Algorithm I is a variant of Algorithm II, we focus on the convergence of Algorithm II. To this end, we need two conditions for the sequence of parameters $\{t_n\}$ as follows:

(C1) $t_{n+1}^2\le a{t}_n$ for all $n\ge 0$ and some $a>0$,

(C2) ${lim\hspace{0.17em}inf}_{n\to \mathrm{\infty }}{t}_n>0$.

These two conditions are not restrictive. As a matter of fact, it is not hard to find that, for each $p>0$, the sequence

$$t_n=1-\frac{1}{{(n+2)}^p},n\ge 0,$$

satisfies (C1) and (C2).

Lemma 2.3 Assume (C1) and (C2). Then the sequence $\{x_n\}$ generated by Algorithm II satisfies the property

$$\underset{n\to \mathrm{\infty }}{lim}\parallel x_n-T{x}_n\parallel =0.$$

(2.9)

Proof From (1.8) it follows that

$$\parallel x_{n+1}-x_n\parallel =t_n\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel .$$

(2.10)

Now condition (C2) implies that $t_n\ge \overline{t}>0$ for all large enough n. Hence from Lemma 2.2, we immediately get

$$\underset{n\to \mathrm{\infty }}{lim}\parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel =0.$$

(2.11)

Conclusion (2.9) now follows from the following inference:

$$\begin{array}{rcl}\parallel x_n-T{x}_n\parallel & \le & \parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel +\parallel T{x}_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel \\ \le & \parallel x_n-T\left(\frac{x_n+x_{n+1}}{2}\right)\parallel +\frac{1}{2}\parallel x_n-x_{n+1}\parallel \to 0.\end{array}$$

 □

To prove the convergence of Algorithm II, we need the following so-called demiclosedness principle for nonexpansive mappings.

Lemma 2.4 ([18])

Let C be a nonempty closed convex subset of a Hilbert space H, and let $V:C\to H$ be a nonexpansive mapping with a fixed point. Assume that $\{x_n\}$ is a sequence in C such that $x_n\to x$ weakly and $(I-V)x_n\to 0$ strongly. Then $(I-T)x=0$ (i.e., $Tx=x$).

We use the notation ${\omega }_w(x_n)$ to denote the set of all weak cluster points of the sequence $\{x_n\}$.

The following result is easily proved (see [19]).

Lemma 2.5 Let K be a nonempty closed convex subset of a Hilbert space H, and let $\{x_n\}$ be a bounded sequence in H. Assume that

• (i) ${lim}_{n\to \mathrm{\infty }}\parallel x_n-p\parallel$ exists for all $p\in K$,

• (ii) ${\omega }_w(x_n)\subset K$.

Then $\{x_n\}$ weakly converges to a point in K.

We are now in a position to state and prove the main convergence result of this paper.

Theorem 2.6 Let H be a Hilbert space and $T:H\to H$ be a nonexpansive mapping with $Fix(T)\ne \mathrm{\varnothing }$. Assume that $\{x_n\}$ is generated by IMR (1.8) where the sequence $\{t_n\}$ of parameters satisfies conditions (C1) and (C2). Then $\{x_n\}$ converges weakly to a fixed point of T.

Proof By Lemmas 2.3 and 2.4, we have ${\omega }_w(x_n)\subset Fix(T)$. Furthermore, by Lemma 2.1, ${lim}_{n\to \mathrm{\infty }}\parallel x_n-p\parallel$ exists for all $p\in Fix(T)$. Consequently, we can apply Lemma 2.5 with $K=Fix(T)$ to assert the weak convergence of $\{x_n\}$ to a point in $Fix(T)$. □

We then have the following convergence result for IMR (1.7).

Theorem 2.7 Let H be a Hilbert space and $T:H\to H$ be a nonexpansive mapping with $Fix(T)\ne \mathrm{\varnothing }$. Assume that $\{x_n\}$ is generated by IMR (1.7) where the sequence $\{t_n\}$ of parameters satisfies conditions (C1) and (C2). Then $\{x_n\}$ converges weakly to a fixed point of T.

Proof Since $\{x_n\}$ is also generated by algorithm (1.9), it suffices to verify that the sequence $\{s_n\}$ defined in (1.10) satisfies conditions (C1) and (C2). As $0\le t_n\le 1$ and satisfies (C2), it is evident that $\{s_n\}$ satisfies (C2) as well. To see that $\{s_n\}$ also fulfils (C1), we argue as follows, using the fact that $\{t_n\}$ satisfies (C1):

$$s_{n+1}^2=\frac{4t_{n+1}^2}{{(2+t_{n+1})}^2}\le t_{n+1}^2\le a{t}_n=a{s}_n(2+t_n)\le 3a{s}_n.$$

 □

3 Applications

3.1 Periodic solution of a nonlinear evolution equation

Consider the time-dependent nonlinear evolution equation in a (possibly complex) Hilbert space H,

$$\frac{du}{dt}+A(t)u=f(t,u),t>0,$$

(3.1)

where $A(t)$ is a family of closed linear operators in H and $f:\mathbb{R}\times H\to H$.

Browder [20] proved the following existence of periodic solutions of equation (3.1).

Theorem 3.1 ([20])

Suppose that $A(t)$ and $f(t,u)$ are periodic in t of period $\xi >0$ and satisfy the following assumptions:

• (i) For each t and each pair $u,v\in H$,

  $$Re〈f(t,u)-f(t,v),u-v〉\le 0.$$

• (ii) For each t and each $u\in D(A(t))$, $Re〈A(t)u,u〉\ge 0$.

• (iii) There exists a mild solution u of equation (3.1) on ${\mathbb{R}}^{+}$ for each initial value $v\in H$. Recall that u is a mild solution of (3.1) with the initial value $u(0)=v$ if, for each $t>0$,

  $$u(t)=U(t,0)v+{\int }_0^{t}U(t,s)f(s,u(s))ds,$$

where ${\{U(t,s)\}}_{t\ge s\ge 0}$ is the evolution system for the homogeneous linear system

$$\frac{du}{dt}+A(t)u=0(t>s).$$

(3.2)

• (iv) There exists some $R>0$ such that

  $$Re〈f(t,u),u〉<0$$

for $\parallel u\parallel =R$ and all $t\in [0,\xi ]$.

Then there exists an element v of H with $\parallel v\parallel <R$ such that the mild solution of equation (3.1) with the initial condition $u(0)=v$ is periodic of period ξ.

We next apply our IMR for nonexpansive mappings to provide an iterative method for finding a periodic solution of (3.1).

As a matter of fact, define a mapping $T:H\to H$ by assigning to each $v\in H$ the value $u(\xi )$, where u is the solution of (3.1) satisfying the initial condition $u(0)=v$. Namely, we define T by

$$Tv=u(\xi ),\text{where }u\text{ solves }(\text{3.1})\text{ with }u(0)=v.$$

We then find that T is nonexpansive. Moreover, assumption (iv) forces T to map the closed ball $B:=\{v\in H:\parallel v\parallel \le R\}$ into itself. Consequently, T has a fixed point which we denote by v, and the corresponding solution u of (3.1) with the initial condition $u(0)=v$ is a desired periodic solution of (3.1) with period ξ. In other words, to find a periodic solution u of (3.1) is equivalent to finding a fixed point of T. Our IMR is thus applicable to (3.1). It turns out that the sequence $\{v_n\}$ defined by the IMR

$$v_{n+1}=(1-t_n)v_n+t_{n}T\left(\frac{v_n+v_{n+1}}{2}\right)$$

(3.3)

converges weakly to a fixed point v of T, and the mild solution of (3.1) with the initial value $u(0)=\xi$ is a periodic solution of (3.1). Note that the iteration method (3.3) is essentially to find a mild solution of (3.1) with the initial value of $(v_n+v_{n+1})/2$.

3.2 Fredholm integral equation

Consider a Fredholm integral equation of the form

$$x(t)=g(t)+{\int }_0^{1}F(t,s,x(s))ds,t\in [0,1],$$

(3.4)

where g is a continuous function on $[0,1]$ and $F:[0,1]\times [0,1]\times \mathbb{R}\to \mathbb{R}$ is continuous. The existence of solutions has been investigated in the literature (see [21] and the references therein). In particular, if F satisfies the Lipschitz continuity condition

$$|F(t,s,x)-F(t,s,y)|\le |x-y|,t,s\in [0,1],x,y\in \mathbb{R},$$

(3.5)

then equation (3.6) has at least one solution in $L^2[0,1]$ ([[21], Theorem 3.3]). Define a mapping $T:L^2[0,1]\to L^2[0,1]$ by

$$(Tx)(t)=g(t)+{\int }_0^{1}F(t,s,x(s))ds,t\in [0,1].$$

(3.6)

It is easily seen that T is nonexpansive. As a matter of fact, we have, for $x,y\in L^2[0,1]$,

$$\begin{array}{rl}{\parallel Tx-Ty\parallel }^2& ={\int }_0^1{|Tx(t)-Ty(t)|}^{2}dt\\ ={\int }_0^1|{\int }_0^1(F(t,s,x(s))-F(t,s,y(s)))ds{|}^{2}dt\\ \le {\int }_0^1|{\int }_0^1|x(s)-y(s)|ds{|}^{2}dt\\ \le {\int }_0^1{|x(s)-y(s)|}^{2}ds={\parallel x-y\parallel }^2.\end{array}$$

This means that to find the solution of integral equation (3.6) is reduced to finding a fixed point of the nonexpansive mapping T in the Hilbert space $L^2[0,1]$. Hence our IMR is again applicable. Initiating with any function $x_0\in L^2[0,1]$, we define a sequence of functions $\{x_n\}$ in $L^2[0,1]$ by

$$x_{n+1}=(1-t_n)x_n+t_{n}T\left(\frac{x_n+x_{n+1}}{2}\right).$$

(3.7)

Then the sequence $\{x_n\}$ converges weakly in $L^2[0,1]$ to the solution of integral equation (3.6).