Rappels d'algèbre linéaire, normes et conditionnement

Cette annexe est un instrument de consultation, pas un chapitre: elle n'est pas faite pour être lue d'une traite, mais pour être ouverte au moment précis où un chapitre écrit «par l'annexe A» et où il vous faut l'énoncé exact, avec ses hypothèses et sa constante. Elle rassemble les faits d'algèbre linéaire dont l'analyse numérique se sert sans arrêt: mesurer un vecteur, mesurer une matrice, comparer le rayon spectral aux normes, reconnaître une matrice symétrique définie positive, choisir une décomposition, et manipuler le nombre de conditionnement sans se tromper de propriété.

Le cours d'algèbre linéaire reste le cours d'algèbre linéaire: cette annexe n'en est pas un résumé. Elle en extrait la vingtaine d'énoncés que les dix chapitres utilisent, avec une démonstration complète chaque fois qu'elle tient en quelques lignes et qu'elle apprend quelque chose, et avec un «admis» explicite, accompagné de sa raison, dans les trois cas où la preuve appartient franchement à un cours de calcul matriciel. Les nombres qui y figurent — les conditionnements des matrices de Hilbert en particulier — ont été recalculés en arithmétique rationnelle exacte et coïncident avec ceux des chapitres 4 et 7.

Objectifs

À la fin de cette annexe, vous serez capable de:

• calculer $\Vert \mathbf{x}{\Vert }_1$, $\Vert \mathbf{x}{\Vert }_2$, $\Vert \mathbf{x}{\Vert }_{\infty }$, dessiner leurs boules unité, et utiliser les inégalités d'équivalence avec leurs constantes optimales, en sachant où l'égalité est atteinte;
• calculer $\Vert A{\Vert }_{\infty }$ et comme des maxima de sommes de lignes et de colonnes, démontrer ces deux formules, et distinguer une norme induite d'une norme matricielle quelconque comme celle de Frobenius;

Normes vectorielles

Une conséquence de l'inégalité triangulaire mérite d'être isolée, car les chapitres 2, 4 et 9 s'en servent sans la nommer: la seconde inégalité triangulaire

Elle s'obtient en écrivant $\Vert \mathbf{x}\Vert \le \Vert \mathbf{x}-\mathbf{y}\Vert +\Vert \mathbf{y}\Vert$ et en échangeant les rôles de $\mathbf{x}$ et de $\mathbf{y}$. C'est elle qui rend toute norme continue, donc qui autorise à passer à la limite dans une inégalité entre normes.

La boule unité d'une norme, $B=\{\mathbf{x}:\Vert \mathbf{x}\Vert \le 1\}$, est la façon la plus économique de se représenter ce que cette norme mesure. Les trois boules unité de ${\mathbb{R}}^2$ sont un losange, un disque et un carré, et leur emboîtement contient déjà tout le théorème d'équivalence.

Démonstration. Posons $m=\Vert \mathbf{x}{\Vert }_{\infty }$ et soit $k$ un indice réalisant ce maximum.

Première chaîne. D'une part $\Vert \mathbf{x}{\Vert }_2^2={\sum }_i{x}_i^2\ge x_k^2=m^2$, donc , avec égalité si et seulement si , c'est-à-dire si toutes les autres composantes sont nulles. D'autre part , donc , avec égalité si et seulement si pour tout , c'est-à-dire si toutes les composantes ont le même module. Les deux bornes sont donc atteintes, la première par , la seconde par .

Deuxième chaîne. En développant le carré,

les termes croisés étant positifs ou nuls; ils sont tous nuls exactement quand au plus une composante ne l'est pas. Dans l'autre sens, l'inégalité de Cauchy–Schwarz appliquée au couple formé de $(|x_1|,\dots ,|x_n|)$ et de $(1,\dots ,1)$ donne

avec égalité si et seulement si les deux vecteurs sont colinéaires, c'est-à-dire si tous les $|x_i|$ sont égaux.

Troisième chaîne. Elle se compose des deux précédentes, ou se vérifie directement: $m\le {\sum }_i|x_i|\le nm$, avec les mêmes cas d'égalité.

Cas général. Toute norme $N$ est continue pour la topologie usuelle, car

Elle atteint donc, sur la sphère $\{\Vert \mathbf{x}{\Vert }_{\infty }=1\}$ qui est fermée et bornée donc compacte, un minimum $c$ et un maximum $C$; le minimum est strictement positif par séparation. L'homogénéité propage l'encadrement $c\le N(\mathbf{x})\le C$ de la sphère à tout ${\mathbb{R}}^n$.

Normes matricielles induites

Une matrice agit sur des vecteurs; la bonne façon de mesurer sa taille est donc de mesurer de combien elle peut allonger un vecteur.

L'inégalité (A.5) est, dans tout ce cours, la seule propriété dont on se sert vraiment: c'est elle qui transporte une majoration sur un vecteur à travers une matrice. Deux conséquences immédiates s'y ajoutent.

Démonstration. Pour tout $\mathbf{x}$, deux applications de (A.5) donnent $\Vert AB\mathbf{x}\Vert \le \Vert A\Vert \Vert B\mathbf{x}\Vert \le \Vert A\Vert \Vert B\Vert \Vert \mathbf{x}\Vert$; en prenant le maximum sur les $\mathbf{x}$ de norme $1$ on obtient la première inégalité, dont la deuxième est l'itérée. Enfin $\Vert I\mathbf{x}\Vert =\Vert \mathbf{x}\Vert$, donc le quotient de (A.4) vaut pour tout et son maximum aussi.

Il reste à savoir calculer (A.4). Le fait remarquable est que, pour les deux normes extrêmes, un maximum sur une sphère se ramène à un maximum sur $n$ nombres, et le calcul est exact si les coefficients sont rationnels.

Démonstration de (A.7). Posons $M={\max }_i{\sum }_j|a_{ij}|$.

Majoration. Soit $\mathbf{x}$ avec $\Vert \mathbf{x}{\Vert }_{\infty }=1$, donc $|x_j|\le 1$ pour tout $j$. Pour toute ligne $i$,

En prenant le maximum sur $i$, $\Vert A\mathbf{x}{\Vert }_{\infty }\le M$, donc $\Vert A{\Vert }_{\infty }\le M$.

Minoration. Il faut exhiber un vecteur qui réalise $M$. Soit $k$ une ligne où le maximum est atteint et posons

Alors $\Vert \mathbf{z}{\Vert }_{\infty }=1$ et $(A\mathbf{z}{)}_k={\sum }_j{a}_{kj}\mathrm{sgn}(a_{kj})={\sum }_j|a_{kj}|=M$, donc et . Les deux inégalités donnent (A.7).

Démonstration de (A.8). Notons ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_n$ les colonnes de $A$ et $N={\max }_j\Vert {\mathbf{a}}_j{\Vert }_1$. De on tire, par inégalité triangulaire puis homogénéité,

d'où $\Vert A{\Vert }_1\le N$. Réciproquement, si $k$ est une colonne réalisant le maximum, le vecteur de base ${\mathbf{e}}_k$ vérifie $\Vert {\mathbf{e}}_k{\Vert }_1=1$ et . D'où l'égalité. Remarquons que ce second vecteur est que celui de (A.7): en norme , le maximum est atteint sur un vecteur de base, alors qu'en norme infinie il faut un vecteur de signes.

La formule (A.9) est démontrée plus bas, au théorème A.9, une fois le théorème spectral disponible: elle demande de savoir que le quotient de Rayleigh d'une matrice symétrique est maximal sur un vecteur propre.

Une norme matricielle qui n'est pas induite: Frobenius

Elle est sous-multiplicative — cela se démontre en appliquant Cauchy–Schwarz à chaque coefficient de $AB$ — et elle est commode: elle se calcule en $n^2$ opérations, sans valeur propre. Mais elle n'est induite par aucune norme vectorielle, et la preuve tient en un mot: $\Vert I_n{\Vert }_F=\sqrt{n}$, alors que le théorème A.2 impose à toute norme induite. La conséquence pratique est qu'on ne peut pas s'en servir dans les majorations de ce cours sans précaution. L'inégalité reste vraie, mais n'est plus constante qui la rende vraie: c'est précisément la propriété d'optimalité de (A.5) qui se perd. Et un conditionnement calculé avec vaudrait sur l'identité au lieu de .

Deux encadrements la relient tout de même aux normes induites; ils servent quand on veut une estimation bon marché de $\Vert A{\Vert }_2$. Si $A$ a pour valeurs singulières ${\sigma }_1\ge \cdots \ge {\sigma }_r>0$ (avec le rang), alors , donc

La seconde inégalité est le moyen le plus rapide de majorer une norme 2 sans calculer de valeur propre, et elle se démontre en deux lignes à partir de ce qui précède: $\Vert A{\Vert }_2^2=\rho (A^{\mathsf{T}}A)\le \Vert A^{\mathsf{T}}A{\Vert }_{\infty }\le \Vert A^{\mathsf{T}}{\Vert }_{\infty }\Vert A{\Vert }_{\infty }=\Vert A{\Vert }_1\Vert A{\Vert }_{\infty }$, par (A.13), (A.6) puis (A.7)–(A.8).

Rayon spectral

Démonstration. Soit $\lambda$ une valeur propre de $A$ et $\mathbf{z}\ne 0$ un vecteur propre associé, tous deux éventuellement complexes. On prolonge la norme à ${\mathbb{C}}^n$ en remplaçant la valeur absolue par le module dans (A.1) — ce prolongement laisse les formules (A.7), (A.8) et (A.9) inchangées pour une matrice réelle, comme on le vérifie sur leurs démonstrations, où les seuls objets manipulés sont les modules des coefficients. Alors $A\mathbf{z}=\lambda \mathbf{z}$ donne

et l'on simplifie par $\Vert \mathbf{z}\Vert >0$. En prenant le maximum sur les valeurs propres, on obtient (A.13). $\square$

Le rayon spectral est donc en dessous de toutes les normes induites à la fois. Il n'en est pas une lui-même, et l'exemple qui le montre est minimal: la matrice non nulle

a pour unique valeur propre $0$, donc $\rho (N)=0$ alors que $N\ne 0$: la séparation est en défaut. La sous-additivité l'est aussi, puisque $\rho (N)+\rho (N^{\mathsf{T}})=0$ tandis que a pour valeurs propres .

Démonstration partielle. L'implication directe de (A.15) est immédiate: si $\lambda$ est une valeur propre de module $|\lambda |\ge 1$ et $\mathbf{z}$ un vecteur propre associé, alors $A^k\mathbf{z}={\lambda }^k\mathbf{z}$ ne tend pas vers $0$, donc $A^k$ ne tend pas vers la matrice nulle. Réciproquement, si , choisissons et une norme induite telle que ; alors par (A.6), et toutes les normes sur l'espace des matrices étant équivalentes (théorème A.1 appliqué à ), coefficient par coefficient.

Ce qui est admis, et pourquoi. L'existence de la norme $\Vert \cdot {\Vert }_{\epsilon }$ et la formule (A.14) elle-même. Les deux se démontrent à partir de la réduction de Jordan: on écrit $A=PJ{P}^{-1}$, on remplace $P$ par $P{D}_{\delta }$ où , ce qui multiplie les coefficients sur-diagonaux de par et les rend aussi petits qu'on veut; la norme convient alors. La réduction de Jordan n'est pas dans le programme de ce cours, et elle est par ailleurs — la forme de Jordan n'est pas une fonction continue de la matrice, ce qui la rend impossible à calculer de façon stable, comme le chapitre 5 l'explique à propos du polynôme caractéristique. Nous admettons donc ces deux résultats: ils appartiennent à un cours de calcul matriciel, où la réduction de Jordan est disponible.

Valeurs propres, similitude et théorème spectral

Démonstration. En utilisant $\det (XY)=\det X\det Y$ et $P^{-1}(A-\lambda I)P=P^{-1}AP-\lambda I$,

puisque $\det (P^{-1})\det (P)=1$. La seconde assertion est un calcul: $(P^{-1}AP)(P^{-1}\mathbf{v})=P^{-1}A\mathbf{v}=\lambda P^{-1}\mathbf{v}$.

C'est ce théorème qui fait fonctionner le découplage du chapitre 10: pour un système différentiel ${\mathbf{y}}^{\prime }=A\mathbf{y}$ avec $A=VD{V}^{-1}$ diagonalisable, le changement d'inconnue $\mathbf{w}=V^{-1}\mathbf{y}$ transforme le système en équations scalaires indépendantes , et c'est pourquoi la stabilité d'un schéma se lit valeur propre par valeur propre. C'est aussi lui qui justifie l'algorithme du chapitre 5, qui n'est qu'une suite de similitudes orthogonales.

Démonstration des points 1 et 2. Soit $\lambda \in \mathbb{C}$ une valeur propre et $\mathbf{z}\in {\mathbb{C}}^n$ un vecteur propre, et notons ${\bar{\mathbf{z}}}^{\mathsf{T}}$ le transposé conjugué. Alors

Mais ${\bar{\mathbf{z}}}^{\mathsf{T}}A\mathbf{z}$ est un scalaire égal à son propre transposé conjugué, car $A$ est réelle et symétrique: $\overline{{\bar{\mathbf{z}}}^{\mathsf{T}}A\mathbf{z}}={\mathbf{z}}^{\mathsf{T}}A\bar{\mathbf{z}}={\bar{\mathbf{z}}}^{\mathsf{T}}{A}^{\mathsf{T}}\mathbf{z}={\bar{\mathbf{z}}}^{\mathsf{T}}A\mathbf{z}$. Un nombre complexe égal à son conjugué est réel, et , donc est réel. Le vecteur propre peut alors être choisi réel, puisqu'il engendre le noyau de la matrice réelle .

Pour le point 2, soient $A\mathbf{u}=\lambda \mathbf{u}$ et $A\mathbf{v}=\mu \mathbf{v}$ avec $\lambda \ne \mu$. La symétrie donne

donc $(\lambda -\mu ){\mathbf{u}}^{\mathsf{T}}\mathbf{v}=0$ et ${\mathbf{u}}^{\mathsf{T}}\mathbf{v}=0$. $\square$

Le point 3 est admis, avec sa raison: il exige de traiter le cas d'une valeur propre multiple, pour laquelle la seule orthogonalité des espaces propres ne suffit pas — il faut montrer que la dimension de chaque espace propre égale la multiplicité de la racine. La démonstration usuelle procède par récurrence sur $n$, en restreignant $A$ à l'orthogonal d'un premier vecteur propre (sous-espace qui est bien stable, par symétrie), ou passe par la factorisation de Schur. C'est un résultat central du cours d'algèbre linéaire, où il est établi proprement; le redémontrer ici n'apporterait rien à l'analyse numérique, alors que s'en servir lui apporte beaucoup.

Matrices symétriques définies positives

Démonstration de (1) ⟹ (2). Soit $\lambda$ une valeur propre et $\mathbf{v}\ne 0$ un vecteur propre associé, réels par le théorème A.7. Alors

et comme $\Vert \mathbf{v}{\Vert }_2^2>0$, on a $\lambda >0$. $\square$

Démonstration de (2) ⟹ (1). Le théorème spectral fournit une base orthonormée $({\mathbf{q}}_i)$ de vecteurs propres. Écrivons $\mathbf{x}={\sum }_i{\alpha }_i{\mathbf{q}}_i$; alors et, l'orthonormalité annulant tous les termes croisés,

dès que $\mathbf{x}\ne 0$, puisque ${\lambda }_{\min }>0$. $\square$

L'encadrement (A.19) mérite d'être retenu sous sa forme complète, car c'est celle qu'utilise le chapitre 5 à propos du quotient de Rayleigh: pour toute matrice symétrique,

les deux bornes étant atteintes sur les vecteurs propres extrêmes.

Démonstration de (4) ⟹ (1). Si $A=B{B}^{\mathsf{T}}$ avec $B$ triangulaire inférieure de diagonale strictement positive, alors $A^{\mathsf{T}}=A$ et, pour tout $\mathbf{x}$,

L'égalité exige $B^{\mathsf{T}}\mathbf{x}=0$; or $\det B=b_{11}\cdots b_{nn}>0$, donc $B^{\mathsf{T}}$ est inversible et .

Démonstration de (1) ⟹ (3). Chaque sous-matrice dominante $A_k$ est elle-même SDP: pour $\mathbf{y}\in {\mathbb{R}}^k$ non nul, le vecteur $\mathbf{x}=(\mathbf{y},0{)}^{\mathsf{T}}\in {\mathbb{R}}^n$ est non nul et . Par l'implication (1) ⟹ (2) appliquée à , toutes les valeurs propres de sont strictement positives, et , qui en est le produit, l'est aussi.

Ce qui est admis. Les deux implications restantes, qui ferment le cycle, ne sont pas démontrées ici.

• (3) ⟹ (1), la réciproque du critère de Sylvester, est le seul énoncé de ce théorème dont la preuve ne tient pas en cinq lignes: elle procède par récurrence sur $n$ en complétant le carré, ou en montrant que la signature de la forme quadratique se lit sur la suite des signes des ${\Delta }_k$ (règle de Jacobi). C'est un théorème du cours d'algèbre linéaire, où il est établi dans le cadre général de la classification des formes quadratiques.
• (1) ⟹ (4), l'existence de la factorisation de Cholesky, — existence et unicité — est démontrée au chapitre 3 (théorème 3.4): on y établit d'abord l'existence de la factorisation $LU$ sous la condition des mineurs, puis on symétrise $A=LD\tilde{U}$ en $A=B{B}^{\mathsf{T}}$ avec . Nous ne la redémontrons pas.

Valeurs singulières, norme 2 et conditionnement en norme 2

Existence admise, avec sa raison: la construction repose sur le théorème spectral appliqué à la matrice symétrique semi-définie positive $A^{\mathsf{T}}A$, puis sur un argument de complétion de base pour $U$ lorsque $A$ n'est pas de rang plein. Elle est élémentaire mais longue, et surtout l'algorithme qui calcule effectivement une SVD (bidiagonalisation de Golub–Kahan suivie d'une itération $QR$ implicite) appartient au cours de calcul matriciel; le chapitre 5 explique pourquoi aucune méthode directe n'est possible. Nous retenons la décomposition, ses conséquences et son coût.

Démonstration. Pour $\mathbf{x}\ne 0$,

qui est le quotient de Rayleigh de la matrice symétrique $A^{\mathsf{T}}A$. L'encadrement (A.20) donne immédiatement

les deux bornes étant atteintes sur les vecteurs propres correspondants. En prenant la racine carrée et le maximum, $\Vert A{\Vert }_2=\sqrt{{\lambda }_{\max }(A^{\mathsf{T}}A)}={\sigma }_1$, ce qui démontre au passage la formule (A.9) annoncée plus haut.

Si $A=U\Sigma V^{\mathsf{T}}$ est inversible, alors $A^{-1}=V{\Sigma }^{-1}{U}^{\mathsf{T}}$ et ${\Sigma }^{-1}$ porte les en ordre croissant: c'est une SVD de , à l'ordre des colonnes près. Donc , et le produit des deux normes est (A.22).

La lecture géométrique est la plus parlante de toute l'annexe: l'image de la sphère unité par $A$ est un ellipsoïde dont les demi-axes sont les ${\sigma }_i$. Le conditionnement en norme 2 est donc le rapport d'aplatissement de cet ellipsoïde: ${\kappa }_2=1$ pour une sphère, ${\kappa }_2$ grand pour une galette.

Les décompositions usuelles

Les six décompositions que ce cours emploie sont rassemblées ici avec, pour chacune, ce qu'elle exige de la matrice, ce qu'elle garantit et ce qu'elle coûte. Les coûts sont des nombres d'opérations flottantes pour une matrice pleine d'ordre $n$, terme dominant seulement; les comptes exacts figurent au chapitre 3.

Trois commentaires sur ce tableau, car il se lit mal sans eux.

Les quatre premières lignes sont des méthodes directes, les deux dernières ne le sont pas. $LU$, $PA=LU$, Cholesky et $QR$ se terminent en un nombre d'opérations connu à l'avance et donnent le résultat exact en arithmétique exacte. La décomposition spectrale et la SVD, non: elles produisent des valeurs propres, et le chapitre 5 rappelle qu'aucune formule ne peut les donner dès $n\ge 5$ (Abel–Ruffini). Leur coût est celui d'un algorithme itératif avec un critère d'arrêt, d'où les «de l'ordre de» du tableau; annoncer un compte exact serait malhonnête.

Le prix de la stabilité se lit dans la colonne de droite. $QR$ coûte deux fois $LU$, et on le paie volontiers: la conjugaison par une matrice orthogonale ne dilate rien, puisque ${\kappa }_2(Q)=1$ (propriété 5 du théorème A.11). C'est la raison pour laquelle les moindres carrés du chapitre 7 passent par $QR$ plutôt que par les équations normales, et pour laquelle l'algorithme $QR$ du chapitre 5 n'emploie que des similitudes orthogonales.

Cholesky est la seule qui soit aussi un test. Les cinq autres décompositions s'appliquent ou échouent selon des hypothèses qu'il faut vérifier au préalable; Cholesky est la vérification, comme l'explique le théorème A.8. C'est pourquoi l'ordre de préférence, pour un système linéaire dense, est: si $A$ est symétrique, tenter Cholesky; sinon, $PA=LU$; et ne calculer $A^{-1}$ jamais.

Propriétés du conditionnement

Démonstration de 1. Par le théorème A.2, $1=\Vert I\Vert =\Vert A{A}^{-1}\Vert \le \Vert A\Vert \Vert A^{-1}\Vert =\kappa (A)$. $\square$

Démonstration de 2. $(\alpha A{)}^{-1}={\alpha }^{-1}{A}^{-1}$, donc par homogénéité de la norme,

Cette propriété est celle que l'on invoque le plus souvent sans le dire, et elle a deux conséquences qu'il faut avoir en tête. La première: multiplier une équation par mille ne change rien au problème, et le conditionnement, contrairement au déterminant, le reflète. La seconde: $\det (10^{-8}{I}_3)=10^{-24}$ alors que $\kappa (10^{-8}{I}_3)=1$; inversement a pour déterminant et pour conditionnement . Le déterminant ne mesure pas le conditionnement, ni de près ni de loin. C'est aussi cette propriété que le chapitre 7 utilise lorsqu'il ramène la matrice des équations normales de la régression polynomiale, , à une matrice de Hilbert: le facteur disparaît.

Démonstration de 3. Immédiate sur (A.23), les deux facteurs étant échangés. $\square$

Démonstration de 4. Par sous-multiplicativité (théorème A.2), $\Vert AB\Vert \le \Vert A\Vert \Vert B\Vert$, et $(AB{)}^{-1}=B^{-1}{A}^{-1}$ donne $\Vert (AB{)}^{-1}\Vert \le \Vert B^{-1}\Vert \Vert A^{-1}\Vert$. En multipliant,

L'inégalité peut être très lâche: elle ne dit rien dans l'autre sens, et $\kappa (A{A}^{-1})=\kappa (I)=1$ alors que le produit des conditionnements vaut $\kappa (A{)}^2$. Elle sert surtout à borner le conditionnement d'un produit que l'on assemble, par exemple un préconditionnement.

Démonstration de 5. Si $A=\alpha Q$ avec $Q^{\mathsf{T}}Q=I$, alors $A^{\mathsf{T}}A={\alpha }^2{Q}^{\mathsf{T}}Q={\alpha }^{2}I$, dont toutes les valeurs propres valent : toutes les valeurs singulières valent et par (A.22).

Réciproquement, supposons ${\kappa }_2(A)=1$, c'est-à-dire ${\sigma }_{\max }={\sigma }_{\min }=\sigma >0$. Toutes les valeurs propres de la matrice symétrique valent alors , et le théorème spectral donne . Posons : alors , donc est orthogonale et .

Ce cinquième point est le pivot de tout ce qui concerne la stabilité: les matrices orthogonales sont exactement les matrices de conditionnement 1 en norme 2, à un facteur d'échelle près. Une transformation orthogonale n'amplifie donc aucune erreur, ce qui justifie leur emploi systématique dans $QR$, dans l'algorithme $QR$ du chapitre 5 et dans la SVD.

Démonstration de 6. Si $A$ est symétrique, le théorème spectral donne $A=Q\Lambda Q^{\mathsf{T}}$, donc $A^{\mathsf{T}}A=Q{\Lambda }^2{Q}^{\mathsf{T}}$ et les valeurs singulières sont les $|{\lambda }_i|$; (A.22) conclut. Pour la seconde assertion, la SVD donne , dont les valeurs propres — qui sont aussi ses valeurs singulières, la matrice étant symétrique définie positive — sont les . Donc

C'est ce dernier résultat que le chapitre 7 invoque pour condamner les équations normales: former $A^{\mathsf{T}}A$ double le nombre de chiffres perdus, avant même qu'on ait résolu quoi que ce soit.

La matrice de Hilbert: les valeurs exactes du cours

La matrice de Hilbert d'ordre $n$, $H_n=(\frac{1}{i+j-1}{)}_{1\le i,j\le n}$, est la matrice mal conditionnée de référence de ce cours. Elle est symétrique, définie positive, et ses coefficients sont aussi simples qu'on peut l'espérer — ce qui est précisément l'enseignement: le mauvais conditionnement ne se lit pas sur les coefficients.

Où les chapitres s'en servent

Cette annexe existe pour être citée. Voici, chapitre par chapitre, ce qui y est emprunté et où le trouver.

Synthèse

• Trois normes, six inégalités, des constantes optimales. $\Vert \cdot {\Vert }_{\infty }\le \Vert \cdot {\Vert }_2\le \Vert \cdot {\Vert }_1$ toujours, et les majorations dans l'autre sens coûtent $\sqrt{n}$ ou . Les égalités à gauche caractérisent les vecteurs à une seule composante non nulle, celles à droite les vecteurs à composantes de même module. Écrivez toujours la norme en indice.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Trefethen, L. N. et Bau, D., Numerical Linear Algebra, SIAM, Philadelphie, leçons 1 à 5 (normes, SVD) et 12 (conditionnement) — la présentation de référence, et celle dont l'esprit géométrique a guidé cette annexe.
• Golub, G. H. et Van Loan, C. F., Matrix Computations, Johns Hopkins University Press, Baltimore, chap. 2 (normes matricielles et vectorielles) et 4 (matrices définies positives et Cholesky).
• Quarteroni, A., Sacco, R. et Saleri, F., Méthodes numériques — algorithmes, analyse et applications, Springer, Milan, chap. 1 (normes, conditionnement) et 3 (valeurs propres).
• Horn, R. A. et Johnson, C. R., Matrix Analysis, Cambridge University Press, chap. 5 (normes matricielles, formule de Gelfand) et 7 (matrices définies positives) — pour les deux résultats admis ici.
• Rappaz, J. et Picasso, M., Introduction à l'analyse numérique, PPUR, Lausanne, chap. 1 et 4.