# Stop criterium for fixed point methods

Let $g(x): \mathbb{R} \to \mathbb{R}$ define a fixed point method. We are interested in the points $\alpha$ s.t. $\alpha = g(\alpha)$.

Let $(x_n)_{n\in\mathbb{N}}$ be defined by $x_{n+1} := g(x_n)$. Suppose that $x_n \to \alpha \ (n \to +\infty)$.

How to prove the following?

If $g$ sufficiently smooth in a neighbourhood of $\alpha$, then

$$\forall \varepsilon > 0 \ \exists m > 0 \ \big(( \ \forall n > m \ \vert x_n - x_{n-1} \vert < \varepsilon) \rightarrow \ (\exists C > 0 \ \forall n > m \ \vert x_n - \alpha\vert < C\varepsilon)\big).$$

In other words the theorem assures that we can safely estimate the error of an iterative fixed point method in a certain iteration, looking a the value $\vert x_n - x_{n-1}\vert$.

• I think I found a proof, I will answer now – Nisba Jan 22 '18 at 11:13
• I think your last inequality which should not be strict or $x_n = \alpha$ gives a problem. More importantly, I believe your final conclusion is not supported by your result. I do not see a practical way to verify that your hypothesis is satisfied. If your focus is actual computation of a computer, your fixed point iteration could be investigated in terms of the Lipschitz constants and the forward relative error when computing values of $g$. – Carl Christian Jan 22 '18 at 19:21

## 1 Answer

Let $g$ be $C^{(1)}$ in a neighbourhood of $\alpha$. Furthermore we suppose $g'(\alpha) \neq 1$, otherwise more regularity is required. From Taylor we have $$x-g(x) = \alpha - g(\alpha) + (x-\alpha) (1-g'(\alpha)) + o(x-\alpha).$$ Substituting $x_n$ to $x$ we get $$x_n - x_{n+1} = (x_n - \alpha)(1-g'(\alpha)) + o(x_n - \alpha).$$ Then for $$C := \left\Vert \frac{1}{1 - g'(\alpha)} \right\Vert_{\infty},$$ where the norm is taken in the interval in which the Taylor expansion is defined, we have the thesis.

We have also proved that $C$ is independent from $\varepsilon$.

• A similar conclusion follows also from Banach-Cacioppoli Theorem – Nisba Jan 22 '18 at 11:28