# Numerical Analysis - Proving that the fixed point iteration method converges.

I am having some trouble with a numerical analysis proof related to the fixed point iteration method. The problem is as follows:

Suppose that $f$ in $C^2[a,b]$ and for some $x$ in $(a, b)$ we have $f(x) = x$ and $|f'(x)| < 1$. Prove that there exists $\epsilon$ > 0 such that if the initial approximation $x_0$ satisfies $x - \epsilon \leq x_0 \leq x + \epsilon$, then the fixed point iteration method converges to x.

My attempt at a solution:

I'm not quite sure where to start. By the fixed point thm, we know that this method converges if for all x in [a,b] we have that $a \leq g(x) \leq b$. This guarantees that we will find at least one fixed point in the given interval. We also have the condition that if for all x in [a,b] $|g'(x)| < 1$ then the fixed point is unique. So the challenge here is in selecting an appropriate $\epsilon$ such that these conditions are met for the interval $[x_0 - \epsilon, x_0 + \epsilon]$. I'm not asking for a solution, but maybe some hints/tips for the right $\epsilon$.

After hint (by @trancelocation), I have the following:

Suppose that $x_0$ is a fixed point ($f(x_0) = x_0$) over $(a,b)$. Because $f'$ is continuous and that $|f'(x_0)| \leq 1$, then there must be an $\varepsilon$ such that for any $x \in [x_0 - \varepsilon, x_0 + \varepsilon]$ we have that $|f'(x)| \leq q < 1$.

(Aside: The way I picture this is if we know that at a particular point $x_0$ $|f'(x_0)| \leq 1$ and because $f'(x)$ being continuous implies that the function is "nice and smooth" over $(a,b)$, then there must be a subset of that interval where for any $x$ it is true that $|f'(x)| \leq 1$. Please correct me if my reasoning is off.)

Now, if we have $x \in [x_0 - \varepsilon, x_0 + \varepsilon]$, then:

$|f(x) - x_0| = |f(x) - f(x_0)|$ (By definition)

$= |f'(\xi)||x - x_0|$ (By the MVT)

$\leq q |x - x_0|$ (By assumption)

But we know that $q<1$, in other words the "distance or length" between $f(x)$ and $f(x_0)$ is less than that of $x$ and $x_0$. Meaning that $f(x) \in [x_0 - \varepsilon, x_0 + \varepsilon]$ for any $x$ in that same interval (This is were I still believe that I am missing something).

Thus, we have that $f(x) \in [x_0 - \varepsilon, x_0 + \varepsilon]$ and that $|f'(x)| \leq q < 1$ for any $x \in [x_0 - \varepsilon, x_0 + \varepsilon]$, which satisfy the conditions of the Fixed Point Theorem. Hence $x_0$ is the unique fixed point within this interval to which the fixed point iteration converges.

Note that $f'$ is continuous. Let's call the fixed point by $x_0$. So, it follows:
• $\exists \varepsilon > 0: |f'(x)| \leq q <1 \mbox{ for } x \in [x_0-\varepsilon , x_0+ \varepsilon]$.
So, for $x \in [x_0-\varepsilon , x_0+ \varepsilon]$ you have
$$\color{blue}{|f(x) - x_0|} = |f(x) - \color{blue}{f(x_0)}|= |f'(\xi)|\cdot|x-x_0| \color{blue}{\leq q\cdot |x-x_0|}$$
• Oh I see. But how do you go from $|f(x)-f(x_0)|$ to $|f'(\xi)||x - x_0|$. Is it because we know that both $f(x)$ and $f(x_0)$ are within the interval $[x_0-\epsilon,x_0+\epsilon]$? – Edward Sep 19 '18 at 21:49
• @Edward : This is just an application of the mean value theorem: $f(x) - f(x_0) = f'(\xi)(x-x_0)$ for a $\xi$ between $x$ and $x_0$. For reference see, for example, en.wikipedia.org/wiki/Mean_value_theorem – trancelocation Sep 20 '18 at 0:56