Discussion :

[kawther]

bonjour;
pouvez vous m'aider à résoudre ce problème. je cherche un programme en C permettant de trouver le zéro de la foction f(x)=exp(-x)-x définie sur l'intervalle [0,1].

[stephl]

Une petite recherche par dichotomie.

[kawther]

peux tu donner plus de détails.

[souviron34]

dichotomie = encadrement et valeur approchée en divisant par 2 l'intervalle à chaque fois...


Cherche un peu sur le Web ou dans tes cours de maths...

[stephl]

peux tu donner plus de détails.

La fonction est décroissante. On considère l'intervalle de départ [0,1] et on calcule l'image y du point milieu de cet intervalle. Si l'image est supérieure à 0 alors on refait le même travail avec l'intervalle [y,1], sinon on recommence avec l'intervalle [0,y]. On s'arrête dès que la précision désirée est atteinte.

[salseropom]

salut, la méthode de newton est bcp plus rapide (vitesse de convergence). C'est une méthode quadratique. En 1D elle s'implémente ultra facilement et dans ton cas, la jacobienne se calcule à la main.

[amaury pouly]

Avant de se lancer avec la méthode de Newton, il y a peut-être intérêt à faire une petite dichotomie avant ?

[forthx]

l'avantage de la methode par dichotomie est qu'elle est simple le probleme c'est qu'elle est un peu lente (convergence lineaire).
La methode de newton demande un peu de math (evaluation de la derivée necessaire) mais sera plus rapide pour cette equation (racine simple)

il reste la methode de la secante (ou de la corde) qui dans ce cas converge encore plus vite, est relativement simple mathematiquement.

Mais attention (ce serait trop beau) cette methode peu devenir instable en convergence avancé (si on veu une tres grande precision)

d'autres info ici: http://www.developpez.net/forums/arc...hp/t-3096.html

[salseropom]

Avant de se lancer avec la méthode de Newton, il y a peut-être intérêt à faire une petite dichotomie avant ?

Pourquoi ? Autant faire directement du Newton.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
f(x)=exp(-x)-x

donc la dérivée est

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
fdot(x)=-(exp(-x)+1)

donc pour tout x dans l'intervalle [0, 1] f'(x)<0

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
double eps=1e-15;
double x1=1.,x2;
double err=1+eps;
 
while(err>eps)
{
  x2=x1;
  x1-=f(x2)/fdot(x2);
  err=fabs(x1-x2);
}
 
printf("la racine est\n",x1);

et voilà, c'est fait. Pourquoi passer tout d'abord par une dichotomie ?

[amaury pouly]

Ici, pas besoin de faire une dichotomie car la fonction est bien sympathique et on la considère dans un intervalle restreint mais dans le cas d'un fonction plus méchante, il vaut mieux procéder par une dichotomie avant, en particulier si la dérivée prend des valeurs très faibles dans certaines portions ce qui nuirait à la convergence de la méthode de Newton.

Je rajouterais au passage pour forthx que le fait qu'elle soit instable à grande précision n'est pas génant....puisqu'elle est déjà instable numériquement à cause des approximations(double n'a pas une précision infinie...). Après si on travaille avec 20 chiffres après la virgule, je sais pas.

[souviron34]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
double eps=1e-15;
double x1=1.,x2;
double err=1+eps;
 
while(err>eps)
{
  x2=x1;
  x1-=f(x2)/fdot(x2);
  err=fabs(x1-x2);
}
 
printf("la racine est\n",x1);

et voilà, c'est fait. Pourquoi passer tout d'abord par une dichotomie ?

Bah moi j'appelle ça approximations successives.. Et franchement, c'est le même principe non ?

[amaury pouly]

D'un point de vue purement mathématique, la dichotomie c'est le niveau 0 de l'approximation et la méthode de newton c'est le niveau 1
Plus sérieusement, la méthode de newton a une convergence bien meilleure que la dichotomie et elle ne se base pas sur le même principe que celle-ci.

[salseropom]

Bah moi j'appelle ça approximations successives.. Et franchement, c'est le même principe non ?

salut, on va s'éloigner du C (et se rapprocher de l'algorithmie). La méthode que j'ai proposée s'appelle la méthode de Newton, qui est certes, une méthode itérative. Il y a aussi la méthode de la sécante qui est une autre méthode itérative (en comparaison aux méthodes directes). Mais ceci n'est que du vocabulaire...

[Zavonen]

Vu que l'application exp(-x) est ici 'contractante'
|f(x)|<=k|x| avec k <1
vous pouvez appliquer la méthode des itérations successives pour déterminer le point fixe de exp(-x)
On part de 0.5 puis f(0.5) puis f(f(0.5), etc...
voici le code C (très rapide et pas besoin de dérivée)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
double f(double x)
{
    return exp(-x);
}
 
double iter (double x0, double f(double), int n)
{
    int i;
    double r=f(x0);
    for (i=1;i<=n;i++)
        r=f(r);
    return r;
}
 
int main()
{   double y=iter(0.5,f,10);
    printf("%lf\n",y);
    printf("%lf\n",y-f(y));
    return 0;
}

[amaury pouly]

C'est vrai que je n'avais pas penser à cette méthode.
C'est très efficace mais pas du tout général malheureusement...

[Zavonen]

C'est très efficace mais pas du tout général malheureusement...

Plus général qu'on ne le croit ...
Supposons f bijective.
x point fixe de f équivaut à x point fixe de f^-1 (réciproque)
f contractante équivaut à f^-1 dilatante :
def f dilatante ssi |f(x-y)] >= k|x-y| avec k>1
En général les applications ne sont (globalement) ni bijectives ni contractantes ni dilatantes, mais il suffit qu'elles le soient localement.
Donc, en général, avant d'appliquer un algo de résolution d'équation on cherche à localiser la solution (déterminer un intervalle, aussi petit que possible dans lequel elle doit se trouver). Ceci est vrai pour toutes les méthodes (dicho. Newton, parties proportionnelles, tangentes, sécantes, etc...).
En somme, pour qu'on ne puisse pas appliquer la méthode des itérations successives, il faut qu'on soit dans un cas où on ne peut trouver un intervalle contenant la solution, dans lequel la fonction ne soit pas localement inversible contractante ou localement inversible dilatante. Il faut déjà se creuser pour trouver des contre-exemples.
En dimension 1, quand on fait un dessin avec le graphe de f et la première diagonale, on voit tout de suite la convergence (phénomène de rebond dans un goulot).
Par ailleurs cette méthode est généralisable aux fonctions de plusieurs variables (Newton aussi d'ailleurs), alors que la dicho. et les parties proportionnelles ne le sont pas.