Distance between fixed points of contracting maps

joshmccraney

1. 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)$.

2. 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\|$.

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?

Related Calculus and Beyond Homework Help News on Phys.org

fresh_42

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

joshmccraney

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
2018 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.

joshmccraney

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

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:

fresh_42

Mentor
2018 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!

WWGD

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?
1. 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)$.

2. 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 $. 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. joshmccraney 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 2018 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$joshmccraney 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 2018 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 joshmccraney 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!

"Distance between fixed points of contracting maps"

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