Livre_silo 30 août 2013 16:32 Page 190
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
190
Informatique pour tous
à n
α avec α = ln 2 (7) ≃ 2, 69 (algorithme de Strassen, 1972). Depuis, on a fait un peu
mieux, mais les constantes multiplicatives sont telles qu’elles rendent ces méthodes peu utilisables. La question « Peut-on, pour tout α > 2, trouver un algorithme de multiplication
de complexité O(n
α ) ? » reste en particulier ouverte.
Enfin, on peut noter que certaines matrices avec une géométrie particulière donnent lieu à
des résolutions de systèmes simplifiées. Par exemple, la matrice tridiagonale ¹² suivante :
V n =
2 −1
(0)
−1 2 −1
. . .
. . .
. . .
−1 2 −1
(0)
−1 2
demande une seule transvection pour chaque pivot, d’où un calcul d’inverse (ou de résolution de V n X = Y ) de complexité quadratique. Cette « matrice de Virginie ¹³ » intervient dans les schémas numériques de résolution d’équations différentielles telles que
∆f = g. Elle est très classique en analyse numérique. Des variantes « tridiagonales par
blocs » existent, en particulier pour résoudre les équations aux dérivées partielles en dimension 2 ou 3.
SAVOIR-FAIRE Tenir compte des aspects pratiques
Un algorithme est la plupart du temps une version idéalisée d’une procédure de résolution d’un problème. Lorsque l’on s’attache à le traduire sous forme d’un programme,
on doit prendre en compte différentes considérations pratiques externes à l’algorithme
proprement dit, notamment :
• les conséquences des erreurs d’arrondi sur les résultats,
• le temps de calcul,
• le stockage des données en mémoire.
La première affecte la confiance que l’on peut avoir dans les résultats fournis par un
programme ; si les deux dernières sont trop critiques, l’algorithme n’a qu’un intérêt
théorique.
On l’a vu sur l’exemple du pivot de Gauss, les méthodes numériques peuvent rapidement poser problème de ces trois points de vue.
12. Qu’ on rencontrera régulièrement dans la suite de ce chapitre.
13. Dénomination classique, bien que d’origine peu claire.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
190
Informatique pour tous
à n
α avec α = ln 2 (7) ≃ 2, 69 (algorithme de Strassen, 1972). Depuis, on a fait un peu
mieux, mais les constantes multiplicatives sont telles qu’elles rendent ces méthodes peu utilisables. La question « Peut-on, pour tout α > 2, trouver un algorithme de multiplication
de complexité O(n
α ) ? » reste en particulier ouverte.
Enfin, on peut noter que certaines matrices avec une géométrie particulière donnent lieu à
des résolutions de systèmes simplifiées. Par exemple, la matrice tridiagonale ¹² suivante :
V n =
2 −1
(0)
−1 2 −1
. . .
. . .
. . .
−1 2 −1
(0)
−1 2
demande une seule transvection pour chaque pivot, d’où un calcul d’inverse (ou de résolution de V n X = Y ) de complexité quadratique. Cette « matrice de Virginie ¹³ » intervient dans les schémas numériques de résolution d’équations différentielles telles que
∆f = g. Elle est très classique en analyse numérique. Des variantes « tridiagonales par
blocs » existent, en particulier pour résoudre les équations aux dérivées partielles en dimension 2 ou 3.
SAVOIR-FAIRE Tenir compte des aspects pratiques
Un algorithme est la plupart du temps une version idéalisée d’une procédure de résolution d’un problème. Lorsque l’on s’attache à le traduire sous forme d’un programme,
on doit prendre en compte différentes considérations pratiques externes à l’algorithme
proprement dit, notamment :
• les conséquences des erreurs d’arrondi sur les résultats,
• le temps de calcul,
• le stockage des données en mémoire.
La première affecte la confiance que l’on peut avoir dans les résultats fournis par un
programme ; si les deux dernières sont trop critiques, l’algorithme n’a qu’un intérêt
théorique.
On l’a vu sur l’exemple du pivot de Gauss, les méthodes numériques peuvent rapidement poser problème de ces trois points de vue.
12. Qu’ on rencontrera régulièrement dans la suite de ce chapitre.
13. Dénomination classique, bien que d’origine peu claire.