Sublinear convergence of a fixed point iteration

Question

A Fixed Point iteration is given by, \begin{equation} x_{k+1} = T(x_k) + q \end{equation} By Banach Contraction theorem, if $T$ is a contraction, then the above iteration convergent.

In particular, if $T$ is a finite dimensional linear opearator such that $\| T \|< 1$, the iteration converges linearly i.e, $$ \limsup_{k\rightarrow\infty} \frac{\|x_{k+1}-x^*\|_2}{\|x_{k}-x^*\|_2} = C<1$$ where $x^* = \lim_{k\rightarrow\infty} x_k$.

My query is if there exist a linear operator $T:\mathbb{R}^n\rightarrow\mathbb{R}^n$ such that, the iteration converges but sublinearly. That is, $x^*$ exists and the following holds: $$ \limsup_{k\rightarrow\infty} \frac{\|x_{k+1}-x^*\|_2}{\|x_{k}-x^*\|_2} = C\geqslant1$$

Some points to note:

• $\| T \|_2 $ should be $\geqslant 1$. Otherwise, the convergence is linear.
• You can assume that $x^*$ exists for some $T$ with $\| T \|_2\geqslant 1$. My question is, how to establish sublinear convergence for such $T$?

Answer 1

I want to prove the following (weaker) claim: there is $\rho\in (0,1)$ and $c>0$ such that $\|x_k - x^*\|_2 \le c \rho^k$. This is R-linear convergence, but not a contradiction to Q-sublinear convergence, which is the question about. I would expect that Q-sublinear convergence is impossible, but I could not manage to prove it.

First, let me reduce the problem: wlog we can assume $x^*=0$, and $T$ is a complex upper triangular matrix, $T \in \mathbb C^{n,n}$.

Then I am going to prove the following claim:

---

Let $(x_k)$ be a sequence in $\mathbb C^n$ with $x_k\ne0$ for all $k$, $x_{k+1} = Tx_k$, and $x_k \to 0$. Then there is $c>0$ and $\rho\in (0,1)$ such that $\|x_k\|_2 \le c \rho^k$.

The proof is by induction wrt $n$. I need the following two results.

---

Lemma 1 Let $(a_k)$ be a sequence of non-negative numbers converging to zero and satisfying $a_{k+1} \le d a_k+ c\rho^k$ with $d\in(0,1)$, $c\ge0$, $\rho\in (0,1)$. Then there is $c'\ge0$ such that $a_n \le c' \max(d,\rho)^k$.

Proof: by induction.

---

Lemma 2 Let $(a_k)$ be a sequence of non-negative numbers converging to zero and satisfying $d a_k \le a_{k+1}+ c\rho^k$ with $d\ge1$, $c\ge0$, $\rho\in (0,1)$. Then there is $c'\ge0$ such that $a_n \le c' \rho^k$.

Proof. Summing the inequality for $k=n\dots m$ yields $$ da_n +(d-1) \sum_{k=n+1}^m a_k\le a_{m+1} + \frac c{1-\rho} \rho^n. $$ Letting $m\to\infty$ proves $da_n \le \frac c{1-\rho} \rho^n$.

---

Proof of the main result

Case $n=1$. Here $x_{k+1} = tx_k$. Since $x_k\ne0$, it follows $t\ne0$. Since $x_k \to0$ it follows $|t|<1$, and the claim holds with $c=1$ and $\rho=|t|<1$.

Induction step. Assume the claim is proven for all such sequences in $\mathbb C^n$, $n\ge 1$. Now take such a sequence in $\mathbb C^{n+1}$. Let me partition $x_k$ and $T$ as $$ x_{k+1} = \pmatrix{ x_{k+1,1} \\ x_{k+1}'} \pmatrix{ d & a^T \\ 0 & T'} \pmatrix{ x_{k,1} \\ x_k'}. $$ If there is $j$ such that $x_j'=0$ then $x_k'=0$ for all $k>j$. As in the case $n=1$ it follows $|d|<1$ and $|x_{k,1}|\le |d|^{k-j}$ for all $k>j$. Adjusting $c$ and $\rho$, the claim follows (for all $k$).

Now suppose $x_k'\ne0$ for all $k$. Then by induction hypothesis, $\|x_k'\|_2\le c \rho^k$ for some $\rho\in (0,1)$. If $|d|<1$ then $$ |x_{k+1,1}|^2 \le |d|^2 |x_{k,1}|^2 + \|a\|c \rho^k. $$ By Lemma 1 $ |x_{k,1}|^2 \le c' \max(|d|,\rho)^k$, which implies $\|x_{k}\|_2^2 \le c'' \max(|d|,\rho)^k$.

In case $|d|\ge1$, we write $d x_{k,1} = x_{k+1,1} - a^T x_k'$, which implies $|d| |x_{k,1}| \le |x_{k+1,1}| + \|a\|c \rho^k$. With Lemma 2 we get the claim.