במתמטיקה , אי-שוויון קנטורוביץ' הוא מקרה פרטי של אי-שוויון קושי-שוורץ , שהוא בעצמו הכללה של אי-שוויון המשולש , ונקרא על שם הכלכלן , המתמטיקאי וזוכה פרס נובל הסובייטי, לאוניד קנטורוביץ' , שהיה חלוץ בתחום התכנון הליניארי .
בצורתו הפשוטה, אי-שוויון המשולש, קובע כי בכל משולש, סכום אורכי כל שתי צלעות יהיה שווה לאורך הצלע השלישית או גדול ממנה. במילים פשוטות, אי-שוויון קנטורוביץ׳ מתרגם את הרעיון הבסיסי של אי-שוויון המשולש למונחים ולסימונים של תכנון ליניארי .[1]
ניסוח פורמלי
עריכה
פורמלית, ניתן לבטא את אי-שוויון קנטורוביץ' כך:
נסמן
A
n
=
{
1
,
2
,
⋯
,
n
}
{\displaystyle A_{n}=\{1,2,\cdots ,n\}}
. אם לכל
i
{\displaystyle i}
ב-
A
n
{\displaystyle A_{n}}
, קיימים
p
i
≥
0
{\displaystyle p_{i}\geq 0}
, ו-
x
i
{\displaystyle x_{i}}
המקיים
0
<
a
≤
x
i
≤
b
{\displaystyle 0<a\leq x_{i}\leq b}
, אזי
(
∑
i
=
1
n
p
i
x
i
)
(
∑
i
=
1
n
p
i
x
i
)
≤
(
a
+
b
)
2
4
a
b
(
∑
i
=
1
n
p
i
)
2
−
(
b
−
a
)
2
4
a
b
⋅
min
{
(
∑
i
∈
X
p
i
−
∑
j
∈
Y
p
j
)
2
:
X
∪
Y
=
A
n
,
X
∩
Y
=
∅
}
.
{\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}}}
ניסוח הסתברותי
עריכה
אם, בניסוח הקודם, מתקיים גם
∑
i
p
i
=
1
{\displaystyle \sum _{i}p_{i}=1}
, ניתן לפרש את המקדמים כהסתברויות. לכן, אם נגדיר משתנה מקרי
X
{\displaystyle X}
המקבל את כל אחד מהערכים
x
i
{\displaystyle x_{i}}
בהסתברות
p
i
{\displaystyle p_{i}}
, אזי
E
[
X
]
⋅
E
[
1
X
]
=
(
∑
i
=
1
n
p
i
x
i
)
(
∑
i
=
1
n
p
i
x
i
)
≤
(
a
+
b
)
2
4
a
b
(
∑
i
=
1
n
p
i
)
2
−
(
b
−
a
)
2
4
a
b
⋅
min
Y
∈
A
n
{
(
1
−
2
∑
j
∈
Y
p
j
)
2
}
=
(
a
+
b
)
2
4
a
b
−
(
b
−
a
)
2
4
a
b
⋅
min
Y
∈
A
n
{
1
−
4
∑
j
∈
Y
p
j
+
4
(
∑
j
∈
Y
p
j
)
2
}
=
1
−
(
b
−
a
)
2
a
b
⋅
min
Y
∈
A
n
{
∑
j
∈
Y
p
j
(
1
−
∑
j
∈
Y
p
j
)
}
.
{\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}}}
הביטוי שצריך למזער מקבל ערך מינימלי כאשר מחלקים את ההסתברויות בצורה הכי קרובה לקבוצות שוות הסתברות, כלומר,
∑
j
∈
Y
p
j
≈
1
2
{\displaystyle \sum _{j\in Y}p_{j}\approx {\frac {1}{2}}}
, ואז החסם יהיה הכי גדול. במילים אחרות, אם ניתן לחלק את
A
n
{\displaystyle A_{n}}
באופן זר ל-
X
{\displaystyle X}
ול-
Y
{\displaystyle Y}
כך שמתקיים
∑
i
∈
X
p
i
=
∑
j
∈
Y
p
j
{\displaystyle \sum _{i\in X}p_{i}=\sum _{j\in Y}p_{j}}
, אז
(
∑
i
=
1
n
p
i
x
i
)
(
∑
i
=
1
n
p
i
x
i
)
≤
(
a
+
b
)
2
4
a
b
{\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}}}
והחסם הדוק.
ניסוח מטריציוני
עריכה
מרשל ואולקין ניסחו גם גרסה מטריציונית לאי-שוויון קנטרוביץ':[2]
תהי
A
{\displaystyle A}
מטריצה הרמיטית חיובית לחלוטין שכל אחד מערכיה העצמיים ,
α
i
{\displaystyle \alpha _{i}}
, מקיים
0
<
m
≤
α
i
≤
M
{\displaystyle 0<m\leq \alpha _{i}\leq M}
עבור
m
{\displaystyle m}
ו-
M
{\displaystyle M}
חיוביים כלשהם. כמו כן, תהי
U
{\displaystyle U}
מטריצה כלשהי המקיימת
U
U
∗
=
I
{\displaystyle UU^{*}=I}
,
כאשר
U
∗
{\displaystyle U^{*}}
הוא הצמוד ההרמיטי של
U
{\displaystyle U}
, ו-
I
{\displaystyle I}
היא מטריצת היחידה מסדר מתאים.
בתנאים אלה,
U
A
−
1
U
∗
≤
m
+
M
m
M
I
−
U
A
U
∗
m
M
≤
(
m
+
M
)
2
4
m
M
(
U
A
U
∗
)
−
1
{\displaystyle UA^{-1}U^{*}\leq {\frac {m+M}{mM}}I-{\frac {UAU^{*}}{mM}}\leq {\frac {\left(m+M\right)^{2}}{4mM}}\left(UAU^{*}\right)^{-1}}
.
הדמיון לאי-שוויון קנטורוביץ' שהוצג לעיל מתגלה אם מכפילים מימין ב-
U
A
U
∗
{\displaystyle UAU^{*}}
את הביטויים בקצוות האי-שוויון, ומתקבל
(
U
A
−
1
U
∗
)
(
U
A
U
∗
)
≤
(
m
+
M
)
2
4
m
M
{\displaystyle \left(UA^{-1}U^{*}\right)\left(UAU^{*}\right)\leq {\frac {\left(m+M\right)^{2}}{4mM}}}
קישורים חיצוניים
עריכה
הערות שוליים
עריכה