排序不等式

维基百科,自由的百科全书
跳转至: 导航搜索

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

如果

x_1 \le x_2 \le \cdots \le x_n,和
y_1 \le y_2 \le \cdots \le y_n

是兩組實數。而

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

x_1, \ldots , x_n的一個排列。排序不等式指出

x_1y_1 + \cdots + x_ny_n \ge x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n \ge x_ny_1 + \cdots + x_1y_n

以文字可以說成是順序和不小於亂序和,亂序和不小於逆序和。與很多不等式不同,排序不等式不需限定x_i, \, y_i的符號。

證明[编辑]

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

x_i \le x_j, \, y_i \le y_j,則有

(x_j - x_i)(y_j - y_i) \ge 0

移項得出

x_i y_i + x_j y_j \ge x_j y_i + x_i y_j

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