Distance between fixed points of contracting maps

I know that I have to get $$\| g(x_f) - x_f \| < \frac{\epsilon}{1-q}$$ but I'm unsure how to get there.In summary, the problem asks to show that for two q-contracting maps that are uniformly close to each other, the distance between their fixed points is at most epsilon divided by one minus q. The approach is to use the Banach Fixed Point Theorem and iterate one map starting at the fixed point of the other map. However, the issue is that the q value for both maps is the same, meaning that the result may not hold if they were different. To address this, the triangle inequality is used to show that the distance between
  • #1
member 428835

Homework Statement


Let ##V## be a Banach space. Let ##f:V\to V## and ##g:V\to V## be two ##q##-contracting maps, ##q\in(0,1)##. Assume they are uniformly close to each other. Show the distance between fixed points of ##f,g## is at most ##\epsilon/(1-q)##.

Homework Equations


Definitions:

Uniformly close implies ##\forall \, \epsilon>0, v\in V## we have ##\| f(v) - g(v) \| < \epsilon##.

A map ##f## is ##q##-contracting if ##\exists \, q \in (0,1):\forall x,y\in\mathbb R^n, \| f(x) - f(y) \| \leq q\| x-y\|##.

The Attempt at a Solution


My idea is to iterate one map starting at the fixed point of the other map and show after sufficient amount of iterations, you will be within ##\epsilon## of the other fixed point. Since we are proving the distance between fixed points, the Banach Fixed Point Theorem seems relevant: $$\| x-x_n \| \leq \frac{q^n}{1-q}\| x_1-x_0 \|$$ where ##x## is the fixed point and ##x_n## is the ##n##th iteration.

So trying to put all this together, if ##x_f## is the fixed point of ##f##, then consider
$$\| g(x_f) - f(x_f) \| = \| g(x_f) - x_f \| \implies\\
\| g(x_f) - x_f \| < \epsilon
$$

But this can't be right. Can someone help me smooth it out?
 
Physics news on Phys.org
  • #2
I don't understand uniformly close. If ##||f(v)-g(v)|| < \varepsilon## for any ##\varepsilon>0##, why isn't ##f \equiv g?##
 
  • #3
fresh_42 said:
I don't understand uniformly close. If ##||f(v)-g(v)|| < \varepsilon## for any ##\varepsilon>0##, why isn't ##f \equiv g?##
Ok, so my conclusion isn't too crazy after all? I'll check and ask the professor when I next see him and post what I find. Thanks for responding!
 
  • #4
joshmccraney said:
Ok, so my conclusion isn't too crazy after all? I'll check and ask the professor when I next see him and post what I find. Thanks for responding!
It could be ##\forall\,\varepsilon>0 \,\exists\,v_\varepsilon## but you haven't quantified ##v##, so it reads as if it is still under the for all quantifier.

In general, you should start with ##||x_f-y_f||=||f(x_f)-g(y_f)||##, insert some terms and use the triangle inequality.
 
  • #5
fresh_42 said:
It could be ##\forall\,\varepsilon>0 \,\exists\,v_\varepsilon## but you haven't quantified ##v##, so it reads as if it is still under the for all quantifier.
Can you clarify what ##v_\epsilon## is?

fresh_42 said:
In general, you should start with ##||x_f-y_f||=||f(x_f)-g(y_f)||##, insert some terms and use the triangle inequality.
Isn't that how I started (begin with a fixed point from one function)?
 
  • #6
Can't you use the general form of the fixed point? It comes from repeated iterations of the map , i.e., ## Lim _{ n \rightarrow \infty} f^{n}(x)=x ## for any x in the space. Then do something to show ff(x) is very close to g(g(x)), etc?
 
Last edited:
  • #7
joshmccraney said:
Can you clarify what ##v_\epsilon## is?
In my notation, the choice of ##v## depends on ##\varepsilon##, because I wrote ##\forall\,\varepsilon \, \exists\,v = v(\varepsilon)##, it varies with ##\varepsilon##. However, what we need is ##||f(x_f)-g(x_f)||<\varepsilon##.
Isn't that how I started (begin with a fixed point from one function)?
You started with the ##||f(x_f)-g(y_f)||## whereas I started with ##||x_f-y_f||##. They are equal, but at the end of the day, it makes the difference!
 
  • #8
joshmccraney said:
Can you clarify what ##v_\epsilon## is?

Isn't that how I started (begin with a fixed point from one function)?
Isn't this assuming
joshmccraney said:
Can you clarify what ##v_\epsilon## is?

Isn't that how I started (begin with a fixed point from one function)?
Where does this come from? We know each map has a fixed point, but where does this equality come from?
joshmccraney said:

Homework Statement


Let ##V## be a Banach space. Let ##f:V\to V## and ##g:V\to V## be two ##q##-contracting maps, ##q\in(0,1)##. Assume they are uniformly close to each other. Show the distance between fixed points of ##f,g## is at most ##\epsilon/(1-q)##.

Homework Equations


Definitions:

Uniformly close implies ##\forall \, \epsilon>0, v\in V## we have ##\| f(v) - g(v) \| < \epsilon##.

A map ##f## is ##q##-contracting if ##\exists \, q \in (0,1):\forall x,y\in\mathbb R^n, \| f(x) - f(y) \| \leq q\| x-y\|##.

I think the key issue here is that we have the same q for both maps, and using the relation:

##\exists \, q \in (0,1):\forall x,y\in\mathbb R^n, \| f(x) - f(y) \| \leq q\| x-y\|##.maybe with #x_1,x_2 ## and ## y_1, y_2 ## and the triangle inequality. This would not be true if we had , say a q- and p- contraction s with ## p \neq q ##.

The Attempt at a Solution


My idea is to iterate one map starting at the fixed point of the other map and show after sufficient amount of iterations, you will be within ##\epsilon## of the other fixed point. Since we are proving the distance between fixed points, the Banach Fixed Point Theorem seems relevant: $$\| x-x_n \| \leq \frac{q^n}{1-q}\| x_1-x_0 \|$$ where ##x## is the fixed point and ##x_n## is the ##n##th iteration.

So trying to put all this together, if ##x_f## is the fixed point of ##f##, then consider
$$\| g(x_f) - f(x_f) \| = \| g(x_f) - x_f \| \implies\\
\| g(x_f) - x_f \| < \epsilon
$$

But this can't be right. Can someone help me smooth it out?

I think the key issue is that these are both q-contractions and not p-, q- contractions, in which case the result would not hold up.
 
  • #9
Sorry, I'm very confused by post 7; perhaps WWGD was viewing from phone app?

Regarding post 6, what do you add? I thought about $$\| f(x_f) - g(x_f) + x_g - x_g \| \leq \| f(x_f) -x_g\| + \|g(x_f) - x_g \| =\\
\| f(x_f) -g(x_g)\| + \|g(x_f) - x_g \| \leq \epsilon + \|g(x_f) - x_g \| \leq \epsilon + \frac{q}{1-q}\| g(g(x_f)) - g(x_f) \|$$ but am now stuck.
 
  • #10
joshmccraney said:
Sorry, I'm very confused by post 7; perhaps WWGD was viewing from phone app?

Regarding post 6, what do you add? I thought about $$\| f(x_f) - g(x_f) + x_g - x_g \| \leq \| f(x_f) -x_g\| + \|g(x_f) - x_g \| =\\
\| f(x_f) -g(x_g)\| + \|g(x_f) - x_g \| \leq \epsilon + \|g(x_f) - x_g \| \leq \epsilon + \frac{q}{1-q}\| g(g(x_f)) - g(x_f) \|$$ but am now stuck.
Why is ##\| f(x_f) -g(x_g)\|<\varepsilon\,?## And I do not understand the rest either.

Try my hint: ##||x_f - x_g|| = ||f(x_f) -g(x_g)|| = ||f(x_f) - g(x_f) + g(x_f) - g(x_g)|| \leq \ldots##
 
  • #11
fresh_42 said:
Why is ##\| f(x_f) -g(x_g)\|<\varepsilon\,?## And I do not understand the rest either.

Try my hint: ##||x_f - x_g|| = ||f(x_f) -g(x_g)|| = ||f(x_f) - g(x_f) + g(x_f) - g(x_g)|| \leq \ldots##

$$\leq \|f(x_f) - g(x_f)\| + \|g(x_f) - g(x_g)\| \leq \epsilon + \frac{q}{1-q}\| g(g(x_f)) - g(x_f) \|
$$

where the final term comes from Remark 1, from the following wiki page:

https://en.wikipedia.org/wiki/Banach_fixed-point_theorem

But now I'm unsure what to do. Is this not what you had in mind?
 
  • #12
joshmccraney said:
$$\leq \|f(x_f) - g(x_f)\| + \|g(x_f) - g(x_g)\| \leq \epsilon + \frac{q}{1-q}\| g(g(x_f)) - g(x_f) \|
$$

where the final term comes from Remark 1, from the following wiki page:

https://en.wikipedia.org/wiki/Banach_fixed-point_theorem

But now I'm unsure what to do. Is this not what you had in mind?
This is way too complicated. We have ##\|f(x_f) - g(x_f)\|<\varepsilon## by assumption of uniformly close functions, and ##\|g(x_f) - g(x_g)\| < q ||x_f-x_g||## since the functions are contractions. All together there is a term ##||x_f-x_g||## at the beginning of the LHS, which is why I wanted to start with it, and a term ##||x_f-x_g||## at the end on the RHS. But this is exactly the distance we want to estimate. The rest is a little algebra and attention on possibly negative factors in our inequality.
 
Last edited:
  • Like
Likes member 428835
  • #13
fresh_42 said:
This is way too complicated. We have ##\|f(x_f) - g(x_f)\|<\varepsilon## by assumption of uniformly close functions, and ##\|g(x_f) - g(x_g)\| < q ||x_f-x_g||## since the functions are contractions. All together there is a term ##||x_f-x_g||## at the beginning of the LHS, which is why I wanted to start with it, and a term ##||x_f-x_g||## at the end on the RHS. But this is exactly the distance we want to estimate. The rest is a little algebra and attention on possibly negative factors in our inequality.
Oooooohhhhh! Sorry, I was thinking the only way to introduce the ##q## component was through iterative estimation. You invoke the definition of a ##q##-contacting map, which sucks for me because I even wrote the definition in the first post but spaced using it! :headbang:

Thanks so much! Marking this as solved!
 

1. What is the definition of the distance between fixed points of contracting maps?

The distance between fixed points of contracting maps is the shortest distance between two points that remain fixed under the action of the map. In other words, it is the distance between the two points that do not change their positions after applying the map repeatedly.

2. How is the distance between fixed points of contracting maps calculated?

The distance between fixed points of contracting maps can be calculated using the Banach fixed point theorem. This theorem provides a formula for finding the distance between two fixed points of a contracting map in terms of the map's contraction factor and the initial distance between the two points.

3. What is the significance of the distance between fixed points of contracting maps?

The distance between fixed points of contracting maps is an important measure of how quickly a map converges to a fixed point. A smaller distance indicates a faster convergence, while a larger distance indicates a slower convergence. This is useful in analyzing the stability and convergence properties of dynamical systems.

4. How does the distance between fixed points of contracting maps relate to other mathematical concepts?

The distance between fixed points of contracting maps is closely related to the concept of contraction mappings, which are maps that shrink distances between points. It is also related to the concept of fixed points, which are points that remain unchanged under the action of a map. Additionally, the distance between fixed points can be used to define the Hausdorff metric, which is a way of measuring the distance between sets.

5. Can the distance between fixed points of contracting maps be negative?

No, the distance between fixed points of contracting maps is always a positive value. This is because contracting maps always decrease distances between points, so the distance between fixed points cannot be negative. If the distance between two fixed points is zero, then the points are actually the same point and there is only one fixed point for the map.

Similar threads

  • Calculus and Beyond Homework Help
Replies
16
Views
1K
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
810
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • General Math
Replies
1
Views
677
  • Calculus and Beyond Homework Help
Replies
32
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
Back
Top