上頁　1│2│3　已在最後一頁

蓋理論(Theory of Majorization)及其在不等式上的應用 （第 3 頁）

楊重駿;楊照崑

 


首頁 | 搜尋

．原載於數學傳播第六卷第四期

•註釋
•對外搜尋關鍵字
 
蓋理論及其應用

我們首先討論在什麼情形下

\begin{displaymath}g(y_1)+g(y_2)\leq g(x_1)+g(x_2)\eqno{(6)}\end{displaymath}

為了使不等式「公平」起見，我們希望

\begin{displaymath}x_1+x_2=y_1+y_2\eqno{(7)}\end{displaymath}

否則 $g(1)+g(2)\leq g(100)+g(200)$ 就沒有太多的價值了。從凸函數的性質，若我們可以找到一個 $0<\lambda<1$，且

\begin{displaymath}y_1=\lambda x_1+(1-\lambda)x_2\quad,\quad y_2=(1-\lambda)x_1+\lambda x_2 \eqno{(8)}\end{displaymath}

則(6)與(7)都顯然成立，從圖2知，(8)式表示 y1,y2 比 x1 與 x2 要緊湊些。


圖2

但要把圖形2的「緊湊」觀念推到 n 度空間，即具 n 個分量的向量(x1,x2,…,xn) 及 (y1,y2,…,yn) 就不太容易了。但有的情形很顯然，譬如說

\begin{displaymath} y_i=\overline{x}=\frac{x_1+x_2+\cdots+x_n}{n} \; , \quad i=1,2,\cdots,n \end{displaymath}


圖1

則由圖3看出 ($\overline{x}$,$\overline{x}$,…,$\overline{x}$) 顯然比 (y1,y2,…,yn) 要緊湊。 因而我們有第(4)式，即

\begin{displaymath}n\phi(x)\leq\sum_{i=1}^n\phi(x_i)\end{displaymath}

蕭爾想到了這樣一個比較兩向量 X=(x1,x2,…,xn)，Y=(y1,y2,…,yn) 緊湊性的方法。

定義:
令 X = (x1,x2,…,xn)，Y = (y1,y2,…,yn) 為兩漸減序列，即

\begin{displaymath}\begin{array}{l} x_1\geq x_2\geq x_3\geq \cdots\cdots\geq x_n\\ y_1\geq y_2\geq y_3\geq \cdots\cdots\geq y_n \end{array}\end{displaymath}

且

\begin{displaymath}x_1+x_2+\cdots\cdots+x_n=y_1+y_2+\cdots\cdots+y_n\end{displaymath}

我們說X可以「蓋得住」Y，或Y比X更緊湊，如果

\begin{displaymath}\begin{array}{rcl} y_1&\leq&x_1\\ y_1+y_2&\leq&x_1+x_2\\ y_... ...1+y_2+\cdots+y_{n-1}&\leq&x_1+x_2+\cdots+x_{n-1}\\ \end{array}\end{displaymath}

一般我們用 Y<X 表示之。

我們所採的定義雖只適用於兩個漸減的序列，但在一般情形下的不等式，幾乎都與序列 x1,x2,…,xn, y1,y2,…,yn 的排列無關；所以我們所採的定義並不失其一般性。舉個例子，X=(3, 2, 1), Y=(2.5, 2.3, 1.2)，則

3+2+1=2.5+2.3+2.1

且

\begin{displaymath}\begin{array}{rcl} 3&\geq&2.5\\ 3+2&\geq&2.5+2.3\\ \end{array}\end{displaymath}

故 Y<X。 又很顯然的 $Y=(\overline{x},\overline{x},\cdots,\overline{x})$ $< X = (x_1, x_2, \cdots, x_n)$。讀者不妨試試證明此一事實。（以後許多地方要用到此一事實）

註:
我們在文中有時把 (x1,x2,…,xn) 以序列看之。 有時也視 $(x_1,x_2,\cdots,x_n) \in R^n$，當向量看之。在當序列看時， x1,x2,… 等可稱為元素，在當向量看時，x1,x2,… 等以分量稱之。 我們稱 X 及 Y 的兩個元素或分量相同時，是除了數值本身外，且具有相同的秩序或位置。例如 (3,2,1,5,3) 及 (3,1,2,5,3) 兩向量有 3 對元素相同。

下面的定理把蓋的觀念與凸函數的關係做了一個引線。

定理4
令X=(x1,x2,…,xn),Y=(y1,y2,…,yn)為兩實數列，且X與Y只有兩個元素不相同，設其位置在i及j上(即xk=yk除非k=i及k=j)，則下列條件(i)與(ii)互為充要條件。

(i)Y<X
(ii)有一個實數α;$0<\alpha <1$ 且 $y_i=\alpha x_i+(1-\alpha)x_j$, $y_j=(1-\alpha )x_i+\alpha x_j$

證:
因i與j可為任何位置。因此我們不妨假設

\begin{displaymath} x_1\geq x_2\geq\cdots\geq x_i\geq\cdots\geq x_j\geq\cdots\geq x_n \end{displaymath}

我們先由(i)推導出(ii)。因除了在 i,j 位置上的元素皆相同，又 Y<X， 則必須有

\begin{displaymath}\begin{array}{rcl} x_i&>&y_i\\ x_i+y_j&=&y_i+y_j\\ \end{array}\end{displaymath}

亦即 $x_i>y_i\geq y_j>x_j$。若令

\begin{displaymath}\alpha=\frac{y_i-x_j}{x_i-x_j}\end{displaymath}

則 $0<\alpha <1$ 並很容易由代入 α 之值而證得(ii)。

現若(ii)成立。則由於在i之前的x,y皆相等，故對k<i而言

\begin{displaymath}x_1+x_2+\cdots +x_k=y_1+y_2+\cdots +y_k\end{displaymath}

又在 k=i 時

\begin{displaymath}\begin{array}{rcl} &&y_1+y_2+\cdots\cdots +y_i\\ &=&x_1+x_2+... ...+\alpha x_i+(1-\alpha)x_i\\ &=&x_1+x_2+\cdots +x_i \end{array}\end{displaymath}

這種不等的情形一直到 $k\geq j$ 時又恢復了等式（因為 yi+yj=xi+xj），故本定理得證。

定理5
設實數列 $X=(x_1,x_2,\cdots ,x_n)$， $Y=(y_1,y_2,\cdots ,y_n)$中，X 與 Y 不全相同並且 Y<X， 則我們可找到一個數列 Z=(z1,z2,…,zn) 具備下列三個性質:

(1) Y<Z<X(即Y<Z,Z<X)
(2) Z與Y比X與Y至少多一個相同的元素
(3) Z與X至多只有兩個元素不同。

證:
因本定理的證明與 X,Y 之元素的排列無關，不妨假定 X,Y 已成漸減排列， 即

\begin{eqnarray*} &X:&x_1\geq x_2\geq x_3\geq\cdots\cdots \geq x_n\\ &Y:&y_1\geq y_2\geq y_3\geq\cdots\cdots \geq y_n \end{eqnarray*}


因 Y<X，故 $\sum_{i=1}^n x_i=\sum_{i=1}^n y_i$，又因 xi 與 yi 不全相同， 必有一個 k 使得 xk>yk 及一個 l 使得 xl<yl，取 i 為最大的 k 有 xk>yk 的性質者， j 為最小的 l>i 並滿足 xl<yl 者，則 X,Y，與 i,j 的關係如下：

\begin{eqnarray*} X:&&x_1\geq x_2\geq x_3\geq\cdots\geq x_{i-1}\geq x_i\\ &&\ge... ...}\selectfont \char 16}}}\geq y_j\geq y_{j+1}\geq\cdots\cdots y_n \end{eqnarray*}


即當 k=i+1,i+2,…,j-1 時 yk=xk(否則 i 可向右移或 j 向左移與所取的 i 及 j 性質不符)， 又 xt>yt, $\forall t\leq　i$及ys>xs, $\forall s\geq　j$。令

\begin{displaymath}\delta=\min(x_i-y_i,y_j-x_j)\end{displaymath}


\begin{displaymath}\alpha=\frac{\delta}{x_i-x_j}\end{displaymath}

由於 $x_i>y_i\geq y_j>x_j$，可知 $\alpha >0$，但 $\alpha <1$。 令 zk 與 xk 除 k=i,j 時皆相同，又 $z_i=x_i-\delta$, $z_j=x_j+\delta$。由 α 之定義，可得

\begin{displaymath}\begin{array}{lcl} z_i&=&x_i-\delta =x_i-\alpha (x_i-x_j)\\ ... ...x_j\\ z_j&=&x_j+\delta=\alpha x_i+(1-\alpha)x_j\\ \end{array}\end{displaymath}

由定理3得知 Z<X，因 Z 與 X 除了 i,j 位置上的元素外，皆相同，故很容易求出

\begin{displaymath} \sum_{t=l}^kz_t\geq \sum_{t=l}^ky_t \qquad t=1,2,\cdots,n-1 \end{displaymath}

及

\begin{displaymath}\sum_{t=l}^nz_t= \sum_{t=l}^ny_t\end{displaymath}

故 Y<Z，即(1)得證。根據 δ 之定義，若 $\delta =x_i-y_i$則zi=yi，若 $\delta =y_j-x_j$ 則zj=yj，故(2)成立。因X與Z除i，j 位置外均相同，(3)亦因此證得。

系理:
依上面定理，我們可以找到 z1,z2,…,$z_s(s\leq n)$ 個數列，使得

(1) $Y=z_0<z_1<z_2<\cdots <z_s<z_{s+1}=X$

(2)所有zi與zi+1之間( $i=0,1,2,\cdots\cdots,s$)至多有兩個不同的元素。

證:
因 X 與 Y 至多有的 n 個不同的元素，由上定理(2)中知 $s\leq n$。

現在我們可以敘述及證明本篇最主要的結果了。

定理6(蕭爾定理Schur's Theorem)
設 f(x) 為區間 [a,b] 上的一凸函數，又 X=(x1,x2,…,xn), Y=(y1,y2,…,yn) 為兩數列， 其元素皆在 [a,b] 中，若 Y<X 則

\begin{displaymath}\sum_{k=1}^n f(y_n)\leq \sum_{k=1}^n f(x_n)\eqno{(9)}\end{displaymath}

證:
由定理5的系理，我們只需證明 Y 與 X 只有兩個元素不相同的情形就行了。（否則我們可由 z1,z2,…,zs 一直推下去） 令 xi,xj 與 yi,yj 各不相同而其餘的 x,y 皆相同，則(9)變成了

\begin{displaymath}f(y_i)+f(y_j)\leq f(x_i)+f(x_j)\eqno(10)\end{displaymath}

因 Y<X，故由定理4知，我們總可找到一個 α, $0<\alpha <1$且

\begin{displaymath}y_i=\alpha x_i+(1-\alpha )x_j\end{displaymath}


\begin{displaymath}y_j=(1-\alpha )x_i+\alpha x_j\end{displaymath}

由 f 的凸性質，我們有

\begin{displaymath}\begin{array}{rcl} f(y_i)+f(y_j)&=&f(\alpha x_i+(1-\alpha )x_... ...\alpha )f(x_i)+\alpha f(x_j)\\ &=&f(x_i)+f(x_j)\\ \end{array}\end{displaymath}

故(10)式成立。定理6因此得證。

現在我們看看定理6的一些用途。

例1：
令 $g(x)=-\log x$, $0<x<\infty$ 為一凸函數，又由事實

\begin{displaymath} \begin{eqalign} & (\overline{x},\overline{x},\cdots,\overlin... ...\overline{x}=\frac{x_1+x_2+\cdots +x_n}{n},x_i>0) \end{eqalign}\end{displaymath}

故由定理6可得

\begin{displaymath}\sum_{i=1}^n(-\log\overline{x})\leq\sum_{i=1}^n(-\log x_i)\end{displaymath}

即

\begin{displaymath}\overline{x}\geq (x_1x_2\cdots x_n)^{\frac{1}{n}}\end{displaymath}

這就是算術平均大於幾何平均的證明。

例2：
x1,x2,…,xn 為 n 個正數， $\overline{x}=\frac{x_1+x_2+\cdots+x_n}{n}$，則因 $f(x)=\frac{1}{x}$為$(0,\infty)$上的一凸函數，故由 $(\overline{x},\overline{x},\cdots,\overline{x})< (x_1,x_2,\cdots,x_n)$及定理6可得

\begin{displaymath}\sum_{i=1}^n\frac{1}{\overline{x}}\leq \sum_{i=1}^n\frac{1}{x_i}\end{displaymath}

即

\begin{displaymath}\sum \frac{1}{x_i}\geq\frac{n}{\overline{x}}=\frac{n^2}{x_1+x_2+\cdots\cdots +x_n}\end{displaymath}

例3：
設 x1,x2,…,xn 為滿足 0<xi<1; $i=1,2,\cdots,n$ 之 n 個數，且 $\sum_{i=1}^nx_i=1$，則 $\sum_{i=1}^n\frac{x_i}{1-x_i}\geq\frac{n}{n-1}$
證:
我們先證 $f(x)=\frac{x}{1-x}$ 在 (0,1) 間為凸函數，我們只需驗證 $\forall x_1,x_2 \in (0,1)$

\begin{displaymath}f(\frac{x_1+x_2}{2})\leq \frac{1}{2}f(x_1)+\frac{1}{2}f(x_2)\end{displaymath}

此相等於

\begin{displaymath}\frac{\frac{x_1+x_2}{2}}{1-\frac{(x_1+x_2)}{2}}\leq\frac{1}{2}(\frac{x_1}{1-x_1}+\frac{x_2}{1-x_2})\end{displaymath}

化簡得

\begin{displaymath}(x_1+x_2)^2-4x_1x_2\geq 0\end{displaymath}

此式恒成立，故 f 為一凸函數。

又因 $\frac{1}{n}=\overline{x}$ 及 $(\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n}) < (x_1,x_2<\cdots,x_n)$ 由定理6可得

\begin{displaymath}n\frac{\frac{1}{n}}{1-\frac{1}{n}}\leq\sum_{i=1}^n\frac{x_i}{1-x_i}\end{displaymath}

即

\begin{displaymath} \sum_{i=1}^n\frac{x_i}{1-x_i}\geq\frac{n}{n-1} \end{displaymath}

例4：
設 xi, $i=1,2,\cdots,n$ 為 n 個實數，a 為一定數。令 $\overline{x}=\frac{\sum_{i=1}^nx_i}{n}$ 試證

\begin{displaymath}\sum_{i=1}^n\vert x_i-a\vert\geq n\vert\overline{x}-1\vert\end{displaymath}

證:
顯然由圖形可知f(x)=|x-a|為一凸函數及 $(\overline{x},\overline{x},\cdots,\overline{x})< (x_1,x_2,\cdots,x_n)$ ，依據定理6原式立即得證。

例5：
因 $-\sin x$ 在區間 (0,π) 之間為凸函數，又在一三角形中，若以 A,B,C 表三頂角，則很容易得知

\begin{displaymath}(\frac{3}{\pi},\frac{3}{\pi},\frac{3}{\pi})<(A,B,C)<(\pi,0,0)\end{displaymath}

故由定理6可得

\begin{displaymath}-3\sin \frac{\pi}{3}\leq -(\sin A+\sin B+\sin C)\leq 0\end{displaymath}

即

\begin{displaymath}0\leq \sin A+\sin B+\sin C \leq 3\frac{\sqrt{3}}{2} \end{displaymath}

同理可證得

\begin{displaymath}1\leq \sin \frac{A}{2}+\sin \frac{B}{2}+\sin \frac{C}{2} \leq 3\sin\frac{\pi}{6}=\frac{3}{2}\end{displaymath}

例6：
令 $f(x)=-\log \sin x$, $0<x<\pi$ 則 f(x) 為凸函數的結論可由

\begin{displaymath}\sin x_1\sin x_2\leq \sin^2\frac{x_1+x_2}{2},\quad x_1,x_2\in(0,\pi)\end{displaymath}

即事實

\begin{displaymath} \cos (x_1-x_2)\leq 1 \mbox{ {\fontfamily{cwM0}\fontseries{m}... ...\char 41}{\fontfamily{cwM0}\fontseries{m}\selectfont \char 1}} \end{displaymath}

又由於 $(\frac{\pi}{3},\frac{\pi}{3},\frac{\pi}{3})<(A,B,C)$依定理6可得

\begin{displaymath}-\log (\sin\frac{\pi}{3})^3\leq-(\log\sin A+\log\sin B+\log\sin C)\end{displaymath}

即

\begin{displaymath}\sin A\sin B\sin C\leq\frac{3\sqrt{3}}{8}\end{displaymath}

蕭爾定理的應用可以推廣到很多超出本篇程度的不等式，有許多是在統計、矩陣等方面的應用。我們不在此多作介紹。希望讀者能從本篇得到開啟蓋理論寶庫的鑰匙，進而能對不等式理論作更深入的瀏覽及貢獻。

1. G.H. Hardy, J.E. Littlewood, and G. Polya,《Inequalities》, Cambridge University Press,1934.
2. A. Marshall and I. Olkin,《Inequalities: Theory of Majorization and its Applications》, Academic Press, 1979.

   

上頁　1│2│3　已在最後一頁

 回頁首
 
（若有指正、疑問……，可以在此 留言 或 寫信 給我們。）
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯：鄧惠文 最後修改日期：5/26/2002