Méthode du pivot de Gauss-Python

Bonsoir,

En cours nous avons abordé la méthode du pivot de Gauss pour trouver les solutions d’un système, où A représente la matrice associée aux coefficients des solutions pour chaque équations et $B$une matrice colonne, la matrice second membre.

Voici ce que j’ai commencé à faire en Python:

[spoiler]from math import *

def ChoisirPivot(A,k):
a=
compteur=0
for i in range (len(A)):
if A[k][i]!=0:
a.append(compteur)
compteur+=1
if a==: return(-1)
else: return(a[0])

def EchangeLigne(A,k,p):
C=[[0 for k in range(len(A))] for j in range (len(A))]
C[k]=A[p]
A[p]=A[k]
A[k]=A[p]

def Resous (A,B):
n=len(A)
for k in range (n):
p=ChoisirPivot(A,k)
if p==-1:
return(« matrice non inversible »)
EchangeLigne (A,k,p)
B[k]=(1/A[k][k])*B[k]
C=[0 for j in range (len(A))]
for s in range (n):
C.append((1/A[k][k])*A[k][s])
A[k]=C

    D=[0 for j in range (len(A))]
    for i in range (n):
        if i!=n:
            B[i]=B[i]-A[i][k]*B[k]
            
            for w in range (n):
                D.append(A[i][w]-A[i][k]*A[k][w])
            A[i]=D
return(B)

A=[[1,3,1],[1,2,1],[3,1,1]]
B=[1,0,-1]

B2=Resous(A,B)
for x in B2: print(x)[/spoiler]Je précise que dans la fonction « ChoisirPivot », j’ai indenté mon deuxième « if a==… » au même niveau que le « for i in range … » et non pas dans la boucle « for… ».

J’ai essayé de le faire tourner, il me renvoie « matrice non inversible ». Je pense que j’ai déjà un problème au niveau de la première fonction " ChoisirPivot", j’ai tenté de bidouiller quelque chose afin d’obtenir en sortie le numéro de la ligne du premier coefficient non nul de la colonne, qui sert ensuite à échanger la ligne « de départ » numérotée « k » dans ce programme, avec la ligne de ce premier coefficient non nul de la même colonne numérotée « p ».
Ensuite, les petites boucles for dans la fonction « Resous » servent uniquement à multiplier les lignes par un coefficients, Python me renvoyait un message d’erreur lorsque je multipliais directement la ligne par un ‹ float › du coup j’ai dû à nouveau contourner le problème.

Si quelqu’un trouve un moyen de résoudre ce qui ne va pas dans mon programme, ce serait fort sympathique !

Merci d’avance.

Je fais une exception car normalement je ne regarde jamais si on me le demande.

Tu fais en gros toutes les erreurs de débutant et c’est normal:

  1. quand on écrit UNE fonction, on la teste avec d’écrire la suite. Tu n’as pas testé tes fonctions une par une.

  2. def EchangeLigne(A,k,p):
    C=[[0 for k in range(len(A))] for j in range (len(A))]
    C[k]=A[p]
    A[p]=A[k]
    A[k]=A[p]
    Ok pour échanger tu as besoin d’une variable MAIS sûrement pas d’une matrice complète. C’est une faute de style…la suite de la fonction est une boulette marrante… A[p]=A[k]
    A[k]=A[p]
    Si tu avais testé tu aurais vu.

  3. 2*[2] renvoie quoi en python? pourquoi faire tout ça avec des listes de listes?? et pas avec des numpy array ou, si vraiment on aime les listes avec une liste et un accès à la liste de type A[i+N*j]???

Merci pour ta réponse ! :slight_smile:

J’ai vérifié et corrigé la première fonction « ChoisirPivot » et la procédure « EchangeLigne » les deux marchent correctement.

J’ai utilisé les listes compréhensives parçe que c’est la seule façon jusqu’à présent qu’on nous a apprise pour créer des « tableaux 2D », autrement dit pour représenter des matrices.
Avec Numpy array, on nous a montré comment créer un tableau (matrice ligne). Je ne sais pas comment créer un « tableau 2D » à partir de Numpy array, mis à part créer un tableau rempli de zéros, il me semble qu’il fait faire « np.zeros(nombre de lignes,nombre de colonnes) ».

Et j’ai essayé ton troisième point, « 2*[2] », ça renvoie « [2,2] » je ne le savais pas ! Je pensais que ça multipliais les cases du tableau, mais ça le duplique apparemment (si on peut dire ça comme ça).
Du coup je vois pas trop comment m’en tirer parce que ça me renvoie une erreur en multipliant la ligne directement, ou ça augmente le tableau si on le fait case par case.

Ben on peut stocker une matrice dans un tableau 1D de longueur N².
Quand on veut stocker/lire l’élément (i,j), il suffit d’aller le stocker/lire à la place i+N*j.

Que fait 4*[2,3,4] ?

D’après d’autres test, « 4*[2,3,4] » devrait renvoyer [2,3,4,2,3,4,2,3,4,2,3,4].

J’ai effectué quelques modifications à mon programme:

[spoiler]from math import *

def ChoisirPivot(A,k):
a=
compteur=0
for i in range (len(A)):
if A[k][i]!=0:
a.append(compteur)
compteur+=1
if a==: return(-1)
else: return(a[0])

def EchangeLigne(A,k,p):
C=[[0 for k in range(len(A))] for j in range (len(A))]
C[k]=A[p]
A[p]=A[k]
A[k]=C[k]

def Resous (A,B):
n=len(A)
for k in range (n):
p=ChoisirPivot(A,k)
if p==-1:
return(« matrice non inversible »)
EchangeLigne (A,k,p)
B[k]=(1/A[k][k])*B[k]
C=[0 for j in range (len(A))]
for s in range (n):
C[s]=((1/A[k][k])*A[k][s])
A[k]=C
D=[0 for j in range (len(A))]
for i in range (n):
if i!=n:
B[i]=B[i]-A[i][k]*B[k]
for w in range (n):
D[w]=A[i][w]-A[i][k]*A[k][w]
A[i]=D
return(B)

A=[[1,3,1],[1,2,1],[3,1,1]]
B=[1,0,-1]

B2=Resous(A,B)
for x in B2: print(x)[/spoiler]

Le problème est qu’il ne renvoie pas le bon résultat :grin: .

Ça doit sans doute provenir des soucis avec les listes dans la fonction « Resous » bien que j’ai changé les boucles « for » qui sont sensées être correcte maintenant. Ou alors ca peut provenir du fait que je me suis bêtement perdu dans les indices.

def ChoisirPivot(A,k):
a=
compteur=0
for i in range (len(A)):
if A[k][i]!=0:
a.append(compteur)
compteur+=1
if a==: return(-1)
else: return(a[0])

Je n’ai rien compris. Tu pars d’une liste vide, tu append des machins dedans et, de toutes façons, tu renvoies soit -1 soit seulement a[0]…

C’était simplement afin d’obtenir l’indice de la première ligne où le coefficient est non nul que j’ai fait tout ça. C’est le premier truc qui me soit venu à l’esprit, pour renvoyer le compteur une seule fois et le « premier ».

on ne devrait pas vous laisser coder avant d’avoir vérifier que vous avez compris/appris les principes de bases.
Créer toute une liste pour ensuite n’en utiliser que le premier élément est une monstruosité.tu vois pourquoi?
Ce que tu voulais c’est soit une boucle for avec un « break » soit un while(pivot==0).
Au passage, == est un très mauvaise idée si on travaille avec des floats…tu vois pourquoi?

fakbill a écrit:

Au passage, == est un très mauvaise idée si on travaille avec des floats…tu vois pourquoi?
Non.

On a eu TD aujourd’hui qui portait sur cette méthode et la méthode de Padé, on a effectivement utilisé des array. Et notamment, on a pu régler assez facilement tous les problèmes concernant les multiplications de listes.

Ce serait sûrement beaucoup plus long, mais je suppose que l’on pourrait aussi résoudre ce type de problème grâce aux matrices qui nous ont servie à définir les opérations élémentaires dans le cours de Maths (ce serait difficile de les illustrer immédiatement). Effectuer une opération que ce doit soit un ajout de ligne, un échange de ligne, ou une multiplication de ligne, revient à multiplier (à gauche si ce sont des opérations sur les lignes) la matrice (sur laquelle on veut effectuer les changements) par ces matrices qui ont servie à définir les opérations élémentaires.
À ce moment là on travaillerait avec des multiplications de matrices et non plus sur les lignes directement (qui utilisent en faite les propriétés mathématiques).
Mais est ce que cela apporterait quelque chose de plus ?

google.com/url?sa=t&rct=j&q= … 2401,d.bGQ pour la version longue.

docs.python.org/3.4/tutorial/floatingpoint.html pour une explication plus « frappante ».

En résumé, avec des floats, il y a des problème très complexe d’arrondis. Si tu divises par 0 ca va lever une exception mais si tu divises par qqch de très très petit tu aura souvent un grave problème de précision. De plus, rien ne garanti par exemple que a*b/b == a avec des floats. il suffit que a soit petit et b très grand pour que ca pose problème. L’égalité avec des flaot se teste donc avec if(abs(a-b)<epsilon) et choisir le bon epsilon est un art (souvent il doit dépendre des données du probléme). Ca peut sembler être des cas ultra particulier mais NON. si tu testes l’égalité entre flaots avec ==, sous peu, tu vas tomber sur un « bug » que tu vas mettre des plombes à corriger. Plein de programmes souffrent de ce problème.
Bien sûr, si tu fait a=0.0 et que tu ne touche plus « a » alors il est parfaitement ok de faire "if(a==0.0) MAIS ne crois pas arccos(cos(x))==x meme si x est dans la bonne plage de valeurs.

Je ne suis pas certain de comprendre exactement ta question.

Ok, on nous a parlé de ces problèmes avec les floats, et je m’en suis aussi rendu compte avec les np.linspace par exemple, mais je n’y pense pas dans la plupart des cas, la preuve ça ne m’a pas du tout dérangé quand j’avais programmé ceci.

Sinon ce que je me demandais, ne doit sûrement pas être un problème en Informatique. Enfin il n’a pas lieu d’être, je pense. C’est plutôt lorsqu’on fait des opérations sur des matrices à la main, qu’il est utile de savoir que l’on multiplie la matrice par des matrices « élémentaires », pour comprendre que cela ne vient pas de nulle part, ces opérations sur les lignes ou sur les colonnes.
Python ne se soucis pas de cela :grin: .

PS: merci pour les liens.

Le problème est que « python » va faire toutes les multiplications même si ta matrice ne contient que des zéros ou presque…ça va donc coûter cher pour intervertir 2 lignes…
Si tu veux creuser le sujet le mot clef est « sparse matrix ».