Livre_silo 30 août 2013 16:32 Page 174
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
174
Informatique pour tous
La résolution d’un système linéaire est une activité formatrice pour un étudiant commençant des études scientifiques. D’une part, c’est l’occasion de réfléchir à des notions clés
telles que les équivalences (leur validité, leur pertinence), la description d’un ensemble de
solutions, et même la notion d’équation : que signifie « résoudre ax = b » ? D’autre part,
il s’agit de perdre la mauvaise habitude fréquente consistant à « bricoler » les équations
pour arriver à une solution ¹ dont on prétend avec plus ou moins de conviction que c’est la
solution.
L’algorithme du pivot de Gauss sert à résoudre un système linéaire au sens où, partant d’un
système à n équations et p inconnues, il va fournir un système équivalent permettant de
paramétrer l’ensemble des solutions (s’il est non vide), ou de démontrer qu’il n’y a pas de
solution en fournissant une condition nécessaire non compatible. Point important d’un
tel algorithme : il ne laisse aucune place à l’astuce, on se contente d’exécuter des tâches
répétitives mais simples, comme lorsqu’on a appris à additionner ou multiplier des entiers en primaire. L’expérience montre que le plus difficile reste d’accepter de changer de
« méthode », pour peu qu’ on puisse nommer ainsi ce qu’on pratiquait en général face à un
système linéaire !
L’algorithme du pivot de Gauss, essentiellement basé sur des transvections (opérations sur
les lignes, de la forme L j ← L j − λL i ) est très simple à mettre en œuvre, du moins
lorsqu’il n’y a pas de paramètres formels, et il possède une complexité raisonnable, à savoir
cubique en la taille de la matrice.
Il existe de nombreuses variations autour du pivot, y compris pour la résolution de systèmes
linéaires, mais on verra que les mêmes idées se retrouvent dans des problèmes tels que :
• inverser une matrice (inversible) ;
• déterminer deux matrices triangulaires L et U (respectivement inférieure et supérieure)
telles que A ∈ M n (R) s’écrive LU (ou LT σ U avec T σ une matrice de permutation
— décomposition de Bruhat) ;
• calculer le déterminant de A ∈ M n (R) ;
• calculer le rang de A ∈ M n,p (R) ;
• déterminer deux matrices inversibles P et Q telles que P AQ = J r , avec r le rang de A ;
• etc.
Nous serons confrontés principalement à deux problèmes :
• La précision du résultat : elle dépend évidemment de celle des données, mais même avec
des données exactes, les erreurs d’arrondis peuvent induire des erreurs dans le résultat,
plus ou moins importantes selon la méthode choisie.
• La comparaison d’un réel à zéro : les calculs avec les flottants induisent des erreurs, qui
peuvent faire apparaître ou au contraire disparaître le réel nul (voir chapitre 2). Comparer
un coefficient à zéro n’a donc pas grand sens, alors que dans l’algorithme du pivot de
Gauss, il est crucial de s’assurer que le pivot en est bien un, c’est-à-dire qu’il est non nul !
1. En fait, plutôt un « candidat-solution », les bricolages fournissant des conditions nécessaires sur les inconnues... conditions dont on ne sait pas si elles sont suffisantes pour que les équations initiales soient vérifiées.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
174
Informatique pour tous
La résolution d’un système linéaire est une activité formatrice pour un étudiant commençant des études scientifiques. D’une part, c’est l’occasion de réfléchir à des notions clés
telles que les équivalences (leur validité, leur pertinence), la description d’un ensemble de
solutions, et même la notion d’équation : que signifie « résoudre ax = b » ? D’autre part,
il s’agit de perdre la mauvaise habitude fréquente consistant à « bricoler » les équations
pour arriver à une solution ¹ dont on prétend avec plus ou moins de conviction que c’est la
solution.
L’algorithme du pivot de Gauss sert à résoudre un système linéaire au sens où, partant d’un
système à n équations et p inconnues, il va fournir un système équivalent permettant de
paramétrer l’ensemble des solutions (s’il est non vide), ou de démontrer qu’il n’y a pas de
solution en fournissant une condition nécessaire non compatible. Point important d’un
tel algorithme : il ne laisse aucune place à l’astuce, on se contente d’exécuter des tâches
répétitives mais simples, comme lorsqu’on a appris à additionner ou multiplier des entiers en primaire. L’expérience montre que le plus difficile reste d’accepter de changer de
« méthode », pour peu qu’ on puisse nommer ainsi ce qu’on pratiquait en général face à un
système linéaire !
L’algorithme du pivot de Gauss, essentiellement basé sur des transvections (opérations sur
les lignes, de la forme L j ← L j − λL i ) est très simple à mettre en œuvre, du moins
lorsqu’il n’y a pas de paramètres formels, et il possède une complexité raisonnable, à savoir
cubique en la taille de la matrice.
Il existe de nombreuses variations autour du pivot, y compris pour la résolution de systèmes
linéaires, mais on verra que les mêmes idées se retrouvent dans des problèmes tels que :
• inverser une matrice (inversible) ;
• déterminer deux matrices triangulaires L et U (respectivement inférieure et supérieure)
telles que A ∈ M n (R) s’écrive LU (ou LT σ U avec T σ une matrice de permutation
— décomposition de Bruhat) ;
• calculer le déterminant de A ∈ M n (R) ;
• calculer le rang de A ∈ M n,p (R) ;
• déterminer deux matrices inversibles P et Q telles que P AQ = J r , avec r le rang de A ;
• etc.
Nous serons confrontés principalement à deux problèmes :
• La précision du résultat : elle dépend évidemment de celle des données, mais même avec
des données exactes, les erreurs d’arrondis peuvent induire des erreurs dans le résultat,
plus ou moins importantes selon la méthode choisie.
• La comparaison d’un réel à zéro : les calculs avec les flottants induisent des erreurs, qui
peuvent faire apparaître ou au contraire disparaître le réel nul (voir chapitre 2). Comparer
un coefficient à zéro n’a donc pas grand sens, alors que dans l’algorithme du pivot de
Gauss, il est crucial de s’assurer que le pivot en est bien un, c’est-à-dire qu’il est non nul !
1. En fait, plutôt un « candidat-solution », les bricolages fournissant des conditions nécessaires sur les inconnues... conditions dont on ne sait pas si elles sont suffisantes pour que les équations initiales soient vérifiées.