אי-שוויון קנטורוביץ'

במתמטיקה, אי-שוויון קנטורוביץ' הוא מקרה פרטי של אי-שוויון קושי-שוורץ, שהוא בעצמו הכללה של אי-שוויון המשולש, ונקרא על שם הכלכלן, המתמטיקאי וזוכה פרס נובל הסובייטי, לאוניד קנטורוביץ', שהיה חלוץ בתחום התכנון הליניארי.

בצורתו הפשוטה, אי-שוויון המשולש, קובע כי בכל משולש, סכום אורכי כל שתי צלעות יהיה שווה לאורך הצלע השלישית או גדול ממנה. במילים פשוטות, אי-שוויון קנטורוביץ׳ מתרגם את הרעיון הבסיסי של אי-שוויון המשולש למונחים ולסימונים של תכנון ליניארי.

ניסוח פורמלי

פורמלית, ניתן לבטא את אי-שוויון קנטורוביץ' כך:

נסמן $A_n=\{1,2,\cdots ,n\}$. אם לכל $i$ ב-$A_n$, קיימים $p_i\ge 0$, ו-$x_i$ המקיים $0<a\le x_i\le b$, אזי

$$\begin{array}{cc}\left(\sum _{i=1}^n{p}_i{x}_i\right)\left(\sum _{i=1}^n\frac{p_i}{x_i}\right)& \le \frac{(a+b{)}^2}{4ab}{\left(\sum _{i=1}^n{p}_i\right)}^2\\ & -\frac{(b-a{)}^2}{4ab}\cdot min\{{(\sum _{i\in X}{p}_i-\sum _{j\in Y}{p}_j)}^2:X\cup Y=A_n,X\cap Y=\varnothing \}.\end{array}$$

ניסוח הסתברותי

אם, בניסוח הקודם, מתקיים גם $\sum _i{p}_i=1$, ניתן לפרש את המקדמים כהסתברויות. לכן, אם נגדיר משתנה מקרי $X$ המקבל את כל אחד מהערכים $x_i$ בהסתברות $p_i$, אזי $$\begin{array}{cc}E[X]\cdot E\left[\frac{1}{X}\right]& =\left(\sum _{i=1}^n{p}_i{x}_i\right)\left(\sum _{i=1}^n\frac{p_i}{x_i}\right)\\ & \le \frac{(a+b{)}^2}{4ab}{\left(\sum _{i=1}^n{p}_i\right)}^2\\ & -\frac{(b-a{)}^2}{4ab}\cdot \underset{Y\in A_n}{min}\left\{{(1-2\sum _{j\in Y}{p}_j)}^2\right\}\\ & =\frac{(a+b{)}^2}{4ab}-\frac{(b-a{)}^2}{4ab}\cdot \underset{Y\in A_n}{min}\{1-4\sum _{j\in Y}{p}_j+4{\left(\sum _{j\in Y}{p}_j\right)}^2\}\\ & =1-\frac{(b-a{)}^2}{ab}\cdot \underset{Y\in A_n}{min}\left\{\sum _{j\in Y}{p}_j(1-\sum _{j\in Y}{p}_j)\right\}.\end{array}$$

הביטוי שצריך למזער מקבל ערך מינימלי כאשר מחלקים את ההסתברויות בצורה הכי קרובה לקבוצות שוות הסתברות, כלומר, $\sum _{j\in Y}{p}_j\approx \frac{1}{2}$, ואז החסם יהיה הכי גדול. במילים אחרות, אם ניתן לחלק את $A_n$ באופן זר ל-$X$ ול-$Y$ כך שמתקיים $\sum _{i\in X}{p}_i=\sum _{j\in Y}{p}_j$, אז $$\left(\sum _{i=1}^n{p}_i{x}_i\right)\left(\sum _{i=1}^n\frac{p_i}{x_i}\right)\le \frac{(a+b{)}^2}{4ab}$$ והחסם הדוק.

ניסוח מטריציוני

מרשל ואולקין ניסחו גם גרסה מטריציונית לאי-שוויון קנטרוביץ':תבנית:הערה

תהי $A$ מטריצה הרמיטית חיובית לחלוטין שכל אחד מערכיה העצמיים, ${\alpha }_i$, מקיים $$0<m\le {\alpha }_i\le M$$ עבור $m$ ו-$M$ חיוביים כלשהם. כמו כן, תהי $U$ מטריצה כלשהי המקיימת

$U{U}^{\ast }=I$,

כאשר $U^{\ast }$ הוא הצמוד ההרמיטי של $U$, ו-$I$ היא מטריצת היחידה מסדר מתאים.

בתנאים אלה,

$U{A}^{-1}{U}^{\ast }\le \frac{m+M}{mM}I-\frac{UA{U}^{\ast }}{mM}\le \frac{{(m+M)}^2}{4mM}{\left(UA{U}^{\ast }\right)}^{-1}$.

הדמיון לאי-שוויון קנטורוביץ' שהוצג לעיל מתגלה אם מכפילים מימין ב-$UA{U}^{\ast }$ את הביטויים בקצוות האי-שוויון, ומתקבל $$\left(U{A}^{-1}{U}^{\ast }\right)\left(UA{U}^{\ast }\right)\le \frac{{(m+M)}^2}{4mM}$$

שימושים

אי-שוויון קנטורוביץ׳ משמש בראש ובראשונה באנליזת התכנסות, שם הוא מטיל חסם על קצב ההתכנסות של אלגוריתם הירידה התלולה ביותר (steepest descent) של קושי.

קישורים חיצוניים

• תבנית:MathWorld
• אי-שוויון קנטורוביץ', במילון תכנון מתמטי