How to derive the convergence condition for $x_{n+1}=g(x_n)$ is $|g'(x_0)<1|$

Question

In the method of fixed point iteration we are looking for solutions to $$f(x)=0,$$ by rearranging to give: $$x=g(x)$$ we then iterate using $$x_{n+1}=g(x_n)$$ using an intial guess of $x_0$. I'm struggling to understand how the taylor expansion helps us find the convergence conditions that $|g'(x_0)<1|$. I'm sure I'm doing something stupid, but I can't seem to get it out, any help greatly appreciated.

Answer 1

This question centers around the following theorem.

Let $I \subseteq \mathbb{R}$ be an open interval and let $g : I \rightarrow \mathbb{R}$ be differentiable with a continuous derivative $g' : I \rightarrow \mathbb{R}$. Suppose $g$ has a fixed point $\xi \in I$ and $|g'(\xi)|<1$. Then there exists a closed bounded interval $J \subset I$, such that $\xi \in J$, $g(J) \subseteq J$ and $g_{|J} : J \rightarrow J$ is a contraction, i.e., there exists $L \in [0,1)$ such that $$\forall x, y \in J \: : \: |g(x) - g(y)| \leq L |x-y|.$$ Moreover, the fixed point iteration $$ x_{n+1} = g(x_n)$$ converges to $\xi$ regardless of the choice of starting point $x_0 \in J$.

The central point is the existence of the interval $J$ and the (Lipschitz) constant $L < 1$. We will delay the proof a moment and instead focus on the convergence of the fixed point iteration. The delightful property that $g$ maps $J$ into itself ensures that the iteration is well defined for all $x_0 \in J$. Moreover, we have $$ |\xi - x_{n+1}| = |g(\xi) - g(x_n)| \leq L |\xi - x_n|.$$ By induction on $n$ we have $$ |\xi - x_n| \leq L^n |\xi - x_0|.$$ Since $L < 1$, convergence follows immediately.

Now for the construction of $J$ and the selection of $L$. By assumption, we have $|g'(\xi)| < 1$. Let $\epsilon>0$ be given by $$ \epsilon = \frac{1 - |g'(\xi)|}{2}.$$ By the continuity of $g'$ there exists a $\delta > 0$ such that $$ \forall z \in I \: : \: |\xi - z| < \delta \: \Rightarrow \: |g'(\xi) - g'(z)| < \epsilon.$$ It is clear that this property implies $|g'(z)| < 1$. Why? By the triangle inequality we have $$ |g'(z)| \leq |g'(\xi)| + |g'(\xi) - g'(z)| < |g'(\xi)| + \frac{1-|g'(\xi)|}{2} = \frac{1+|g'(\xi)|}{2} < 1.$$ Since $I$ is an open interval we can without loss of generality assume that $(\xi - \delta, \xi + \delta) \subseteq I$. If necessary, we simply reduce $\delta$. We now define $$J = \left[\xi - \frac{\delta}{2}, \xi + \frac{\delta}{2}\right].$$ By design $J$ is a closed and bounded interval and we have $|g'(z)| < 1$ for all $z \in J$ which automatically implies that $$ L = \sup \{ |g'(z)| \: : \: z \in J \} < 1.$$ At this juncture the mean value theorem finally makes it appearance. Given $x, y \in J$, there exists at least one $z$ between $x$ and $y$, such that $$ g(x) - g(y) = g'(z)(x-y).$$ Since $z \in J$, we have $|g'(z)| \leq L$. This completes the analysis.

---

Higher order Taylor expansions enter into the picture when higher order derivatives of $g$ exist and vanish at the fixed point, but this is perhaps a subject for another question.

Answer 2

First consider what happens when $g(x) = ax + b.$ Then $$|x_{n+1} - x_0| = |g(x_n) - g(x_0)| = |a| |x_n-x_0| \\ \Rightarrow \\ |x_{n+1} - x_0| = |a|^n \cdot |x_1-x_0|$$ so in this situation, $|g'(x_0)| = |a| < 1$ is necessary and sufficient for convergence when $x_1\neq x_0.$

That's how we can deduce the condition $|g'(x_0)| < 1.$ To see it works in a broader class of functions, we can use the mean value theorem (which is the "base case" of Taylor's theorem).

Specifically, if we assume $g$ is continuously differentiable in a neighborhood of $x_0$ and $|g'(x_0)| < 1$ then it is possible to choose $x_1$ such that $|g'(x)| < 1$ for all $|x - x_0| \leq |x_1-x_0|.$ Using this choice of $x_1,$ the mean value theorem effectively reduces the problem to the linear case. From this, we can conclude that $|g'(x_0)| < 1$ is a sufficient condition for $x_n \to x_0$ for some choice of $x_1.$ (and by a similar argument, $|g'(x_0)| \leq 1$ is a necessary condition)