Tschebyschow-Summenungleichung

Die Tschebyschow-Summenungleichung (nach Pafnuti Lwowitsch Tschebyschow) ist eine bekannte Ungleichung der Mathematik. In älteren Transkriptionen findet sich gelegentlich noch die Schreibweise Tschebyscheff.

Definition

Sie besagt , dass für monoton gleich geordnete n-Tupel reeller Zahlen
a1≥a2≥⋯≥ana_1 \geq a_2 \geq \cdots \geq a_n
und
b1≥b2≥⋯≥bn,b_1 \geq b_2 \geq \cdots \geq b_n,
die Beziehung
n∑i=1naibi≥(∑i=1nai)(∑i=1nbi) n \sum\limits_{i=1}^n a_ib_i \geq \braceNT{\sum\limits_{i=1}^n a_i}\braceNT{\sum\limits_{i=1}^n b_i}\,
gilt. Sind aia_i und bib_i hingegen entgegengesetzt geordnet, also beispielsweise
a1≥a2≥⋯≥ana_1 \geq a_2 \geq \cdots \geq a_n
und
b1≤b2≤⋯≤bn,b_1 \leq b_2 \leq \cdots \leq b_n,
so gilt die Ungleichung in umgekehrte Richtung:
n∑i=1naibi≤(∑i=1nai)(∑i=1nbi) n \sum\limits_{i=1}^n a_ib_i \leq \braceNT{\sum\limits_{i=1}^n a_i}\braceNT{\sum\limits_{i=1}^n b_i}\,
Man beachte, dass im Gegensatz zu vielen anderen Ungleichungen keine Voraussetzungen für die Vorzeichen von aia_i und bib_i notwendig sind.

Beweise

Beweis aus Umordnungs-Ungleichung

Die Tschebyschow-Summenungleichung lässt sich aus der Umordnungs-Ungleichung ableiten. Multipliziert man die rechte Seite aus, so ergibt sich
(∑i=1nai)(∑i=1nbi)=(a1b1+a2b2+⋯+an−1bn−1+anbn)\braceNT{\sum\limits_{i=1}^n a_i}\braceNT{\sum\limits_{i=1}^n b_i}=\braceNT{a_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n}
+(a1b2+a2b3+⋯+an−1bn+anb1)+\braceNT{a_1b_2 + a_2 b_3 + \dots +a_{n-1}b_{n}+a_nb_1}
+(a1b3+a2b4+⋯+an−1b1+anb2)+\braceNT{a_1b_3 + a_2 b_4 + \dots +a_{n-1}b_{1}+a_nb_2}
+…+\dots
+(a1bn+a2b1+⋯+an−1bn−2+anbn−1)+\braceNT{a_1b_n + a_2 b_1 + \dots +a_{n-1}b_{n-2}+a_nb_{n-1}}
Wegen der Umordnungs-Ungleichung ist nun jede dieser nn Summen (im Fall gleich geordneter Zahlen aia_i und bib_i) kleiner oder gleich (a1b1+a2b2+⋯+an−1bn−1+anbn)\braceNT{a_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n}, insgesamt erhält man also genau die gewünschte Beziehung
(∑i=1nai)(∑i=1nbi)\braceNT{\sum\limits_{i=1}^n a_i}\braceNT{\sum\limits_{i=1}^n b_i}≤n(a1b1+a2b2+⋯+an−1bn−1+anbn) \leq n\braceNT{a_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n} .
Im Fall entgegengesetzt geordneter Zahlen aia_i und bib_i braucht die Umordnungs-Ungleichung nur in die umgekehrte Richtung angewendet werden.

Beweis mit vollständiger Induktion

Die Tschebyschow-Summenungleichung lässt sich auch mit vollständiger Induktion und Anwendung der Umordnungs-Ungleichung für den einfachsten Fall mit zwei Summanden beweisen. Der Induktionsanfang ist einfach zu führen. Im Induktionsschritt betrachtet man nun
(an+1+∑i=1nai)(bn+1+∑i=1nbi)\braceNT{a_{n+1}+\sum\limits_{i=1}^{n} a_i}\braceNT{b_{n+1}+\sum\limits_{i=1}^{n} b_i}=an+1bn+1 =a_{n+1}b_{n+1} +∑i=1n(an+1bi+aibn+1) + \sum\limits_{i=1}^n\braceNT{a_{n+1}b_i + a_ib_{n+1}}+(∑i=1nai)(∑i=1nbi) +\braceNT{\sum\limits_{i=1}^{n} a_i}\braceNT{\sum\limits_{i=1}^{n} b_i}.
Wendet man nun auf den mittleren Summanden die Umordnungs-Ungleichung für zwei Summanden und auf den letzten Summanden die Induktionsvoraussetzung an, so ergibt sich (im Fall gleich geordneter Zahlen aia_i und bib_i)
(an+1+∑i=1nai)(bn+1+∑i=1nbi)\braceNT{a_{n+1}+\sum\limits_{i=1}^{n} a_i}\braceNT{b_{n+1}+\sum\limits_{i=1}^{n} b_i}≤an+1bn+1 \leq a_{n+1}b_{n+1} +∑i=1n(aibi+an+1bn+1) + \sum\limits_{i=1}^n\braceNT{a_{i}b_i + a_{n+1}b_{n+1}}+n∑i=1naibi +n\sum\limits_{i=1}^{n} a_ib_i
=an+1bn+1=a_{n+1}b_{n+1}+∑i=1naibi +\sum\limits_{i=1}^{n} a_ib_i +nan+1bn+1+n∑i=1naibi=(n+1)∑i=1n+1aibi  + n a_{n+1}b_{n+1}+ n\sum\limits_{i=1}^{n} a_ib_i=(n+1)\sum\limits_{i=1}^{n+1} a_ib_i\,
Im Fall entgegengesetzt geordneter Zahlen aia_i und bib_i ist der Beweis analog.

Beweis aus Gleichungs-Formulierung

Ein anderer Beweis ergibt sich direkt aus der Gleichung
n∑i=1naibi n\sum\limits_{i=1}^n a_i b_i −(∑i=1nai)(∑i=1nbi) - \braceNT{\sum\limits_{i=1}^n a_i}\braceNT{\sum\limits_{i=1}^n b_i}=∑i=1n∑k=i+1n(ai−ak)(bi−bk) =\sum\limits_{i=1}^n\sum\limits_{k=i+1}^n (a_i-a_k)(b_i-b_k)=12∑i=1n∑k=1n(ai−ak)(bi−bk) =\dfrac{1}{2}\sum\limits_{i=1}^n\sum\limits_{k=1}^n (a_i-a_k)(b_i-b_k)
bzw. allgemeiner mit Gewichten wiw_i
∑i=1nwi∑i=1nwiaibi \sum\limits_{i=1}^n w_i\sum\limits_{i=1}^n w_ia_i b_i −(∑i=1nwiai)(∑i=1nwibi) - \braceNT{\sum\limits_{i=1}^n w_i a_i}\braceNT{\sum\limits_{i=1}^n w_i b_i}=12∑i=1n∑k=inwiwk(ai−ak)(bi−bk) =\dfrac{1}{2}\sum\limits_{i=1}^n\sum\limits_{k=i}^n w_i w_k(a_i-a_k)(b_i-b_k).
Es gilt nämlich
∑i=1nwi∑k=1nwkakbk \sum\limits_{i=1}^n w_i\sum\limits_{k=1}^n w_ka_k b_k −(∑i=1nwiai)(∑k=1nwkbk) - \braceNT{\sum\limits_{i=1}^n w_i a_i}\braceNT{\sum\limits_{k=1}^n w_kb_k} =∑i=1n∑k=1n(wiwkakbk−wiwkaibk) = \sum\limits_{i=1}^n\sum\limits_{k=1}^n \braceNT{w_iw_ka_kb_k-w_iw_ka_ib_k}.
Mit Umbenennung der Indizes ergibt sich
∑i=1n∑k=1n(wiwkakbk−wiwkaibk)\sum\limits_{i=1}^n\sum\limits_{k=1}^n \braceNT{w_iw_ka_kb_k-w_iw_ka_ib_k}=∑k=1n∑i=1n(wiwkaibi−wiwkakbi) =\sum\limits_{k=1}^n\sum\limits_{i=1}^n \braceNT{w_iw_ka_ib_i-w_iw_ka_kb_i},
insgesamt also genau die Behauptung:
∑i=1nwi∑k=1nwkakbk \sum\limits_{i=1}^n w_i\sum\limits_{k=1}^n w_ka_k b_k −(∑i=1nwiai)(∑k=1nwkbk) - \braceNT{\sum\limits_{i=1}^n w_i a_i}\braceNT{\sum\limits_{k=1}^n w_kb_k} =12∑i=1n∑k=1nwiwk(akbk−aibk+aibi−akbi) = \dfrac{1}{2}\sum\limits_{i=1}^n\sum\limits_{k=1}^n w_iw_k\braceNT{a_kb_k-a_ib_k+a_ib_i-a_kb_i}=12∑i=1n∑k=1nwiwk(ai−ak)(bi−bk) =\dfrac{1}{2}\sum\limits_{i=1}^n\sum\limits_{k=1}^n w_iw_k\braceNT{a_i-a_k}\braceNT{b_i-b_k}.

Verallgemeinerung

Die Tschebyschow-Summenungleichung lässt sich auch in der Form
1n∑i=1naibi≥(1n∑i=1nai)(1n∑i=1nbi) \dfrac{1}{n} \sum\limits_{i=1}^n a_ib_i \geq \braceNT{\dfrac{1}{n}\sum\limits_{i=1}^n a_i}\braceNT{\dfrac{1}{n}\sum\limits_{i=1}^n b_i}\,
schreiben. In dieser Form lässt sie sich auch auf mehr als zwei gleich geordnete n-Tupel verallgemeinern, wobei die betrachteten Zahlen allerdings größer oder gleich Null sein müssen: Für
aj=(aj,1,…,aj,n)a_j=\braceNT{a_{j,1},\dots,a_{j,n}}; j=1,…,m j=1,\dots,m
mit
aj,1≥aj,2≥⋯≥aj,n≥0 a_{j,1}\geq a_{j,2}\geq \dots \geq a_{j,n}\geq 0\,
gilt
1n∑i=1n∏j=1maj,i≥∏j=1m(1n∑i=1naj,i) \dfrac{1}{n} \sum\limits_{i=1}^n \prod\limits_{j=1}^m a_{j,i} \geq \prod\limits_{j=1}^m\braceNT{\dfrac{1}{n}\sum\limits_{i=1}^n a_{j,i}}\,
Der Beweis kann beispielsweise mit vollständiger Induktion nach mm erfolgen, da ja für bezüglich ii fallend geordnete nichtnegative Zahlen ajia_{j_i} auch deren Produkte
∏j=1maj,1≥∏j=1maj,2≥⋯≥∏j=1maj,n≥0 \prod\limits_{j=1}^m a_{j,1}\geq \prod\limits_{j=1}^m a_{j,2}\geq \dots \geq \prod\limits_{j=1}^m a_{j,n}\geq 0
fallend geordnet und nichtnegativ sind.

Varianten

Sind f,gf,g auf [0,1][0,1] gleichsinnig monoton und ist ω:[0,1]→R≥0\omega:[0,1]\to\R_{\ge 0} eine Gewichtsfunktion, d.h. ∫01ω(x)dx=1\int\limits_0^1 \omega(x) dx=1 dann ist ∫01ω(x)f(x)g(x)dx≥∫01ω(x)f(x)dx ∫01ω(x)g(x)dx\int\limits_0^1 \omega(x) f(x) g(x) dx\ge \int\limits_0^1 \omega(x) f(x) dx \, \int\limits_0^1 \omega(x) g(x) dx. Zum Beweis integriert man die nichtnegative Funktion ω(x)ω(y)(f(x)−f(y))(g(x)−g(y))\omega(x) \omega(y) \braceNT{f(x)-f(y)}\braceNT{g(x)-g(y)} ausmultipliziert nach x und y jeweils von 0 bis 1. Dies lässt sich weiter ausbauen. Sind f0,…,fnf_0,\dots ,f_n auf [0,1][0,1] gleichsinnig monoton und nichtnegativ dann ist ∫01ω(x)∏k=0nfk dx≥∏k=0n∫01ω(x)fk dx\int\limits_0^1 \omega(x) \prod\limits_{k=0}^n f_k \, dx \ge \prod\limits_{k=0}^n \int\limits_0^1 \omega(x) f_k \, dx. Und sind f0,…,fnf_0,\dots ,f_n auf [a,b][a,b] gleichsinnig monoton und nichtnegativ und ist ω:[a,b]→R≥0\omega:[a,b]\to\R_{\ge 0} eine Gewichtsfunktion dann ist ∫abω(x)∏k=0nfk dx≥1(b−a)n−1∏k=0n∫abω(x)fk dx\int\limits_a^b \omega(x) \prod\limits_{k=0}^n f_k \, dx \ge \dfrac{1}{(b-a)^{n-1}}\prod\limits_{k=0}^n \int\limits_a^b \omega(x) f_k \, dx. Dies ergibt sich wenn man x durch x−ab−a\dfrac{x-a}{b-a} substituiert.

Siehe auch

  • Tschebyschow-Ungleichung
 
 

Gott existiert, weil die Mathematik widerspruchsfrei ist, und der Teufel existiert, weil wir das nicht beweisen können.

Andre Weil

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Tschebyschow-Summenungleichung aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Reelle Zahlen