Livre_silo 30 août 2013 16:32 Page 188
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
188
Informatique pour tous
Si on décide de désigner par opération élémentaire chaque comparaison, affectation ou opération arithmétique sur les flottants, le coût à i fixé est majoré par (n − i) + (2n + 2) +
(n − 1 − i)(2n + 2), c’est-à-dire (2n + 3)(n − i). En sommant sur les i ∈ 0, n − 1, on
trouve donc un coût majoré par (2n + 3)
n(n + 1)
2
= n
3 +
5
2
n
2 +
3
2
n. Comme d’habitude
on ne s’intéresse qu’au terme dominant : la complexité dans le pire des cas est équivalente
à n
3 .
Pour être plus rapide sans réellement perdre en pertinence, on peut se contenter de dire :
« Pour chaque i, la recherche du pivot puis l’échange de ligne ont une complexité linéaire en n,
ainsi que chacune des transvections (il y en a au plus n), d’où une complexité quadratique à i fixé.
Puisque i décrit 0, n − 2, on a finalement une complexité en n
3 . »
7.3.2 Phase de remontée
Voici la deuxième et dernière phase :
pour i de n − 1 à 0 faire
pour k de i + 1 à n − 1 faire
y i ← y i − a i,k x k
x i ←
y i
a i,i
Cette fois, on a un coût clairement quadratique : à i fixé, on réalise de l’ordre de n opérations élémentaires (la fonction sum de Python n’est pas magique : son temps d’exécution
est linéaire en la taille de la liste à sommer).
Finalement, le coût total d’une résolution est de l’ordre de n
3 . Il est à noter que ce coût est
principalement payé lors de la mise sous forme triangulaire.
On reprend maintenant les résultats chronométrés de la section 7.2.3. Lorsque n est multiplié par 2 :
• Le temps de calcul de la fonction resolution est multiplié à peu près par 8 : il s’agit bien
d’une complexité cubique.
• Celui de solve est multiplié par quelque chose de beaucoup plus fluctuant, mais sensiblement inférieur à 8. La documentation en ligne de Python assure que cette résolution
est déléguée à la bibliothèque Fortran LAPACK via une décomposition LU . Une telle décomposition est a priori cubique... On atteint les limites de l’analyse au chronomètre,
peu probante ici.
7.3.3 Peut-on faire mieux que n
3 ?
Quand on pratique par exemple la méthode des éléments finis (pour résoudre des équations
aux dérivées partielles), on peut être confronté à des systèmes à n équations et n inconnues
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
188
Informatique pour tous
Si on décide de désigner par opération élémentaire chaque comparaison, affectation ou opération arithmétique sur les flottants, le coût à i fixé est majoré par (n − i) + (2n + 2) +
(n − 1 − i)(2n + 2), c’est-à-dire (2n + 3)(n − i). En sommant sur les i ∈ 0, n − 1, on
trouve donc un coût majoré par (2n + 3)
n(n + 1)
2
= n
3 +
5
2
n
2 +
3
2
n. Comme d’habitude
on ne s’intéresse qu’au terme dominant : la complexité dans le pire des cas est équivalente
à n
3 .
Pour être plus rapide sans réellement perdre en pertinence, on peut se contenter de dire :
« Pour chaque i, la recherche du pivot puis l’échange de ligne ont une complexité linéaire en n,
ainsi que chacune des transvections (il y en a au plus n), d’où une complexité quadratique à i fixé.
Puisque i décrit 0, n − 2, on a finalement une complexité en n
3 . »
7.3.2 Phase de remontée
Voici la deuxième et dernière phase :
pour i de n − 1 à 0 faire
pour k de i + 1 à n − 1 faire
y i ← y i − a i,k x k
x i ←
y i
a i,i
Cette fois, on a un coût clairement quadratique : à i fixé, on réalise de l’ordre de n opérations élémentaires (la fonction sum de Python n’est pas magique : son temps d’exécution
est linéaire en la taille de la liste à sommer).
Finalement, le coût total d’une résolution est de l’ordre de n
3 . Il est à noter que ce coût est
principalement payé lors de la mise sous forme triangulaire.
On reprend maintenant les résultats chronométrés de la section 7.2.3. Lorsque n est multiplié par 2 :
• Le temps de calcul de la fonction resolution est multiplié à peu près par 8 : il s’agit bien
d’une complexité cubique.
• Celui de solve est multiplié par quelque chose de beaucoup plus fluctuant, mais sensiblement inférieur à 8. La documentation en ligne de Python assure que cette résolution
est déléguée à la bibliothèque Fortran LAPACK via une décomposition LU . Une telle décomposition est a priori cubique... On atteint les limites de l’analyse au chronomètre,
peu probante ici.
7.3.3 Peut-on faire mieux que n
3 ?
Quand on pratique par exemple la méthode des éléments finis (pour résoudre des équations
aux dérivées partielles), on peut être confronté à des systèmes à n équations et n inconnues