Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1496 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Algo récursif du pivot de gauss

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Algo récursif du pivot de gauss

n°1049249
Zipo
Ours bipolaire
Posté le 15-04-2005 à 22:40:41  profilanswer
 

Bonjour
 
Je cherche un algorithme récursif de la méthode de résolution des systèmes linéaires par pivot de Gauss, est ce que qqn aurait ça sous la main ??
 
J'ai trouvé la version itérative sur le net (il yen a plein) mais impossible de trouver la version récursive, alors que je sais qu'elle existe !
 
Merci beaucoup


Message édité par Zipo le 15-04-2005 à 22:47:42

---------------
- mon feed-back
mood
Publicité
Posté le 15-04-2005 à 22:40:41  profilanswer
 

n°1049252
Emmanuel D​elahaye
C is a sharp tool
Posté le 15-04-2005 à 22:47:43  profilanswer
 

Zipo a écrit :

Je cherche un algorithme récursif de la méthode de résolution des systèmes linéaires par pivot de Gauss, est ce que qqn aurait ça sous la main ??


La récursion, c'est esthétique, intello et tout, mais c'est très casse-gueule... Un pétage de mémoire automatique (aka 'pile' sur la plupart des implémentations) est toujours à craindre si la récursion s'enfonce un peu trop...


Message édité par Emmanuel Delahaye le 15-04-2005 à 22:48:43

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
n°1049253
Zipo
Ours bipolaire
Posté le 15-04-2005 à 22:49:53  profilanswer
 

Emmanuel Delahaye a écrit :

La récursion, c'est esthétique, intello et tout, mais c'est très casse-gueule... Un pétage de mémoire automatique (aka 'pile' sur la plupart des implémentations) est toujours à craindre si la récursion s'enfonce un peu trop...


oui je sais mais c'est justement pour comparer la version récusive avec l'itérative ;)


---------------
- mon feed-back
n°1049442
Chronoklaz​m
Posté le 16-04-2005 à 04:47:49  profilanswer
 

Emmanuel Delahaye a écrit :

La récursion, c'est esthétique, intello et tout, mais c'est très casse-gueule... Un pétage de mémoire automatique (aka 'pile' sur la plupart des implémentations) est toujours à craindre si la récursion s'enfonce un peu trop...


 
C'est sur si on prend un language imperatif qui ne trouve rien de mieux que de passer en iteratif ...
 
Je pensais au fait qu'une structure de boucle generale (while par exemple) était équivalente à un simple appel recursif de la fonction sur elle meme en incrementant un certain i ...  :whistle: et en faisant un return quand ce fameux i atteignai une certaine valeur.


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°1052650
Zipo
Ours bipolaire
Posté le 19-04-2005 à 18:21:36  profilanswer
 

personne n'a de réponse ? :(
 
:bounce:


---------------
- mon feed-back
n°1052730
black_lord
Truth speaks from peacefulness
Posté le 19-04-2005 à 19:17:58  profilanswer
 

tu viens de l'avoir [:spamafote]


---------------
uptime is for lousy system administrators what Viagra is for impotent people - mes unixeries - github me
n°1052771
Zipo
Ours bipolaire
Posté le 19-04-2005 à 19:39:19  profilanswer
 

Ah vous voulez que je récursive manuellement la version itérative ? ouai pas con mais ça risque d'être super chaud non?
 
j'ai trouvé une version C++ itérative que j'ai traduite en C comme ça :
 

Code :
  1. #include <stdio.h>
  4. int main(){
  6. int a, af, i, ligne, n, p, sol, t, x, y=0;
  7. double e[11][10], s[10];
  8. double temp, var1=0,var2=0;
  10. printf("programme de résolution utilisant le pivot de gauss\nEntrez le nombre d'équations à traiter\nN= " );
  11. scanf("%d", &n);
  12. printf("\n" );
  13. for (i=0; i<n; i++){
  15.         printf("equation %d\n", i+1);
  16.         for (p=0; p<n; p++){
  17.                 printf("var %d = ", p+1);
  18.                 scanf("%lf", &e[p][i]);
  19.         }
  21. printf("\nequation %d = ", i+1);
  22. scanf("%lf", &e[n][i]);
  23. printf("\n" );
  24. }       
  25. // on a donc saisi les facteurs des equations dans la matrice e
  27. for(x=0; x<n-1; x++){               
  28.         for(a=1+x; a<n; a++){
  29.        
  30.                 temp=e[x][a];
  31.        
  32.                 for (t=x; t<n+1; t++){
  33.                
  34.                         // On triangularise le système
  35.                         e[t][a] = e[t][a] * e[x][x] - e[t][x] * temp;
  36.        
  37.                 }
  39.         }
  40. }
  42. // On remplace
  43. s[n-1] = e[n][n-1] / e[n-1][n-1];
  44. e[n][n-1]=0;
  45. e[n-1][n-1]=0;
  47. for (ligne=1; ligne<=n; ligne++){
  48.         for (sol=2; sol<=n; sol++){
  49.                 e[n-ligne][n-sol] *= s[n-ligne];
  50.                 e[n][n-sol] -= e[n-ligne][n-sol];
  51.                 e[n-ligne][n-sol]=0;
  53.         }
  54.         s[n-(ligne+1)] = e[n][n-(ligne+1)] / e[n-(ligne+1)][n-(ligne+1)];
  55. }
  58. // Affichage
  59. printf("*** RESOLUTION ***\n\nLes solutions du système sont:\n" );
  60. for (af=0; af<n; af++)
  61.         printf("\n\tvar %d = %lf", af+1, s[af]);
  63. printf("\n" );
  64. getchar();
  65. return 0;
  66. }


 
la récursivation me semble assez chaude à faire non? [:gm_superstar]


Message édité par Zipo le 19-04-2005 à 19:39:47

---------------
- mon feed-back
n°1062193
Apocalypse​13
Posté le 27-04-2005 à 08:19:44  profilanswer
 

:hello:  Salut!
 
Beurk ton code !  :ouch:  
Précautions, ça te dit quelques chose?  :D  
Quelques manques de précaution évidents :
- si un pivot est nul, adieu la résolution ( tu peux remplacer les pivots nuls par des epsilons très petits, ta solution devient approximative )
- les divisions par zéro!!!!! (l.54)
- tu peux aussi faire un test pour savoir si le système admet une solution, cela t'évitera des surprises désagréables (calcul du rang de la matrice associée au système, calcul du déterminant, des trucs comme ça)
 
Pour la récursion, cela ne me semble pas très difficile puisque la méthode du pivot est une méthode récursive :
Avec N = nombre d'équations de départ et n = nombre d'équations restant après une étape de la méthode du pivot  
 
ResolRecur(n,N)
   - Si n=1 alors fin (trouver les solutions)
   - Sinon appliquer la méthode du pivot sur la sous matrice de taille n*(n+1) et ResolRecur(n-1,N)
 
Ainsi à chaque étape ton système est réduit d'une équation et d'une variable jusqu'à n=1. Voili, N est en paramètre uniquement pour savoir la taille de la matrice.
Bonne chance!  :hello:

n°1063975
Zipo
Ours bipolaire
Posté le 28-04-2005 à 10:44:00  profilanswer
 

Je viens de traduire en récursif, j'obtiens ça :
ça vous parait correct ?
 

Code :
  1. #include <stdio.h>
  3. double e[11][10], s[10];
  4. int ERROR;
  9. void Triang2(double temp, int x, int n, int a, int t)
  10. {
  11. if(t<n+1){
  12. e[t][a] = e[t][a] * e[x][x] - e[t][x] * temp;
  13. Triang2(temp, x, n, a, t+1);
  14. }
  15. }
  20. void Triangularisation(int x, int n, int a)
  21. {
  22. double temp; int t;
  24. if(x<n-1){
  26. if(a<n){
  27.  temp=e[x][a];
  29.  Triang2(temp, x, n, a, x);
  30.  Triangularisation(x, n, a+1);
  31. }
  32. else
  33.  Triangularisation(x+1, n, 0);
  34. }
  35. }
  38. void RemplaceLigne(int n, int ligne, int sol)
  39. {
  40. if(ligne<=n){
  42. if(sol<=n){
  44.  e[n-ligne][n-sol] *= s[n-ligne];
  45.  e[n][n-sol] -= e[n-ligne][n-sol];
  46.  e[n-ligne][n-sol]=0;
  47.  RemplaceLigne(n, ligne, sol+1);
  49. }
  50. else{
  51.  if( e[n-(ligne+1)][n-(ligne+1)] != 0){
  52.   s[n-(ligne+1)] = e[n][n-(ligne+1)] / e[n-(ligne+1)][n-(ligne+1)];
  53.   RemplaceLigne(n, ligne+1, 0);
  54.  }
  55.  else{
  56.   printf("DIVISION PAR ZERO!!!\n\n" );
  57.   ERROR=1;
  58.  }
  59. }
  60. }
  61. }
  64. void Remplace(int n)
  65. {
  67. s[n-1] = e[n][n-1] / e[n-1][n-1];
  68. e[n][n-1]=0;
  69. e[n-1][n-1]=0;
  71. RemplaceLigne(n, 1, 2);
  73. }
  76. void Affichage(int af, int n)
  77. {
  78. if(af<n){
  79. printf("\n\tvar %d = %lf", af+1, s[af]);
  80. Affichage(af+1, n);
  81. }
  82. else{
  83. printf("\n" );
  84. getchar();
  85. }
  86. }
  90. int main(){
  92. int i, n, p;
  93. ERROR=0;
  94. printf("programme de résolution utilisant le pivot de gauss\nEntrez le nombre d'équations à traiter\nN= " );
  95. scanf("%d", &n);
  96. printf("\n" );
  97. for (i=0; i<n; i++){
  99. printf("equation %d\n", i+1);
  100. for (p=0; p<n; p++){
  101.  printf("var %d = ", p+1);
  102.  scanf("%lf", &e[p][i]);
  103. }
  105. printf("\nequation %d = ", i+1);
  106. scanf("%lf", &e[n][i]);
  107. printf("\n" );
  108. }
  109. // on a donc saisi les facteurs des equations dans la matrice e
  111. // RESOLUTION ET AFFICHAGE DES SOLUTIONS
  113. Triangularisation(0, n, 1);
  114. Remplace(n);
  116. if(!ERROR){
  117. printf("*** RESOLUTION ***\n\nLes solutions du système sont:\n" );
  118. Affichage(0, n);
  119. }
  120. }


 
j'ai mis un test pour les divisions par 0 apocalypse, par contre pourrai-tu m'expliquer + en détail l'histoire du epsilon ? mon prof nous en a parlé mais j'ai pas tout compris :/


Message édité par Zipo le 28-04-2005 à 10:56:48

---------------
- mon feed-back
n°1064636
Apocalypse​13
Posté le 28-04-2005 à 17:53:20  profilanswer
 

Salut zipo!  :hello:  
Alors deux choses :  
 
- pour ton programme :
 
il est pas super clair et optimisé  :o  surtout pour la résolution après triangularisation :
* le tableau s est inutile, tu peux stocker tes réponses dans la n+1 ième colonne.
* en général dans un tableau à deux dimensions : la première représente les lignes et la deuxième les colonnes...
* est-ce que ça serait pas plus simple de faire ceci : une fois une solution trouvée, disons la première, ligne n-1, colonne n dans ton pg. Tu soustrais pour toutes les lignes i telles que i<(n-1) (simple boucle) au terme de la colonne n (derrière le =) c*s[n-1] où c est le coeffiscient de la ligne i qui correspond à la variable dont tu viens de trouver la solution. Et après tu peux remplacer ce coef par zéro (même si c'est pas utile puisque tu ne les regardera plus :) ). Comme ça quand tu passes à la ligne suivante (du dessus) tu n'as plus rien à faire qu'une division. (si tu comprends pas je te ferai un exemple).
 
- pour l'histoire des coeffiscients nuls et des epsilons :
En général lorsqu'on résout un système de manière systématique, on suit cet ordre :
* vérification que le système a une solution et une seule (déterminant non nul je crois)
* on applique le pivot de gauss
Mais le problème est que même si le système a une solution, selon dans quel ordre les équations sont rentrées il se peut qu'un pivot soit nul et donc la résolution foire alors qu'il y a une solution. Il y a alors deux possibilités :
* changer l'ordre des équations ou des variables en priant d'en trouver un dans lequel le pb ne se représente pas, c'est certainement la meilleure solution. Elle est expliquée à cette adresse :  http://gershwin.ens.fr/vdaniel/Doc [...] ode90.html  
un lien sympa et très clair avec exemple : http://www.dil.univ-mrs.fr/~garret [...] /Pb_01.pdf  
 
* méthode des epsilons qui abouti à une solution approximative. Je ne sais pas ton niveau en maths et j'ai peur de t'embrouiller et de devoir faire cinq pages de commentaires. Si tu vraiment intéressé je repotasserai mes cours de DEUG et j'essayerai de te synthétiser ça.
 
Bonne chance!  :hello:


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Algo récursif du pivot de gauss

 

Sujets relatifs
pivot gauss en PASCALfaire un algo pour enlever les yeux rouges
Parcours récursif Treeview ( Neuds + branches ) ... ??Traduction algo en Visual Basic ???
Exemple d'algo de jeu asm ?Algo pour faire des stats sur un questionnaires [k c dure !]
[MySQL] DELETE récursifAlgo -> C++
[algo] inverser les mots d'une chaine de charactere 
Plus de sujets relatifs à : Algo récursif du pivot de gauss

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.072 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR