Distance between fixed points of contracting maps

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

 

[fresh_42]

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

 

[member 428835]

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]

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.

 

[member 428835]

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]

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?

 

[fresh_42]

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]

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.

 

[member 428835]

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]

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$

 

[member 428835]

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]

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

 

[member 428835]

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!