Fixed Point Iteration Requirements

  • Thread starter k3N70n
  • Start date
  • #1
67
0
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 [itex] x_{n+1}=\frac{1}{3}(x_n^2+2)[/itex] prove that [itex]x_n\rightarrow 1[/itex] as [itex]n\rightarrow\infty [/itex] if [itex] -2<x_0<2[/itex] (that is prove [itex]x_{n+1}[/itex] is between [itex]x_n[/itex] and 1 when [itex]n \geq 1[/itex])

What was most natural to me was to find the interval where |f'(x)|<1 which happens to be on [itex](-\frac{3}{2},\frac{3}{2})[/itex]. 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.
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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).
 
  • #3
67
0
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.
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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|.​
 
  • #5
67
0
All of them? Are you sure?

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

So then it remains to be shown that on [itex](\frac{3}{2},2)[/itex] 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:

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

Related Threads on Fixed Point Iteration Requirements

  • Last Post
Replies
3
Views
704
Replies
1
Views
3K
Replies
1
Views
2K
Replies
10
Views
2K
  • Last Post
Replies
3
Views
6K
Replies
3
Views
835
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
Replies
5
Views
3K
  • Last Post
Replies
14
Views
6K
Top