Maximum norm and Banach fixed-point theorem

[JulienB]

Homework Statement

Hi everybody! I have a math problem to solve, I'd like to check if I understand well the Banach fixed-point theorem in the case of Euclidean norm and how to deal with maximum norm.

Check if the following functions ƒ: ℝ² → ℝ² are strictly contractive in relation to the given norms:
$$\mbox{a) } || \cdot ||_2 , f(x_1,x_2) = \frac{1}{2} (sin x_1, cos x_2) \\ \mbox{b) } || \cdot ||_2 , f(x_1,x_2) = \frac{1}{2} (x_1 + x_2, x_2) \\ \mbox{c) } || \cdot ||_{\infty} , f(x_1,x_2) = \frac{1}{2} (x_1 + x_2, x_2)$$

(note: not sure about my translation, can you say "contractive" in english?)

Homework Equations

Banach fixed-point theorem, mean value theorem for a), definition of norms

The Attempt at a Solution

I found it was not so easy to prove that the functions were strictly contractive or not, but here is a go:

$$\mbox{a) } || \frac{1}{2} \binom{sin x_1}{cos x_2} - \frac{1}{2} \binom{sin y_1}{cos y_2} ||_2 = \frac{1}{2} || \binom{sin x_1 - sin y_1}{cos x_2 - cos y_2} ||_2 \\ = \frac{1}{2} \sqrt{(sin x_1 - sin y_1)^2 + (cos x_2 - cos y_2)^2} \\ = \frac {1}{2} \sqrt{cos^2(α) (x_1 - y_1)^2 + sin^2 (β) (x_2 - y_2)^2} ≤ \frac{1}{2} \sqrt{(x_1 - y_1)^2 - (x_2 - y_2)^2} = \frac{1}{2} || \binom{x_1 - y_1}{x_2 - y_2} ||_2 \\ \mbox{(note that I made use of the mean value theorem to show the inequality)} \\ c < 1 \implies f(x_1,x_2) \mbox{ is strictly contractive.}$$

Is that correct? Am I understanding the Banach fixed-point theorem correctly? Now start the problems:

$$\mbox{b) } || \frac{1}{2} \binom{x_1 + x_2}{x_2} - \frac{1}{2} \binom{y_1 + y_2}{y_2} ||_2 = \frac{1}{2} \sqrt{(x_1 + x_2 - y_1 - y_2)^2 + (x_2 - y_2)^2} \\ = \frac{1}{2} \sqrt{x_1^2 + 2x_1 x_2 + x_2^2 - 2x_1y_1 + 2x_1y_2 - 2 x_2y_1 + 2x_2y_2 + y_1^2 - 2y_1y_2 + y_2^2 + (x_2 - y_2)^2} \\ = \frac{1}{2} \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_2 + y_2)^2 + 2(x_1x_2 + x_1y_2 - x_2y_1 - y_1y_2)}$$

Ehem... It seems to me that it would require a c bigger than 1 to make the inequality of the Banach theorem work, therefore the function would not be strictly contractive. On another hand the ½ makes it hard to prove... Is my intuition correct? Any clue about how to prove it if so?

And for c) I don't have a clue really. According to the definition in my teacher's script:

$$c \cdot || \binom{x_1 - y_1}{x_2 - y_2} ||_{\infty} = c \cdot max | \binom{x_1 - y_1}{x_2 - y_2} | \\ \mbox{and} \\ \frac{1}{2} || \binom{x_1 + x_2 - y_1 - y_2}{x_2 - y_2} ||_{\infty} = \frac{1}{2} \cdot max | \binom{x_1 + x_2 - y_1 - y_2}{x_2 - y_2} |$$

But what does that mean? It seems to me like those maximums are not existing! Is that the case? If yes, what can I conclude? If no, I must have misunderstood how to determine the maximum of a function in ℝ²...or the definition of a maximum norm altogether!

Thank you in advance for your answers.


Julien.

 

[JulienB]

Nobody has an idea?

 

[LCKurtz]

Homework Statement

Hi everybody! I have a math problem to solve, I'd like to check if I understand well the Banach fixed-point theorem in the case of Euclidean norm and how to deal with maximum norm.

Check if the following functions ƒ: ℝ² → ℝ² are strictly contractive in relation to the given norms:
$$\mbox{a) } || \cdot ||_2 , f(x_1,x_2) = \frac{1}{2} (sin x_1, cos x_2) \\ \mbox{b) } || \cdot ||_2 , f(x_1,x_2) = \frac{1}{2} (x_1 + x_2, x_2) \\ \mbox{c) } || \cdot ||_{\infty} , f(x_1,x_2) = \frac{1}{2} (x_1 + x_2, x_2)$$

(note: not sure about my translation, can you say "contractive" in english?)

Homework Equations

Banach fixed-point theorem, mean value theorem for a), definition of norms

The Attempt at a Solution

I found it was not so easy to prove that the functions were strictly contractive or not, but here is a go:

$$\mbox{a) } || \frac{1}{2} \binom{sin x_1}{cos x_2} - \frac{1}{2} \binom{sin y_1}{cos y_2} ||_2 = \frac{1}{2} || \binom{sin x_1 - sin y_1}{cos x_2 - cos y_2} ||_2 \\ = \frac{1}{2} \sqrt{(sin x_1 - sin y_1)^2 + (cos x_2 - cos y_2)^2} \\ = \frac {1}{2} \sqrt{cos^2(α) (x_1 - y_1)^2 + sin^2 (β) (x_2 - y_2)^2} ≤ \frac{1}{2} \sqrt{(x_1 - y_1)^2 - (x_2 - y_2)^2} = \frac{1}{2} || \binom{x_1 - y_1}{x_2 - y_2} ||_2 \\ \mbox{(note that I made use of the mean value theorem to show the inequality)} \\ c < 1 \implies f(x_1,x_2) \mbox{ is strictly contractive.}$$

Is that correct? Am I understanding the Banach fixed-point theorem correctly? Now start the problems:

That looks good. You have shown it is a contraction map. That is just a definition, regardless of the Banach fixed-point theorem.

$$\mbox{b) } || \frac{1}{2} \binom{x_1 + x_2}{x_2} - \frac{1}{2} \binom{y_1 + y_2}{y_2} ||_2 = \frac{1}{2} \sqrt{(x_1 + x_2 - y_1 - y_2)^2 + (x_2 - y_2)^2} \\ = \frac{1}{2} \sqrt{x_1^2 + 2x_1 x_2 + x_2^2 - 2x_1y_1 + 2x_1y_2 - 2 x_2y_1 + 2x_2y_2 + y_1^2 - 2y_1y_2 + y_2^2 + (x_2 - y_2)^2} \\ = \frac{1}{2} \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_2 + y_2)^2 + 2(x_1x_2 + x_1y_2 - x_2y_1 - y_1y_2)}$$

Ehem... It seems to me that it would require a c bigger than 1 to make the inequality of the Banach theorem work, therefore the function would not be strictly contractive. On another hand the ½ makes it hard to prove... Is my intuition correct? Any clue about how to prove it if so?

If you suspect it isn't true, find a couple of points $X=(x_1,x_2)$ and $Y=(y_1,y_2)$ where $\|f(X) - f(Y)\| > \| X-Y\|$. With a little fiddling around, that shouldn't be difficult.

I will look at the third one if I have time.

 

[Samy_A]

And for c) I don't have a clue really. According to the definition in my teacher's script:

$$c \cdot || \binom{x_1 - y_1}{x_2 - y_2} ||_{\infty} = c \cdot max | \binom{x_1 - y_1}{x_2 - y_2} | \\ \mbox{and} \\ \frac{1}{2} || \binom{x_1 + x_2 - y_1 - y_2}{x_2 - y_2} ||_{\infty} = \frac{1}{2} \cdot max | \binom{x_1 + x_2 - y_1 - y_2}{x_2 - y_2} |$$

But what does that mean? It seems to me like those maximums are not existing! Is that the case? If yes, what can I conclude? If no, I must have misunderstood how to determine the maximum of a function in ℝ²...or the definition of a maximum norm altogether!

For c), since $f$ is linear, you can simplify it somewhat by looking at $||f(x)||_\infty =\frac12 ||(x_1+x_2,x_2)||_\infty$. As @LCKurtz suggested for b), you can rather easily find values for $(x_1,x_2)$ that answer the question whether $f$ is a contraction or not.

 

[JulienB]

@LCKurtz @Samy_A Hi guys and thanks for your answers!

If you suspect it isn't true, find a couple of points $X=(x_1,x_2)$ and $Y=(y_1,y_2)$ where $\|f(X) - f(Y)\| > \| X-Y\|$. With a little fiddling around, that shouldn't be difficult.

As @LCKurtz suggested for b), you can rather easily find values for $(x_1,x_2)$ that answer the question whether $f$ is a contraction or not.

I've been trying to find values of x and y for which ∥f(X)−f(Y)∥>∥X−Y∥ but I couldn't! Could you? I tried to put the highest value for x₁ and the smallest for y₁ but the ½ makes that I always get smaller than ∥X−Y∥! I now think it is a contraction, but I must work harder to prove it (if I'm right). I'll get back to you tomorrow.

For c), since $f$ is linear, you can simplify it somewhat by looking at $||f(x)||_\infty =\frac12 ||(x_1+x_2,x_2)||_\infty$.

I did that, and to my mind the maximum of |(x₁ + x₂ - y₁ - y₂, x₂ - y₂)| is |(∞,∞)|... Same thing for the maximum of |(x₁ - y₁, x₂ - y₂)|. That would be the case for example if x has an infinitely high value for both x₁ and x₂ while y = (0, 0), right?


Thanks a lot for your help, I appreciate it.


Julien.

 

[Samy_A]

@LCKurtz @Samy_A Hi guys and thanks for your answers!





I've been trying to find values of x and y for which ∥f(X)−f(Y)∥>∥X−Y∥ but I couldn't! Could you? I tried to put the highest value for x₁ and the smallest for y₁ but the ½ makes that I always get smaller than ∥X−Y∥! I now think it is a contraction, but I must work harder to prove it (if I'm right). I'll get back to you tomorrow..

There may be a good reason why you can't find values of x and y for which ∥f(X)−f(Y)∥>∥X−Y∥
But, to prove $f$ is not a contraction, it is sufficient to find a $x \neq (0,0)$ such that $∥f(x)∥_\infty=∥x∥_\infty$.

I did that, and to my mind the maximum of |(x₁ + x₂ - y₁ - y₂, x₂ - y₂)| is |(∞,∞)|... Same thing for the maximum of |(x₁ - y₁, x₂ - y₂)|. That would be the case for example if x has an infinitely high value for both x₁ and x₂ while y = (0, 0), right?

Of course the maximum of the norms over the whole $\mathbb R^2$ is $\infty$. But that is not what you have to check.
You have (for c)) to compare $∥f(x)∥_\infty$ with $∥x∥_\infty$.
Let's take an example: $x=(x_1,x_2)=(1,2)$.
Then $∥x∥_\infty = \max(1,2)=2$, $∥f(x)∥_\infty =\frac12\max(1+2,2)=\frac12 . 3=1.5$.

 

[JulienB]

But, to prove $f$ is not a contraction, it is sufficient to find a $x \neq (0,0)$ such that $∥f(x)∥_\infty=∥x∥_\infty$.

Does that apply even when the norm specified for the problem is $$|| \cdot ||_2 ?$$

Of course the maximum of the norms over the whole $\mathbb R^2$ is $\infty$. But that is not what you have to check.
You have (for c)) to compare $∥f(x)∥_\infty$ with $∥x∥_\infty$.
Let's take an example: $x=(x_1,x_2)=(1,2)$.
Then $∥x∥_\infty = \max(1,2)=2$, $∥f(x)∥_\infty =\frac12\max(1+2,2)=\frac12 . 3=1.5$.

Aha that is already quite different from what I had in mind. I'm giving it a go now and I'll post again after that.


Thanks for those precious explanations!


Julien.

 

[JulienB]

$$|| f(x) - f(y) ||_{\infty} = \frac{1}{2} \cdot max |(x_1 + x_2 - y_1 - y_2, x_2 - y_2)| = \frac{1}{2} \cdot |x_1 - y_1 + x_2 - y_2| \\ ||x - y||_{\infty} = max \cdot |(x_1 - y_1, x_2 - y_2)| = \frac{1}{2} \cdot |x_1 - y_1 + x_2 - y_2| (\mbox{for } x_2 - y_2 = x_1 - y_1) \\ \implies c = 1 \implies \mbox{The function is not a contraction.}$$
Is that correct then?


Julien.

 

[Samy_A]

Does that apply even when the norm specified for the problem is $$|| \cdot ||_2 ?$$.

Yes.

By definition, a contraction mapping (as used in the Banach fixed-point theorem) $T: X \to X$, where $X$ is a normed space, satisfies $\forall x,y \in X: ||Tx-Ty|| \leq q||x-y||$, where $q \in [0,1[$.
Notice that $0\leq q<1$.
If $T$ is linear, this is really saying that $||T||<1$.

$$|| f(x) - f(y) ||_{\infty} = \frac{1}{2} \cdot max |(x_1 + x_2 - y_1 - y_2, x_2 - y_2)| = \frac{1}{2} \cdot |x_1 - y_1 + x_2 - y_2| \\ ||x - y||_{\infty} = max \cdot |(x_1 - y_1, x_2 - y_2)| = \frac{1}{2} \cdot |x_1 - y_1 + x_2 - y_2| (\mbox{for } x_2 - y_2 = x_1 - y_1) \\ \implies c = 1 \implies \mbox{The function is not a contraction.}$$
Is that correct then?

It certainly shows that $c \geq 1$, proving that the function is not a contraction.
It is correct that $c=1$. That's why you couldn't find $x,y$ satisfying $||f(x)-f(y)||_\infty>||x-y||_\infty$.

 

[JulienB]

@Samy_A Great! Thx a lot! For b) it is a bit farfetched but I think I got it too:

$$\frac{1}{2} \sqrt{|x_1 - y_1 + x_2 - y_2|^2 + |x_2 - y_2|^2} ≤ \frac{1}{2} \sqrt{|x_1 - y_1|^2 + 2|x_1 - y_1| \cdot |x_2 - y_2|^2 + 2|x_2 - y_2|^2} \\ ≤ \frac{1}{2} \sqrt{2|x_1 - y_1|^2 + 3|x_2 - y_2|^2} \\ ≤ \sqrt{\frac{3}{4} |x_1 - y_1|^2 + \frac{3}{4} |x_2 - y_2|^2} \\ = \frac{\sqrt{3}}{2} || \binom{x_1}{x_2} - \binom{y_1}{y_2} ||_2 \\ \implies \mbox{f is a contraction!}$$

At least I got a c smaller than 1! :D


Julien.