WikiMath

Introduction

Rappel (wikipedia)...

En mathématiques, initialement introduit en algèbre pour déterminer le nombre de solutions d'un système d'équations linéaires, le déterminant se révèle un outil très puissant dans de nombreux domaines (étude d'endomorphisme, recherche de valeurs propres, calcul différentiel).

C'est ainsi qu'on définit le déterminant d'un système d'équations, le déterminant d'un endomorphisme ou le déterminant d'un système de vecteurs.

Le déterminant avec numpy

Les calculs d'inverses, de déterminants, etc. sont accessibles avec le paquetage numpy.linalg :

  >>> from numpy.linalg import *
  >>> A = matrix((1,2,3,4,5,6,7,8,1)).reshape((3,3))
  >>> print det(A)
  24.0

Calcul par pivot de Gauss

Méthode numérique pour obtenir un déterminant

On a déjà vu quelle était la fonction numpy qui permettait le calcul du déterminant.

En pratique, on peut procéder à un algorithme du type pivot, pour obtenir une forme triangulaire de la matrice $A$ qui nous intéresse. Le déterminant de $A$ est alors égal au produit des éléments diagonaux. Cette méthode est à peu près la seule à n'être pas prohibitif en temps de calcul.

Travaux pratiques

1. Réutiliser le code pour le pivot de Gauss, afin d'obtenir le déterminant d'une matrice donnée.
2. Comparer vos résultats avec le retour de la fonction det de numpy.

Jordan-Bareiss

Présentation

Si la matrice n'est constituée que d'entiers, le pivot introduit artificiellement des fractions, ce qui rallonge les calculs et peut être source d'erreurs. Cela est d'autant plus paradoxal qu'il existe une formule, inutile en pratique, affirmant que le déterminant s'exprime comme sommes et produits des coefficients de la matrice : tout devrait se passer chez les entiers.

Il existe cependant une variante à la méthode du pivot pour le calcul du déterminant, utile dans le cas des matrices à coefficients entiers : la méthode de Jordan-Bareiss. Dans ce cas, on ne travaille qu'avec des entiers :

• on est ainsi à l'abri des erreurs d'arrondis,
• l'algorithme devrait être plus rapide.

Jordan-Bareiss en Python

La bibliothèque sympy a implanté l'algorithme de Bareis :

  >>> from sympy import *
  >>> A = Matrix((-5,2,4,-4,
                  10,-3,-6,8,
                  11,-4,-6,8,22,
                  -8,-14,17)).reshape(4,4)
  >>> A
  [-5,  2,   4, -4]
  [10, -3,  -6,  8]
  [11, -4,  -6,  8]
  [22, -8, -14, 17]
  >>> A.det_bareis()
  -2
  >>> help(A.det_bareis)

L'algorithme de Jordan-Bareiss

Soit $M$ une matrice carrée de taille $n$, à coefficients entiers, dont on souhaite calculer le déterminant.

On suppose que les mineurs principaux $x_{k,k}^k$ de $M$ sont tous non nuls (le mineur principal d'ordre k de A est le déterminant obtenu à partir des k premières lignes et des k premières colonnes de A).

  $M_{0,0} \leftarrow 1$
  pour k de 0 à n-1 faire
      pour i de k+1 à n faire
          pour j de k+1 à n faire
              $M_{i,j} = \frac{M_{i,j}M_{k,k}-M_{i,k}M_{k,j}}{M_{k-1,k-1}}$

La division ci-dessus est exacte : $M_{i,j}$ sera entier. Le déterminant est égal à $M_{n-1,n-1}$.

Remarquons, pour bien comprendre l'algorithme, et bien pouvoir le mettre en oeuvre, que les coefficients de $M$ vont de $(1,1)$ à $(n,n)$. Donc...

• Le $M_{0,0}$ est donc en-dehors de la matrice, et ne sert qu'à éviter un problème pour la dernière ligne de l'algorithme,
• On prendra garde à ce que, en python :
  • le range(x,y) va de x à y-1,
  • les coefficients des matrices ne vont pas de 1 à $n$, mais de 0 à $n-1$ : l'algorithme est donc à adapter légèrement.

Travaux pratiques

1. Mettre en place un algorithme de calcul de déterminant pour une matrice quelconque.
2. Implantez l'algorithme de Jordan-Bareiss.
3. Vérifiez vos résultats en utilisant la fonction det de numpy.