Livre_silo 30 août 2013 16:32 Page 198
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
198
Informatique pour tous
POUR ALLER PLUS LOIN Méthode de Gauss-Seidel
La méthode de Jacobi est la plus élémentaire des méthodes itératives. Ces dernières, de
façon générique, partent d’une décomposition A = D + M , avec D « facilement » inversible ²⁰, et on itère l’opération x ← −D −1 M x+D −1 y dans le but de s’approcher d’un point
fixe de l’application Z → −D −1 M Z + D −1 y.
Pour la méthode de Jacobi, D est constituée uniquement des éléments diagonaux (avec
des zéros en dehors de la diagonale). Une variante est la méthode de Gauss-Seidel : il
s’agit simplement de prendre pour D la matrice constituée des éléments diagonaux et sousdiagonaux de A. En pratique, cela revient à calculer la i-ème composante de x (k) en utilisant les composantes x
(k+1)
j
déjà calculées pour j < i et les x
(k)
j
pour j ⩾ i. Cette simple
modification améliore la convergence.
La méthode de Gauss-Seidel est beaucoup plus délicate à paralléliser, mais ça reste possible
en pipelinant les calculs. C’est très technique, mais le jeu en vaut la chandelle !
Exercice 7.23 * On s’intéresse ici au calcul du polynôme minimal d’une matrice carrée A ∈ Mn(K),
c’est-à-dire le polynôme unitaire P de plus petit degré tel que P (A) = 0. On sait qu’un tel polynôme
existe et est de degré majoré par n.
1 Un algorithme simple pour calculer le polynôme minimal d’une matrice A ∈ Mn(K) consiste à calculer
A 2 , ..., A n , placer leurs coefficients (ainsi que ceux de In) dans une matrice B ∈ M n 2 ,n (K), pivoter
sur les colonnes jusqu’à obtenir une colonne nulle, fournissant ainsi une combinaison linéaire nulle non
triviale et minimale des A k .
a) Détailler, en écrivant le pseudo-code de l’algorithme.
b) Montrer qu’on obtient ainsi un calcul du polynôme minimal en O(n 4 ) opérations élémentaires.
c) Expliquer pourquoi, numériquement, cet algorithme est voué à l’échec. ²¹
2 (Difficile) Proposer un algorithme probabiliste permettant d’obtenir en O(n 3 ) opérations arithmétiques
le polynôme minimal d’une matrice « avec une forte probabilité »... en un sens à préciser !
On pourra tirer un vecteur au hasard et calculer le polynôme minimal de A vis-à-vis de ce vecteur.
Exercice 7.24 **** Pour rire.
Le Permanent d’une matrice A ∈ Mn(K) est défini par :
∑
σ∈Sn
n
∏
i=1
a i,σ(i) .
Trouver un algorithme calculant le permanent d’une matrice de Mn(K) en temps polynomial en n.
ATTENTION Un exercice impossible ?
On évitera de passer trop de temps sur l’exercice précédent... Le lecteur intéressé pourra
faire une recherche sur le mot-clé « ♯P-complet » (prononcer « sharp P-complet »). Quelqu’un sachant calculer le permanent en temps polynômial sait répondre rapidement à la
question suivante : « combien de n-uplets de booléens (b 1 , ..., bn) satisfont telle formule
booléenne (de longueur O(n)) ? ». Cette personne sait a fortiori répondre rapidement à la
question « Telle formule booléenne de longueur O(n) est-elle satisfaisable ? ».
Fortune et gloire sont promises à cette personne.
20. Au sens : la résolution de DX = Y est simple.
21. Si on fait du calcul formel dans Mn(Q) par exemple, il est tout à fait valable. Encore une idée de TP !
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
198
Informatique pour tous
POUR ALLER PLUS LOIN Méthode de Gauss-Seidel
La méthode de Jacobi est la plus élémentaire des méthodes itératives. Ces dernières, de
façon générique, partent d’une décomposition A = D + M , avec D « facilement » inversible ²⁰, et on itère l’opération x ← −D −1 M x+D −1 y dans le but de s’approcher d’un point
fixe de l’application Z → −D −1 M Z + D −1 y.
Pour la méthode de Jacobi, D est constituée uniquement des éléments diagonaux (avec
des zéros en dehors de la diagonale). Une variante est la méthode de Gauss-Seidel : il
s’agit simplement de prendre pour D la matrice constituée des éléments diagonaux et sousdiagonaux de A. En pratique, cela revient à calculer la i-ème composante de x (k) en utilisant les composantes x
(k+1)
j
déjà calculées pour j < i et les x
(k)
j
pour j ⩾ i. Cette simple
modification améliore la convergence.
La méthode de Gauss-Seidel est beaucoup plus délicate à paralléliser, mais ça reste possible
en pipelinant les calculs. C’est très technique, mais le jeu en vaut la chandelle !
Exercice 7.23 * On s’intéresse ici au calcul du polynôme minimal d’une matrice carrée A ∈ Mn(K),
c’est-à-dire le polynôme unitaire P de plus petit degré tel que P (A) = 0. On sait qu’un tel polynôme
existe et est de degré majoré par n.
1 Un algorithme simple pour calculer le polynôme minimal d’une matrice A ∈ Mn(K) consiste à calculer
A 2 , ..., A n , placer leurs coefficients (ainsi que ceux de In) dans une matrice B ∈ M n 2 ,n (K), pivoter
sur les colonnes jusqu’à obtenir une colonne nulle, fournissant ainsi une combinaison linéaire nulle non
triviale et minimale des A k .
a) Détailler, en écrivant le pseudo-code de l’algorithme.
b) Montrer qu’on obtient ainsi un calcul du polynôme minimal en O(n 4 ) opérations élémentaires.
c) Expliquer pourquoi, numériquement, cet algorithme est voué à l’échec. ²¹
2 (Difficile) Proposer un algorithme probabiliste permettant d’obtenir en O(n 3 ) opérations arithmétiques
le polynôme minimal d’une matrice « avec une forte probabilité »... en un sens à préciser !
On pourra tirer un vecteur au hasard et calculer le polynôme minimal de A vis-à-vis de ce vecteur.
Exercice 7.24 **** Pour rire.
Le Permanent d’une matrice A ∈ Mn(K) est défini par :
∑
σ∈Sn
n
∏
i=1
a i,σ(i) .
Trouver un algorithme calculant le permanent d’une matrice de Mn(K) en temps polynomial en n.
ATTENTION Un exercice impossible ?
On évitera de passer trop de temps sur l’exercice précédent... Le lecteur intéressé pourra
faire une recherche sur le mot-clé « ♯P-complet » (prononcer « sharp P-complet »). Quelqu’un sachant calculer le permanent en temps polynômial sait répondre rapidement à la
question suivante : « combien de n-uplets de booléens (b 1 , ..., bn) satisfont telle formule
booléenne (de longueur O(n)) ? ». Cette personne sait a fortiori répondre rapidement à la
question « Telle formule booléenne de longueur O(n) est-elle satisfaisable ? ».
Fortune et gloire sont promises à cette personne.
20. Au sens : la résolution de DX = Y est simple.
21. Si on fait du calcul formel dans Mn(Q) par exemple, il est tout à fait valable. Encore une idée de TP !