Élever une matrice à une puissance en $lo g_{2} n$ produits

Exercice d'entraînement · niveau 3 (difficile) · mathématiques approfondies (ECG 1re année), chapitre 11 — Informatique et algorithmique · Boucles, arrêt et algorithmes

Énoncé

Écrire une fonction qui calcule $A^{n}$ en n'employant que np.dot, avec un nombre de produits matriciels de l'ordre de $lo g_{2} n$ et non de $n$ . Justifier sa correction par un invariant, puis la contrôler avec al.matrix_power sur $A = (1110)$ et $n = 10$ .

Corrigé

Ce qu'on montre. Que l'écriture binaire de $n$ permet de n'effectuer que des carrés successifs, et qu'un invariant de boucle démontre la correction du procédé.

L'idée. Si $n$ est pair, $A^{n} = (A^{2})^{n /2}$ : un seul produit divise l'exposant par deux. Si $n$ est impair, $A^{n} = A \times A^{n - 1}$ et l'on se ramène au cas pair. On accumule donc les facteurs « impairs » rencontrés dans une variable, pendant qu'on élève au carré la base.

Le programme.

import numpy as np
import numpy.linalg as al

def puissance_rapide(A, n):
    """A**n avec environ 2*log2(n) produits matriciels."""
    taille = np.shape(A)[0]
    P = np.eye(taille)          # accumulateur, neutre du produit
    B = A                       # vaut A**(2**etape)
    while n > 0:
        if n % 2 == 1:
            P = np.dot(P, B)
        B = np.dot(B, B)
        n = n // 2
    return P

A = np.array([[1., 1.], [1., 0.]])
print(puissance_rapide(A, 10))
print(al.matrix_power(A, 10))

L'invariant. Notons $n_{0}$ l'exposant initial, et considérons, à chaque passage en tête de boucle, la quantité $P \times B^{n} .$ Au départ, $P = I$ , $B = A$ et $n = n_{0}$ : la quantité vaut $A^{n_{0}}$ . Un tour de boucle la conserve :

si $n$ est pair, $P$ ne change pas, $B$ devient $B^{2}$ et $n$ devient $\frac{n}{2}$ : la quantité devient $P \times (B^{2})^{n /2} = P B^{n}$ ;
si $n$ est impair, $P$ devient $P B$ , $B$ devient $B^{2}$ , $n$ devient $\frac{n - 1}{2}$ : la quantité devient $P B \times (B^{2})^{(n - 1) /2} = P B^{n}$ .

Dans les deux cas la valeur $P B^{n}$ est inchangée. À la sortie, $n = 0$ donc $B^{n} = I$ et la valeur vaut $P$ : la fonction renvoie bien $A^{n_{0}}$ . (Le calcul ci-dessus n'exige aucune commutativité étrangère : $P$ et $B$ sont toutes deux des puissances de $A$ , donc elles commutent.)

La terminaison. À chaque tour $n$ devient $⌊ n /2 ⌋$ , entier strictement plus petit tant que $n \geq 1$ : la suite décroît strictement dans $N$ , elle atteint $0$ .

Le coût. Le nombre de tours est le nombre de chiffres binaires de $n_{0}$ , soit $⌊ lo g_{2} n_{0} ⌋ + 1$ . Chaque tour fait un ou deux produits : au plus $2 lo g_{2} n_{0} + 2$ produits, contre $n_{0} - 1$ pour la méthode naïve. Pour $n_{0} = 1000$ : environ $20$ produits au lieu de $999$ .

Le contrôle. Pour $A = (1110)$ , une récurrence donne $A^{n} = (F_{n + 1} F_{n} F_{n} F_{n - 1})$ où $(F_{n})$ est la suite de Fibonacci. Avec $F_{11} = 89$ , $F_{10} = 55$ , $F_{9} = 34$ , les deux affichages donnent $A^{10} = (89555534),$ identiques à la matrice renvoyée par al.matrix_power.

Point délicat. np.eye produit des flottants : la comparaison avec al.matrix_power se fait avec np.allclose, jamais avec ==.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.

Élever une matrice à une puissance en log2​n produits

Énoncé

Corrigé

Élever une matrice à une puissance en $lo g_{2} n$ produits