במתמטיקה, אי-שוויון קנטורוביץ' הוא מקרה פרטי של אי-שוויון קושי-שוורץ, שהוא בעצמו הכללה של אי-שוויון המשולש, ונקרא על שם הכלכלן, המתמטיקאי וזוכה פרס נובל הסובייטי, לאוניד קנטורוביץ', שהיה חלוץ בתחום התכנון הליניארי.
בצורתו הפשוטה, אי-שוויון המשולש, קובע כי בכל משולש, סכום אורכי כל שתי צלעות יהיה שווה לאורך הצלע השלישית או גדול ממנה. במילים פשוטות, אי-שוויון קנטורוביץ׳ מתרגם את הרעיון הבסיסי של אי-שוויון המשולש למונחים ולסימונים של תכנון ליניארי.[1]
ניסוח פורמלי
פורמלית, ניתן לבטא את אי-שוויון קנטורוביץ' כך:
- נסמן
. אם לכל
ב-
, קיימים
, ו-
המקיים
, אזי
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac00c0d577396d054404f6ceb2750d7da5413237)
ניסוח הסתברותי
אם, בניסוח הקודם, מתקיים גם
, ניתן לפרש את המקדמים כהסתברויות. לכן, אם נגדיר משתנה מקרי
המקבל את כל אחד מהערכים
בהסתברות
, אזי
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9a3c62e0e5a67a0d4b52030ff3f79e37d590132)
הביטוי שצריך למזער מקבל ערך מינימלי כאשר מחלקים את ההסתברויות בצורה הכי קרובה לקבוצות שוות הסתברות, כלומר,
, ואז החסם יהיה הכי גדול. במילים אחרות, אם ניתן לחלק את
באופן זר ל-
ול-
כך שמתקיים
, אז
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/681140eb8b8ad9de29a54df696f1c3a6aafb9e12)
וה
חסם הדוק.
ניסוח מטריציוני
מרשל ואולקין ניסחו גם גרסה מטריציונית לאי-שוויון קנטרוביץ':[2]
תהי
מטריצה הרמיטית חיובית לחלוטין שכל אחד מערכיה העצמיים,
, מקיים
![{\displaystyle 0<m\leq \alpha _{i}\leq M}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ab4f14ea8ef1fa75ace7f849c779374c8ecd2fc)
עבור
![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
ו-
![{\displaystyle M}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
חיוביים כלשהם. כמו כן, תהי
![{\displaystyle U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025)
מטריצה כלשהי המקיימת
,
כאשר
הוא הצמוד ההרמיטי של
, ו-
היא מטריצת היחידה מסדר מתאים.
בתנאים אלה,
.
הדמיון לאי-שוויון קנטורוביץ' שהוצג לעיל מתגלה אם מכפילים מימין ב-
את הביטויים בקצוות האי-שוויון, ומתקבל
![{\displaystyle \left(UA^{-1}U^{*}\right)\left(UAU^{*}\right)\leq {\frac {\left(m+M\right)^{2}}{4mM}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c123689d1a41df3ce1396feb047efe255526c3ce)
הוכחה
שימושים
אי-שוויון קנטורוביץ׳ משמש בראש ובראשונה באנליזת התכנסות, שם הוא מטיל חסם על קצב ההתכנסות של אלגוריתם הירידה התלולה ביותר (steepest descent) של קושי.
קישורים חיצוניים
הערות שוליים
אי-שוויון קנטורוביץ'29770555