AnaNum GI.pdf


Aperçu du fichier PDF ananum-gi.pdf - page 3/58

Page 1 2 34558


Aperçu texte


3.4 Autres factorisations . . . . . . . .
3.4.1 Factorisation QR . . . . .
3.4.2 Factorisation de SCHUR
Exercices . . . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

32
32
33
34

.
.
.
.
.
.
.
.

35
35
37
38
38
39
39
40
40

5 Décomposition en valeurs singulières. Problème aux moindres carrés linéaires
5.1 Décomposition en valeurs singulières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Pseudo-inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Problème aux moindres carrés linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42
42
42
42

Annexes

42

4 Méthodes de descente
4.0 Motivation . . . . . . . . . . . . . . . . . . . . . .
4.1 Méthode de plus grande pente . . . . . . .
4.1.1 Version à pas constant . . . . . . . .
4.1.2 Version à pas variable optimal . .
4.2 Méthode du gradient conjugué . . . . . . .
4.2.1 Définition et propriétés . . . . . . .
4.2.2 Algorithme du gradient conjugué
4.2.3 Version préconditionnée . . . . . .

.
.
.
.

.
.
.
.
.
.
.
.

A Analyse de propagation d’erreurs
A.1 Erreurs d’une opération élémentaire . . . .
A.2 Propagation d’erreurs dans un algorithme
A.3 Comparaison d’algorithmes . . . . . . . . . .
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

B Matrices creuses
B.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2 Résolution de systèmes linéaires « en bande » .
B.2.1 Résolution de systèmes triangulaires . .
B.2.2 Factorisation LU . . . . . . . . . . . . . . . . .
B.2.3 Réduction de la largeur de bande . . . .
B.3 Stockage . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.3.1 Implémentations incrémentales . . . . .
B.3.2 Implémentations avancées . . . . . . . . .

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

44
44
45
46
46

.
.
.
.
.
.
.
.

47
47
49
49
50
51
52
52
54

C Décomposition en valeurs propres
56
C.1 Localisation des valeurs propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
C.2 Techniques de calcul des valeurs propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Bibliographie

Romain Dujol, Laurence Lamoulie, Chrysostome Baskiotis

57

2