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

+