Looking for Guarantees that the method of fixed-point iteration will work

  • I
  • Thread starter mcastillo356
  • Start date
  • Tags
    Method Work
In summary, The fixed point theorem guarantees that the method of fixed point iteration will work for a particular class of functions. This class of functions is defined by two conditions: (i) the function is defined on an interval and (ii) there exists a constant with such that the absolute value of the difference between the function applied to two points in the interval is less than or equal to the constant times the absolute value of the difference between the two points. These conditions ensure that the function has a unique fixed point within the interval, and that starting with any number in the interval, the iterates will converge to the fixed point. To prove this, we can use the Intermediate-Value Theorem and the
  • #1
mcastillo356
Gold Member
603
331
TL;DR Summary
Want to understand which kind of functions I can be sure that the method of fixed-point iteration is suitable
Hi PF

Not every function works when we try to compute the root with this method

20220129_185054.jpg

The following theorem guarantees that the method of fixed point iteration will work for a particular class of functions

A fixed point theorem
Suppose that is defined on an interval and satisfies the following two conditions
(i) belongs to whenever belongs to ; and
(ii) there exists a constant with such that for every and in

Then has a unique fixed point in , that is, , and starting with any number in , the iterates

converge to
Hints for the proof
1- Condition (ii) of theorem implies that is continuous on . Use condition (i) to show that has a unique fixed point on . Apply the Intermediate-Value Theorem to on .
2- Use condition (ii) of theorem and mathematical induction to show that . Since , we know that as . This shows that
First: ¿Why bounded Newton quotient means continuity on the interval?.

Thanks
 
Physics news on Phys.org
  • #2
Continuity of on means that for any and we can find such that for all we have .

Given and , how would you use the inequality given in the OP to find a suitable that satisfies the required condition for continuity?
 
  • Informative
Likes mcastillo356 and berkeman
  • #3
Hi, PF
Sorry, I have had to review all: the concept of limit, and, consequently, continuity. And still have uncertainty though hope to have solved everything: bounded Newton quotient absolute value means continuity, because "a precise definition of limit is based on the idea of controlling the input of a function so that the output will lie in a specific interval. When we say that has a limit as approaches , we are really saying that we can ensure that the error will be less than any allowed tolerance, no matter how small, by taking a close enough to (but not equal to )" (Calculus, 9th edition, by Robert A. Adams and Christopher Essex). These words mean specifically that is bounded by , i.e., we have a limit on the Newton quotient, therefore a derivative, and eventually continuity.

andrewkirk said:
Given and , how would you use the inequality given in the OP to find a suitable that satisfies the required condition for continuity?



Is it ok?

Greetings!
 
  • #4
mcastillo356 said:
Yes, that works.
 
  • Love
Likes mcastillo356
  • #5
Hi
I'm wondering...
I would like to have the written proof itself.
No way?
Greetings
 
  • #6
mcastillo356 said:
Hi, PF
Sorry, I have had to review all: the concept of limit, and, consequently, continuity.
mcastillo356 said:
bounded Newton quotient absolute value means continuity, because "a precise definition of limit is based on the idea of controlling the input of a function so that the output will lie in a specific interval. When we say that has a limit as approaches , we are really saying that we can ensure that the error will be less than any allowed tolerance, no matter how small, by taking a close enough to (but not equal to )" (Calculus, 9th edition, by Robert A. Adams and Christopher Essex). These words mean specifically that is bounded by , i.e., we have a limit on the Newton quotient, therefore a derivative, and eventually continuity.
This last quote is wrong
. We can make


But this function has not derivative at
 
Last edited:
  • #7
You are correct. The author's statement that we have a derivative is wrong. Fortunately it is not necessary to reach the desired conclusion, which is that is continuous.
 
  • Informative
Likes mcastillo356
  • #8
Thanks, PF, for editing the right way!

¡Viva!
 
  • #9
andrewkirk said:
You are correct. The author's statement that we have a derivative is wrong. Fortunately it is not necessary to reach the desired conclusion, which is that is continuous.
Just to point out Lipschitz functions * are a.e. differentiable. Maybe this can be used.

* In f.d . spaces.
 
  • Like
Likes mcastillo356
  • #10
mcastillo356 said:
Hints for the proof
1- Condition (ii) of theorem implies that is continuous on . Use condition (i) to show that has a unique fixed point on . Apply the Intermediate-Value Theorem to on .
Hi, PF, now that we know is continuous on , next step, i,e., next two sentences of the quote above.
1- Use condition (i) to achieve the first hint
Condition (i), if I am right, is . This is the tool to show has a fixed point on . We must apply the IVT to , this is, some in the interval must be . But this is not IVT, is Bolzano's Theorem, to be precise.
Question: What means exactly ?
Regards
 
  • #11
mcastillo356 said:
Hi, PF, now that we know is continuous on , next step, i,e., next two sentences of the quote above.
1- Use condition (i) to achieve the first hint
Condition (i), if I am right, is . This is the tool to show has a fixed point on . We must apply the IVT to , this is, some in the interval must be . But this is not IVT, is Bolzano's Theorem, to be precise.
Question: What means exactly ?
Regards
I assume means set inclusion. The standard proof of this theorem I'm aware of, iterates the contraction map.
 
  • Like
Likes mcastillo356
  • #12
mcastillo356 said:
Condition (i), if I am right, is . ...
'''
What means exactly ?
Regards
Where did you get that condition from? It's wrong. Counterexample: the constant mapping . Then .
It should be the other way around:
 
  • Love
Likes mcastillo356
  • #13
andrewkirk said:
Where did you get that condition from? It's wrong. Counterexample: the constant mapping . Then .
It should be the other way around:
Ok, restart with an easy exercise. Find a root of the equation . I play tricks graphing , just to find out . Twenty iterations lead me to , .
Now let's leave behind this weird example to talk about . What means ? ?

mcastillo356 said:
The following theorem guarantees that the method of fixed point iteration will work for a particular class of functions

A fixed point theorem
Suppose that is defined on an interval and satisfies the following two conditions
(i) belongs to whenever belongs to ; and
(ii) there exists a constant with such that for every and in

Hints for the proof
1- Condition (ii) of theorem implies that is continuous on . Use condition (i) to show that has a unique fixed point on . Apply the Intermediate-Value Theorem to on .
We have proved is continuous on . Now, condition (i), i.e., .
Question
Why if I apply IVT to on , provided , I show that has got a fixed point?

PS: If I'm asking too much, ignore me, please. Just feel free to answer the way you like. PF, if LaTeX mistakes, sorry.

Regards!
 
  • #14
Write some inequalities showing the range of possible values for g(0) and g(1), using the premise assumption (i) that f(x) is in I.
Then consider cases.
If g(0) or g(1) is zero, you've found the fixed point.
If both are nonzero, you will find you can apply the IVT to g on I to prove the existence of a fixed point on I where g is zero.
 
  • Informative
Likes mcastillo356
  • #15
I think this is what the textbook suggests, for . I've done it quickly: up the image, there should appear . I think the is the key to get the fixed point
geogebra-export.png
 
  • #16
andrewkirk said:
Write some inequalities showing the range of possible values for g(0) and g(1), using the premise assumption (i) that f(x) is in I.
Then consider cases.
If g(0) or g(1) is zero, you've found the fixed point.
If both are nonzero, you will find you can apply the IVT to g on I to prove the existence of a fixed point on I where g is zero.
Intermediate-Value Theorem applied to ,
If is continuous on and is a real number lying between the numbers and , then there exists a point in such that .
1- is continuous on because and are
2-
3- Hypothesis: (the same if ):
4- in such that
5- , on
6- , on
7- such that on

Is it ok?
Regards!
 
  • #17
You make a hypothesis in step 3, and later steps depend on that hypothesis (or its alternative, in parentheses) being true. So you need to show that that hypothesis or its alternative is true. You have not shown that. In fact you need to show that either:
- the hypothesis is true, or
- its alternative is true, or
- g(a) = 0, or
- g(b) = 0
Also, you should fix s=0 at the hypothesis step, not leave it an unfixed variable.
 
  • Informative
Likes mcastillo356
  • #18
Hi, @andrewkirk , PF
First of all forgive this twist. I will try to put it other way. Reset :headbang:
Aims:
1) Justify is continuous on . Already proved
2) If or , check we already have the fixed point. Easy work
3) Otherwise, realize and got different signs, and apply Bolzano. A root of satisfies

If , and ... Here comes that, if , we conclude and . Thus, applied this to , and . Bolzano theorem: there exists such that

This is the solution I've been given outlined, but, why if , we conclude and ?

My attempt: the image of in is a subset of the domain of : preceeds , and stands before .

Am I on the way?
Love.
 
  • #19
is defined as which is defined as .
So saying is in is just another way of saying that is real and and . Similarly for .
 
  • Like
Likes mcastillo356
  • #20
Hi, @andrewkirk , PF
Back to #1, just to review done work, and work to be done:
1) Already shown that has a unique fixed point on
2) Next:
mcastillo356 said:
The following theorem guarantees that the method of fixed point iteration will work for a particular class of functions

A fixed point theorem
Suppose that is defined on an interval and satisfies the following two conditions
(i) (...), and
(ii) there exists a constant with such that for every and in

Then has a unique fixed point in , that is, , and starting with any number in , the iterates

converge to
Hints for the proof
1- (...)
2- Use condition (ii) of theorem and mathematical induction to show that . Since , we know that as . This shows that
How about if I give a try and tackle second hint?: use condition (ii) of theorem and mathematical induction to show that
Here the idea is that is the fixed point then , and by (ii)


...
This idea is not mine: thanks to Spanish Rincón Matemático.
P.S. I will leave the effort to solve for some other thread.
Thanks, love.
Again, PF, check the LaTeX, I will post not previewing. Regards
 
  • #21
mcastillo356 said:
Hi, @andrewkirk , PF
Back to #1, just to review done work, and work to be done:
1) Already shown that has a unique fixed point on
2) Next:

How about if I give a try and tackle second hint?: use condition (ii) of theorem and mathematical induction to show that
Here the idea is that is the fixed point then , and by (ii)


...
Hi, PF, here is my attempt:

Required to prove



Let's test for and





Assume for

for

And prove



but

Thus



By PMI, the statement is true for

Sorry, all my background has been a tutorial on the principle of mathematical induction. I post just to pick your opinions.

Questions:
Is there something usable in my soliloquy?
Any suggestion?

Thanks in advance.
 
  • #22
Your attempted proof is mostly correct but you've omitted steps in the last line of inequalities. Here it is with the missing steps inserted:
 
  • Love
Likes mcastillo356
  • #23
When I need to solve an equation like and I can't find a fixed point iteration function that works, I try to see the equation as the minimization problem
Then I can try to solve it by using some numerical methods to handle with the differential equation which is the same as the equation

If you have some guarantee that the Jacobian matrix of has an inverse, the equation and the Euler method can produce the Newton method, for instance.

Try to search for gradient descent method on SearchOnMath.
 
Last edited:
  • Like
Likes mcastillo356

Similar threads

Replies
13
Views
2K
Replies
2
Views
2K
Replies
5
Views
2K
Replies
6
Views
2K
Replies
16
Views
3K
Replies
4
Views
1K
Back
Top