Les formules de Cramer

Quand un système linéaire de $n$ équations à $n$ inconnues est de rang $n$, il a une solution unique. Il existe une formule explicite qui relie la solution $(x_1,\ldots,x_n)$ aux coefficients. Elle est connue, au moins pour les faibles valeurs de $n$, depuis très longtemps, même si elle est attribuée traditionnellement au mathématicien genevois Gabriel Cramer (1704-1752). Commençons par le cas $n=2$.

$$\left\{ \begin{array}{lcl} a_{1,1}x_1+a_{1,2} x_2&=&b_1\\ a_{2,1}x_1+a_{2,2} x_2&=&b_2 \end{array}\right.$$

Ce système a une solution unique si et seulement si son déterminant est non nul.

$$\Delta = \left\vert \begin{array}{cc} a_{1,1}& a_{1,2}\\ a_... ...nd{array}\right\vert = a_{1,1}a_{2,2}-a_{2,1}a_{1,2} \neq 0\;.$$

Si c'est le cas, les coordonnées de la solution s'écrivent comme des rapports de déterminants.

$$x_1 = \frac{b_1a_{2,2}-b_2a_{1,2}}{\Delta}=\frac{\left\vert ... ..._{1,1}& b_1\\ a_{2,1}& b_2 \end{array}\right\vert}{\Delta}\;.$$

Une formule analogue permet de calculer la solution d'un système $3\times 3$.

$$\left\{ \begin{array}{lcl} a_{1,1}x_1+a_{1,2} x_2+a_{1,3}x_3... ...\\ a_{3,1}x_1+a_{3,2} x_2+a_{3,3}x_3&=&b_3 \end{array}\right.$$

Ce système a une solution unique si et seulement si son déterminant est non nul.

$$\Delta = \left\vert \begin{array}{ccc} a_{1,1}& a_{1,2}& a_{... ...\\ a_{3,1}& a_{3,2}& a_{3,3} \end{array}\right\vert \neq 0\;.$$

Si c'est le cas les coordonnées de la solution s'écrivent encore comme des rapports de déterminants.

$$x_1 = \frac{\left\vert \begin{array}{ccc} b_1& a_{1,2}&a_{1,... ..._2\\ a_{3,1}& a_{3,2}& b_3 \end{array}\right\vert}{\Delta}\;.$$

La notion de déterminant s'étend à des tableaux carrés de nombres $n\times n$ pour $n$ quelconque. On peut en donner la définition récursive suivante.

Définition 2   Soit $(a_{i,j}) ,\;i,j=1,\ldots,n$ un tableau carré de $n\times n$ réels.

1. Si $n=1$, on appelle déterminant d'un tableau contenant un seul réel ce réel lui-même.
2. si $n>1$, pour $i=1,\ldots,n$ notons $\Delta_i$ le déterminant du tableau carré $(n\!-\!1)\times (n\!-\!1)$ obtenu en supprimant la première colonne et la $i$-ième ligne du tableau initial. On appelle déterminant du tableau $n\times n$ la quantité
   $$\Delta = \sum_{i=1}^n (-1)^{i+1} a_{i,1} \Delta_{i}\;.$$

Vous pouvez vérifier que l'application de cette définition à un déterminant $2\times 2$ ou $3\times 3$ donne bien le calcul que vous savez effectuer. Les formules de Cramer expriment les coordonnées de la solution d'un système de $n$ équations à $n$ inconnues comme des rapports de déterminants.

$$(S)\qquad \left\{\begin{array}{ccccccc} a_{1,1} x_1+&\cdots&+a_{... ...n,1} x_1+&\cdots&+a_{n,j} x_j+&\cdots&+a_{n,n} x_n&=&b_n \end{array}\right.$$

Le déterminant de ce système est celui du tableau des coefficients du premier membre.

$$\Delta = \left\vert\begin{array}{ccccc} a_{1,1}&\cdots&a_{1,j}&\... ...ots&&\vdots\\ a_{n,1}&\cdots&a_{n,j}&\cdots&a_{n,n} \end{array}\right\vert\;.$$

Théorème 4   Le système $(S)$ a une solution unique si et seulement si son déterminant $\Delta$ est non nul. Pour $j=1,\ldots,n$, notons $\Delta_j$ le déterminant obtenu en remplaçant la $j$-ième colonne de $\Delta$ par le second membre. Si $\Delta\neq 0$, l'unique solution du système $(S)$ est telle que :

$$\forall j=1,\ldots,n\;,\quad x_j = \frac{\Delta_j}{\Delta}\;.$$

Pour séduisantes qu'elles soient, les formules de Cramer sont parfaitement inefficaces. Le problème vient du calcul du déterminant. Si on applique la définition récursive 2, elle implique $n$ calculs de déterminants de taille $(n\!-\!1)\times (n\!-\!1)$, suivis de $n$ multiplications et $(n\!-\!1)$ additions. Pour chacun des déterminants de taille $(n\!-\!1)\times (n\!-\!1)$, il faudra recommencer avec $n\!-\!1$ déterminants de taille $(n\!-\!2)\times (n\!-\!2)$. Au total, si on programme avec un algorithme récursif la définition 2, le calcul d'un déterminant $n\times n$ prendra de l'ordre de $n(n!)$ opérations. Il se trouve que le bon moyen algorithmique de calculer un déterminant est ...  la méthode du pivot de Gauss. On montre en effet qu'un déterminant n'est pas modifié si on ajoute à une ligne une combinaison linéaire des autres. Il est changé en son opposé si deux lignes ou deux colonnes sont permutées. Si on applique la méthode du pivot de Gauss au système $(S)$, on arrive à un système échelonné $(S_E)$. Le déterminant de $(S_E)$ est celui d'un tableau de nombres triangulaire : ses coefficients au-dessous de la diagonale sont nuls. Le déterminant de $(S_E)$, qui est égal ou opposé à celui de $(S)$, est tout simplement le produit des pivots. Le nombre d'opérations pour calculer un déterminant $n\times n$ par la méthode du pivot de Gauss est de l'ordre de $\frac{2}{3}n^3$, soit très inférieur à ce que requiert la définition 2.

Donc pour utiliser les formules de Cramer, il faudrait appliquer la méthode du pivot de Gauss à $(n+1)$ systèmes, avant d'effectuer les quotients des déterminants obtenus : mieux vaut ne l'appliquer qu'à un seul !