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|}$$

  • $\begingroup$ 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]$? $\endgroup$ – Edward Sep 19 '18 at 21:49
  • 1
    $\begingroup$ @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 $\endgroup$ – trancelocation Sep 20 '18 at 0:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.