Fixed Point Iteration Requirements

[k3N70n]

Hi

I wrote a numerical analysis midterm earlier this week and there was one question I couldn't figure out. I was wondering if anyone had some insight.

What I've been told and what I've read in many many places is that
f(x) will converge to a fixed point on an interval I if
1. f(x) is continuous and differentiable on I
2. |f'(x)|<1 on I

Now the question I was posed was given $x_{n+1}=\frac{1}{3}(x_n^2+2)$ prove that $x_n\rightarrow 1$ as $n\rightarrow\infty$ if $-2<x_0<2$ (that is prove $x_{n+1}$ is between $x_n$ and 1 when $n \geq 1$)

What was most natural to me was to find the interval where |f'(x)|<1 which happens to be on $(-\frac{3}{2},\frac{3}{2})$. It easy to see (but not so easy to prove) that the interval (-2,2) will work as well. How would you go about showing that? Do think that it would be possible to generalize this such that the requirement |f'(x)|<1 would not be needed for fixed point iteration?

Anyway, hope this interest someone else.

 

[Hurkyl]

Have you looked at a few of the sequences produced from different starting points? The behavior is very easy to describe... it's the sort of behavior whose existence I would expect to be very easy to prove directly (particularly due to the algebraically simple nature of the iteration).

 

[k3N70n]

Yes I have looked at different starting points. I did show that for all starting points on (-2,2) you end up on (1,2). I also noted that the iteration function was strictly decreasing after the first iteration but I wasn't able to show that. I guess if I was more specific I would have said that was my question.

 

[Hurkyl]

I did show that for all starting points on (-2,2) you end up on (1,2).

All of them? Are you sure?

I also noted that the iteration function was strictly decreasing after the first iteration but I wasn't able to show that. I guess if I was more specific I would have said that was my question.

In other words,

If y = (x^2 + 2)/3 and x is in (1, 2), then y < x​

But you can do better than that... you know that it's strictly decreasing to 1; in other words, the distance from 1 is decreasing. This suggests it's more natural to seek to prove

|y-1| < |x-1|.​

 

[k3N70n]

All of them? Are you sure?

Whoops. no. that should have been $(\frac{2}{3},2)$
but I guess it doesn't matter much because I had already showed that it converges on $(-\frac{3}{2},\frac{3}{2})$

So then it remains to be shown that on $(\frac{3}{2},2)$ that

In other words,

If y = (x^2 + 2)/3 and x is in (1, 2), then y < x​

But you can do better than that... you know that it's strictly decreasing to 1; in other words, the distance from 1 is decreasing. This suggests it's more natural to seek to prove

|y-1| < |x-1|.​

I'm still confused. I do know that it is strictly decreasing but I don't know how to prove it.
What you're suggesting to me is prove:

$$|x_{n+1}-1|<|\frac{x_n}{3}-\frac{1}{3}|$$ for any $$x_n\in(\frac{3}{2},2)$$
I still don't know how to do that though. I there just something really stupid that I'm missing.