1 Problem setting: fixed points of mappings
1.1 Fixed point formulation \(x=T(x)\)
A fixed point of a mapping \(T\) is a point \(x\) such that applying the mapping does not change it, i.e., \(x=T(x)\). In nonlinear analysis, fixed-point formulations recast difficult equations into a geometric problem: repeatedly apply \(T\) and hope the iterates settle at a point that remains invariant.
The general question is therefore: given a space \(X\) and a mapping \(T:X\to X\), under what conditions does there exist at least one fixed point, and how can one construct it numerically or analytically?
1.2 Iterative methods and motivation
Directly solving \(x=T(x)\) is often impractical because the mapping may be nonlinear, computationally expensive, or may not have a closed-form inverse. Iterative methods attempt to approximate a solution by generating a sequence \((x_n)\) via a rule that uses current information, typically by evaluating \(T\).
A core motivation behind Krasnosel’skiĭ–Mann iteration is to handle operator classes for which straightforward iteration \(x_{n+1}=T(x_n)\) may fail to converge, even when fixed points exist. The method introduces relaxation to stabilize the process.
1.3 Function spaces and norms/metrics
| The iteration is studied in metric spaces and, more commonly, in normed linear spaces such as Banach spaces and Hilbert spaces. Convergence may be formulated in terms of the metric \(d(\cdot,\cdot)\) or the norm \(\|\cdot\|\). Many results rely on convexity and geometric properties typical of normed spaces, especially for Hilbert spaces where inner products provide additional tools. |
|---|
When \(X\) is convex and complete, and when \(T\) maps \(X\) into itself, the framework supports both existence and convergence analyses.
2 Krasnosel’skiĭ–Mann iteration scheme
2.1 Definition of the iteration
2.1.1 Averaged/relaxed update with parameters \(\alpha_n\)
Krasnosel’skiĭ–Mann iteration constructs a sequence \((x_n)\) from an initial point \(x_0\) by combining the current iterate with its image under \(T\). In a common form, \[ x_{n+1}=(1-\alpha_n)x_n+\alpha_n T(x_n), \] where \((\alpha_n)\) is a relaxation parameter sequence. Equivalently, the update can be written using the “residual” \(T(x_n)-x_n\): \[ x_{n+1}=x_n+\alpha_n\bigl(T(x_n)-x_n\bigr). \] The choice of \(\alpha_n\) controls how aggressively the method moves toward \(T(x_n)\). This averaged step is central to obtaining convergence under broad assumptions.
2.1.2 Notation: iterates, starting point, and mapping classes
Typically, one assumes:
- \(X\) is a metric space or a convex subset of a Banach/Hilbert space,
- \(T:X\to X\) belongs to a class of mappings with fixed points (e.g., nonexpansive, firmly nonexpansive, or averaged operators),
- a starting point \(x_0\in X\) is chosen,
- \((\alpha_n)\subset[0,1]\) satisfies admissibility conditions suited to the operator class.
Under these hypotheses, the iteration aims to produce a sequence whose limit (or weak limit) is a fixed point.
2.2 Choice of relaxation parameters
2.2.1 Common admissibility conditions
A typical admissibility template requires that \(\alpha_n\) is bounded away from the extremes and that its “activation” persists over time. Common conditions include:
- \(\alpha_n\in(0,1)\) for all \(n\),
- \(\inf_n \alpha_n>0\) and \(\sup_n \alpha_n<1\) in many classical settings,
- or weaker summability/divergence relations such as \(\sum_n \alpha_n(1-\alpha_n)=\infty\) paired with control of error terms in approximate schemes.
The exact assumptions depend on the operator geometry. For instance, nonexpansive mappings may require conditions ensuring that the iteration does not stall (by taking \(\alpha_n\) too close to 0) or oscillate (by taking \(\alpha_n\) too close to 1) in problematic cases.
2.2.2 Effects of constant vs. varying \(\alpha_n\)
If \(\alpha_n\equiv \alpha\) is constant, the scheme behaves like an iteration with a fixed averaged operator. Under appropriate conditions, constant relaxation can yield convergence and may simplify the analysis. In other cases, particularly where stability is delicate, varying \(\alpha_n\) can improve robustness by gradually adjusting step sizes.
Varying parameters can also influence the speed at which residuals \(T(x_n)-x_n\) decrease. Even when convergence is guaranteed, practical performance can change significantly with the schedule.
2.3 Related formulations and special cases
2.3.1 Picard iteration as a limiting case
Picard iteration is the simplest fixed-point scheme: \[ x_{n+1}=T(x_n). \] This corresponds to the limiting choice \(\alpha_n=1\) in the relaxed update. For many nonlinear problems, Picard iteration may not converge unless \(T\) is a contraction or otherwise sufficiently stable.
Krasnosel’skiĭ–Mann iteration can be viewed as a relaxation/generalization of Picard iteration that remains effective for broader operator classes (notably nonexpansive mappings).
2.3.2 Mann iteration vs. Krasnosel’skiĭ variant
Mann iteration is often written in the same relaxed form as above, with parameter choices \(\alpha_n\) guided by convergence theory. In many texts, Krasnosel’skiĭ–Mann refers to the general averaged-relaxation framework for nonexpansive operator classes, emphasizing the convex combination structure and the associated Fejér-type arguments.
Differences between the “Mann” and “Krasnosel’skiĭ” labels can reflect historical conventions or particular parameter regimes, but mathematically the core idea is the same: averaging the current point with its image under \(T\) to control iterative behavior.
3 Convergence theory
3.1 Operator assumptions
3.1.1 Nonexpansive mappings
A mapping \(T\) is nonexpansive if it does not increase distances: \[
| \|T(x)-T(y)\|\le \|x-y\| |
|---|
\] (or the corresponding condition in metric spaces). Nonexpansiveness alone does not guarantee that iterating \(T\) converges. However, it supports the use of relaxed/averaged iterations, which can enforce a kind of monotonic decrease of distances to the fixed point set.
In this setting, one assumes fixed points exist, and the analysis focuses on how the iteration behaves relative to them.
3.1.2 Firmly nonexpansive and averaged operators
A stronger class is provided by firmly nonexpansive mappings, which satisfy inequalities stronger than nonexpansiveness. For such \(T\), one can often prove that certain energy functionals decrease more directly, yielding convergence and sometimes stronger forms of stability.
Another key operator class is that of averaged mappings: \(T\) is averaged if it can be expressed as \[ T=(1-\theta)I+\theta S \] for some \(\theta\in(0,1)\) and nonexpansive \(S\). Averaged operators naturally align with the Krasnosel’skiĭ–Mann structure, making the analysis particularly effective.
3.2 Basic convergence mechanisms
3.2.1 Fejér monotonicity ideas
A common convergence mechanism is Fejér monotonicity relative to the fixed point set \( \operatorname{Fix}(T)\). Informally, the iteration produces terms that do not move farther away from any fixed point, at least in an inequality sense, often resembling \[
| \|x_{n+1}-p\|\le \|x_n-p\| \quad \text{for all } p\in\operatorname{Fix}(T), |
|---|
\] or with additional error terms. While strict monotonicity may fail in general, “quasi-monotone” behavior combined with boundedness allows extraction of weakly convergent subsequences.
3.2.2 Asymptotic regularity
Asymptotic regularity means that the successive iterates become nearly stationary under the mapping, typically expressed as \[
| \|x_{n+1}-x_n\|\to 0 |
|---|
\quad\text{and/or}\quad
| \|T(x_n)-x_n\|\to 0. |
|---|
\] In Krasnosel’skiĭ–Mann iteration, asymptotic regularity is often derived from Fejér-type inequalities plus the parameter conditions. Together with demiclosedness arguments, this turns small residuals into convergence to an actual fixed point.
3.3 Types of convergence
3.3.1 Strong vs. weak convergence (Banach/Hilbert context)
In finite-dimensional spaces, many bounded sequences have convergent subsequences, and strong convergence can often be shown under relatively mild conditions. In infinite-dimensional Hilbert or Banach spaces, the best general statements frequently involve weak convergence: \[ x_n \rightharpoonup x^\ast. \] Strong convergence may require extra assumptions such as uniform convexity properties, additional regularity of \(T\), or compactness-type conditions.
Weak convergence is particularly common in nonexpansive fixed-point theory because it aligns with how demiclosedness and boundedness arguments work.
3.3.2 Rate notions and practical interpretation
Unlike contraction methods, nonexpansive fixed-point iterations generally do not yield uniform exponential-type rates. Nevertheless, one can discuss:
- sublinear rate bounds for certain averaged quantities,
| - rates for residual norms \(\|T(x_n)-x_n\|\) under additional structure, |
|---|
- practical indicators based on empirical decay of residuals.
In computation, the focus is often on residual-based stopping criteria, since the true fixed point is unknown.
3.4 Fixed point existence and demiclosedness tools
3.4.1 Demiclosedness principles
Demiclosedness is a technical property connecting approximate fixed point behavior to genuine fixed points. Roughly, if \(x_n\) converges weakly to some \(x\) and the residual \(T(x_n)-x_n\) converges strongly to zero, then \(x\) must be a fixed point: \[ x\in\operatorname{Fix}(T). \] This principle is a cornerstone for proving convergence in nonexpansive settings.
3.4.2 Existence conditions and iteration feasibility
Fixed point existence depends on both the mapping class and the geometry of the set. Common assumptions include:
- closed, convex, and bounded subsets of a Banach space where the mapping is nonexpansive,
- compactness or conditions ensuring that approximate fixed points exist,
- in some frameworks, use of fixed point theorems guaranteeing nonempty \(\operatorname{Fix}(T)\).
Feasibility in computation means that all iterates remain in the domain. When \(X\) is convex and \(T\) maps \(X\) into itself, the convex combination in the iteration keeps \(x_{n+1}\in X\).
4 Proof techniques and key lemmas
4.1 Inequalities used in analysis
4.1.1 Norm identities and convexity bounds
Hilbert space proofs typically use the parallelogram law and inner product expansions: \[
| \|a+b\|^2=\|a\|^2+\|b\|^2+2\langle a,b\rangle, |
|---|
\] or inequalities derived from convexity of the norm. In Banach spaces, one uses analogues involving the norm’s geometry and duality.
| For the relaxed update, convex combination structure yields inequalities bounding \(\|x_{n+1}-p\|^2\) in terms of \(\|x_n-p\|^2\) and \(\|T(x_n)-x_n\|^2\). |
|---|
4.1.2 Bounding residuals \(\|x_{n+1}-x_n\|\)
From \[ x_{n+1}-x_n=\alpha_n(T(x_n)-x_n), \] one immediately gets \[
| \|x_{n+1}-x_n\|=\alpha_n\|T(x_n)-x_n\|. |
|---|
\]
| Thus, if \(\alpha_n\) does not vanish and one shows \(\|T(x_n)-x_n\|\to 0\), then the step differences decay as well. Conversely, bounding \(\|x_{n+1}-x_n\|\) can help infer residual decay under suitable parameter control. |
|---|
4.2 Limit arguments
4.2.1 Cluster points and uniqueness of fixed points
Weak convergence proofs often proceed by:
- showing boundedness of \((x_n)\),
- extracting weakly convergent subsequences,
- identifying the weak limit as a fixed point using demiclosedness or similar arguments,
- proving that all cluster points lie in \(\operatorname{Fix}(T)\),
- using additional structure (or Opial-type properties) to show the whole sequence converges.
When the fixed point is unique, the identification of the limit is simpler. Without uniqueness, convergence may still occur to a particular fixed point selected by the iteration.
4.2.2 Extraction of subsequences
Boundedness plus reflexivity (in Banach settings) or the Banach–Alaoglu theorem (in Hilbert spaces) provides weakly convergent subsequences. The residual decay typically implies that every such weak cluster point must satisfy the fixed point property.
This approach isolates the essential role of asymptotic regularity and demiclosedness.
4.3 Energy function viewpoints
4.3.1 Lyapunov/Fejér-type functionals
Many analyses can be expressed in terms of an energy functional measuring distance to the fixed point set. A prototype inequality is \[
| \|x_{n+1}-p\|^2 \le \|x_n-p\|^2 - c\,\|T(x_n)-x_n\|^2 |
|---|
\] for some constant \(c>0\) and for all \(p\in\operatorname{Fix}(T)\), possibly after averaging across parameters. Summing such inequalities yields square-summability of residual-related terms, from which asymptotic regularity follows.
4.3.2 Orthogonality in Hilbert spaces (where applicable)
In Hilbert spaces, firmly nonexpansive operators often allow orthogonality interpretations that sharpen Fejér monotonicity. While exact orthogonality may not hold universally, inner product identities can convert nonexpansiveness conditions into energy descent inequalities.
These tools can strengthen conclusions, including convergence of certain projection-like residuals.
5 Variants and extensions
5.1 Inertial/accelerated versions
5.1.1 Momentum terms and stability considerations
Inertial methods augment the basic iteration with momentum, often taking a form like \[ y_n = x_n + \beta_n(x_n-x_{n-1}),\quad x_{n+1}=(1-\alpha_n)x_n+\alpha_n T(y_n). \] The parameters \(\beta_n\) control the amount of “memory” carried by the method. Acceleration can improve empirical speed, but it complicates convergence because momentum can destabilize the iteration if chosen too aggressively.
Analyses therefore impose constraints on \(\beta_n\) (e.g., boundedness and relation with \(\alpha_n\)) and frequently require stronger assumptions on \(T\).
5.2 Relaxed vs. over-relaxed schemes
5.2.1 Parameter tuning strategies
Relaxed iterations use \(\alpha_n\in[0,1]\), ensuring a convex combination. Over-relaxation may allow \(\alpha_n\) outside \([0,1]\) in specialized settings where stability remains. In practice, over-relaxation can accelerate movement in problems resembling projection algorithms, but it can also lead to divergence for general nonexpansive mappings.
Parameter tuning typically aims to balance residual reduction with stability, guided by theory when available and by diagnostics (residual norms, objective decrease) in numerical experiments.
5.3 Stochastic and approximate iterations
5.3.1 Errors in applying \(T\)
Many real computations evaluate an approximate operator \(T_\varepsilon\) or introduce numerical error. One studies iterations of the form \[ x_{n+1}=(1-\alpha_n)x_n+\alpha_n \tilde T(x_n), \] where \(\tilde T(x_n)\) differs from \(T(x_n)\). Convergence can persist if errors are summable or sufficiently small compared to the iteration’s natural descent quantities.
5.3.2 Randomized relaxation choices
Randomization can appear through random selection of relaxation parameters or random choice of operator approximations (e.g., stochastic components). Under suitable independence assumptions and moment bounds, one can often establish convergence in expectation and sometimes almost sure convergence. The main difficulty lies in controlling how randomness interacts with the Fejér-type descent mechanism.
6 Computational aspects
6.1 Implementation details
6.1.1 Stopping criteria (residual-based)
Because fixed points are generally unknown, stopping criteria usually rely on residuals, such as \[
| \|T(x_n)-x_n\| \le \text{tol} |
|---|
\quad\text{or}\quad
| \|x_{n+1}-x_n\|\le \text{tol}. |
|---|
\] Residual-based criteria align with asymptotic regularity results: if the residual becomes small, the iterate is close to being a fixed point.
In practice, one selects tolerances based on the expected scale of the problem and the accuracy of operator evaluations.
6.1.2 Handling projection/approximation subroutines
Many applications implement \(T\) via auxiliary steps (e.g., solving subproblems, projecting onto constraint sets, or using iterative solvers internally). If these subroutines introduce errors, one must account for them in the convergence analysis—typically by ensuring that approximation errors diminish appropriately or are controlled by a summability condition.
6.2 Practical performance considerations
6.2.1 Conditioning and operator evaluation cost
The computational bottleneck is often the cost of evaluating \(T(x_n)\). If \(T\) involves expensive inner solves, then the choice of \(\alpha_n\) matters because it changes how many iterations are required. Moreover, ill-conditioning can affect both the residual decay and the stability of the approximate evaluations, making careful parameter selection important.
6.2.2 Empirical behavior of parameter schedules
Constant step sizes may be easy to implement but can be suboptimal. Adaptive or scheduled \(\alpha_n\) can reduce oscillations and improve performance in problems where the effective nonexpansiveness behavior changes across the domain. Empirical studies typically compare residual decay across different schedules and correlate it with theoretical expectations about step sizes.
7 Applications in nonlinear analysis
7.1 Solving operator equations via fixed points
Many nonlinear equations can be rearranged into fixed-point form. When the associated operator belongs to a nonexpansive or averaged class, Krasnosel’skiĭ–Mann iteration offers a systematic way to approximate solutions without requiring contraction properties.
The iteration thus serves as a general-purpose solver for operator equations under relatively mild stability assumptions.
7.2 Convex optimization links (as fixed-point problems)
A common bridge between convex optimization and fixed-point theory uses proximal and resolvent operators. For instance, splitting methods often generate operators that are nonexpansive or averaged, enabling the application of Krasnosel’skiĭ–Mann-type iterations.
In this perspective, fixed-point iterates correspond to successive refinements of primal variables or auxiliary constructs such as dual variables.
7.3 Variational inequalities and equilibrium problems (conceptual connections)
Variational inequalities and equilibrium models can frequently be reformulated using operator inclusions or monotonicity-based mappings. Under suitable regularity, the resulting operator may fall into classes where averaged iteration is justified. While the details depend on the model, the conceptual role is consistent: convert equilibrium conditions into an operator fixed-point problem and iterate with relaxation to ensure convergence.
8 Example walk-throughs (worked iterations)
8.1 Simple nonexpansive map on a Hilbert space
8.1.1 Computing a few iterations by hand
Consider a Hilbert space \(H=\mathbb{R}\) (viewed as a Hilbert space) and a nonexpansive map \(T(x)=\frac{x+1}{2}\). The fixed point solves \(x=\frac{x+1}{2}\), giving \(x^\ast=1\).
Take relaxation parameters \(\alpha_n\equiv \alpha\) and initial point \(x_0=0\). The iteration becomes \[ x_{n+1}=(1-\alpha)x_n+\alpha\frac{x_n+1}{2} = \left(1-\alpha+\frac{\alpha}{2}\right)x_n+\frac{\alpha}{2} = \left(1-\frac{\alpha}{2}\right)x_n+\frac{\alpha}{2}. \] With \(\alpha=\frac12\), we get \(x_{n+1}=\left(1-\frac14\right)x_n+\frac14= \frac34 x_n+\frac14\). Then:
- \(x_1=\frac34\cdot 0+\frac14=\frac14\)
- \(x_2=\frac34\cdot \frac14+\frac14=\frac{3}{16}+\frac{4}{16}=\frac{7}{16}\)
- \(x_3=\frac34\cdot \frac{7}{16}+\frac14=\frac{21}{64}+\frac{16}{64}=\frac{37}{64}\)
These values move toward \(1\), illustrating convergence via relaxation.
8.2 Averaged operator example
8.2.1 Demonstrating contraction-like behavior
Let \(T\) be a nonexpansive map on a Hilbert space that can be expressed as an averaged operator: \[ T=(1-\theta)I+\theta S,\quad S \text{ nonexpansive},\quad \theta\in(0,1). \] Apply Krasnosel’skiĭ–Mann iteration to \(T\) with relaxation parameters \(\alpha_n=\alpha\in(0,1)\). The combined averaging effectively yields a new averaged structure with improved stability. In many cases, one can show that distances to fixed points decrease in an energy sense, resembling contraction behavior without requiring strict contraction of \(T\).
This “contractive-like” effect is a key reason averaged operators work well with the Krasnosel’skiĭ–Mann framework.
8.3 Illustrative parameter choices
8.3.1 Comparing two \(\alpha_n\) schedules on the same example
Using the scalar example \(T(x)=\frac{x+1}{2}\), compare two schedules:
- Constant relaxation: \(\alpha_n=0.5\).
- Decreasing relaxation: \(\alpha_n=\frac{1}{n+1}\) (always in \((0,1)\), but tends to 0).
With constant \(\alpha\), the iteration repeatedly applies a fixed averaged step toward the image \(T(x_n)\), typically producing steady residual decrease. With decreasing \(\alpha_n\), the method may initially move toward the fixed point but then slow down as \(\alpha_n\) becomes small, risking stagnation if \(\alpha_n\) decays too quickly relative to the needs of asymptotic regularity.
The comparison highlights why parameter conditions often include lower bounds or divergence-type requirements rather than allowing \(\alpha_n\to 0\) arbitrarily fast.
9 Further reading and references
9.1 Foundational texts in fixed-point theory
Foundational accounts of fixed-point theory in metric and Banach spaces provide the background for nonexpansive mappings, averaged operators, and fixed-point existence theorems. These texts typically cover the geometric tools used to prove convergence of iterative schemes, including Fejér monotonicity and demiclosedness.
9.2 Survey articles on iteration schemes
Survey literature focused on iteration methods compiles convergence results for Mann, Krasnosel’skiĭ–Mann, and related relaxed schemes, including inertial and stochastic extensions. These references are useful for tracking parameter regimes and for understanding which operator assumptions yield which types of convergence.
9.3 Notes on parameter conditions and convergence refinements
Refinements often concern:
- sharp admissibility conditions on \((\alpha_n)\),
- improved rate statements for averaged quantities,
- stability under inexact evaluations of \(T\),
- additional assumptions that upgrade weak convergence to strong convergence.
Such notes help connect the theoretical iteration rule with practical implementation and tuning.