Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermé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:
#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 948
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...
Hors 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 948
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...
Hors 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 948
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 :
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 " Matrice triangularisée"
for i in range(n):
for j in range(n):
print "%5.1f" % A[i][j],
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...
Hors ligne
#7 01-03-2009 18:28:01
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 948
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...
Hors 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 948
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 :
* 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...
Hors 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
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 948
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...
Hors 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 948
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...
Hors ligne
Pages : 1
Discussion fermée