Livre_silo 30 août 2013 16:32 Page 187
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
187
7 – Pivot de Gauss et résolution de systèmes
Voici les temps de calcul en secondes, sur un ordinateur de puissance moyenne, de la résolution de H n X = C, pour différentes valeurs de n :
n
50
100
200
400
800
resolution
0.028
0.17
1.31
10.3
82.9
numpy.linalg.solve
0.0012 0.0034 0.014 0.065 0.37
On reviendra dans le paragraphe suivant sur l’évolution de ces temps de calcul en fonction
de n mais on peut déjà constater que numpy est très rapide. En réalité, les fonctions de cette
bibliothèque ne sont pas écrites en Python mais font plutôt appel à d’autres bibliothèques
très optimisées écrites en C ou Fortran.
7.3 Complexité
On s’intéresse ici à la complexité de l’algorithme du pivot de Gauss, c’est-à-dire au nombre
d’opérations élémentaires effectuées lors de la résolution d’un système à n équations et
n inconnues. Cette complexité dépend bien entendu de n ; mais comment ?
7.3.1 Mise sous forme triangulaire
Il s’agit d’analyser la première phase de l’algorithme, qu’on rappelle ici :
pour i de 0 à n − 2 faire
Trouver j entre i et n − 1 tel que |a j,i | soit maximale.
Échanger L i et L j (coefficients de la matrice et membres de droite).
pour k de i + 1 à n − 1 faire
L k ← L k −
a k,i
a i,i
Li
On va dans un premier temps évaluer cette complexité de façon assez fine et on donnera
ensuite une version « allégée », largement suffisante en première approximation ¹⁰.
Pour chaque valeur de i ∈ 0, n − 2 :
• La recherche de j coûte n − i comparaisons.
• L’échange éventuel des deux lignes coûte 2n + 2 affectations.
• Pour chaque valeur de k entre i + 1 et n − 1, la transvection coûte 2n + 2 affectations
et autant de divisions, multiplications et soustractions.
10. Et en fait bien au-delà.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
187
7 – Pivot de Gauss et résolution de systèmes
Voici les temps de calcul en secondes, sur un ordinateur de puissance moyenne, de la résolution de H n X = C, pour différentes valeurs de n :
n
50
100
200
400
800
resolution
0.028
0.17
1.31
10.3
82.9
numpy.linalg.solve
0.0012 0.0034 0.014 0.065 0.37
On reviendra dans le paragraphe suivant sur l’évolution de ces temps de calcul en fonction
de n mais on peut déjà constater que numpy est très rapide. En réalité, les fonctions de cette
bibliothèque ne sont pas écrites en Python mais font plutôt appel à d’autres bibliothèques
très optimisées écrites en C ou Fortran.
7.3 Complexité
On s’intéresse ici à la complexité de l’algorithme du pivot de Gauss, c’est-à-dire au nombre
d’opérations élémentaires effectuées lors de la résolution d’un système à n équations et
n inconnues. Cette complexité dépend bien entendu de n ; mais comment ?
7.3.1 Mise sous forme triangulaire
Il s’agit d’analyser la première phase de l’algorithme, qu’on rappelle ici :
pour i de 0 à n − 2 faire
Trouver j entre i et n − 1 tel que |a j,i | soit maximale.
Échanger L i et L j (coefficients de la matrice et membres de droite).
pour k de i + 1 à n − 1 faire
L k ← L k −
a k,i
a i,i
Li
On va dans un premier temps évaluer cette complexité de façon assez fine et on donnera
ensuite une version « allégée », largement suffisante en première approximation ¹⁰.
Pour chaque valeur de i ∈ 0, n − 2 :
• La recherche de j coûte n − i comparaisons.
• L’échange éventuel des deux lignes coûte 2n + 2 affectations.
• Pour chaque valeur de k entre i + 1 et n − 1, la transvection coûte 2n + 2 affectations
et autant de divisions, multiplications et soustractions.
10. Et en fait bien au-delà.