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

Maximum norm and Banach fixed-point theorem

  • Thread starter JulienB
  • Start date
  • #1
408
12

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 ƒ: ℝ2 → ℝ2 are strictly contractive in relation to the given norms:
[tex]\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)
[/tex]

(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:

[tex] \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.}
[/tex]

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

[tex] \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)}
[/tex]

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:

[tex]
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} |
[/tex]

But what does that mean? It seems to me like those maximums are not existing! :wideeyed: 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 ℝ2...or the definition of a maximum norm altogether!

Thank you in advance for your answers.


Julien.
 

Answers and Replies

  • #2
408
12
Nobody has an idea? :smile:
 
  • #3
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,519
734

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 ƒ: ℝ2 → ℝ2 are strictly contractive in relation to the given norms:
[tex]\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)
[/tex]

(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:

[tex] \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.}
[/tex]

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.

[tex] \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)}
[/tex]

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.
 
  • #4
Samy_A
Science Advisor
Homework Helper
1,241
510
And for c) I don't have a clue really. According to the definition in my teacher's script:

[tex]
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} |
[/tex]

But what does that mean? It seems to me like those maximums are not existing! :wideeyed: 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 ℝ2...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.
 
  • #5
408
12
@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 x1 and the smallest for y1 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 |(x1 + x2 - y1 - y2, x2 - y2)| is |(∞,∞)|... Same thing for the maximum of |(x1 - y1, x2 - y2)|. That would be the case for example if x has an infinitely high value for both x1 and x2 while y = (0, 0), right?


Thanks a lot for your help, I appreciate it.


Julien.
 
  • #6
Samy_A
Science Advisor
Homework Helper
1,241
510
@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 x1 and the smallest for y1 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 |(x1 + x2 - y1 - y2, x2 - y2)| is |(∞,∞)|... Same thing for the maximum of |(x1 - y1, x2 - y2)|. That would be the case for example if x has an infinitely high value for both x1 and x2 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##.
 
  • #7
408
12
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 [tex]|| \cdot ||_2 ?[/tex]

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.
 
  • #8
408
12
[tex]
|| 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.} [/tex]
Is that correct then?


Julien.
 
Last edited:
  • #9
Samy_A
Science Advisor
Homework Helper
1,241
510
Does that apply even when the norm specified for the problem is [tex]|| \cdot ||_2 ?[/tex].
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##.

[tex]
|| 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.} [/tex]
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##.
 
Last edited:
  • #10
408
12
@Samy_A Great! Thx a lot! For b) it is a bit farfetched but I think I got it too:

[tex]
\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!}
[/tex]

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


Julien.
 

Related Threads on Maximum norm and Banach fixed-point theorem

  • Last Post
Replies
24
Views
4K
Replies
2
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
525
Replies
7
Views
904
Replies
1
Views
859
Replies
2
Views
1K
Replies
13
Views
4K
Replies
12
Views
1K
  • Last Post
Replies
2
Views
2K
Top