mathématiques approfondies (ECG 1re année) · Chapitre 11 · Exercice d'entraînement

Élever une matrice à une puissance en ${\log }_{2}n$ produits

Informatique et algorithmique · Boucles, arrêt et algorithmes · ★★★ niveau 3 (difficile)

Énoncé

Écrire une fonction qui calcule $A^n$ en n'employant que np.dot, avec un nombre de produits matriciels de l'ordre de ${\log }_{2}n$ et non de $n$. Justifier sa correction par un invariant, puis la contrôler avec al.matrix_power sur $A=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ et $n=10$.

Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.