Algorithmes Numériques: norme vectorielle

Généralités

Normes et rayon spectral:

Définition norme vectorielle :

vérifiant :

Exemple de norme vectorielle :

Norme 1 :

Norme 2 :

Norme  :

Proposition : En dimension finie, toutes ces normes sont équivalentes ; en pratique, on choisit celle qui nous arrange.

Définition norme matricielle :

C'est une norme dans l'espace vectorielle Mn(R), avec en plus.

Norme matricielle induite :

A partir d'une norme vectorielle, on construit une norme matricielle induite : .

Notons de plus que .

En particulier pour la norme 2, on a la relation : avec le rayon spectral.

Propriétés :

et

Cas de A symétrique :

Dans le cas général, , maximum des valeurs singulières avec les valeurs propres (positives) de la matrice symétrique. (?)

Soit A une matrice carré quelconque n x n. Pour toutes normes de matrice induite, on a .

Conditionnement d’une matrice inversible :

Considérons un système linéaire AX=b. L'expérience de Wilson met un évidence une instabilité des calculs dans certains cas. Si l'on modifie sensiblement les paramètres de la matrice A, ou du second membre b, on peut trouver des résultats complètement différends !

avec

Soit une matrice Q orthogonale : et

Les bons conditionnements sont les petits conditionnements (au mieux 1 pour les matrices orthogonales).

Pour A symétrique : ; dans la cas général :

Théorèmes sur le conditionnement :

Théorème : . On a .

Théorème : . On a .

Remarque : Le conditionnement traduit l'amplification des grandeurs relatives.

Inverse numérique d’une matrice :

Soit A une matrice inversible et A-1 son inverse théorique.

M est un inverse de A du point de vue numérique si :

est petit, ce qui correspond à M=A-1

est petit, ce qui correspond à A=M-1

sont petits, ce qui correspond à

On s'adapte au calcul que l'on veut faire. Notons que l'on résout rarement un système linéaire en calculant l'inverse

Systèmes linéaires Ax=b : méthodes directes

Formules de Crammer

Cette méthode nécessite le calcul d'un déterminant, dont la complexité est en n!. La compléxité de la formule de Cramer est en n 2 n!. Par conséquent, cette méthode n'est pas utilisable en informatique.

Méthode du pivot de Gauss

À la kème étape : pour . On pose .

L'algorithme à une complexité en .

Le problème des coefficients diagonaux nuls : il faut permuter les lignes lorsque apparaît un zéro sur la diagonale.

Stratégie du pivot maximum partiel :

On permute la kème ligne et la ième ligne avec i tel que . Pour des raisons de stabilité numérique, on divise par le terme de la colonne k, qui a la plus grande valeur absolue.

Stratégie du pivot avec seuil :

On effectue une permutation uniquement des. Cependant cette méthode peut être mise en défaut. Il vaut mieux utiliser la méthode du pivot maximum partiel, qui n'est pas vraiment plus coûteuse en calcul.

Calcul de l’inverse

Une idée pour résoudre le sytème Ax=b serait de calculer l’inverse de A. En effet, on a .

Méthode de Shermann – Morison

Soit A une matrice n x n, réelle inversible, dont on connaît l’inverse A-1 ; soit B une perturbation, on cherche à calculer .

On démontre que si , alors , avec .

On suppose maintenant que la perturbation ne modifie qu’un seul en : .

Notons . Alors on trouve .

Elimination de Gauss

On applique la stratégie du pivot partiel maximum, au calcul de l’inverse.

On considère une matrice A inversible, de dimension n

On résout , ce qui revient à écrire . On procède par élimination de Gauss, ce qui donne une matrice triangulaire supérieure (complexité en n3). Ensuite, on réalise n remontées, une par vecteur (complexité en n 2).

En résumé, on a  et une matrice triangulaire supérieure.

On veut traiter tous les seconds membres en une seule passe ; pour cela on considère la matrice n x 2n suivante : qui après calculs donne .

On donne ici un exemple d’écriture en langage de description algorithmique :

Procédure pivot ( k , l : entiers ; OK : booléens )

Début

Max :=  ;

l := k ;

Pour i := k+1 à n faire

Si max <

Alors

Début

Max :=  ;

l := i ;

Fin ;

...