L’inégalité de Kantorovitch [Python]

On munit {\mathbb R^n} de son produit scalaire canonique {(\cdot\mid\cdot)} et de sa norme {\|\cdot\|}. Soit {A} une matrice réelle symétrique définie positive : {x^TAx>0} pour {x\ne0}. On admet que cela équivaut à la stricte positivité de ses valeurs propres. Les questions [P] utilisent Python.

1. Montrer que {(x\mid y)_A=x^TAy} est un produit scalaire. On note {\|\cdot\|_A} sa norme. Écrire une fonction Python testant le caractère défini positif d’une matrice symétrique réelle, puis une fonction calculant {(x\mid y)_A}.

La matrice {A} est inversible. Pour {b\in\mathbb R^n}, on note {\bar x=A^{-1}b} et l’on cherche à approcher cette solution. On pose {J(x)=\frac12(Ax\mid x)-(b\mid x)}.

2. (a) Calculer {J(x+h)-J(x)} et en déduire {\nabla J(x)}.

2. (b) Montrer que {J} admet un minimum atteint en {\bar x}.

On construit {x_{k+1}=x_k+\alpha_{k+1}r_k}, où {r_k=b-Ax_k} et où {\alpha_{k+1}} minimise {J(x_k+\alpha r_k)} pour {\alpha\in\mathbb R}. Si {x_k=\bar x}, on arrête l’algorithme et prolonge la suite par cette valeur constante.

3. (a) Si {x_k\ne\bar x}, montrer que {\alpha_{k+1}=\|r_k\|^2/\|r_k\|_A^2>0}.

3. (b) Montrer, tant que {x_k\ne\bar x}, que {\begin{array}{rl}\dfrac{\|x_{k+1}-\bar x\|_A^2}{\|x_k-\bar x\|_A^2}&=1-\dfrac{\|r_k\|^4}{\|r_k\|_A^2\|x_k-\bar x\|_A^2}\\[4pt]&=1-\dfrac{\|r_k\|^4}{(Ar_k\mid r_k)(A^{-1}r_k\mid r_k)}\end{array}}

3. (c) Utiliser l’inégalité de Kantorovitch (question 5) pour déterminer {\alpha\geq0} tel que {\|x_{k+1}-\bar x\|_A\leq\alpha\|x_k-\bar x\|_A}.

3. (d) Conclure que {(x_k)} converge vers {\bar x}.

4. [P] Écrire une fonction resolution(A,b,x0). Tester sur {A=(\min(i+1,j+1))_{0\leq i,j\leq5}} et {b=(1,\ldots,1)} ; comparer avec np.linalg.solve.

5. L’inégalité de Kantorovitch. On note {0\lt\lambda_1\leq\cdots\leq\lambda_n} les valeurs propres de {A}.

5. (a) Démontrer que {\|x\|^4\leq(Ax\mid x)(A^{-1}x\mid x)}. Indication : décomposer {x} dans une base orthonormée propre.

5. (b) Montrer que {\sup_{\lambda\in[\lambda_1,\lambda_n]}\left(\frac\lambda{\lambda_1}+\frac{\lambda_n}\lambda\right)=1+\frac{\lambda_n}{\lambda_1}}

5. (c) Démontrer l’inégalité de Kantorovitch : {(Ax\mid x)(A^{-1}x\mid x)\leq\frac{(\lambda_1+\lambda_n)^2}{4\lambda_1\lambda_n}\|x\|^4}