Résolution numérique d'équations
L'objet du TP est de trouver une solution, si elle existe à l'équation $f(x)=0$.
En plus de trouver la solution, on s'intéresse aussi à la qualité de l'algorithme c'est à dire à sa rapidité.
Méthode par balayage
La méthode par balayage consiste à partir du point $a$, à progresser par pas $p$ jusqu'à ce que la fonction change de signe ou que une valeur limite $b$ soit dépassée
Écrire l'algorithme correspondant à cette méthode, on pourra envisager une valeur limite $b$ pour éviter une boucle infinie.
Écrire le programme.
Remarque : en moyenne, il faudra parcourir la moitié de l'intervalle, le nombre d'itérations est donc $\displaystyle \lfloor\frac{b-a}{2p}\rfloor$. Si on veut une solution comprise entre 0 et 1 à 0,001 près par balayage, il faut compter 500 pas.
On peut améliorer la méthode en commençant par un pas de 1, puis quand on a dépassé la solution, on recule et on recommence en divisant le pas par 10 jusqu'à arriver à la précision souhaitée. Dans ce cas, pour chaque valeur de p (0.1, 0.01, 0.001) il faut compter à chaque fois, en moyenne, 5 pas, au total 15 pas !
Modifier le programme précédent en conséquence.
Méthode par dichotomie
Dans la méthode par dichotomie, on considère que si $f(a).f(b)<0$ alors $a$ et $b$ encadrent la solution $x$ et qu'en général $c=\dfrac{a+b}{2}$ est en général une meilleure approximation de $x$.
On pourra réitérer le procédé si l'on connaît le signe de $f(c)$.
On construit ainsi deux suites $(a_n)$ et $(b_n)$ par récurrence de la façon
$a_0=a,\ b_0=b$ et pour tout $n \in N$,
- $c_{n}=\dfrac{a_n+b_n}{2}$
- Si $f(a_n)f(c_n)>=0,\ a_{n+1}=c_n\ ;\ b_{n+1}=b_n$
- Si $f(a_n)f(c_n)<0,\ a_{n+1}=a_n\ ;\ b_{n+1}=c_n$
Les deux suites sont adjacentes et forment un encadrement de la solution $x$.
Programmer la méthode par dichotomie
Remarque : On peut soit programmer une boucle FOR ou une boucle WHILE avec la condition d'arrêt $|b_n-a_n|\leq p$.
Combien d'itérations sont nécessaire pour obtenir le même résultat p à 0.001 près ?
Méthode de Newton
La méthode de Newton est basée sur des idées simples :
- On trouve une solution approchée de $f(x)=0$ en remplaçant la courbe par sa tangente.
- Si $x_0$ est une valeur approchée de la solution $x$, on construit une meilleure approximation $x_1$ en utilisant la tangente $T$ au point $M(x_0,f(x_0))$.
- En réitérant ce procédé, on définit une suite $(x_n)$ qui tend vers la solution $x$. On s'arrête dès que l'on peut affirmer que $|x_n-x|<p$.
Considérons la tangente en $x_0$ à $C_f$, son équation est $y = f(x_0)+(x-x_0)f'(x_0)$ .
L'intersection avec l'axe $0x$ donne $x_1=$ tel que $0 = f(x_0) + (x_1 -x_0)f'(x_0)\Rightarrow x_1 = x_0 - \frac{f(x_0)}{ f'(x_0)}$
On construit alors la suite définie par la récurrence suivante en répétant ce procédé. $ x_{n+1} = x_n- \frac{f(x_n)}{f'(x_n)}$
et on montre que cette dernière converge vers la racine de f.
Indication pour écrire le programme :
- on calcule une valeur approchée de la dérivée en $x_0$ sans connaître l'expression de $f$ à l'aide de l'approximation
$$f'(x_0)=\lim_{h\to0}\dfrac{f(x_0+h)-f(x_0-h)}{2h}.$$
- La plupart du temps, on n'a pas la valeur de $x$, donc la condition d'arrêt sera $|x_{n+1}-x_n|<p$ ou à $p/10$ par précaution mais rien ne vous permet d'affirmer, sans calcul supplémentaire que $x_n$ est bien une solution à $p$ près.
Remarque : Si dans la méthode par dichotomie, la précision est de l'ordre de $\dfrac{b-a}{2^n}$ alors on montre que sous certaines conditions la précision par la méthode de Newton est de l'ordre de $\dfrac{b-a}{2^{2^n}}$ .
Programmer la méthode de Newton
- Identifiez-vous pour poster des commentaires