Puissance rapide d'une matrice
Exponentiation en $O(\log n)$
Enonce
Implémenter $A^n$ par exponentiation rapide, sans utiliser np.linalg.matrix_power. $A$ est carrée, $n \geq 0$. Utiliser l'opérateur @ pour le produit matriciel.
Signature attendue
def puissance_rapide(A: np.ndarray, n: int) -> np.ndarray:Exemples
int(puissance_rapide(F, 10)[0, 1])→F(10) = 55int(puissance_rapide(F, 20)[0, 1])→F(20) = 6765
📖 Rappel de cours
Calculer $A^n$ naïvement par $n-1$ multiplications coûte $O(k^3 \cdot n)$ ($k$ = taille de $A$). L'exponentiation rapide exploite la décomposition binaire de $n$ :
$A^n = \begin{cases} I & \text{si } n = 0 \\ (A^{n/2})^2 & \text{si } n \text{ pair} \\ A \cdot A^{n-1} & \text{si } n \text{ impair} \end{cases}$
Exemple : $A^{13} = A \cdot A^{12} = A \cdot (A^6)^2 = A \cdot ((A^3)^2)^2$, soit 5 multiplications au lieu de 12.
Application ECG : calcul du $n$-ième terme d'une suite récurrente linéaire (Fibonacci, suites arithmético-géométriques) ou de la distribution à long terme d'une chaîne de Markov.
← Exercices Python pour la prépa ECG — probabilités, matrices, suites
Exercices du meme theme
- Loi des grands nombres
- Produit matriciel
- Résolution d'un système linéaire
- Chaîne de Markov — distribution à $n$ étapes
- Distribution stationnaire d'une chaîne de Markov
- Mensualité d'un prêt à taux fixe
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.