TP Python – Inverse par la méthode de Gauss en Python

BTS SIO SISR 1re année – Mathématiques pour l'informatique – S14

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Les calculs utilisent des fractions exactes (Fraction) pour éviter les erreurs d'arrondi des décimaux : Fraction(1, 2) + Fraction(1, 3) vaut exactement Fraction(5, 6).

Exercice A – Matrice identité et produit

Écris identite(n) et produit(a, b) (ils servent à tout vérifier). Les coefficients peuvent être des Fraction.

###

assert identite(2) == [[1, 0], [0, 1]]bksl-nlassert identite(3)[1][1] == 1 and identite(3)[0][2] == 0bksl-nlassert produit([[2, 1], [5, 3]], [[3, -1], [-5, 2]]) == [[1, 0], [0, 1]]bksl-nlassert produit([[1, 2, 3]], [[1], [1], [1]]) == [[6]]bksl-nlassert produit([[Fraction(1, 2), 0], [0, 2]], [[2, 0], [0, Fraction(1, 2)]]) == [[1, 0], [0, 1]]bksl-nlbksl-nl ∞/∞

from fractions import Fractionbksl-nlbksl-nldef identite(n):bksl-nl m = []bksl-nl for i in range(n):bksl-nl ligne = []bksl-nl for j in range(n):bksl-nl # À compléter : 1 sur la diagonale, 0 ailleurs (en Fraction)bksl-nl ligne.append(Fraction(0))bksl-nl m.append(ligne)bksl-nl return mbksl-nlbksl-nldef produit(a, b):bksl-nl resultat = []bksl-nl for i in range(len(a)):bksl-nl ligne = []bksl-nl for j in range(len(b[0])):bksl-nl s = Fraction(0)bksl-nl for k in range(len(b)):bksl-nl # À compléter : ajouter a[i][k] py-str b[k][j]bksl-nl passbksl-nl ligne.append(s)bksl-nl resultat.append(ligne)bksl-nl return resultatbksl-nlbksl-nl

Exercice B – Vérifier un inverse

Écris est_inverse(a, b) qui renvoie True si \(AB = I\) et \(BA = I\).

J'anticipe. Pourquoi vérifier les deux produits ? (pour des matrices carrées l'un suffit, mais il est utile de comprendre pourquoi le test complet est plus sûr à écrire.)

###

assert estpy-undinverse([[2, 1], [5, 3]], [[3, -1], [-5, 2]]) is Truebksl-nlassert estpy-undinverse([[2, 1], [5, 3]], [[3, 1], [5, 2]]) is Falsebksl-nlassert estpy-undinverse([[1, 2, 3], [0, 1, 4], [5, 6, 0]], [[-24, 18, 5], [20, -15, -4], [-5, 4, 1]]) is Truebksl-nlassert estpy-undinverse([[2, 0], [0, 2]], [[Fraction(1, 2), 0], [0, Fraction(1, 2)]]) is Truebksl-nlassert estpy-undinverse([[1, 2], [2, 4]], [[1, 0], [0, 1]]) is Falsebksl-nlbksl-nl ∞/∞

from fractions import Fractionbksl-nlbksl-nldef identite(n):bksl-nl m = []bksl-nl for i in range(n):bksl-nl ligne = []bksl-nl for j in range(n):bksl-nl ligne.append(Fraction(1 if i == j else 0))bksl-nl m.append(ligne)bksl-nl return mbksl-nlbksl-nldef produit(a, b):bksl-nl resultat = []bksl-nl for i in range(len(a)):bksl-nl ligne = []bksl-nl for j in range(len(b[0])):bksl-nl s = Fraction(0)bksl-nl for k in range(len(b)):bksl-nl s = s + a[i][k] py-str b[k][j]bksl-nl ligne.append(s)bksl-nl resultat.append(ligne)bksl-nl return resultatbksl-nlbksl-nldef estpy-undinverse(a, b):bksl-nl n = len(a)bksl-nl return False # À compléter : AB et BA doivent être égaux à l'identitébksl-nlbksl-nl

Exercice C – Inverse par la méthode des lignes

Écris inverse(a) qui renvoie l'inverse de la matrice carrée a (liste de listes d'entiers) sous forme de matrice de Fraction, ou None si elle n'est pas inversible. Suis la méthode du cours : colonne par colonne, choisir un pivot non nul (échanger des lignes si besoin), le ramener à 1, annuler le reste de la colonne, en appliquant les mêmes opérations à la matrice identité.

Je comprends. À quel moment la fonction détecte-t-elle qu'une matrice n'est pas inversible ?

###

assert inverse([[2, 1], [5, 3]]) == [[3, -1], [-5, 2]]bksl-nlassert inverse([[1, 2, 3], [0, 1, 4], [5, 6, 0]]) == [[-24, 18, 5], [20, -15, -4], [-5, 4, 1]]bksl-nlassert inverse([[0, 1], [1, 0]]) == [[0, 1], [1, 0]]bksl-nlassert inverse([[1, 2], [2, 4]]) is Nonebksl-nlassert inverse([[1, 1, 1], [1, 2, 3], [2, 3, 4]]) is Nonebksl-nlassert inverse([[2, 0], [0, 4]]) == [[Fraction(1, 2), 0], [0, Fraction(1, 4)]]bksl-nlassert produit([[2, 1, 1], [1, 3, 2], [3, 2, 1]], inverse([[2, 1, 1], [1, 3, 2], [3, 2, 1]])) == identite(3)bksl-nlbksl-nl ∞/∞

from fractions import Fractionbksl-nlbksl-nldef identite(n):bksl-nl m = []bksl-nl for i in range(n):bksl-nl ligne = []bksl-nl for j in range(n):bksl-nl ligne.append(Fraction(1 if i == j else 0))bksl-nl m.append(ligne)bksl-nl return mbksl-nlbksl-nldef produit(a, b):bksl-nl resultat = []bksl-nl for i in range(len(a)):bksl-nl ligne = []bksl-nl for j in range(len(b[0])):bksl-nl s = Fraction(0)bksl-nl for k in range(len(b)):bksl-nl s = s + a[i][k] py-str b[k][j]bksl-nl ligne.append(s)bksl-nl resultat.append(ligne)bksl-nl return resultatbksl-nlbksl-nldef inverse(a):bksl-nl """Inverse de a par la méthode des lignes, ou None si a n'est pas inversible."""bksl-nl n = len(a)bksl-nl g = []bksl-nl for i in range(n):bksl-nl g.append([Fraction(x) for x in a[i]] + identite(n)[i]) # la matrice [A | I]bksl-nl for j in range(n):bksl-nl p = Nonebksl-nl for i in range(j, n):bksl-nl if g[i][j] != 0:bksl-nl p = ibksl-nl breakbksl-nl if p is None:bksl-nl return Nonebksl-nl # À compléter : échanger les lignes j et pbksl-nl # À compléter : diviser la ligne j par le pivot g[j][j]bksl-nl # À compléter : pour chaque autre ligne i, retrancher g[i][j] fois la ligne jbksl-nl return [ligne[n:] for ligne in g]bksl-nlbksl-nl

Exercice D – Résoudre un système

Écris resoudre(a, b) qui renvoie la liste des solutions (en Fraction) du système \(AX = B\) (b : liste des seconds membres), ou None si \(A\) n'est pas inversible. Utilise inverse.

###

assert resoudre([[2, 1], [5, 3]], [7, 18]) == [3, 1]bksl-nlassert resoudre([[1, 2], [3, 7]], [5, 16]) == [3, 1]bksl-nlassert resoudre([[2, 1, 1], [1, 3, 2], [3, 2, 1]], [31, 58, 39]) == [3, 5, 20]bksl-nlassert resoudre([[1, 2], [2, 4]], [3, 6]) is Nonebksl-nlassert resoudre([[1, 1, 1], [2, -1, 1], [1, 2, -1]], [6, 3, 2]) == [1, 2, 3]bksl-nlbksl-nl ∞/∞

from fractions import Fractionbksl-nlbksl-nldef identite(n):bksl-nl m = []bksl-nl for i in range(n):bksl-nl ligne = []bksl-nl for j in range(n):bksl-nl ligne.append(Fraction(1 if i == j else 0))bksl-nl m.append(ligne)bksl-nl return mbksl-nlbksl-nldef produit(a, b):bksl-nl resultat = []bksl-nl for i in range(len(a)):bksl-nl ligne = []bksl-nl for j in range(len(b[0])):bksl-nl s = Fraction(0)bksl-nl for k in range(len(b)):bksl-nl s = s + a[i][k] py-str b[k][j]bksl-nl ligne.append(s)bksl-nl resultat.append(ligne)bksl-nl return resultatbksl-nlbksl-nldef inverse(a):bksl-nl """Inverse de a par la méthode des lignes, ou None si a n'est pas inversible."""bksl-nl n = len(a)bksl-nl g = []bksl-nl for i in range(n):bksl-nl g.append([Fraction(x) for x in a[i]] + identite(n)[i])bksl-nl for j in range(n):bksl-nl p = Nonebksl-nl for i in range(j, n):bksl-nl if g[i][j] != 0:bksl-nl p = ibksl-nl breakbksl-nl if p is None:bksl-nl return Nonebksl-nl g[j], g[p] = g[p], g[j]bksl-nl pivot = g[j][j]bksl-nl g[j] = [x / pivot for x in g[j]]bksl-nl for i in range(n):bksl-nl if i != j and g[i][j] != 0:bksl-nl c = g[i][j]bksl-nl g[i] = [x - c py-str y for x, y in zip(g[i], g[j])]bksl-nl return [ligne[n:] for ligne in g]bksl-nlbksl-nldef resoudre(a, b):bksl-nl """Solution de AX = B (liste de Fraction), ou None."""bksl-nl ai = inverse(a)bksl-nl if ai is None:bksl-nl return Nonebksl-nl x = []bksl-nl for i in range(len(ai)):bksl-nl s = Fraction(0)bksl-nl for k in range(len(b)):bksl-nl # À compléter : ajouter ai[i][k] py-str b[k]bksl-nl passbksl-nl x.append(s)bksl-nl return xbksl-nlbksl-nl