Umordnungs-Ungleichung

Gegeben seien zwei n-Tupel reeller Zahlen x=(x1,…,xn)x=(x_1,\dots,x_n) und y=(y1,…,yn)y=(y_1,\dots,y_n) mit
x1≤⋯≤xnx_1 \leq \cdots \leq x_n\quad undy1≤⋯≤yn\quad y_1 \leq \cdots \leq y_n.
Das Tupel
xσ=(xσ(1),…,xσ(n))x_{\sigma}=\braceNT{x_{\sigma (1)}, \dots ,x_{\sigma (n)}}
sei eine Permutation des Tupels xx. Fasst man nun die n-Tupel als Vektoren auf und betrachtet deren Skalarprodukt, so besagt die Umordnungs-Ungleichung, dass
x1y1+⋯+xnyn≥xσ(1)y1+⋯+xσ(n)yn≥xny1+⋯+x1yn x_1y_1 + \cdots + x_ny_n \geq x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n \geq x_ny_1 + \cdots + x_1y_n\,
Das Skalarprodukt ist also maximal, wenn die Elemente der n-Tupel gleich geordnet sind, und minimal, wenn sie entgegengesetzt geordnet sind.
Man beachte, dass im Gegensatz zu vielen anderen Ungleichungen keine Voraussetzungen für die Vorzeichen von xix_i und yiy_i notwendig sind.

Beweise

Beweis mittels Vertauschungen

Die Beweisidee besteht darin, das kleinste ii, das σ(i)≠i\sigma (i)\neq i erfüllt und jenes jj mit i=σ(j)i=\sigma(j) zu betrachten. Dann sind also σ(i)>i\sigma(i)>i und j>ij>i, daher gilt xσ(j)≤xσ(i)x_{\sigma(j)}\leq x_{\sigma(i)} und yi≤yjy_i\leq y_j, also
(xσ(i)−xσ(j))(yi−yj)≤0(x_{\sigma(i)}-x_{\sigma(j)})(y_i-y_j)\leq 0
und daher
xσ(i)yi+xσ(j)yj≤xσ(j)yi+xσ(i)yj=xiyi+xσ(i)yj x_{\sigma (i)}y_i + x_{\sigma(j)}y_j \leq x_{\sigma (j)}y_i + x_{\sigma(i)}y_j = x_i y_i + x_{\sigma(i)}y_j\,
Solange also ein ii mit σ(i)≠i\sigma (i)\neq i existiert, lässt sich die Summe für gleich geordnete Tupel vergrößern.
Analog zeigt man, dass sich die Summe für entgegengesetzt geordnete Tupel verkleinern lässt, solange ein ii mit σ(i)≠i\sigma (i)\neq i existiert.

Beweis mit Induktion

Dieser Beweis lässt sich ausführlicher auch mit vollständiger Induktion führen. Für den Induktionsanfang n=2n=2 gibt es nur zwei Permutationen, es ist also zu zeigen, dass
x2y1+x1y2≤x1y1+x2y2 x_2y_1+x_1y_2\leq x_1y_1+x_2y_2\,
Das ist aber äquivalent zu
0≤(y1−y2)(x1−x2),0\leq (y_1-y_2)(x_1-x_2),
also zur Voraussetzung, dass beide Tupel gleich geordnet sind.
Im Induktionsschritt sei nun jj der Index mit σ(j)=n+1 \sigma(j)=n+1\, Der Fall j=n+1j=n+1 ist einfach zu behandeln, sei also j≠n+1 j\neq n+1\, Dann gilt
∑i=1n+1xσ(i)yi\sum\limits_{i=1}^{n+1}x_{\sigma(i)}y_i=∑i∉{j,n+1}xσ(i)yi+xσ(j)yj+xσ(n+1)yn+1 =\sum\limits_{i\notin\{j, n+1\} }x_{\sigma(i)}y_i + x_{\sigma(j)}y_j+x_{\sigma(n+1)}y_{n+1}=∑i∉{j,n+1}xσ(i)yi+xn+1yj+xσ(n+1)yn+1  =\sum\limits_{i\notin\{j, n+1\} }x_{\sigma(i)}y_i + x_{n+1}y_j+x_{\sigma(n+1)}y_{n+1}\,
Nun wendet man den im Induktionsanfang bewiesenen Fall n=2n=2 an und erhält
∑i∉{j,n+1}xσ(i)yi+xn+1yj+xσ(n+1)yn+1\sum\limits_{i\notin\{j, n+1\} }x_{\sigma(i)}y_i + x_{n+1}y_j+x_{\sigma(n+1)}y_{n+1}≤∑i∉{j,n+1}xσ(i)yi+xσ(n+1)yj+xn+1yn+1  \leq\sum\limits_{i\notin\{j, n+1\} }x_{\sigma(i)}y_i + x_{\sigma(n+1)}y_j+x_{n+1}y_{n+1}\,
Definiert man nun für i=1,…,ni=1,\dots,n die Permutation
τ(i)={σ(n+1)  fallsi=jσ(i) sonst\tau(i)=\begin{cases}\sigma(n+1) \qquad \, \, \textrm{falls} \quad i=j \\ \sigma(i) \, \textrm{sonst}\end{cases}
so ergibt sich aus der Induktionsvoraussetzung
∑i∉{j,n+1}xσ(i)yi+xσ(n+1)yj+xn+1yn+1\sum\limits_{i\notin\{j, n+1\} }x_{\sigma(i)}y_i + x_{\sigma(n+1)}y_j+x_{n+1}y_{n+1}=∑i∉{j,n+1}xτ(i)yi+xτ(j)yj+xn+1yn+1 =\sum\limits_{i\notin\{j, n+1\} }x_{\tau(i)}y_i + x_{\tau(j)}y_j+x_{n+1}y_{n+1}=∑i=1nxτ(i)yi+xn+1yn+1 =\sum\limits_{i=1}^n x_{\tau(i)}y_i+x_{n+1}y_{n+1}≤∑i=1nxiyi+xn+1yn+1, \leq\sum\limits_{i=1}^n x_{i}y_i+x_{n+1}y_{n+1},
also genau die Behauptung für das Maximum des Skalarprodukts.
Der Beweis für das Minimum des Skalarprodukts ist analog.

Anwendungen

Viele bekannte Ungleichungen lassen sich aus der Umordnungs-Ungleichung beweisen, beispielsweise die Ungleichung vom arithmetischen und geometrischen Mittel, Cauchy-Schwarzsche Ungleichung und die Tschebyschow-Summenungleichung.

Literatur

  • G. H. Hardy, J. E. Littlewood, G. Polya: Inequalities, Cambridge University Press (1952), Kapitel 10.2.
 
 

Ein Mathematiker, der nicht irgendwie ein Dichter ist, wird nie ein vollkommener Mathematiker sein.

Karl Weierstraß

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Umordnungs-Ungleichung 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