Tschebyschow-Summenungleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel behandelt die arithmetische Tschebyschow-Ungleichung. Für die statistische Tschebyschow-Ungleichung siehe Tschebyschow-Ungleichung.

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

Definition[Bearbeiten]

Sie besagt , dass für monoton gleich geordnete n-Tupel reeller Zahlen

a_1 \geq a_2 \geq \cdots \geq a_n

und

b_1 \geq b_2 \geq \cdots \geq b_n,

die Beziehung

n \sum_{i=1}^n a_ib_i \geq \left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right).

gilt. Sind a_i und b_i hingegen entgegengesetzt geordnet, also beispielsweise

a_1 \geq a_2 \geq \cdots \geq a_n

und

b_1 \leq b_2 \leq \cdots \leq b_n,

so gilt die Ungleichung in umgekehrte Richtung:


n \sum_{i=1}^n a_ib_i \leq \left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right).

Man beachte, dass im Gegensatz zu vielen anderen Ungleichungen keine Voraussetzungen für die Vorzeichen von a_i und b_i notwendig sind.

Beweise[Bearbeiten]

Beweis aus Umordnungs-Ungleichung[Bearbeiten]

Die Tschebyschew-Summenungleichung lässt sich aus der Umordnungs-Ungleichung ableiten. Multipliziert man die rechte Seite aus, so ergibt sich

\left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)=\left(a_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n\right)

+\left(a_1b_2 + a_2 b_3 + \dots +a_{n-1}b_{n}+a_nb_1\right)
+\left(a_1b_3 + a_2 b_4 + \dots +a_{n-1}b_{1}+a_nb_2\right)
+\dots
+\left(a_1b_n + a_2 b_1 + \dots +a_{n-1}b_{n-2}+a_nb_{n-1}\right)

Wegen der Umordnungs-Ungleichung ist nun jede dieser n Summen (im Fall gleich geordneter Zahlen a_i und b_i) kleiner oder gleich \left(a_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n\right), insgesamt erhält man also genau die gewünschte Beziehung

\left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)\leq n\left(a_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n\right) .

Im Fall entgegengesetzt geordneter Zahlen a_i und b_i braucht die Umordnungs-Ungleichung nur in die umgekehrte Richtung angewendet werden.

Beweis mit vollständiger Induktion[Bearbeiten]

Die Tschebyschew-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

\left(a_{n+1}+\sum_{i=1}^{n} a_i\right)\left(b_{n+1}+\sum_{i=1}^{n} b_i\right)=a_{n+1}b_{n+1} + \sum_{i=1}^n\left(a_{n+1}b_i + a_ib_{n+1}\right)+\left(\sum_{i=1}^{n} a_i\right)\left(\sum_{i=1}^{n} b_i\right).

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 a_i und b_i)

\left(a_{n+1}+\sum_{i=1}^{n} a_i\right)\left(b_{n+1}+\sum_{i=1}^{n} b_i\right)\leq a_{n+1}b_{n+1} + \sum_{i=1}^n\left(a_{i}b_i + a_{n+1}b_{n+1}\right)+n\sum_{i=1}^{n} a_ib_i
=a_{n+1}b_{n+1}+\sum_{i=1}^{n} a_ib_i  + n a_{n+1}b_{n+1}+ n\sum_{i=1}^{n} a_ib_i=(n+1)\sum_{i=1}^{n+1} a_ib_i.

Im Fall entgegengesetzt geordneter Zahlen a_i und b_i ist der Beweis analog.

Beweis aus Gleichungs-Formulierung[Bearbeiten]

Ein anderer Beweis ergibt sich direkt aus der Gleichung

 n\sum_{i=1}^n a_i b_i  - \left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)=\sum_{i=1}^n\sum_{k=i+1}^n (a_i-a_k)(b_i-b_k)=\frac{1}{2}\sum_{i=1}^n\sum_{k=1}^n (a_i-a_k)(b_i-b_k)

bzw. allgemeiner mit Gewichten w_i

 \sum_{i=1}^n w_i\sum_{i=1}^n w_ia_i b_i  - \left(\sum_{i=1}^n w_i a_i\right)\left(\sum_{i=1}^n w_i b_i\right)=\frac{1}{2}\sum_{i=1}^n\sum_{k=i}^n w_i w_k(a_i-a_k)(b_i-b_k).

Es gilt nämlich

 \sum_{i=1}^n w_i\sum_{k=1}^n w_ka_k b_k  - \left(\sum_{i=1}^n w_i a_i\right)\left(\sum_{k=1}^n w_kb_k\right) = \sum_{i=1}^n\sum_{k=1}^n \left(w_iw_ka_kb_k-w_iw_ka_ib_k\right).

Mit Umbenennung der Indizes ergibt sich

\sum_{i=1}^n\sum_{k=1}^n \left(w_iw_ka_kb_k-w_iw_ka_ib_k\right)=\sum_{k=1}^n\sum_{i=1}^n \left(w_iw_ka_ib_i-w_iw_ka_kb_i\right),

insgesamt also genau die Behauptung:

 \sum_{i=1}^n w_i\sum_{k=1}^n w_ka_k b_k  - \left(\sum_{i=1}^n w_i a_i\right)\left(\sum_{k=1}^n w_kb_k\right) = \frac{1}{2}\sum_{i=1}^n\sum_{k=1}^n w_iw_k\left(a_kb_k-a_ib_k+a_ib_i-a_kb_i\right)=\frac{1}{2}\sum_{i=1}^n\sum_{k=1}^n w_iw_k\left(a_i-a_k\right)\left(b_i-b_k\right).

Verallgemeinerung[Bearbeiten]

Die Tschebyschew-Summenungleichung lässt sich auch in der Form

\frac{1}{n} \sum_{i=1}^n a_ib_i \geq \left(\frac{1}{n}\sum_{i=1}^n a_i\right)\left(\frac{1}{n}\sum_{i=1}^n b_i\right).

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

a_j=\left(a_{j,1},\dots,a_{j,n}\right); j=1,\dots,m

mit

a_{j,1}\geq a_{j,2}\geq \dots \geq a_{j,n}\geq 0.

gilt

\frac{1}{n} \sum_{i=1}^n \prod_{j=1}^m a_{j,i} \geq \prod_{j=1}^m\left(\frac{1}{n}\sum_{i=1}^n a_{j,i}\right).

Der Beweis kann beispielsweise mit vollständiger Induktion nach m erfolgen, da ja für bezüglich i fallend geordnete nichtnegative Zahlen a_{j_i} auch deren Produkte

 \prod_{j=1}^m a_{j,1}\geq \prod_{j=1}^m a_{j,2}\geq \dots \geq \prod_{j=1}^m a_{j,n}\geq 0

fallend geordnet und nichtnegativ sind.

Varianten[Bearbeiten]

Sind f,g auf [0,1] gleichsinnig monoton und ist \omega:[0,1]\to\R_{\ge 0} eine Gewichtsfunktion, d.h. \int_0^1 \omega(x) dx=1 dann ist

\int_0^1 \omega(x) f(x) g(x) dx\ge \int_0^1 \omega(x) f(x) dx\;
\int_0^1 \omega(x) g(x) dx.

Zum Beweis integriert man die nichtnegative Funktion \omega(x) \omega(y) \Big(f(x)-f(y)\Big)\Big(g(x)-g(y)\Big) ausmultipliziert nach x und y jeweils von 0 bis 1. Dies lässt sich weiter verallgemeinern:

Sind f_0,...,f_n auf [0,1] gleichsinnig monoton und nichtnegativ dann ist

\int_0^1 \omega(x) \prod_{k=0}^n f_k \, dx
\ge \prod_{k=0}^n \int_0^1 \omega(x) f_k \, dx.

Und sind f_0,...,f_n auf [a,b] gleichsinnig monoton und nichtnegativ und ist \omega:[a,b]\to\R_{\ge 0} eine Gewichtsfunktion dann ist \int_a^b \omega(x) \prod_{k=0}^n f_k \, dx
\ge \frac{1}{(b-a)^{n-1}}\prod_{k=0}^n \int_a^b \omega(x) f_k \, dx.

Dies ergibt sich wenn man x durch \frac{x-a}{b-a} substituiert.

Siehe auch[Bearbeiten]