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

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

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

ניסוח פורמלי

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

נסמן $A_{n}=\{1,2,\cdots ,n\}$. אם לכל $i$ ב-$A_{n}$, קיימים $p_{i}\geq 0$, ו-$x_{i}$ המקיים $0<a\leq x_{i}\leq b$, אזי

$${\begin{aligned}\left(\sum _{i=1}^{n}p_{i}x_{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{aligned}}$$

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

אם, בניסוח הקודם, מתקיים גם $\sum _{i}p_{i}=1$, ניתן לפרש את המקדמים כהסתברויות. לכן, אם נגדיר משתנה מקרי $X$ המקבל את כל אחד מהערכים $x_{i}$ בהסתברות $p_{i}$, אזי

$${\begin{aligned}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)\\&\leq {\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{aligned}}$$

הביטוי שצריך למזער מקבל ערך מינימלי כאשר מחלקים את ההסתברויות בצורה הכי קרובה לקבוצות שוות הסתברות, כלומר, $\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)\leq {\frac {(a+b)^{2}}{4ab}}$$

והחסם הדוק.

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

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

תהי $A$ מטריצה הרמיטית חיובית לחלוטין שכל אחד מערכיה העצמיים, $\alpha _{i}$, מקיים

$$0<m\leq \alpha _{i}\leq M$$

עבור $m$ ו-$M$ חיוביים כלשהם. כמו כן, תהי $U$ מטריצה כלשהי המקיימת

$UU^{*}=I$,

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

בתנאים אלה,

$UA^{-1}U^{*}\leq {\frac {m+M}{mM}}I-{\frac {UAU^{*}}{mM}}\leq {\frac {\left(m+M\right)^{2}}{4mM}}\left(UAU^{*}\right)^{-1}$.

הדמיון לאי-שוויון קנטורוביץ' שהוצג לעיל מתגלה אם מכפילים מימין ב-$UAU^{*}$ את הביטויים בקצוות האי-שוויון, ומתקבל

$$\left(UA^{-1}U^{*}\right)\left(UAU^{*}\right)\leq {\frac {\left(m+M\right)^{2}}{4mM}}$$

הוכחה

פרק זה לוקה בחסר. אנא תרמו למכלול והשלימו אותו.

שימושים

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

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

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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