Documents

30 views

Cauchy-Schwarz

Cauchy-Schwarz. (Cauchy-Schwarz inequality) For any a1,…,an, and any b1,…bn. When n=1, LHS <= RHS. Proof by induction (on n):. When n=2, want to show. Consider. Cauchy-Schwarz. (Cauchy-Schwarz inequality) For any a1,…,an, and any b1,…bn. Induction step: assume true for <=n, prove n+1.
of 12
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Transcript
Cauchy-Schwarz(Cauchy-Schwarz inequality) For any a1,…,an, and any b1,…bn When n=1, LHS <= RHS.Proof by induction (on n):When n=2, want to showConsiderCauchy-Schwarz(Cauchy-Schwarz inequality) For any a1,…,an, and any b1,…bn Induction step: assume true for <=n, prove n+1.inductionby P(2)Cauchy-Schwarz(Cauchy-Schwarz inequality) For any a1,…,an, and any b1,…bn Exercise: proveAnswer: Let bi = 1 for all i, and plug into Cauchy-SchwarzThis has a very nice application in graph theory that hopefully we’ll see.Geometric Interpretation(Cauchy-Schwarz inequality) For any a1,…,an, and any b1,…bn Interpretation:
  • The left hand side computes the inner
  • product of the two vectors
  • If we rescale the two vectors to be of
  • length 1, then the left hand side is <= 1
  • The right hand side is always 1.
  • abArithmetic Mean – Geometric Mean Inequality(AM-GM inequality) For any a1,…,an, Interesting induction (on n):
  • Prove P(2)
  • Prove P(n) -> P(2n)
  • Prove P(n) -> P(n-1)
  • Arithmetic Mean – Geometric Mean Inequality(AM-GM inequality) For any sequence of non-negative numbers a1,…,an, Interesting induction (on n):
  • Prove P(2)
  • Want to showConsiderArithmetic Mean – Geometric Mean Inequality(AM-GM inequality) For any sequence of non-negative numbers a1,…,an, Interesting induction (on n):
  • Prove P(n) -> P(2n)
  • inductionby P(2)Arithmetic Mean – Geometric Mean Inequality(AM-GM inequality) For any sequence of non-negative numbers a1,…,an, Interesting induction (on n):
  • Prove P(n) -> P(n-1)
  • Letthe average of the first n-1 numbers.Arithmetic Mean – Geometric Mean Inequality(AM-GM inequality) For any sequence of non-negative numbers a1,…,an, Interesting induction (on n):
  • Prove P(n) -> P(n-1)
  • LetGeometric Interpretation(AM-GM inequality) For any sequence of non-negative numbers a1,…,an, Interpretation:
  • Think of a1, a2, …, an are the side lengths of a high-dimensional rectangle.
  • Then the right hand side is the volume of this rectangle.
  • The left hand side is the volume of the square with the same total side length.
  • The inequality says that the volume of the square is always not smaller.
  • e.g.Arithmetic Mean – Geometric Mean Inequality(AM-GM inequality) For any sequence of non-negative numbers a1,…,an, Exercise: What is an upper bound on?
  • Set a1=n and a2=…=an=1, then the upper bound is 2 – 1/n.
  • Set a1=a2=√n and a3=…=an=1, then the upper bound is 1 + 2/√n – 2/n.
  • Set a1=…=alogn=2 and ai=1 otherwise, then the upper bound is 1 + log(n)/n
  • Good Book
    Advertisement
    Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks