Distance between fixed points of contracting maps

Gold Member

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?

Mentor
2022 Award
I don't understand uniformly close. If ##||f(v)-g(v)|| < \varepsilon## for any ##\varepsilon>0##, why isn't ##f \equiv g?##

Gold Member
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!

Mentor
2022 Award
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.

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

Gold Member
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:
Mentor
2022 Award
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!

Gold Member
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?

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.

Gold Member
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.

Mentor
2022 Award
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##

Gold Member
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?

Mentor
2022 Award
$$\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:
joshmccraney
Gold Member
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!

Thanks so much! Marking this as solved!