排序不等式

排序不等式是數學上的一條不等式。它可以推導出很多有名的不等式，例如算術幾何平均不等式(簡稱算幾不等式)，柯西不等式，和切比雪夫總和不等式。它是說：

如果

x_{1}\leq x_{2}\leq \cdots \leq x_{n}

，和

y_{1}\leq y_{2}\leq \cdots \leq y_{n}

是兩組實數。而

x_{\sigma (1)},\ldots ,x_{\sigma (n)}

是 $x_{1},\ldots ,x_{n}$ 的一個排列。排序不等式指出

x_{1}y_{1}+\cdots +x_{n}y_{n}\geq x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}\geq x_{n}y_{1}+\cdots +x_{1}y_{n}

。

以文字可以說成是順序和不小於亂序和，亂序和不小於逆序和。與很多不等式不同，排序不等式不需限定 $x_{i},\,y_{i}$ 的符號。

證明

排序不等式可以用數學歸納法證明。關鍵在於下列結果：

若 $x_{i}\leq x_{j},\,y_{i}\leq y_{j}$ ，則有

(x_{j}-x_{i})(y_{j}-y_{i})\geq 0

移項得出

x_{i}y_{i}+x_{j}y_{j}\geq x_{j}y_{i}+x_{i}y_{j}

。

重複以上步骤便可得出排序不等式。

我们设Si为b1,b2,...bn 原序列的前i个数的和，即Si=b1+b2+...bi；设S' 为打乱顺序后的序列，S'i表示乱序后的前i个数的和。所以有：Si<=S'i. 注意到 a[n]-a[n+1]<=0 则 Si*(a[n]-a[n+1])>=S'i*(a[n]-a[n+1])

$\sum _{k=1}^{N}a[k]*b[k]=\sum _{k=1}^{n-1}Sk*(a[k]-a[k+1])+Sn*an>=\sum _{k=1}^{n-1}S'k*(a[k]-a[k+1])+S'n*an(S'n=Sn)$ 得证

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.