Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 28-02-2009 22:21:12

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

algorithme de factorisation de Gauss

Bonjour,

Pour reprendre rapidement le principe, la méthode de Gauss consiste à factoriser une matrice carré quelconque de déterminant non nul en 2 matrices triangulaires:
A=L.U
/A, matrice carré
L, matrice triangulaire inférieure
U, matrice triangulaire supérieure

tout est très bien expliqué ici: http://jmblanc.developpez.com/algorithm … page_2#LII

je ne reprendrais pas tout l'aspect théorique, mais voici mon progamme:

A=[[a11,...,a1n],...[an1,...,ann]]
#on suppose que A est connue

for k=1 to n-1

     #code pour la matrice L
     for i=k+1 to n
          A[i][k]=A[i][k]/A[k][k]

     #code pour la matrice U
     for i=k+1 to n
          for j=k+1 to n
               A[i][j]=A[i][j]-A[i][k]xA[k][j]

#affichage
for i=1 to n
     print A[i]
#le triangle superieur, diagonale comprise est la matrice U
#le triangle inférieur est la matrice L

et normalement en multipliant L.U , je devrais retrouver A
mais ça ne fonctionne pas.

quelqu'un verait-t-il une erreur?
merci

Dernière modification par tibo (28-02-2009 22:26:14)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#2 01-03-2009 09:59:07

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : algorithme de factorisation de Gauss

SAlut,

Quel langage utilises-tu (tu ne l'as pas pas précisé en Objet) ?
Un basic ? Parce que ce n'est pas du C, du Python, du Java, du Pascal...
Visual Basic ?
Bon, décris-moi le procédé "à la main", s'il te plaît, et donne-nous un exemple chiffré que tu as utilisé (matrice 3 x 3, ou 4 x 4 : si ça marche, alors on généralisera)...

@+

PS je vais aller voir ton lien...


Arx Tarpeia Capitoli proxima...

En ligne

#3 01-03-2009 11:16:42

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : algorithme de factorisation de Gauss

Bonjour, excusez moi en fait c'est bon, je m'étais trompé dans les indices dans mon programme.

sinon c'est du Python
merci d'avoir pris la peine de me lire yoshi


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#4 01-03-2009 13:30:14

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : algorithme de factorisation de Gauss

Salut,

for.. to... du Python... ????
Bizarre, parce que ton for i = to n:  mon Python le refuse, tout comme for i == 1 to 5...
Quelle version de Python utilises-tu ? On travaille généralement avec 2.5 ou 2.6, pour la 3.0, il vaut mieux attendre (problèmes de compatibilité avec les versions précédentes) ,
En Python 2.5 ou 2.6, les boucles for s'écrivent
1. en partant de l'indice 0
2. avec range
3. On termine l'instruction par : (deux points)
Pour parcourir les indices de 1 à 4, il faut donc écrire :
for i in range(1,5):
    print i,

D'autre part, il faudrait trouver un moyen pour faire des calculs fractionnaires, là, Python, tel que j'ai récrit ton prog pour qu'il tourne chez moi, il calcule les quotients décimaux approchés...
Pas propre !

@+


Arx Tarpeia Capitoli proxima...

En ligne

#5 01-03-2009 14:35:18

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : algorithme de factorisation de Gauss

J'utilise la version 2.6
Je ne savais pas comment écrire les boucles for et j'en avais mare des while
donc un pote m'a créé une nouvelle bibliotèque de fonction, c'est pour ça que cette écriture marche. Et ne me demande pas comment il a fait, j'en sais rien, je ne suis qu'un débutant programeur, surtout en Python. Je n'ai rien compris mais touours est-il que ça fonctionne.
Par contre j'ai oublié les ":"


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#6 01-03-2009 16:33:47

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : algorithme de factorisation de Gauss

Salut,

OK ! Demande à ton pote s'il peut réinventer pêle-mêle la roue, l'eau tiède, la fil à couper le beurre...

Ma syntaxe Python :

A=[[5.0,3.0,8.0,11.0],[1.0,-2.0,9.0,8.0],[7.0,2.0,5.0,2.0],[3.0,2.0,5.0,6.0]]
B = [[5.0,3.0,8.0,11.0],[1.0,-2.0,9.0,8.0],[7.0,2.0,5.0,2.0],[3.0,2.0,5.0,6.0]]
n = 4
for p in range(n-1): # Nombre de passes
    for l in range(p+1,n):  # traitement des lignes
        coeff=B[l][p]/B[p][p]          
        for c in range(p,n):  # traitement de chaque colonne pour la nouvelle A
            B[l][c]=B[l][c]-coeff*B[p][c]
            if abs(B[l][c])<10**(-15):
                   B[l][c]=0  
# Affichage
# Affichage
print "         Matrice d'origine"
for i in range(n):
    for j in range(n):
        a=A[i][j]
        print "%5.1f" % a,
    print
print
print "         Matrice triangularisée"
for i in range(n):
    for j in range(n):
         print "%5.1f" % A[i][j],
    print

Dans un souci de présentation, je formate l'affichage à 1 chiffre après la virgule : avec 2 chiffres avant possible + 1 signe -, ça me laisse 2 espaces entre chaque colonne :

>>>
         Matrice d'origine
  5.0   3.0   8.0  11.0
  1.0  -2.0   9.0   8.0
  7.0   2.0   5.0   2.0
  3.0   2.0   5.0   6.0

         Matrice diagonalisée
  5.0   3.0   8.0  11.0
  0.0  -2.6   7.4   5.8
  0.0   0.0 -12.5 -18.3
  0.0   0.0   0.0  -1.3

Si je mets B = A, je me retrouve devant le même problème que tu as signalé dans ton autre post...
Si je n'ajoute pas des .0 derrière les nombres, les divisions effectuées sont des divisions euclidiennes.
La valeur absolue c'est pour être sûr d'avoir 0, sinon j'ai quelque chose du genre k * 10^(-17) à cause de la gestion standard des décimaux par Python...

@+

PS : Je vais maintenant penser aux calculs fractionnaires, mais ça ne va pas être de la "petite bière"...
PS2 : J'ai trouvé comment me passer de tous les .0 :
Remettre :
A = [[5,3,8,11],[1,-2,9,8],[7,2,5,2],[3,2,5,6]]
B = [[5,3,8,11],[1,-2,9,8],[7,2,5,2],[3,2,5,6]]

Puis modifier :
coeff=B[l][p]/B[p][p]
en
coeff=B[l][p]/float(B[p][p])

Dernière modification par yoshi (01-03-2009 18:19:48)


Arx Tarpeia Capitoli proxima...

En ligne

#7 01-03-2009 18:28:01

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : algorithme de factorisation de Gauss

Re,

Je crois bien que je suis à côté de la plaque :
j'ai triangularisé par la méthode du pivot de Gauss, mais ce n'est pas ça que tu cherchais me semble-t-il ?
Alors je n'ai pas trouvé...
Je choisis quoi sur ta page ?

II-A. Systèmes avec matrice triangulaire
II-B. Systèmes avec matrice orthogonale
II-B-1. Vecteurs orthogonaux en algèbre linéaire
II-B-2. Matrices orthogonales
II-C. Méthode d'élimination de Gauss
II-D. Systèmes mal conditionnés
II-E. Echange de pivots
II-F. Factorisation LU (méthode de Crout)
II-G. Factorisation LU avec échange de pivots
II-H. Raffinement itératif de la solution
II-I. Inversion d'une matrice
II-J. Calcul d'un déterminant
II-K. Matrices symétriques et matrices hermitiennes
II-L. Méthode de Cholesky
II-M. Factorisation QR (méthode de Householder)
II-N. Factorisation SVD (valeurs singulières)

II-F ? II-G ? Autre chose ?

@+


Arx Tarpeia Capitoli proxima...

En ligne

#8 01-03-2009 21:12:47

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : algorithme de factorisation de Gauss

Re,

Merci de t'impliquer autant.
Moi je m'intéressais à la factorisation LU (II-F)
Mais je ne l'ai codé juste pour vérifier que mon algorithme était bon, je ne cherchais pas un programme super performant.


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#9 20-05-2010 01:16:57

Kiru
Invité

Re : algorithme de factorisation de Gauss

Slt yoshi,


Je sollicite ton aide!
Ayant compris le principe de la factorisation LU (méthode de CROUT), j'ai donc écris un algo en langage C pour l'appliquer à des matrices. Et je constate que pour certaines matrices régulières (déterminant # 0), je n'arrive pas à faire la décomposition avec mon algo car division par zéro quand le pivot est nul.
exple de matrice: A=(-2,2,-3;-1,1,3;2,0,-1) ou B=(1,2,3;2,4,7;3,7,3).
je cherche donc un algo en langage C de la factorisation LU avec échange de pivots (pivot complet si possible sinon partiel) (II-G sur la page de developpez.com).


Merci d'avance!

Ci-dessous mon code en langage C

#include<stdio.h>
#include<conio.h>
#define q 50

/* Décomposition LU de la matrice A*/
void decomposerMatA(float a[q][q],int n)
{int i,j,k;
float s1,s2,s3,s4,u[q][q],l[q][q],detA,x;
printf("\n");
printf("\n");
for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    {printf("Entrer a[%d][%d]= ",i,j);
     scanf("%f",&x);
     a[i][j]=x;
    }

u[0][0]=a[0][0];

for(j=1;j<n;j++)
   {
    u[0][j]=a[0][j];
    l[j][0]=a[j][0]/a[0][0];
   }
   
     s1=0;
for(i=1;i<n-1;i++)
    { for(k=0;k<i;k++)
      s1=s1-(l[i][k]*u[k][i]);
      u[i][i]=a[i][i]+s1;
        s2=0;
        s3=0;
        for(j=i+1;j<n+1;j++)   
           for(k=0;k<i;k++)
               {s2=s2-(l[i][k]*u[k][j]);
               u[i][j]=a[i][j]+s2;
               s3=s3-(l[j][k]*u[k][i]);
               l[j][i]=(a[j][i]+s3)/u[i][i];
               }   
    }
s4=0;
for(k=0;k<n-1;k++)
s4=s4-(l[n-1][k]*u[k][n-1]);
u[n-1][n-1]=a[n-1][n-1]+s4;

         
printf("\n");
printf("La Matrice Superieure U est : \n");
printf("\n");
for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    {printf("%5.2f\t",u[i][j]);
     if (j==n-1) printf("\n");
    }

printf("\n");
printf("La Matrice Inferieure L est : \n");
printf("\n");
for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    {if (i==j) l[i][j]=1;
     printf("%5.2f\t",l[i][j]);
     if (j==n-1) printf("\n");
    }

}     

/* Programme Principal*/
main()
{float val[q][q];
int z;
printf("Entrer l'ordre de la Matrice: ");
     scanf("%d",&z);
decomposerMatA(val,z);
getch();
}

#10 20-05-2010 10:20:30

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : algorithme de factorisation de Gauss

Bonjour,


Je préfère te prévenir que j'ai seulement une grosse poignée d'heures en C derrière moi dont une moitié passée à débugger des programmes élémentaires..
Donc, je suis retourné voir sur Développez.com (tu aurais eu plus de chances de réponse efficace sur leur site qu'ici, soit dit en passant).
Après le travail fait pour Valentin, et qui fonctionne, je voulais me pencher justement sur ce problème des pivots nuls...
Donc, j'ai trouvé ça :

Développez.com a écrit :

*   Nous avons vu que le mécanisme d'élimination faisait intervenir une division par chaque terme diagonal, appelée aussi pivot. Cette opération n'est évidemment possible que si le pivot n'est pas nul. Si l'on tombe sur un pivot nul, il est possible de contourner la difficulté en permutant l'équation où il se trouve avec une des suivantes. Si, à la fin de l'élimination de Gauss, il reste un pivot nul lorsque plus aucune permutation n'est possible, cela signifie que la matrice est singulière.
    * On constate d'autre part que, pour la détermination de chaque nouveau coefficient, on calcule la différence de l'ancienne valeur de ce coefficient et d'un terme qui est le produit de deux coefficients divisé par le pivot. Ce terme est entaché d'une erreur d'arrondi résultant de la multiplication et de la division. Pour que l'erreur relative sur la différence soit minimale, il faut que ce terme soit le plus petit possible en comparaison de l'ancienne valeur. Cela signifie que l'ordre optimal des équations et des inconnues est celui qui conduit à diviser par des pivots de plus grande valeur absolue.

Je ferais donc comme ça, je déclarerais une matrice uniligne
float temp[4](4 est un exemple]
En cours de calcul avant de lancer le traitement de la ligne j, où se trouve le pivot potentiel (colonne c je teste si le pivot est nul...
if (pivot ==0)
{
   for  (x=0, c<..,c++)
         {
           stockage de ligne j dans temp;
           stockage de ligne j+1 dans la ligne j;
           stockage de temp dans la ligne j+1;
         }
}
retour début de boucle sans incrément
else {
   calcul classique
C'est le système d'échange entre a et b en passant par c :
c=a, a=b, b=c;

Ça te va comme idée ? Ai-je compris ce que tu voulais ?

@+


Arx Tarpeia Capitoli proxima...

En ligne

#11 22-12-2013 20:34:18

khaoula solita
Invité

Re : algorithme de factorisation de Gauss

bnsoir jai besoin davoire la mèthode de gauss en language pascal très urgent

#12 26-12-2013 14:34:42

MathRack
Membre
Inscription : 02-04-2012
Messages : 78

Re : algorithme de factorisation de Gauss

Bonjour,

1 - Il existe des librairies open-source qui font ça très bien, par exemple lapack

2 - Vous pouvez appeler des fonctions fortran en pascal cf ici

Si c'est urgent, mieux vaut utiliser des librairies externes et robustes.

Cordialement,
MathRack

Hors ligne

#13 12-01-2015 16:24:19

ablaabla
Invité

Re : algorithme de factorisation de Gauss

SVP qui peut me programmer cet algorithme en java? c la résolution d'un système d'équation linéaire par la méthode de gauss-jordan avec la matrice triangulaire:
Algorithme Gauss-par
Début
        Procédure forward élimination
   Pour (k allant de 1 à n/2) faire
         // Trouver q tel que
          |Aq,k| = max de (|Ak,k|,|Ak+1,k|,……|Am,k|)
        // Échanger la ligne k et la ligne q.Tkk
       Pour (q allant de (k+1) à n) faire
                        Aq,k= Aq,k/ Ak,k.
              Pour  (j allant de (k+1) à n) faire
     Pour (i allant de (k+1) à n) faire
Ai,j = Ai,j - Ai,k * Ak,jTkj
    Fin pour ;
           Fin pour ; 
        Fin pour ;
  Fin pour ;
        Fin ;
      // Fin de la procédure forward élimination
       Procédure backward élimination
    Pour (k allant de n à n/2+1) faire
                       // Trouver q tel que
                       |Aq,k| = max de (|Ak,k|,|Ak-1,k|,……|A1,k|)
   



// Echanger la ligne k et la ligne q
      Pour (q allant de k-1 à 1)  faire
                      Aq,k= Aq,k / Ak,k ;
        Pour (j allant de k-1 à 1) faire
     Pour (i allant de k-1 à 1)  faire
Ai,j = Ai,j - Ai,k * Ak,j
      Fin pour ;
Fin pour ;
                 Fin pour ;
           Fin pour ; 
     Fin ;
   // Fin de la procédure backward-élimination.
Fin.

#14 08-04-2016 14:58:51

moustapha
Invité

Re : algorithme de factorisation de Gauss

bonsoir
je suis étudiant en master 2 en économie ;je veux écrire un programme en langage python réalisant le produit matriciel et aussi le système d'équation linéaire de Gauss et de Cramer .mais je voudrais solliciter votre aider pour faire de l'optimisation avec python

#15 14-04-2016 19:53:37

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : algorithme de factorisation de Gauss

Bonsoir,

Inutile de réinventer la roue... Regarde plutôt du côté de numpy, le module mathématique associé à Python qu'il faut télécharger et installer...
https://sourceforge.net/projects/numpy/ … e/download
http://www.courspython.com/tableaux-numpy.html
http://www-irma.u-strasbg.fr/~navaro/imfs/numpy.pdf

@+


Arx Tarpeia Capitoli proxima...

En ligne

#16 31-12-2017 18:49:08

Dembele
Invité

Re : algorithme de factorisation de Gauss

Bonjour je suis etudiant en master structure, j'ai besoin de la methode d'elimination de gauss sur matlab.
Merci d'avance pour votre aide.

#17 31-12-2017 19:36:46

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : algorithme de factorisation de Gauss

Bonsoir,

Méthode d'élimination de Gauss ? Connais pas...
Je connais la méthode du pivot de Gauss, mais pas avec matlab.
https://fr.wikipedia.org/wiki/%C3%89lim … uss-Jordan
Avec cette recherche, je vois que c'est bien ça. Ce lien en pseudo code t'aidera à le programmer sous MatLab. Mais je crois avoir lu que Matlab possède déjà des fonctions intégrées pour ça...

Si c'est urgent, je te conseillerais d'aller faire un tour ici : https://www.developpez.net/forums/f148/ … nt/matlab/
C'est un forum spécialisé dans MatLab et en fouillant un peu, tu trouveras sûrement que le sujet y a déjà été traité...
Pour faire une recherche, tu dois t'inscrire...
Sinon, j'ai trouvé ceci  :
https://www.developpez.net/forums/d1177 … optimisee/
https://www.google.fr/url?sa=t&rct=j&q= … IU2YLELO6U


Bonne chance

@+


Arx Tarpeia Capitoli proxima...

En ligne

Pied de page des forums