Does Monotone (linear) convergence of iterates imply monotone (linear) convergence of function values?

Question

I am considering a proof that would require a certain connection between convergence of iterates and corresponding function values: Consider an algorithm with iterates $\left\{{\mathbf{x}}^k\right\}_{k\in \mathbb{N}}$ and a continuously differentiable function ${\mathbf{f}}:\mathbb{R}^{n} \to \mathbb{R}^{m}$. Assume that ${\mathbf x}^k \xrightarrow{k \to \infty} {\mathbf{x}}^+$, but $\mathbf{f}(\mathbf{x}^k)\neq \mathbf{f}({\mathbf{x}}^+) \forall k$.

Can we show that

1. monotone decrease in the distance between iterates will eventually yield monotone decrease in distance of function values, i.e., \begin{align} \exists K &\in \mathbb{N}: \forall k>K: \\ &\lVert {\mathbf x}^{k+1} - {\mathbf x}^{k}\rVert \le \lVert {\mathbf x}^{k} - {\mathbf x}^{k-1}\rVert \implies \lVert {\mathbf{f}} ({\mathbf x}^{k+1}) - {\mathbf{f}}({\mathbf x}^{k})\rVert \le c \lVert {\mathbf{f}}({\mathbf x}^{k}) - {\mathbf{f}}({\mathbf x}^{k-1})\rVert \end{align} with $c=1$ or $1<c\le2$ ?
2. linear convergence of the residuals follows from the linear convergence of iterates, i.e., $$ \lim \limits_{k \to \infty} \frac{\lVert {\mathbf x}^{+} - {\mathbf x}^{k}\rVert}{\lVert {\mathbf x}^{+} - {\mathbf x}^{k-1}\rVert} = \mu\in (0,1) \implies \lim \limits_{k \to \infty} \frac{\lVert {\mathbf{f}} ({\mathbf x}^{+}) - {\mathbf{f}}({\mathbf x}^{k})\rVert}{\lVert {\mathbf{f}} ({\mathbf x}^{k+1}) - {\mathbf{f}}({\mathbf x}^{k})\rVert} < \nu\in (0,1) \;? $$

So far, I have only been able to make progress on (1.): I was able to convince myself for (1.) in the case of a function $f:\mathbb{R}\to \mathbb{R}$, because it is either constant equal $0$ near $x^+$ or is monotone in a small area around $0$. I tried constructing a counterexample for (1.) in the linear case (using eigenvectors with eigenvalue 0 and 1), but failed because of the assumption that $\mathbf{f}(\mathbf{x}^k)\neq \mathbf{f}({\mathbf{x}}^+)$.

I was able to find some loosely connected literature here talking about Ostrowki’s convergence theorem and a connected result by Meyer.

However, I have hope that these questions are not novel and have been answered (considering one might seek such a connection between iterate convergence and residual convergence for, e.g., Newton's method. Does anybody have pointers on this?

Answer 1

I found a counter example in the linear case:

Consider $\boldsymbol{f}(\boldsymbol{x})= \begin{pmatrix} \frac{1}{3} & 0 \\ 0 & 1 \end{pmatrix} \boldsymbol{x}$ and the sequence $x^i=\begin{cases} 0.5^i\begin{pmatrix} 1 \\ 0\end{pmatrix} & \text{if $i$ is odd,} \\ 0.5^i\begin{pmatrix} 0 \\ 1\end{pmatrix} & \text{if $i$ is even.}\end{cases}$

It is clear that $\left\{\boldsymbol{x}^i\right\}$ converges q-linear with factor 0.5 to $\begin{pmatrix} 0 \\ 0\end{pmatrix}$. However, the corresponding function values do not.