Livre_silo 30 août 2013 16:32 Page 194
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
194
Informatique pour tous
Les valeurs extrêmes du spectre des matrices de Hilbert sont relativement bien connues, mais les résultats
(surtout l’équivalent de la plus petite) sont « non élémentaires » à démontrer !
Exercice 7.13 Comment l’exercice 7.9 a-t-il été conçu ?
7.5 Exercices
Exercice 7.14 * Démontrer rigoureusement à l’aide d’un invariant de boucle que la première phase de
l’algorithme du pivot de Gauss conduit à un système sous forme triangulaire.
Exercice 7.15 Une façon naïve pour calculer le déterminant d’une matrice consiste à développer selon
une ligne ou colonne, ce qui amène à un calcul récursif coûteux en général.
1 Évaluer la complexité d’un tel algorithme.
2 Si un ordinateur peut effectuer 10 9 opérations sur les flottants par seconde, jusqu’à quelle dimension
peut-on espérer calculer un déterminant par cette méthode en un temps majoré par une journée ?
Une autre façon de calculer le déterminant consiste à pivoter, pour se ramener à une matrice diagonale.
3 Expliciter cet algorithme à l’aide de pseudo-code. Évaluer sa complexité.
4 Programmer effectivement cet algorithme en Python.
5 Le tester, exhiber des cas limites mettant en défaut le programme.
Le lecteur voulant tester sa virtuosité en manipulation de tableaux avec numpy pourra programmer le calcul
naïf du déterminant et vérifier empiriquement la complexité.
Exercice 7.16 * En réalisant des opérations élémentaires sur les lignes (et/ou colonnes, mais on peut se
contenter d’opérations sur les lignes), on peut passer d’une matrice inversible quelconque A à la matrice
identité In. Ceci permet de calculer A −1 .
1 Préciser l’algorithme à l’aide de pseudo-code. Évaluer sa complexité.
2 Programmer effectivement cet algorithme en Python.
3 Tester ce programme sur des exemples tels que Vn et Hn (matrices de Virginie et de Hilbert). Comparer
le résultat numérique avec celui obtenu avec numpy.
4 Vérifier empiriquement que le temps de calcul de ce programme est bien de l’ordre du cube de la
dimension de la matrice à inverser.
Exercice 7.17 Le module fractions de Python fournit une représentation et des opérations pour manipuler des rationnels en valeur exacte. L’expression Fraction(numerateur, denominateur) construit la
fraction correspondante, sur laquelle on peut ensuite utiliser les opérations usuelles. On consultera sa
documentation pour plus de détails.
1 Adapter le programme Python du pivot de Gauss pour qu’il résolve des systèmes à coefficients rationnels
de façon exacte.
2 Le tester sur des exemples tels que Vn et Hn (matrices de Virginie et de Hilbert).
3 Empiriquement, le temps de calcul de ce programme est-il toujours de l’ordre du cube de la dimension
de la matrice à inverser ? Si ce n’est pas le cas, proposer une explication.
Exercice 7.18 * Pour tester une procédure « maison » calculant l’inverse d’une matrice, on va l’exécuter
sur une matrice aléatoire, dont on peut raisonnablement espérer qu’elle sera inversible. On comparera
(en termes de précicion et de rapidité) avec la fonction dédiée numpy.linalg.inv.
1 Évaluer la différence entre les résultats de votre procédure d’inversion et ceux de numpy.linalg.inv, sur
des matrices de taille (n, n), avec n ∈ {10, 50, 100, 200}.
2 En utilisant le module Image, visualiser les matrices initiales et inverses.
Pour évaluer la différence, on commencera par choisir une norme matricielle. Pour visualiser, on renormalisera la matrice pour obtenir des coefficients entre 0 et 255, ce qui permet de créer un fichier bitmap.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
194
Informatique pour tous
Les valeurs extrêmes du spectre des matrices de Hilbert sont relativement bien connues, mais les résultats
(surtout l’équivalent de la plus petite) sont « non élémentaires » à démontrer !
Exercice 7.13 Comment l’exercice 7.9 a-t-il été conçu ?
7.5 Exercices
Exercice 7.14 * Démontrer rigoureusement à l’aide d’un invariant de boucle que la première phase de
l’algorithme du pivot de Gauss conduit à un système sous forme triangulaire.
Exercice 7.15 Une façon naïve pour calculer le déterminant d’une matrice consiste à développer selon
une ligne ou colonne, ce qui amène à un calcul récursif coûteux en général.
1 Évaluer la complexité d’un tel algorithme.
2 Si un ordinateur peut effectuer 10 9 opérations sur les flottants par seconde, jusqu’à quelle dimension
peut-on espérer calculer un déterminant par cette méthode en un temps majoré par une journée ?
Une autre façon de calculer le déterminant consiste à pivoter, pour se ramener à une matrice diagonale.
3 Expliciter cet algorithme à l’aide de pseudo-code. Évaluer sa complexité.
4 Programmer effectivement cet algorithme en Python.
5 Le tester, exhiber des cas limites mettant en défaut le programme.
Le lecteur voulant tester sa virtuosité en manipulation de tableaux avec numpy pourra programmer le calcul
naïf du déterminant et vérifier empiriquement la complexité.
Exercice 7.16 * En réalisant des opérations élémentaires sur les lignes (et/ou colonnes, mais on peut se
contenter d’opérations sur les lignes), on peut passer d’une matrice inversible quelconque A à la matrice
identité In. Ceci permet de calculer A −1 .
1 Préciser l’algorithme à l’aide de pseudo-code. Évaluer sa complexité.
2 Programmer effectivement cet algorithme en Python.
3 Tester ce programme sur des exemples tels que Vn et Hn (matrices de Virginie et de Hilbert). Comparer
le résultat numérique avec celui obtenu avec numpy.
4 Vérifier empiriquement que le temps de calcul de ce programme est bien de l’ordre du cube de la
dimension de la matrice à inverser.
Exercice 7.17 Le module fractions de Python fournit une représentation et des opérations pour manipuler des rationnels en valeur exacte. L’expression Fraction(numerateur, denominateur) construit la
fraction correspondante, sur laquelle on peut ensuite utiliser les opérations usuelles. On consultera sa
documentation pour plus de détails.
1 Adapter le programme Python du pivot de Gauss pour qu’il résolve des systèmes à coefficients rationnels
de façon exacte.
2 Le tester sur des exemples tels que Vn et Hn (matrices de Virginie et de Hilbert).
3 Empiriquement, le temps de calcul de ce programme est-il toujours de l’ordre du cube de la dimension
de la matrice à inverser ? Si ce n’est pas le cas, proposer une explication.
Exercice 7.18 * Pour tester une procédure « maison » calculant l’inverse d’une matrice, on va l’exécuter
sur une matrice aléatoire, dont on peut raisonnablement espérer qu’elle sera inversible. On comparera
(en termes de précicion et de rapidité) avec la fonction dédiée numpy.linalg.inv.
1 Évaluer la différence entre les résultats de votre procédure d’inversion et ceux de numpy.linalg.inv, sur
des matrices de taille (n, n), avec n ∈ {10, 50, 100, 200}.
2 En utilisant le module Image, visualiser les matrices initiales et inverses.
Pour évaluer la différence, on commencera par choisir une norme matricielle. Pour visualiser, on renormalisera la matrice pour obtenir des coefficients entre 0 et 255, ce qui permet de créer un fichier bitmap.