• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Distance between fixed points of contracting maps

1,688
50
1. The problem statement, all variables and given/known data
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)##.

2. Relevant 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\|##.

3. 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?
 

fresh_42

Mentor
Insights Author
2018 Award
10,329
7,032
I don't understand uniformly close. If ##||f(v)-g(v)|| < \varepsilon## for any ##\varepsilon>0##, why isn't ##f \equiv g?##
 
1,688
50
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!
 

fresh_42

Mentor
Insights Author
2018 Award
10,329
7,032
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.
 
1,688
50
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?

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)?
 

WWGD

Science Advisor
Gold Member
4,173
1,740
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:

fresh_42

Mentor
Insights Author
2018 Award
10,329
7,032
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!
 

WWGD

Science Advisor
Gold Member
4,173
1,740
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
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?
1. The problem statement, all variables and given/known data
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)##.

2. Relevant 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 ##.

3. 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.
 
1,688
50
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.
 

fresh_42

Mentor
Insights Author
2018 Award
10,329
7,032
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##
 
1,688
50
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?
 

fresh_42

Mentor
Insights Author
2018 Award
10,329
7,032
$$\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:
1,688
50
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!
 

Want to reply to this thread?

"Distance between fixed points of contracting maps" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top