Rates of convergence for inexact Krasnosel’skii–Mann iterations in Banach spaces

Abstract

We study the convergence of an inexact version of the classical Krasnosel’skii–Mann iteration for computing fixed points of nonexpansive maps. Our main result establishes a new metric bound for the fixed-point residuals, from which we derive their rate of convergence as well as the convergence of the iterates towards a fixed point. The results are applied to three variants of the basic iteration: infeasible iterations with approximate projections, the Ishikawa iteration, and diagonal Krasnosels’kii–Mann schemes. The results are also extended to continuous time in order to study the asymptotics of nonautonomous evolution equations governed by nonexpansive operators.

Bound for approximate projections

The goal of this Appendix is to establish the next technical Lemma used in the proof of Theorem 5.

Lemma 3

Let $(x_n,z_n)$ be given by (IKM$_z$), and denote $\delta _n=d(x_n,C)+ \gamma _n$ and $\xi _n=\Vert e_n\Vert +\gamma _n/\alpha _n$ with $\delta _0=\xi _0=0$. If $\sum _{k\ge 1}\alpha _k=\infty$ and $\sum _{k\ge 1}\alpha _k\xi _k<\infty$, then $\delta _n\rightarrow 0$ and $\sum _{k\ge 1}\alpha _{k}\delta _{k-1}<\infty$.

Proof

Starting from the identity

$$\begin{aligned} x_{n}=(1-\alpha _{n})z_{n-1}+\alpha _{n}Tz_{n-1}+(1-\alpha _{n})(x_{n-1} -z_{n-1})+\alpha _{n}e_{n} \end{aligned}$$

and since $(1-\alpha _{n})z_{n-1}+\alpha _{n}Tz_{n-1}\in C$, we get

$$\begin{aligned} \text{ dist }(x_{n},C)\le \Vert (1-\alpha _{n})(x_{n-1}-z_{n-1})+\alpha _{n}e_{n}\Vert \le (1-\alpha _{n})\delta _{n-1}+\alpha _{n}\Vert e_{n}\Vert . \end{aligned}$$

It follows that $\delta _{n}\le (1-\alpha _{n})\delta _{n-1}+\alpha _{n}\xi _n$ and letting $\rho _n=\prod _{j=1}^n(1\!-\!\alpha _j)$ with $\rho _0=1$ we get

$$\begin{aligned} \frac{\delta _{n}}{\rho _n}\le \frac{\delta _{n-1}}{\rho _{n-1}}+\frac{\alpha _{n}}{\rho _n}\xi _n. \end{aligned}$$

Iterating this inequality we get $\frac{\delta _{n}}{\rho _n}\le \sum _{i=0}^n\frac{\alpha _{i}}{\rho _i}\xi _i$ which yields $\delta _{n}\le \sum _{i=0}^n\alpha _i\xi _i\,\frac{\rho _n}{\rho _i}.$

This inequality can be written as $\delta _{n}\le \int _{{\mathbb N}}f_n\,d\mu$ with $\mu$ the finite measure on ${\mathbb N}$ defined by $\mu (\{i\})=\alpha _i\xi _i$, and $f_n:{\mathbb N}\rightarrow {\mathbb R}$ given by $f_n(i)=\frac{\rho _n}{\rho _i}$ for $i\le n$ and $f_n(i)=0$ for $i>n$. Since $f_n(i)\rightarrow 0$ as $n\rightarrow \infty$ and $f_n(i)\le 1$, Lebesgue’s dominated convergence theorem implies that $\int _{{\mathbb N}}f_nd\mu$ tends to zero so that $\delta _n\rightarrow 0$.

It remains to show that the sum $S=\sum _{k\ge 1}\alpha _{k}\delta _{k-1}$ is finite. Using the previous bound for $\delta _{k-1}$ and exchanging the order of summation we get

$$\begin{aligned} S\le \sum _{k=1}^\infty \alpha _{k}\sum _{i=0}^{k-1}\alpha _i\xi _i\, \frac{\rho _{k-1}}{\rho _i} =\sum _{i=0}^\infty \alpha _i\xi _i\sum _{k=i+1}^\infty \alpha _{k}\prod _{j=i+1}^{k-1}(1\!-\!\alpha _j). \end{aligned}$$

The term $q_{i+1}^k=\alpha _{k}\prod _{j=i+1}^{k-1}(1\!-\!\alpha _j)$ in this last sum can be interpreted as a probability. Namely, suppose that at every integer j we toss a coin that falls head with probability $\alpha _j$. Then, $q_{i+1}^k$ is the probability that starting at position $i+1$ the first head occurs exactly at position k. Hence $\sum _{k=i+1}^\infty q_{i+1}^k=1$ and therefore $S\le \sum _{i=0}^\infty \alpha _i\xi _i<\infty$. $\square$