Écrire un programme permettant de calculer les zéros d’une fonction continue. Ladite fonction sera implémentée en dur dans votre programme (voir plus bas). Pour ce faire, il faut utiliser la méthode de la bissection. L’utilisateur devra entrer en paramètres au programme les deux bornes entre lesquelles votre programme devra trouver le zéro.
Afin de déterminer le zéro d’une fonction, une des méthodes les plus simples est la méthode de la bissection. Il s’agit de choisir deux points, \(a_1\) et \(b_1\), \(b_1>a_1\), tels que le signe de \(g(a_1)\) et \(g(b_1)\) est différent. Si cela est le cas, nous sommes assurés de l’existence d’au moins un zéro si la fonction \(g(x)\) est continue (en vertu du théorème de la valeur intermédiaire). Ensuite, nous allons calculer la valeur se situant au milieu entre \(a_1\) et \(b_1\) \[ c_1=\frac{b_1+a_1}{2}. \qquad{(3.1)}\] Puis, nous évaluons \(g(c_1)\) et si ce n’est pas un zéro, nous étudions son signe. Si le signe \(g(c_1)\) est différent de celui de \(g(a_1)\), nous remplaçons \(b_1\) par \(c_1\) et recommençons. Si le signe de \(g(c_1)\) est différent de celui de \(g(b_1)\), nous remplaçons \(a_1\) par \(c_1\). Nous itérons cette méthode jusqu’à ce que nous ayons atteint une valeur “suffisamment proche” du zéro. Une façon d’exprimer “proche” est de considérer la taille de l’intervalle \(b_1-a_1\) et de le comparer avec une précision \(\varepsilon>0\) que nous aurons choisie en fonction de la précision voulue. Ainsi, lorsque que \[ |b_1-a_1|<\varepsilon, \qquad{(3.2)}\] nous pouvons arrêter l’algorithme
Dans le pire des cas, cette méthode nous rapproche de \((b_1+a_1)/2\) du zéro à chaque itération. Après \(n\) itérations, nous sommes donc à une distance maximale du zéro, \(d_\mathrm{max}\), de
\[ d_\mathrm{max}=(b_1+a_1)/2^n. \qquad{(3.3)}\]
Considérons la fonction suivante: \[ g(x)=x^5+2\cdot x^4+x^3+x^2-1. \qquad{(4.1)}\]
Votre programme devra au minimum:
Implémenter la fonction g(x) (quelle est sa
signature?).
Prendre en argument (à l’aide de scanf()) les bornes
de l’intervalle dans lequel on veut calculer le zéro (a1 et b1
avec a1 < b1) ainsi
que la tolérance epsilon>0.
Vérifier que les arguments sont cohérents (a1 < b1, epsilon > 0
et sign(g(a1)) != sign(g(b1)))
et afficher un message d’erreur avant de quitter le programme si cela
n’est pas le cas.
Implémenter la fonction bissect() ayant la signature
suivante:
int32_t bissect(double a1, double b1, double epsilon,
double *zero);qui assigne à zero la valeur du
zéro déterminé à l’aide de la méthode de la bissection et retourne le
nombre d’itérations nécessaires pour le trouver. Si le zéro n’a pas pu
être trouvé (si par exemple epsilon est si petit qu’il faut
un trop grand nombre d’itérations), la fonction retourne -1
et zero contient la valeur du dernier
“zéro” calculé.
En fonction des \(a_1\), \(b_1\) que vous avez choisis, vous devriez trouver un des trois zéros suivants: \[\begin{align} x&=-1,\\ x&=-\frac{1}{2}\pm \frac{\sqrt{5}}{2}\cong -1.618..., 0.618... \end{align}\]
L’éq. 3.3 nous donne la distance maximale entre le zéro et notre approximation après \(n\) itérations de l’algorithme. Il est dès lors assez aisé de déterminer le nombre maximal nécessaire pour que l’algorithme converge pour une précision \(\varepsilon\) donnée:
\[\begin{align} \varepsilon&=(b_1+a_1)/2^n,\nonumber\\ 2^n&=(b_1+a_1)/\varepsilon,\nonumber\\ n&=\log_2((b_1+a_1)/\varepsilon), \end{align}\] où \(a_1\) et \(b_1\) sont les bornes de l’intervalle de départ.
Ainsi avec \(a_1=0.5\), \(b_1=1\) et \(\varepsilon=10^{-5}\), on a \[ n=\log_2(1.5\cdot 10^5)=17.2. \qquad{(4.2)}\] On a donc que \(n\leq 16\) pour converger vers le zéro.
Mettez vous par groupes de cinq et écrivez (à l’aide d’un papier et d’un crayon) le pseudo-code de toutes les fonctions que vous devez réaliser. Une fois que vous avez fini, montrez votre pseudo-code à un enseignant (vous aurez le choix par ordre alphabétique entre Messieurs Albuquerque, Boquete, El Kharroubi, Heirich, Leblanc ou Malaspinas).
Quand vous aurez fini cette première partie, réfléchissez à un moyen pour calculer tous les zéros à l’aide d’un papier et d’un crayon (n’hésitez pas à réfléchir en groupe à ce problème). Une fois votre méthode mise au point, montrez-la à un enseignant et implémentez-la.
Il existe d’autres méthodes pour déterminer les zéros de fonctions. L’une d’entre-elles est la méthode de Newton–Raphson (voir https://en.wikipedia.org/wiki/Newton%27s_method). Implémentez cette méthode et comparez les performances des deux façons de faire.