Kantorovich inequality

The Kantorovich inequality ( English Kantorovich inequality ) is an inequality that a scientific publication of the Soviet mathematician Leonid Kantorovich back in 1948 and both the mathematical branch of functional analysis as well as that of numerical mathematics can be attributed. It provides an estimate for positively definite and symmetric matrices of the real matrix ring and is related to Schweitzer's inequality . The Kantorowitsch inequality is significant in numerical mathematics in convergence behavior studies in connection with the gradient method and gave rise to a number of generalizations and further work . ${\displaystyle {\mathbb {R} }^{n\times n}}$

Representation of the inequality

The inequality can be represented as follows:

Is given - for a natural number - a positive definite and symmetric matrix , which as the smallest eigenvalue the positive real number was, and as the largest positive real number . ${\displaystyle n>0}$ ${\displaystyle Q\in {\mathbb {R} }^{n\times n}}$ ${\displaystyle m}$ ${\displaystyle M}$

Then the inequality holds for all ${\displaystyle x\in {\mathbb {R} }^{n}\setminus \{0\}}$

${\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}}}}$ .

In other words - and beyond the above - if

${\displaystyle \mathrm {cond} (Q):={\frac {M}{m}}}$

is set:

${\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)}}}$ ,

and the upper estimate is sharp in the sense that the equation

${\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)}}}$

consists.

More general representation of the inequality

In the specialist literature on the theory of convex functions , the Kantorowitsch inequality is placed in a wider context and is also given here in the more general version:

Let a compact interval and two non-negative convex functions be given . ${\displaystyle [a,b]\subset \mathbb {R} }$ ${\displaystyle f\;,\;g\;\colon [a,b]\to [0,{+\infty })}$

Furthermore, a natural number and real numbers as well as positive real numbers with and, in addition, another positive real number are given . ${\displaystyle n>0}$ ${\displaystyle x_{1},\ldots ,x_{n}\in [a,b]}$ ${\displaystyle p_{1},\ldots ,p_{n}}$ ${\displaystyle c}$

Under these conditions applies to the associated convex combinations

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

and

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

the general inequality

${\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)}$  .

If for is always , then m an also has the lower estimate ${\displaystyle x\in [a,b]}$ ${\displaystyle f(x)g(x)\geq 0}$ ${\displaystyle p_{1}+\ldots +p_{n}=1}$

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

In particular, the two inequalities always apply in this case ${\displaystyle a>0}$

${\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}}$  .

Derivation of the matrix inequality from the more general representation

At first glance it is not obvious how the above matrix inequality follows from the more general representation, but that can be said in a few words. Be positive definite and symmetrical with eigenvalues . Then there is an orthogonal matrix such that the diagonal matrix is with diagonal elements . Be anything and . With applies and ${\displaystyle Q}$ ${\displaystyle 0<m=x_{1}\leq \ldots \leq x_{n}=M}$ ${\displaystyle S}$ ${\displaystyle S^{T}QS}$ ${\displaystyle x_{1}\ldots x_{n}}$ ${\displaystyle 0\not =z\in \mathbb {R} ^{n}}$ ${\displaystyle y=(y_{1},\ldots ,y_{n}):=S^{T}z}$ ${\displaystyle \textstyle p_{i}:={\frac {y_{i}^{2}}{\|y\|^{2}}}}$ ${\displaystyle p_{1}+\ldots +p_{n}=1}$

${\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 }$.

Since positive is also definite and symmetric with eigenvalues and since the diagonal matrix is also with diagonal elements , we also get ${\displaystyle Q^{-1}}$ ${\displaystyle \textstyle {\frac {1}{x_{1}}}\ldots {\frac {1}{x_{n}}}}$ ${\displaystyle S^{T}Q^{-1}S}$ ${\displaystyle \textstyle {\frac {1}{x_{1}}}\ldots {\frac {1}{x_{n}}}}$

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

The more general representation of the inequality thus provides with and ${\displaystyle a=m}$ ${\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}}}$.

This is exactly the above matrix inequality if one inverts both sides. Hence, the second given version of the Kantorovich inequality actually generalizes the above matrix inequality.

literature

• 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 LV Kantorovich . In: Proceedings of the American Mathematical Society . tape 10 , 1959, pp. 407-415 , doi : 10.2307 / 2032857 ( MR0105028 ).
• LV Kantorovič : Functional analysis and applied mathematics . (Russian). In: Uspehi Mat. Nauk (NS) . tape 3 , 1948, p. 89-185 ( MR0027947 ).
• Peter Kosmol : Methods for the numerical treatment of nonlinear equations and optimization tasks (=  Teubner study books mathematics ). BG Teubner Verlag , Stuttgart 1989, ISBN 3-519-02085-8 ( MR1002944 ).
• DS Mitrinović : Analytic Inequalities . In cooperation with PM Vasić (=  The basic teachings of the mathematical sciences in individual representations with special consideration of the areas of application . Volume 165 ). Springer Verlag , Berlin ( inter alia ) 1970, ISBN 3-540-62903-3 ( MR0274686 ).
• A. Wayne Roberts , Dale E. Varberg : Convex Functions (  Pure and Applied Mathematics . Volume 57 ). Academic Press , New York, San Francisco, London 1973 ( MR0442824 ).
• WG Strang : On the Kantorovich inequality . In: Proceedings of the American Mathematical Society . tape 11 , 1960, pp. 60 , doi : 10.2307 / 2034801 ( MR0112046 ).

Web links

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

Individual evidence

1. ↑ Peter Kosmol: Methods for the numerical treatment of nonlinear equations and optimization tasks . 1989, pp. 110-112
2. ↑ DS Mitrinović: Analytic Inequalities. 1970, pp. 60-65
3. ^ Owe Axelsson: Iterative Solution Methods. 1994, p. 95 ff.
4. ^ Wilhelm Forst, Dieter Hoffmann: Optimization - Theory and Practice. 2010, p. 100 ff.
5. ↑ Kosmol, op.cit., P. 110
6. ↑ Kosmol, op.cit., P. 101
7. ↑ is the scalar product of . ${\displaystyle \langle \cdot ,\cdot \rangle }$ ${\displaystyle {\mathbb {R} }^{n}}$
8. ↑ In the English-language specialist literature, the size is also referred to as the condition number of . ${\displaystyle \mathrm {cond} (Q)}$ ${\displaystyle Q}$
9. ↑ Axelsson, op.cit., P. 96
10. ^ A. Wayne Roberts, Dale E. Varberg: Convex Functions. 1973, pp. 208-209
11. ↑ With and and ! ${\displaystyle f(x)=x}$ ${\displaystyle g(x)={\frac {1}{x}}}$ ${\displaystyle c={\frac {1}{\sqrt {ab}}}}$