Kantorowitsch-Ungleichung

Die Kantorowitsch-Ungleichung (englisch Kantorovich inequality) ist eine Ungleichung, die auf eine wissenschaftliche Publikation des sowjetischen Mathematikers Leonid Witaljewitsch Kantorowitsch aus dem Jahre 1948 zurückgeht und sowohl dem mathematischen Teilgebiet der Funktionalanalysis als auch dem der Numerischen Mathematik zugerechnet werden kann. Sie liefert eine Abschätzung für positiv definite und symmetrische Matrizen des reellen Matrizenrings ${\displaystyle {\mathbb {R} }^{n\times n}}$ und ist verwandt mit der Ungleichung von Schweitzer. Die Kantorowitsch-Ungleichung ist nicht zuletzt in der Numerischen Mathematik bedeutsam bei Konvergenzverhaltensuntersuchungen im Zusammenhang mit dem Gradientenverfahren und gab Anlass zu einer Anzahl von Verallgemeinerungen und weitergehenden Arbeiten.^[1][2][3][4]

Die Ungleichung lässt sich folgendermaßen darstellen:^[5][6]

Gegeben sei – für eine natürliche Zahl ${\displaystyle n>0}$ – eine positiv definite und symmetrische Matrix ${\displaystyle Q\in {\mathbb {R} }^{n\times n}}$, welche als kleinsten Eigenwert die positive reelle Zahl ${\displaystyle m}$ habe und als größten die positive reelle Zahl ${\displaystyle M}$.

Dann gilt für alle ${\displaystyle x\in {\mathbb {R} }^{n}\setminus \{0\}}$ die Ungleichung

${\displaystyle {\frac {{\langle x,x\rangle }^{2}}{{\langle x,Qx\rangle }\cdot {\langle x,Q^{-1}x\rangle }}}\geq 4{\frac {M\cdot m}{(M+m)^{2}}}}$ .^[7]

Anders ausgedrückt – und über das obige hinaus – gilt, wenn

${\displaystyle \mathrm {cond} (Q):={\frac {M}{m}}}$^[8]

gesetzt wird:^[9]

${\displaystyle 1\leq {\frac {{\langle x,Qx\rangle }\cdot {\langle x,Q^{-1}x\rangle }}{{\langle x,x\rangle }^{2}}}\leq {\frac {{\bigl (}1+\mathrm {cond} (Q){\bigr )}^{2}}{4\cdot \mathrm {cond} (Q)}}}$ ,

und dabei ist die obere Abschätzung in dem Sinne scharf, dass die Gleichung

${\displaystyle \sup _{x\in {\mathbb {R} }^{n}\setminus \{0\}}{\frac {{\langle x,Qx\rangle }\cdot {\langle x,Q^{-1}x\rangle }}{{\langle x,x\rangle }^{2}}}={\frac {(1+\mathrm {cond} (Q))^{2}}{4\cdot \mathrm {cond} (Q)}}}$

besteht.

In der Fachliteratur zur Theorie der konvexen Funktionen wird die Kantorowitsch-Ungleichung in einen weiteren Kontext gestellt und hier auch in der allgemeineren Version angegeben:^[10]

Gegeben seien ein kompaktes Intervall ${\displaystyle [a,b]\subset \mathbb {R} }$ sowie zwei nichtnegative konvexe Funktionen ${\displaystyle f\;,\;g\;\colon [a,b]\to [0,{+\infty })}$.

Weiterhin gegeben seien eine natürliche Zahl ${\displaystyle n>0}$ und dazu reelle Zahlen ${\displaystyle x_{1},\ldots ,x_{n}\in [a,b]}$ sowie positive reelle Zahlen ${\displaystyle p_{1},\ldots ,p_{n}}$ mit ${\displaystyle p_{1}+...+p_{n}=1}$ und darüber hinaus eine weitere positive reelle Zahl ${\displaystyle c}$.

Unter diesen Bedingungen gilt für die zugehörigen Konvexkombinationen

${\displaystyle K_{f}:=p_{1}f(x_{1})+\ldots +p_{n}f(x_{n})}$

und

${\displaystyle K_{g}:=p_{1}g(x_{1})+\ldots +p_{n}g(x_{n})}$

die allgemeine Ungleichung

${\displaystyle {\sqrt {K_{f}}}\cdot {\sqrt {K_{g}}}\leq {\frac {1}{2}}\cdot \max \left(cf(a)+{\frac {g(a)}{c}}\;,\;cf(b)+{\frac {g(b)}{c}}\right)}$  .

Ist für ${\displaystyle x\in [a,b]}$ sogar stets ${\displaystyle f(x)g(x)\geq 1}$, so gilt zusätzlich

${\displaystyle 1\leq {\sqrt {K_{f}}}\cdot {\sqrt {K_{g}}}}$  .

Insbesondere^[11] gelten im Falle ${\displaystyle a>0}$ stets die beiden Ungleichungen

${\displaystyle 1\leq {\bigl (}p_{1}x_{1}+\ldots +p_{n}x_{n}{\bigr )}\cdot {\bigl (}{\frac {p_{1}}{x_{1}}}+\ldots +{\frac {p_{n}}{x_{n}}}{\bigr )}\leq {\frac {1}{4}}\cdot \left({\sqrt {\frac {a}{b}}}+{\sqrt {\frac {b}{a}}}\right)^{2}}$  .

Es ist auf den ersten Blick nicht ersichtlich, wie obige Matrixungleichung aus der allgemeineren Darstellung folgt, aber das lässt sich in wenigen Worten sagen. Sei ${\displaystyle Q}$ positiv definit und symmetrisch mit Eigenwerten ${\displaystyle 0<m=x_{1}\leq \ldots \leq x_{n}=M}$. Dann gibt es eine orthogonale Matrix ${\displaystyle S}$, so dass ${\displaystyle S^{T}QS}$ die Diagonalmatrix mit Diagonalelementen ${\displaystyle x_{1}\ldots x_{n}}$ ist. Sei ${\displaystyle 0\not =z\in \mathbb {R} ^{n}}$ beliebig und ${\displaystyle y=(y_{1},\ldots ,y_{n}):=S^{T}z}$. Mit ${\displaystyle \textstyle p_{i}:={\frac {y_{i}^{2}}{\|y\|^{2}}}}$ gilt ${\displaystyle p_{1}+\ldots +p_{n}=1}$ und

${\displaystyle p_{1}x_{1}+\ldots +p_{n}x_{n}={\frac {1}{\|y\|^{2}}}(y_{1}x_{1}y_{1}+\ldots +y_{n}x_{n}y_{n})={\frac {1}{\|y\|^{2}}}\langle y,S^{T}QSy\rangle ={\frac {1}{\|Sy\|^{2}}}\langle Sy,QSy\rangle ={\frac {1}{\|z\|^{2}}}\langle z,Qz\rangle }$.

Da ${\displaystyle Q^{-1}}$ ebenfalls positiv definit und symmetrisch ist mit Eigenwerten ${\displaystyle \textstyle {\frac {1}{x_{1}}}\ldots {\frac {1}{x_{n}}}}$ und da auch ${\displaystyle S^{T}Q^{-1}S}$ die Diagonalmatrix mit Diagonalelementen ${\displaystyle \textstyle {\frac {1}{x_{1}}}\ldots {\frac {1}{x_{n}}}}$ ist, erhalten wir auch

${\displaystyle {\frac {p_{1}}{x_{1}}}+\ldots +{\frac {p_{n}}{x_{n}}}={\frac {1}{\|z\|^{2}}}\langle z,Q^{-1}z\rangle }$.

Die allgemeinere Darstellung der Ungleichung liefert also mit ${\displaystyle a=m}$ und ${\displaystyle b=M}$

${\displaystyle {\frac {1}{\|z\|^{4}}}\langle z,Qz\rangle \langle z,Q^{-1}z\rangle ={\bigl (}p_{1}x_{1}+\ldots +p_{n}x_{n}{\bigr )}\cdot {\bigl (}{\frac {p_{1}}{x_{1}}}+\ldots +{\frac {p_{n}}{x_{n}}}{\bigr )}\leq {\frac {1}{4}}\cdot \left({\sqrt {\frac {m}{M}}}+{\sqrt {\frac {M}{m}}}\right)^{2}={\frac {1}{4}}\cdot \left({\frac {m}{M}}+{\frac {M}{m}}+2\right)={\frac {1}{4}}{\frac {(m+M)^{2}}{m\cdot M}}}$.

Das ist genau obige Matrixungleichung, wenn man beide Seiten noch invertiert. Daher verallgemeinert die zweite gegebene Version der Kantorowitsch-Ungleichung tatsächlich obige Matrixungleichung.

• Owe Axelsson: Iterative Solution Methods. Cambridge University Press, Cambridge 1994, ISBN 0-521-44524-8 (MR1276069). 
• Wilhelm Forst, Dieter Hoffmann: Optimization — Theory and Practice (= Springer Undergraduate Texts in Mathematics and Technology). Springer Verlag, New York, Dordrecht, Heidelberg, London 2010, ISBN 978-0-387-78976-7, doi:10.1007/978-0-387-78976-4 (MR2675748). 
• Werner Greub, Werner Rheinboldt: On a generalization of an inequality of L. V. Kantorovich. In: Proceedings of the American Mathematical Society. Band 10, 1959, S. 407–415, doi:10.2307/2032857 (MR0105028). 
• L. V. Kantorovič: Functional analysis and applied mathematics. (Russisch). In: Uspehi Mat. Nauk (N.S.). Band 3, 1948, S. 89–185 (MR0027947). 
• Peter Kosmol: Methoden zur numerischen Behandlung nichtlinearer Gleichungen und Optimierungsaufgaben (= Teubner Studienbücher Mathematik). B. G. Teubner Verlag, Stuttgart 1989, ISBN 3-519-02085-8 (MR1002944). 
• D. S. Mitrinović: Analytic Inequalities. In cooperation with P. M. Vasić (= Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete. Band 165). Springer Verlag, Berlin (u. a.) 1970, ISBN 3-540-62903-3 (MR0274686). 
• A. Wayne Roberts, Dale E. Varberg: Convex Functions (= Pure and Applied Mathematics. Band 57). Academic Press, New York, San Francisco, London 1973 (MR0442824). 
• W. G. Strang: On the Kantorovich inequality. In: Proceedings of the American Mathematical Society. Band 11, 1960, S. 60, doi:10.2307/2034801 (MR0112046). 

• Eric W. Weisstein: Kantorovich inequality. In: MathWorld (englisch).

1. ↑ Peter Kosmol: Methoden zur numerischen Behandlung nichtlinearer Gleichungen und Optimierungsaufgaben. 1989, S. 110–112
2. ↑ D. S. Mitrinović: Analytic Inequalities. 1970, S. 60–65
3. ↑ Owe Axelsson: Iterative Solution Methods. 1994, S. 95 ff.
4. ↑ Wilhelm Forst, Dieter Hoffmann: Optimization — Theory and Practice. 2010, S. 100 ff.
5. ↑ Kosmol, op. cit., S. 110
6. ↑ Kosmol, op. cit., S. 101
7. ↑ ${\displaystyle \langle \cdot ,\cdot \rangle }$ ist das Skalarprodukt des ${\displaystyle {\mathbb {R} }^{n}}$.
8. ↑ In der englischsprachigen Fachliteratur wird die Größe ${\displaystyle \mathrm {cond} (Q)}$ auch als condition number of ${\displaystyle Q}$ bezeichnet.
9. ↑ Axelsson, op. cit., S. 96
10. ↑ A. Wayne Roberts, Dale E. Varberg: Convex Functions. 1973, S. 208–209
11. ↑ Mit ${\displaystyle f(x)=x}$ und ${\displaystyle g(x)={\frac {1}{x}}}$ und ${\displaystyle c={\frac {1}{\sqrt {ab}}}}$!