### Effective Uniform Bounds on the Krasnoselski-Mann Iteration

#### Abstract

This paper is a case study in proof mining applied to non-effective proofs

in nonlinear functional analysis. More specifically, we are concerned with the

fixed point theory of nonexpansive selfmappings f of convex sets C in normed spaces. We study the Krasnoselski iteration as well as more general so-called Krasnoselski-Mann iterations. These iterations converge to fixed points of f only under special compactness conditions and even for uniformly convex

spaces the rate of convergence is in general not computable in f (which is

related to the non-uniqueness of fixed points). However, the iterations yield

approximate fixed points of arbitrary quality for general normed spaces and

bounded C (asymptotic regularity).

In this paper we apply general proof theoretic results obtained in previous

papers to non-effective proofs of this regularity and extract uniform explicit

bounds on the rate of the asymptotic regularity. We start off with the classical

case of uniformly convex spaces treated already by Krasnoselski and show

how a logically motivated modification allows to obtain an improved bound. Already the analysis of the original proof (from 1955) yields an elementary

proof for a result which was obtained only in 1990 with the use of the deep

Browder-G¨ohde-Kirk fixed point theorem. The improved bound from the modified

proof gives applied to various special spaces results which previously had

been obtained only by ad hoc calculations and which in some case are known

to be optimal.

The main section of the paper deals with the general case of arbitrary normed

spaces and yields new results including a quantitative analysis of a theorem

due to Borwein, Reich and Shafrir (1992) on the asymptotic behaviour of

the general Krasnoselski-Mann iteration in arbitrary normed spaces even for unbounded sets C. Besides providing explicit bounds we also get new qualitative results concerning the independence of the rate of convergence of the norm of that iteration from various input data. In the special case of bounded convex sets, where by well-known results of Ishikawa, Edelstein/O'Brian and Goebel/Kirk the norm of the iteration converges to zero, we obtain uniform

bounds which do not depend on the starting point of the iteration and the

nonexpansive function and the normed space X and, in fact, only depend

on the error epsilon, an upper bound on the diameter of C and some very general information on the sequence of scalars k used in the iteration. Even non-effectively only the existence of bounds satisfying weaker uniformity conditions was known before except for the special situation, where lambda_k := lambda is constant. For the unbounded case, no quantitative information was known so far.

in nonlinear functional analysis. More specifically, we are concerned with the

fixed point theory of nonexpansive selfmappings f of convex sets C in normed spaces. We study the Krasnoselski iteration as well as more general so-called Krasnoselski-Mann iterations. These iterations converge to fixed points of f only under special compactness conditions and even for uniformly convex

spaces the rate of convergence is in general not computable in f (which is

related to the non-uniqueness of fixed points). However, the iterations yield

approximate fixed points of arbitrary quality for general normed spaces and

bounded C (asymptotic regularity).

In this paper we apply general proof theoretic results obtained in previous

papers to non-effective proofs of this regularity and extract uniform explicit

bounds on the rate of the asymptotic regularity. We start off with the classical

case of uniformly convex spaces treated already by Krasnoselski and show

how a logically motivated modification allows to obtain an improved bound. Already the analysis of the original proof (from 1955) yields an elementary

proof for a result which was obtained only in 1990 with the use of the deep

Browder-G¨ohde-Kirk fixed point theorem. The improved bound from the modified

proof gives applied to various special spaces results which previously had

been obtained only by ad hoc calculations and which in some case are known

to be optimal.

The main section of the paper deals with the general case of arbitrary normed

spaces and yields new results including a quantitative analysis of a theorem

due to Borwein, Reich and Shafrir (1992) on the asymptotic behaviour of

the general Krasnoselski-Mann iteration in arbitrary normed spaces even for unbounded sets C. Besides providing explicit bounds we also get new qualitative results concerning the independence of the rate of convergence of the norm of that iteration from various input data. In the special case of bounded convex sets, where by well-known results of Ishikawa, Edelstein/O'Brian and Goebel/Kirk the norm of the iteration converges to zero, we obtain uniform

bounds which do not depend on the starting point of the iteration and the

nonexpansive function and the normed space X and, in fact, only depend

on the error epsilon, an upper bound on the diameter of C and some very general information on the sequence of scalars k used in the iteration. Even non-effectively only the existence of bounds satisfying weaker uniformity conditions was known before except for the special situation, where lambda_k := lambda is constant. For the unbounded case, no quantitative information was known so far.

#### Full Text:

PDFDOI: http://dx.doi.org/10.7146/brics.v7i9.20136

ISSN: 0909-0878

Hosted by the State and University Library and Aarhus University Library