Puissance d'une matrice

Le problème

Pour l'ensemble de ce TD, vous utiliserez, bien entendu, la bibliothèque d'opérations sur les matrices que nous avons déjà écrite.

1. Ecrire une procédure ou fonction itérative puiss-iter permettant de calculer une matrice à une puissance quelconque ;
2. écrire une procédure ou fonction récursive puiss-recu permettant de calculer une matrice à une puissance quelconque ;
3. essayer d'évaluer, avec un papier et un crayon, le nombre d'opérations (multiplications et additions) requises pour élever une matrice carrée de taille n à la puissance p ;

Programmation

Il y a bien longtemps que les Mathématiciens savent qu'effectuer (n-1) multiplications pour calculer un nombre à la puissance n est loin d'être une méthode optimale (Legendre, 1798). En effet, pour calculer, par exemple, 7¹⁶ il faut effectuer :

7² = 49
7⁴ = 49 * 49 = 2 401
7⁸ = 2 401 * 2 401 = 5 764 801
7¹⁶ = 5 764 801 * 5 764 801 = 33 232 930 569 601

Ce calcul ne nécessite que 4 multiplications au lieu de 15 !!!

On peut généraliser ce raisonnement de la manière suivante : soient M et A deux réels (ou deux matrices !) et p un entier, le produit MxA^p reste constant au cours des deux opérations suivantes :

si p est pair
remplacer A par A² et p par p/2

sinon
remplacer M par MxA et p par p-1

Au cours de ces opérations l'entier p ne peut que diminuer, il atteint donc obligatoirement 0.

A vous d'écrire une procédure ou fonction puiss-legendre qui utilise l'algorithme de Legendre ci-dessus pour calculer la puissance d'une matrice.