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

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

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

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

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

<math display="block">
\begin{align}
\left( \sum_{i=1}^n p_ix_i \right ) \left (\sum_{i=1}^n \frac{p_i}{x_i} \right)
& \leq \frac{(a+b)^2}{4ab} \left (\sum_{i=1}^n p_i \right )^2 \\
& \qquad -\frac{(b-a)^2}{4ab} \cdot \min \left\{ \left (\sum_{i \in X}p_i-\sum_{j \in Y}p_j \right )^2\,:\, {X \cup Y=A_n},{X \cap Y=\varnothing} \right\}.
\end{align}
</math>

=== ניסוח הסתברותי ===
אם, בניסוח הקודם, מתקיים גם <math>\sum_i p_i = 1</math>, ניתן לפרש את המקדמים כהסתברויות. לכן, אם נגדיר משתנה מקרי <math>X</math> המקבל את כל אחד מהערכים <math>x_i</math> בהסתברות <math>p_i</math>, אזי
<math display="block">
\begin{align}
E[X]\cdot E\left[\frac{1}{X}\right] & = \left( \sum_{i=1}^n p_ix_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 \\
& \qquad -\frac{(b-a)^2}{4ab} \cdot \min_{Y\in A_n} \left\{ \left (1-2\sum_{j \in Y}p_j \right )^2\right\} \\
& = \frac{(a+b)^2}{4ab} -\frac{(b-a)^2}{4ab} \cdot \min_{Y\in A_n} \left\{ 1 - 4\sum_{j \in Y}p_j + 4\left(\sum_{j \in Y}p_j\right)^2 \right\} \\
& = 1 - \frac{(b-a)^2}{ab} \cdot \min_{Y\in A_n}\left\{\sum_{j \in Y}p_j\left(1 - \sum_{j \in Y}p_j\right)\right\}.
\end{align}
</math>

הביטוי שצריך למזער מקבל ערך מינימלי כאשר מחלקים את ההסתברויות בצורה הכי קרובה לקבוצות שוות הסתברות, כלומר, <math>\sum_{j \in Y}p_j\approx\frac{1}{2}</math>, ואז החסם יהיה הכי גדול. במילים אחרות, אם ניתן לחלק את <math>A_n</math> באופן זר ל-<math>X</math> ול-<math>Y</math> כך שמתקיים <math>\sum_{i \in X}p_i=\sum_{j \in Y}p_j</math>, אז
<math display="block">\left( \sum_{i=1}^n p_ix_i \right ) \left (\sum_{i=1}^n \frac{p_i}{x_i} \right)
\leq \frac{(a+b)^2}{4ab}</math>
והחסם הדוק.

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

תהי <math>A</math> מטריצה הרמיטית חיובית לחלוטין שכל אחד מערכיה העצמיים, <math>\alpha_i</math>, מקיים
<math display="block">0 < m \le \alpha_i \le M</math>
עבור <math>m</math> ו-<math>M</math> חיוביים כלשהם. כמו כן, תהי <math>U</math> מטריצה כלשהי המקיימת
:<math>UU^*=I</math>,
כאשר <math>U^*</math> הוא הצמוד ההרמיטי של <math>U</math>, ו-<math>I</math> היא מטריצת היחידה מסדר מתאים.

בתנאים אלה,
:<math>UA^{-1}U^* \le \frac{m+M}{mM}I - \frac{UAU^*}{mM} \le \frac{\left(m+M\right)^2}{4mM} \left(UAU^*\right)^{-1}</math>.
הדמיון לאי-שוויון קנטורוביץ' שהוצג לעיל מתגלה אם מכפילים מימין ב-<math>UAU^*</math> את הביטויים בקצוות האי-שוויון, ומתקבל
<math display="block">\left(UA^{-1}U^*\right)\left(UAU^*\right) \le \frac{\left(m+M\right)^2}{4mM} </math>

== הוכחה ==

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

== קישורים חיצוניים ==
* 
* [https://web.archive.org/web/20040807003154/http://carbon.cudenver.edu/~hgreenbe/glossary/index.php?page=K.html אי-שוויון קנטורוביץ'], במילון תכנון מתמטי

== הערות שוליים ==

קנטורוביץ'
קטגוריה:משפטים באנליזה