Livre_silo 30 août 2013 16:32 Page 189
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
189
7 – Pivot de Gauss et résolution de systèmes
pour lesquels n est très grand, par exemple de l’ordre du milliard. Une résolution « en n
3 »
est alors absolument exclue.
EN PRATIQUE Temps de calcul et complexité
On peut retenir comme ordre de grandeur qu’un ordinateur personnel va réaliser de l’ordre
de 10 9 opérations élémentaires dans une minute. Par exemple, un algorithme en O(n 2 )
s’exécutera en temps raisonnable si n = 10 4 , mais est à proscrire si n = 10 7 .
Pour une application industrielle dont le calcul peut durer de l’ordre de quelques jours
dans un centre de calcul dédié ¹¹, on peut imaginer un nombre d’opérations élémentaires
allant jusqu’à 10
18 voire 10
20 , mais certainement pas 10
25 . Par ailleurs, si on doit traiter un
système à n équations et n inconnues en manipulant sa matrice à n
2 entrées, la question de
la gestion de la mémoire va devenir problématique si n est par exemple de l’ordre de 10
6 .
Ces systèmes ne sont donc en général pas traités avec une représentation « pleine » des
matrices associées.
On dispose de deux types d’améliorations :
• Des méthodes itératives permettent d’approcher les solutions. Dans le cadre fréquent
des matrices creuses (de taille n × n, mais avec un nombre d’entrées non nulles de
l’ordre de K.n), ces algorithmes ont en général un coût de l’ordre de αn
2 voire moins,
avec α dépendant de la qualité de l’approximation souhaitée et des caractéristiques de la
matrice. Dans ces méthodes, on peut en plus paralléliser les calculs. C’est un avantage
intéressant.
• On peut tenter d’améliorer la complexité de l’inversion matricielle « exacte ».
Le premier point sera évoqué dans les exercices. Pour le second, un résultat est assez remarquable pour être signalé et plutôt surprenant :
éorème. Si on note M (n) la complexité (dans le pire des cas) du calcul du produit de
deux matrices (n, n), et sous l’hypothèse raisonnable n
2 = O(M (n)), alors on sait inverser
toute matrice (n, n) en temps O(M (n)). Bref : inverser ne coûte pas plus cher que multiplier.
Démonstration. La première étape, simple, consiste à se ramener au cas des matrices symétriques définies positives via l’écriture A
−1 =
( t A.A
) −1 t A. Ensuite, lorsque B est
symétrique définie positive, on l’écrit par blocs de tailles (n/2, n/2) puis on effectue le
calcul de B
−1 en inversant récursivement différents blocs et leur complément de Schur. On
obtient ainsi un très joli algorithme « diviser pour régner »... dont le lecteur curieux trouvera
les détails par exemple dans [Cormen].
La multiplication naïve requiert de l’ordre de n
3 opérations élémentaires. Une amélioration
classique utilisant le principe « diviser pour régner » permet de descendre cette complexité
11. Les très gros ordinateurs actuels réalisent de l’ordre de 10 15 opérations sur les flottants par seconde ; on
parle de « petaflops ».
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
189
7 – Pivot de Gauss et résolution de systèmes
pour lesquels n est très grand, par exemple de l’ordre du milliard. Une résolution « en n
3 »
est alors absolument exclue.
EN PRATIQUE Temps de calcul et complexité
On peut retenir comme ordre de grandeur qu’un ordinateur personnel va réaliser de l’ordre
de 10 9 opérations élémentaires dans une minute. Par exemple, un algorithme en O(n 2 )
s’exécutera en temps raisonnable si n = 10 4 , mais est à proscrire si n = 10 7 .
Pour une application industrielle dont le calcul peut durer de l’ordre de quelques jours
dans un centre de calcul dédié ¹¹, on peut imaginer un nombre d’opérations élémentaires
allant jusqu’à 10
18 voire 10
20 , mais certainement pas 10
25 . Par ailleurs, si on doit traiter un
système à n équations et n inconnues en manipulant sa matrice à n
2 entrées, la question de
la gestion de la mémoire va devenir problématique si n est par exemple de l’ordre de 10
6 .
Ces systèmes ne sont donc en général pas traités avec une représentation « pleine » des
matrices associées.
On dispose de deux types d’améliorations :
• Des méthodes itératives permettent d’approcher les solutions. Dans le cadre fréquent
des matrices creuses (de taille n × n, mais avec un nombre d’entrées non nulles de
l’ordre de K.n), ces algorithmes ont en général un coût de l’ordre de αn
2 voire moins,
avec α dépendant de la qualité de l’approximation souhaitée et des caractéristiques de la
matrice. Dans ces méthodes, on peut en plus paralléliser les calculs. C’est un avantage
intéressant.
• On peut tenter d’améliorer la complexité de l’inversion matricielle « exacte ».
Le premier point sera évoqué dans les exercices. Pour le second, un résultat est assez remarquable pour être signalé et plutôt surprenant :
éorème. Si on note M (n) la complexité (dans le pire des cas) du calcul du produit de
deux matrices (n, n), et sous l’hypothèse raisonnable n
2 = O(M (n)), alors on sait inverser
toute matrice (n, n) en temps O(M (n)). Bref : inverser ne coûte pas plus cher que multiplier.
Démonstration. La première étape, simple, consiste à se ramener au cas des matrices symétriques définies positives via l’écriture A
−1 =
( t A.A
) −1 t A. Ensuite, lorsque B est
symétrique définie positive, on l’écrit par blocs de tailles (n/2, n/2) puis on effectue le
calcul de B
−1 en inversant récursivement différents blocs et leur complément de Schur. On
obtient ainsi un très joli algorithme « diviser pour régner »... dont le lecteur curieux trouvera
les détails par exemple dans [Cormen].
La multiplication naïve requiert de l’ordre de n
3 opérations élémentaires. Une amélioration
classique utilisant le principe « diviser pour régner » permet de descendre cette complexité
11. Les très gros ordinateurs actuels réalisent de l’ordre de 10 15 opérations sur les flottants par seconde ; on
parle de « petaflops ».