Algo récursif du pivot de gauss

Algo récursif du pivot de gauss - Algo - Programmation

Marsh Posté le 15-04-2005 à 22:40:41    

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
Reply

Marsh Posté le 15-04-2005 à 22:40:41   

Reply

Marsh Posté le 15-04-2005 à 22:47:43    

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/
Reply

Marsh Posté le 15-04-2005 à 22:49:53    

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
Reply

Marsh Posté le 16-04-2005 à 04:47:49    

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 !
Reply

Marsh Posté le 19-04-2005 à 18:21:36    

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


---------------
- mon feed-back
Reply

Marsh Posté le 19-04-2005 à 19:17:58    

tu viens de l'avoir [:spamafote]


---------------
uptime is for lousy system administrators what Viagra is for impotent people - mes unixeries - github me
Reply

Marsh Posté le 19-04-2005 à 19:39:19    

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
Reply

Marsh Posté le 27-04-2005 à 08:19:44    

: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:

Reply

Marsh Posté le 28-04-2005 à 10:44:00    

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
Reply

Marsh Posté le 28-04-2005 à 17:53:20    

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:

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed