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.
Best Answer
Hint:
Note that $f'$ is continuous. Let's call the fixed point by $x_0$. So, it follows:
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|}$$