Krasnoselskii-Mann Iteration
1 Picard Iterations
Given a mapping \(T:D\to D\) on some space \(D\) (usually a Hilbert space or a Banach space) and a starting point \(x_0\in D\), the Picard iteration is defined as
\[ x_{n+1}=T(x_n). \]
A fixed-point (FP) of a mapping \(T\) is a point \(x\in D\) such that \(T(x)=x\). A map \(T:D\to D\) is called a Picard operator if it has a unique FP \(x^*\) and the Picard iteration converges to \(x^*\) for any starting point \(x_0\in D\).
Denoting metric \(d\) on \(D\), a mapping \(T:D\to D\) is called a contraction mapping if there exists a constant \(0\leq k<1\) such that
\[ d(T(x),T(y))\leq k d(x,y) \quad \forall x,y\in D. \]
If \(0\leq k \leq 1\) the mapping is said to be non-expansive, otherwise it is called expansive. The following theorem gives conditions under which the Picard iteration converges to a unique fixed point of a contraction mapping.
Any map \(T:D\to D\) on a complete metric space \((D,d)\) that is a contraction mapping is a Picard operator
2 Krasnoselskii-Mann (KM) Iterations
If \(T\) is only non-expansive, the Picard iteration can fail to reach a FP even is one exists. The Krasnoselskii-Mann (KM) iteration is a generalization of the Picard iteration that can converge to a FP of a non-expansive mapping.
Let \(T:D\to D\) be a non-expansive mapping on a closed convex subset \(D\neq \emptyset\) of a Hilbert Space \(\mathcal{H}\). Letting \(x_0\in D\) we define the Krasnoselskii-Mann (KM) iterations as
\[ x_{n+1}=G_{KM}(x_n, \lambda_n)=(1-\lambda_n)x_n+\lambda_nTx_n. \]
where \(\lambda_n\in[0,1]\).
This is just a convex combination of the current iterate \(x_n\) and the image of the current iterate under the non-expansive mapping \(T\) with a weight \(\lambda_n\) that can vary with each iteration. The following theorem gives conditions under which the KM iteration converges to a fixed point of \(T\).
If \(\text{Fix}(T)=\emptyset\) and
\[ \sum_{n=0}^{\infty}\lambda_n(1-\lambda_n)=\infty, \]
then the following results hold:
- \(x_n\) is \(F\)-mono with respect to set \(\text{Fix}(T)\).
- \(x_n - T X_n \to 0\) convergence of error to zero is strong.
- \(x_n\stackrel{D}\to \bar{x} \in \text{Fix}(T)\) sequence converges weakly to a point in the fixed point set of \(T\).
When \(D\) is a bounded set, theorem holds after if the existence assumption of the fixed point set is removed because fixed point set of non-expansive operator is convex (see nonexpansive operator in Hilbert Space).
Proof. To prove (1) we take \(y\in\text{Fix}(T)\) by non-empty assumption. Consider
\[ \begin{align*} \lVert x_{n+1}-y\rVert^2 & = \lVert (1-\lambda_n)x_n+\lambda_nTx_n-y\rVert^2 \\ & = \lVert (1-\lambda_n)(x_n-y)+\lambda_n(T x_n-y)\rVert^2 \\ & = (1-\lambda_n)\lVert x_n-y\rVert^2+\lambda_n\lVert Tx_n-y\rVert^2 - \lambda_n(1-\lambda_n)\lVert x_n - Tx_n \rVert^2 \\ & \leq (1-\lambda_n)\lVert x_n - y\rVert^2 + \lambda_n\lVert x_n - y \rVert^2-\lambda_n(1-\lambda_n)\lVert x_n - Tx_n\rVert^2 \\ & = \lVert x_n-y\rVert^2-\lambda_n(1-\lambda_n)\lVert x_n - Tx_n\rVert^2 \\ & \leq \lVert x_n-y\rVert^2, \end{align*} \]
where on line 3 we used an identity for the norm of a convex combination and on line 4 we used the non-expansiveness of \(T\) (see [[norm-spaces]]).
Thus \(x_n\) is \(F\)-monotone with respect to the \(\text{Fix}(T)\). Moreover
\[ \begin{align*} \lambda_n(1-\lambda_n)\lVert x_n - tx_n\rVert^2 & \leq \lVert x_n - y\rVert ^2 - \lVert x_{n+1} - y\rVert^2 \\ \implies \sum_{n=0}^N\lambda_n(1-\lambda_n)\lVert x_n - Tx_n\rVert ^2 & \leq \lVert x_0 - y\rVert ^2 - \lim_{n\to\infty}\lVert x_{n+1} - y\rVert^2 < \infty. \end{align*} \]
Thus \(x_{n+1}-x_n \to \mathbf{0}\), proving (2). To prove (3) we consider
\[ \begin{align*} \lVert x_{n+1} - Tx_{n+1}\rVert & = \lVert (1-\lambda_n) x_n - \lambda_n T(x_n) - T(x_n+1) \rVert \\ & = \lVert (1-\lambda _n)(x_n - T(x_n)) + (T(x_n) - T(x_n+1))\rVert \\ & \leq (1-\lambda_n)\lVert x_n - T(x_n)\rVert + \lVert T(x_n) - T(x_n+1)\rVert \\ & \leq (1-\lambda _n) \lVert x_n - T(x_n)\rVert + \lVert x_n - x_{n+1}\rVert \\ & = \lvert x_n - (1-\lambda _n)x_n - \lambda _n T(x_n)\rVert + (1-\lambda _n)\lVert x_n - T(x_n)\rVert \\ & = \lambda _n \lVert x_n - T(x_n)\rVert + (1-\lambda _n)\lVert x_n - T(x_n)\rVert \\ & = \lVert x_n - T(x_n)\rVert. \end{align*} \]
Therefore \(\lVert x_n - T(x_n)\rVert \to l \ge 0\) by the Monotone Convergence Theorem. We want to show that \(l=0\), so for contradiction let \(l>0\) and consider
\[ \infty > \sum_{n=0}^N \lambda _n(1-\lambda _n)\lVert x_n - T(x_n)\rVert^2 \geq l^2 \sum_{n=0}^N \lambda _n(1-\lambda _n). \]
Therefore
\[ \lim_{n \to \infty} \lVert T(x_n) - x_n\rVert = 0. \]
Since \(x_n\) is \(F\)-monotone with respect to \(\text{Fix}(T)\) there exists a subsequence \(x_{n_k}\) with weak limit \(\bar {x}\). Thus
\[ x_{n_k} \stackrel{D}\to \bar{x} \]
Hence,
\[ T(x_{n_k})-x_{n_k} \to 0. \]
By Demi-closure of a non-expansive operator, \(\bar{x}\in\text{Fix}(T)\). By \(F\)-monotone convergence of the sequence, \(x_n \to \bar {x}\).