AnnalesÉcoles d'ingénieurs

X-ENS PSI 2019 — Maths

La méthode du gradient conjugué · 8 pages

Le sujet étudie la résolution de $Ax = b$ pour $A$ symétrique définie positive. Après des préliminaires sur la norme subordonnée, la norme $\|x\|_A$ et la racine carrée $A^{1/2}$ , il introduit les espaces de Krylov $H_k$ engendrés par les $P(A)r_0$ et montre que le minimiseur $x_k$ de $J(x) = \frac{1}{2}\langle x, Ax\rangle - \langle b, x\rangle$ sur $x_0 + H_k$ atteint la solution en au plus $d$ étapes. Les polynômes de Tchebychev donnent la majoration $\|x_k - \bar{x}\|_A \leqslant 2\|x_0 - \bar{x}\|_A \left((\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1)\right)^k$ , et l'algorithme du gradient conjugué est construit par récurrence avec des directions $A$ -orthogonales.

Le sujet, partie par partie

Notations et Partie I — Matrices symétriques définies positives p. 3–4

Matrices symétriques positives · Théorème spectral · Normes subordonnées et applications linéaires continues · Normes équivalentes · Projection orthogonale et moindres carrés — matrice symétrique définie positive, norme subordonnée, norme associée à $A$ , racine carrée d'une matrice, polynôme de matrice

Partie II — Espaces de Krylov p. 5

Polynômes d'endomorphismes · Espaces vectoriels et dimension · Théorème spectral · Endomorphismes cycliques et matrice compagnon — espaces de Krylov, polynôme annulateur d'un vecteur, suite croissante de sous-espaces, valeurs propres distinctes, sous-espace cyclique

Partie III — Minimisation et majoration de l'erreur par les polynômes de Tchebychev p. 6–7

Polynômes de Tchebychev · Extrema et optimisation · Projection orthogonale et moindres carrés · Normes subordonnées et applications linéaires continues · Matrices symétriques positives · Valeurs singulières et conditionnement · Analyse numérique — fonctionnelle quadratique, minimiseur unique, polynômes de Tchebychev, cosinus hyperbolique, conditionnement, vitesse de convergence

Partie IV — L'algorithme du gradient conjugué p. 8

Descente de gradient · Procédé de Gram-Schmidt · Analyse numérique · Projection orthogonale et moindres carrés — gradient conjugué, directions $A$ -orthogonales, résidus orthogonaux, relations de récurrence, orthogonalisation

Dans l'édifice

Espaces de Hilbert et théorème de projection Applications linéaires continues et dual topologique Normes en dimension finie Applications linéaires Anneaux de polynômes Espaces vectoriels et sous-espaces Familles libres, génératrices, bases Dimension d'un espace vectoriel Sommes directes, supplémentaires, projecteurs Matrices d'une application linéaire Applications différentiables Théorème du point fixe de Banach