05 · Matrices : opérations de base¶
Intuition
Une matrice est un tableau de nombres. Ce n'est pas une définition très éclairante — l'important est ce qu'elle représente : une transformation de l'espace, un système d'équations, un graphe, un jeu de données.
Le point qui déroute au début est le produit matriciel. Il n'est pas « terme à terme », et cela paraît arbitraire. La raison est simple : le produit de matrices est fait pour représenter la composition de transformations. La formule bizarre est exactement celle qui rend \(\mathbf{A}\mathbf{B}\) égal à « appliquer \(\mathbf{B}\), puis \(\mathbf{A}\) ».
Une fois ce fait admis, la non-commutativité cesse d'être surprenante : mettre ses chaussettes puis ses chaussures n'est pas la même chose que l'inverse.
1. Définitions¶
Une matrice \(\mathbf{A}\) de taille \(n \times p\) (\(n\) lignes, \(p\) colonnes) est un tableau
On note \(a_{ij}\) le coefficient situé ligne \(i\), colonne \(j\).
L'ordre des indices
Ligne d'abord, colonne ensuite. \(a_{23}\) est ligne 2, colonne 3. Et une matrice « \(3\times5\) » a 3 lignes et 5 colonnes.
C'est une convention arbitraire mais universelle, et l'inverser produit des erreurs indétectables.
L'ensemble des matrices \(n\times p\) à coefficients réels se note \(\mathcal{M}_{n,p}(\mathbb{R})\), et \(\mathcal{M}_n(\mathbb{R})\) si \(n = p\) (matrices carrées).
1.1 Matrices particulières¶
| Nom | Description |
|---|---|
| Ligne | \(1\times p\) |
| Colonne (ou vecteur) | \(n\times1\) |
| Carrée | \(n\times n\) |
| Nulle \(\mathbf{0}\) | tous coefficients nuls |
| Diagonale | carrée, \(a_{ij}=0\) pour \(i\neq j\) |
| Identité \(\mathbf{I}_n\) | diagonale avec des 1 |
| Triangulaire supérieure | \(a_{ij}=0\) pour \(i>j\) |
| Triangulaire inférieure | \(a_{ij}=0\) pour \(i<j\) |
| Symétrique | carrée, \(a_{ij}=a_{ji}\) |
2. Somme et multiplication par un scalaire¶
Ces deux opérations sont terme à terme, et ne réservent aucune surprise.
Condition de taille
On n'additionne que des matrices de même taille. Il n'y a aucune convention de complétion par des zéros.
Propriétés : la somme est commutative, associative, d'élément neutre \(\mathbf{0}\), et chaque matrice a un opposé. Avec la multiplication scalaire, \(\mathcal{M}_{n,p}(\mathbb{R})\) est un espace vectoriel — notion qui sera formalisée plus tard, mais dont on utilise déjà les règles.
3. Le produit matriciel¶
3.1 La règle¶
Définition
Si \(\mathbf{A}\) est \(n\times p\) et \(\mathbf{B}\) est \(p\times q\), alors \(\mathbf{AB}\) est \(n\times q\), de coefficients
Ce que dit la formule : le coefficient en position \((i,j)\) est le produit scalaire de la ligne \(i\) de \(\mathbf{A}\) par la colonne \(j\) de \(\mathbf{B}\).
La condition de compatibilité
Le nombre de colonnes de la première doit égaler le nombre de lignes de la seconde. Sinon le produit n'existe pas — ce n'est pas « zéro », c'est indéfini.
Méthode mnémotechnique : écrivez les tailles côte à côte. Les deux nombres du milieu doivent être égaux et disparaissent ; les extrêmes donnent la taille du résultat.
3.2 La disposition pratique¶
Pour calculer à la main sans se tromper, disposez \(\mathbf{B}\) au-dessus à droite :
| b11 b12 |
| b21 b22 |
------------+-----------
| a11 a12 | | c11 c12 |
| a21 a22 | | c21 c22 |
Le coefficient \(c_{ij}\) se trouve à l'intersection de la ligne \(i\) de \(\mathbf{A}\) et de la colonne \(j\) de \(\mathbf{B}\) — littéralement, à la croisée.
3.3 Exemple détaillé¶
Et dans l'autre sens :
3.4 Propriétés — et les trois pièges¶
Ce qui est vrai :
Piège 1 — le produit n'est pas commutatif
\(\mathbf{AB} \neq \mathbf{BA}\) en général. Les deux peuvent même ne pas avoir la même taille, ou l'un exister et l'autre non.
Conséquence : \((\mathbf{A}+\mathbf{B})^2 = \mathbf{A}^2 + \mathbf{AB}+\mathbf{BA}+\mathbf{B}^2\), et non \(\mathbf{A}^2+2\mathbf{AB} +\mathbf{B}^2\). Les identités remarquables ne s'appliquent que si \(\mathbf{A}\) et \(\mathbf{B}\) commutent.
Piège 2 — un produit peut être nul sans facteur nul
Le théorème du produit nul, valable pour les réels, est faux pour les matrices. On dit qu'il existe des diviseurs de zéro.
Piège 3 — on ne peut pas simplifier
\(\mathbf{AB} = \mathbf{AC}\) n'implique pas \(\mathbf{B} = \mathbf{C}\), même si \(\mathbf{A}\neq\mathbf{0}\).
La simplification n'est licite que si \(\mathbf{A}\) est inversible — voir le chapitre 08.
3.5 Pourquoi cette définition¶
Une matrice \(n\times p\) code une application linéaire de \(\mathbb{R}^p\) vers \(\mathbb{R}^n\) : le vecteur colonne \(\mathbf{x}\) est envoyé sur \(\mathbf{A}\mathbf{x}\).
Avec cette lecture, le produit \(\mathbf{AB}\) correspond exactement à la composée : \(\mathbf{A}(\mathbf{B}\mathbf{x}) = (\mathbf{AB})\mathbf{x}\).
Tout s'explique
- La non-commutativité vient de celle de la composition (chapitre 03).
- L'associativité vient de celle de la composition, qui est automatique.
- L'identité correspond à l'application identité.
- La condition de taille traduit que l'arrivée de la première application doit être le départ de la seconde.
Exemple concret — rotation du plan. La rotation d'angle \(\theta\) autour de l'origine a pour matrice
et l'on vérifie que \(\mathbf{R}_\alpha\mathbf{R}_\beta = \mathbf{R}_{\alpha+\beta}\) : composer deux rotations, c'est additionner les angles. Le produit matriciel contient les formules d'addition de \(\cos\) et \(\sin\).
4. Puissances¶
Pour \(\mathbf{A}\) carrée : \(\mathbf{A}^0 = \mathbf{I}\), \(\mathbf{A}^{n+1} = \mathbf{A}^n\mathbf{A}\).
Cas facile — matrice diagonale :
L'objectif du bloc matriciel
Calculer \(\mathbf{A}^n\) pour une matrice quelconque est difficile. Toute la fin de cette partie — déterminant, valeurs propres, diagonalisation — vise à ramener \(\mathbf{A}\) à une forme diagonale, où le calcul redevient trivial.
Cas utile — matrice nilpotente. Si \(\mathbf{N}^k = \mathbf{0}\) pour un certain \(k\), les puissances s'arrêtent. Combinée au binôme (quand les matrices commutent), cette propriété permet des calculs explicites — voir l'exemple 4.
5. Transposée¶
On échange lignes et colonnes ; une matrice \(n\times p\) devient \(p\times n\).
Propriétés :
L'ordre s'inverse dans la transposée d'un produit
Comme pour la réciproque d'une composée. Ce n'est pas une coïncidence : transposer, c'est passer à l'application « duale », qui inverse le sens des flèches.
\(\mathbf{A}\) est symétrique si \(\mathbf{A}^\top = \mathbf{A}\). Les matrices symétriques réelles jouent un rôle central : ce sont exactement celles qui sont diagonalisables en base orthonormée, et les matrices de covariance en probabilités en sont.
6. Trace¶
La somme des coefficients diagonaux, définie pour les matrices carrées.
Une propriété remarquable
\(\operatorname{tr}(\mathbf{AB}) = \operatorname{tr}(\mathbf{BA})\) même quand \(\mathbf{AB}\neq\mathbf{BA}\). C'est l'une des rares quantités insensibles à l'ordre, et elle servira au chapitre 09 : la trace est la somme des valeurs propres.
Exemples traités¶
Exemple 1 — Produit et vérification des tailles
Tailles : \((2\times\mathbf 3)(\mathbf 3\times2) \to 2\times2\) ✓
Notez que \(\mathbf{BA}\) existe aussi mais est \(3\times3\) : les deux produits n'ont même pas la même taille.
Exemple 2 — Une matrice qui n'est pas ce qu'elle semble
Soit \(\mathbf{J} = \begin{pmatrix}1&1\\1&1\end{pmatrix}\). Calculer \(\mathbf{J}^n\).
Donc \(\mathbf{J}^3 = \mathbf{J}^2\mathbf{J} = 2\mathbf{J}^2 = 4\mathbf{J}\), et par récurrence immédiate :
Vérification \(n=1\) : \(2^0\mathbf J = \mathbf J\) ✓
La technique
Chercher une relation polynomiale vérifiée par \(\mathbf{A}\) — ici \(\mathbf{J}^2 = 2\mathbf{J}\) — est souvent bien plus rapide que la diagonalisation. Cette relation s'appelle un polynôme annulateur, et elle est au cœur du théorème de Cayley-Hamilton.
Exemple 3 — Matrice d'adjacence d'un graphe
Soit un graphe à 3 sommets, avec les arêtes \(1\to2\), \(2\to3\), \(1\to3\). Sa matrice d'adjacence \(\mathbf{M}\) vaut 1 en \((i,j)\) s'il y a une arête de \(i\) vers \(j\) :
Calculons \(\mathbf{M}^2\) :
Le coefficient \((1,3)\) vaut 1 : il existe exactement un chemin de longueur 2 de 1 vers 3, à savoir \(1\to2\to3\).
Théorème implicite
\((\mathbf{M}^k)_{ij}\) est le nombre de chemins de longueur exactement \(k\) allant de \(i\) à \(j\).
La démonstration est immédiate par récurrence, en lisant la formule du produit : \((\mathbf M^{k+1})_{ij} = \sum_s (\mathbf M^k)_{is}m_{sj}\) — on découpe un chemin de longueur \(k+1\) selon son avant-dernier sommet.
C'est le fondement du calcul de la fermeture transitive, au programme de théorie des graphes au deuxième semestre.
Exemple 4 — Binôme matriciel
Soit \(\mathbf{A} = \begin{pmatrix}1&1\\0&1\end{pmatrix}\). Calculer \(\mathbf{A}^n\).
Écrivons \(\mathbf{A} = \mathbf{I}+\mathbf{N}\) avec \(\mathbf{N} = \begin{pmatrix}0&1\\0&0\end{pmatrix}\).
On vérifie que \(\mathbf{N}^2 = \mathbf{0}\) : \(\mathbf{N}\) est nilpotente.
Comme \(\mathbf{I}\) commute avec tout, le binôme de Newton s'applique :
(tous les termes avec \(k\geqslant2\) sont nuls).
La condition de commutation
Le binôme n'est licite que parce que \(\mathbf I\) et \(\mathbf N\) commutent. Avec deux matrices quelconques, l'écriture \((\mathbf A+\mathbf B)^n = \sum\binom nk\mathbf A^{n-k}\mathbf B^k\) est fausse — il faudrait tenir compte de tous les ordres possibles.
Erreurs fréquentes¶
| Erreur | Correction |
|---|---|
| Multiplier terme à terme | Ligne × colonne |
| Ignorer la compatibilité des tailles | Colonnes de \(\mathbf A\) = lignes de \(\mathbf B\) |
| \(\mathbf{AB}=\mathbf{BA}\) | Faux en général |
| \((\mathbf A+\mathbf B)^2 = \mathbf A^2+2\mathbf{AB}+\mathbf B^2\) | Seulement si elles commutent |
| \(\mathbf{AB}=\mathbf 0 \implies \mathbf A=\mathbf 0\) ou \(\mathbf B=\mathbf 0\) | Faux |
| \((\mathbf{AB})^\top = \mathbf A^\top\mathbf B^\top\) | L'ordre s'inverse |
Exercices¶
Dans tout ce qui suit :
★ Exercice 1. Calculer \(\mathbf{A}+\mathbf{B}\), \(3\mathbf{A}\), \(\mathbf{A}-2\mathbf{B}\).
★ Exercice 2. Calculer \(\mathbf{AB}\) et \(\mathbf{BA}\). Sont-elles égales ?
★ Exercice 3. Pour chaque produit, dire s'il existe et donner sa taille : \(\mathbf{AC}\), \(\mathbf{CA}\), \(\mathbf{C}^\top\mathbf{C}\), \(\mathbf{C}\mathbf{C}^\top\).
★★ Exercice 4. Calculer \(\mathbf{A}^2\), puis vérifier que \(\mathbf{A}^2 = 2\mathbf{A}-3\mathbf{I}_2\).
En déduire \(\mathbf{A}^3\) sans effectuer de produit matriciel.
★★ Exercice 5. Soit \(\mathbf{D} = \begin{pmatrix}2&0\\0&-1\end{pmatrix}\). Calculer \(\mathbf{D}^5\) et \(\mathbf{D}^{100}\).
★★ Exercice 6. Soit \(\mathbf{N} = \begin{pmatrix}0&2&3\\0&0&4\\0&0&0\end{pmatrix}\).
a) Calculer \(\mathbf{N}^2\) et \(\mathbf{N}^3\). b) En déduire \((\mathbf{I}_3+\mathbf{N})^n\) pour tout \(n\geqslant2\).
★★★ Exercice 7. Trouver toutes les matrices \(\mathbf{M}\) de \(\mathcal{M}_2(\mathbb{R})\) qui commutent avec \(\mathbf{A} = \begin{pmatrix}1&1\\0&1\end{pmatrix}\).
★★★ Exercice 8. Soit \(\mathbf{R}_\theta = \begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix}\).
a) Calculer \(\mathbf{R}_\alpha\mathbf{R}_\beta\) et montrer que c'est \(\mathbf{R}_{\alpha+\beta}\). b) En déduire \(\mathbf{R}_\theta^n\). c) Quelles formules de trigonométrie a-t-on redémontrées ?
★★★ Exercice 9. Soit \(\mathbf{A}\in\mathcal{M}_n(\mathbb{R})\).
a) Montrer que \(\mathbf{A}+\mathbf{A}^\top\) est symétrique. b) Montrer que \(\mathbf{A}-\mathbf{A}^\top\) est antisymétrique (\(\mathbf{M}^\top = -\mathbf{M}\)). c) En déduire que toute matrice carrée se décompose de manière unique en somme d'une symétrique et d'une antisymétrique. d) Appliquer à \(\mathbf{A} = \begin{pmatrix}1&4\\2&3\end{pmatrix}\).
★★★★ Exercice 10. Soit \(\mathbf{F} = \begin{pmatrix}1&1\\1&0\end{pmatrix}\).
a) Calculer \(\mathbf{F}^2\), \(\mathbf{F}^3\), \(\mathbf{F}^4\). b) Conjecturer une expression de \(\mathbf{F}^n\) en fonction des nombres de Fibonacci \(F_n\) (avec \(F_0=0\), \(F_1=1\), \(F_{n+2}=F_{n+1}+F_n\)). c) Démontrer la conjecture par récurrence. d) En déduire la relation \(F_{m+n} = F_{m+1}F_n + F_m F_{n-1}\).
★★★★ Exercice 11 — lien informatique. Le produit de deux matrices \(n\times n\) par la définition demande \(n^3\) multiplications.
a) Vérifier ce compte. b) L'algorithme de Strassen ramène le produit \(2\times2\) à 7 multiplications au lieu de 8, au prix d'additions supplémentaires. En appliquant cette idée récursivement à des matrices \(n\times n\) découpées en quatre blocs, montrer que le nombre de multiplications \(M(n)\) vérifie \(M(n) = 7M(n/2)\), et en déduire \(M(n) = n^{\log_2 7}\). c) Calculer \(\log_2 7\) et comparer à 3. À partir de quelle taille le gain dépasse-t-il un facteur 2 ? d) Pourquoi Strassen n'est-il pas utilisé pour de petites matrices ?
Corrigés¶
Corrigé — Exercice 1
Corrigé — Exercice 2
Non égales. On remarque au passage que \(\mathbf{BA}\) est symétrique alors que \(\mathbf{AB}\) ne l'est pas — coïncidence de cet exemple.
Vérification par la trace : \(\operatorname{tr}(\mathbf{AB}) = 4+12 = 16\) et \(\operatorname{tr}(\mathbf{BA}) = 14+2 = 16\) ✓ — cohérent avec la propriété \(\operatorname{tr}(\mathbf{AB})=\operatorname{tr}(\mathbf{BA})\).
Corrigé — Exercice 3
\(\mathbf{A}\) est \(2\times2\), \(\mathbf{C}\) est \(2\times3\).
- \(\mathbf{AC}\) : \((2\times2)(2\times3)\) ✓ existe, taille \(2\times3\).
- \(\mathbf{CA}\) : \((2\times3)(2\times2)\) ✗ — \(3\neq2\), n'existe pas.
- \(\mathbf{C}^\top\mathbf{C}\) : \((3\times2)(2\times3)\) ✓ taille \(3\times3\).
- \(\mathbf{C}\mathbf{C}^\top\) : \((2\times3)(3\times2)\) ✓ taille \(2\times2\).
Info
\(\mathbf{C}^\top\mathbf{C}\) et \(\mathbf{C}\mathbf{C}^\top\) sont toujours symétriques, quelle que soit \(\mathbf{C}\) : \((\mathbf{C}^\top\mathbf{C})^\top = \mathbf{C}^\top(\mathbf{C}^\top)^\top = \mathbf{C}^\top\mathbf{C}\). C'est de cette façon qu'apparaissent les matrices de covariance en statistique.
Corrigé — Exercice 4
Vérification de la relation :
Calcul de \(\mathbf{A}^3\). On multiplie la relation par \(\mathbf{A}\) :
Ce que cette relation est
\(\mathbf{A}^2-2\mathbf{A}+3\mathbf{I}=\mathbf{0}\) est le polynôme caractéristique de \(\mathbf{A}\) appliqué à \(\mathbf{A}\) — c'est le théorème de Cayley-Hamilton, qu'on retrouvera au chapitre 09. Elle permet de réduire toute puissance de \(\mathbf{A}\) à une combinaison de \(\mathbf{A}\) et \(\mathbf{I}\).
Corrigé — Exercice 5
car \((-1)^{100} = 1\). Et \(2^{100}\approx1{,}27\times10^{30}\).
Corrigé — Exercice 6
a)
b) \(\mathbf{I}\) commute avec \(\mathbf{N}\), donc le binôme s'applique. Comme \(\mathbf{N}^k = \mathbf 0\) pour \(k\geqslant3\), il ne reste que trois termes :
soit un coefficient \((1,3)\) égal à \(4n^2-n\).
Vérification \(n=2\) : \(4(4)-2 = 14\). Et par le calcul direct, \((\mathbf I+\mathbf N)^2 = \mathbf I+2\mathbf N+\mathbf N^2\) a pour coefficient \((1,3)\) : \(0+2(3)+8 = 14\) ✓
Corrigé — Exercice 7
Posons \(\mathbf{M} = \begin{pmatrix}a&b\\c&d\end{pmatrix}\).
L'égalité coefficient par coefficient donne :
- \((1,1)\) : \(a+c = a\) donc \(c = 0\) ;
- \((1,2)\) : \(b+d = a+b\) donc \(d = a\) ;
- \((2,1)\) : \(c = c\), sans information ;
- \((2,2)\) : \(d = c+d\) donc \(c=0\), déjà obtenu.
Le commutant de \(\mathbf{A}\) est donc l'ensemble des combinaisons linéaires de \(\mathbf I\) et \(\mathbf A\) — un espace de dimension 2 dans un espace de dimension 4.
Corrigé — Exercice 8
a)
Coefficient \((1,1)\) : \(\cos\alpha\cos\beta - \sin\alpha\sin\beta = \cos(\alpha+\beta)\).
Coefficient \((1,2)\) : \(-\cos\alpha\sin\beta - \sin\alpha\cos\beta = -\sin(\alpha+\beta)\).
Coefficient \((2,1)\) : \(\sin\alpha\cos\beta+\cos\alpha\sin\beta = \sin(\alpha+\beta)\).
Coefficient \((2,2)\) : \(-\sin\alpha\sin\beta+\cos\alpha\cos\beta = \cos(\alpha+\beta)\).
b) Par récurrence immédiate, \(\mathbf{R}_\theta^n = \mathbf{R}_{n\theta}\).
c) On a redémontré les formules d'addition :
et, via b), la formule de Moivre : \(\cos(n\theta)\) et \(\sin(n\theta)\) s'obtiennent en développant \(\mathbf{R}_\theta^n\).
Un résultat, trois écritures
Ces mêmes formules réapparaîtront sous forme complexe au chapitre Analyse 11 : \(e^{i\alpha}e^{i\beta} = e^{i(\alpha+\beta)}\). Matrices de rotation et nombres complexes de module 1 sont deux représentations du même groupe.
Corrigé — Exercice 9
a) \((\mathbf A+\mathbf A^\top)^\top = \mathbf A^\top + \mathbf A = \mathbf A+\mathbf A^\top\) ✓ symétrique.
b) \((\mathbf A-\mathbf A^\top)^\top = \mathbf A^\top-\mathbf A = -(\mathbf A - \mathbf A^\top)\) ✓ antisymétrique.
c) Existence.
Unicité. Supposons \(\mathbf A = \mathbf S_1+\mathbf K_1 = \mathbf S_2+\mathbf K_2\). Alors \(\mathbf S_1-\mathbf S_2 = \mathbf K_2-\mathbf K_1\). Le membre de gauche est symétrique, celui de droite antisymétrique. Notons \(\mathbf M\) cette matrice commune : \(\mathbf M^\top = \mathbf M\) et \(\mathbf M^\top = -\mathbf M\), donc \(\mathbf M = -\mathbf M\), donc \(\mathbf M = \mathbf 0\). D'où \(\mathbf S_1 = \mathbf S_2\) et \(\mathbf K_1=\mathbf K_2\). \(\blacksquare\)
d) \(\mathbf A^\top = \begin{pmatrix}1&2\\4&3\end{pmatrix}\).
Vérification : \(\mathbf S+\mathbf K = \begin{pmatrix}1&4\\2&3\end{pmatrix}\) ✓
Une décomposition qu'on a déjà vue
C'est exactement la décomposition d'une fonction en partie paire et partie impaire (Prérequis 04, exercice 8), avec la transposition dans le rôle de \(x\mapsto -x\). Le schéma « \(\frac{u+\sigma(u)}{2} + \frac{u-\sigma(u)}{2}\) » fonctionne pour toute involution \(\sigma\).
Corrigé — Exercice 10
a)
b) On reconnaît \(1,1,2,3,5\) : les nombres de Fibonacci.
c) Initialisation \(n=1\) : \(\begin{pmatrix}F_2&F_1\\F_1&F_0\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix} = \mathbf F\) ✓
Hérédité. Supposons la formule au rang \(n\).
par la relation de Fibonacci ✓ \(\blacksquare\)
d) Écrivons \(\mathbf F^{m+n} = \mathbf F^m\mathbf F^n\) et identifions le coefficient \((1,2)\) :
(produit de la ligne 1 de \(\mathbf F^m\), soit \((F_{m+1}, F_m)\), par la colonne 2 de \(\mathbf F^n\), soit \((F_n, F_{n-1})\)). \(\blacksquare\)
Applications
Cette identité, combinée à l'exponentiation rapide (Algèbre 01, exercice 8), permet de calculer \(F_n\) en \(O(\log n)\) multiplications au lieu de \(O(n)\) additions. C'est l'algorithme utilisé en pratique pour les très grands indices.
Le déterminant donne par ailleurs l'identité de Cassini : \(\det(\mathbf F^n) = (\det\mathbf F)^n = (-1)^n\), soit \(F_{n+1}F_{n-1}-F_n^2 = (-1)^n\).
Corrigé — Exercice 11
a) Il y a \(n^2\) coefficients à calculer, chacun demandant une somme de \(n\) produits : \(n^2\times n = n^3\) multiplications ✓ (et \(n^2(n-1)\) additions).
b) On découpe chaque matrice \(n\times n\) en quatre blocs \(\frac n2\times\frac n2\). Le produit par blocs s'écrit comme un produit de matrices \(2\times2\) dont les « coefficients » sont des blocs.
Strassen effectue ce produit \(2\times2\) avec 7 produits de blocs au lieu de 8. Chaque produit de blocs est lui-même un produit de matrices \(\frac n2\times\frac n2\), traité récursivement. D'où
En itérant \(\log_2 n\) fois :
c) \(\log_2 7 = \dfrac{\ln 7}{\ln 2} \approx \dfrac{1{,}9459}{0{,}6931} \approx 2{,}807\).
Le rapport avec l'algorithme naïf est \(\dfrac{n^3}{n^{2{,}807}} = n^{0{,}193}\).
Pour que ce rapport atteigne 2 :
Il faut donc des matrices d'environ 36×36 pour diviser par deux le nombre de multiplications — en théorie.
d) Trois raisons, toutes pratiques :
- Les additions explosent. Strassen remplace 1 multiplication par 18 additions de blocs. Sur de petites matrices, où multiplication et addition coûtent le même prix, c'est perdant.
- La localité mémoire est détruite. Le produit naïf par blocs exploite très bien les caches ; le découpage récursif de Strassen produit des accès dispersés, et sur les processeurs modernes le coût dominant est le trafic mémoire, pas l'arithmétique.
- La stabilité numérique est moins bonne. Les soustractions intermédiaires de Strassen amplifient les erreurs d'arrondi en virgule flottante.
En pratique, les bibliothèques BLAS basculent sur Strassen — quand elles le font — à partir de tailles de l'ordre de 1000, et pas en dessous.
La leçon de modélisation
Un algorithme asymptotiquement meilleur n'est pas nécessairement meilleur. C'est exactement la critique demandée par le module MOMA11 : « analyser et critiquer la qualité (pertinence et performance) des résultats obtenus ». Voir Modélisation 05.
Chapitre suivant : Systèmes linéaires et pivot de Gauss.