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

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

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

ניסוח פורמלי

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

נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_n = \{1,2,\cdots,n\}} . אם לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_n} , קיימים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i \ge 0} , ו-$x_{i}$ המקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 < a \leq x_i \leq b} , אזי

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} }

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

אם, בניסוח הקודם, מתקיים גם $\sum _{i}p_{i}=1$, ניתן לפרש את המקדמים כהסתברויות. לכן, אם נגדיר משתנה מקרי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} המקבל את כל אחד מהערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i} , אזי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} }

הביטוי שצריך למזער מקבל ערך מינימלי כאשר מחלקים את ההסתברויות בצורה הכי קרובה לקבוצות שוות הסתברות, כלומר, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j \in Y}p_j\approx\frac{1}{2}} , ואז החסם יהיה הכי גדול. במילים אחרות, אם ניתן לחלק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_n} באופן זר ל-$X$ ול-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y} כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i \in X}p_i=\sum_{j \in Y}p_j} , אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}} והחסם הדוק.

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

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

תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} מטריצה הרמיטית חיובית לחלוטין שכל אחד מערכיה העצמיים, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_i} , מקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 < m \le \alpha_i \le M} עבור $m$ ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} חיוביים כלשהם. כמו כן, תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} מטריצה כלשהי המקיימת

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle UU^*=I} ,

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U^*} הוא הצמוד ההרמיטי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} , ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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}$.

הדמיון לאי-שוויון קנטורוביץ' שהוצג לעיל מתגלה אם מכפילים מימין ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle UAU^*} את הביטויים בקצוות האי-שוויון, ומתקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(UA^{-1}U^*\right)\left(UAU^*\right) \le \frac{\left(m+M\right)^2}{4mM} }

הוכחה

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

שימושים

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

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

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

הערות שוליים

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

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