É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 au clavier les deux bornes entre lesquelles votre programme devra trouver le zéro, ainsi que la précision souhaitée.
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 \(g(a_1)\) et \(g(b_1)\) soient de signes différents. Si cela est le cas, nous sommes assurés de l’existence d’au moins un zéro entre \(a_1\) et \(b_1\) si la fonction \(g(x)\) est continue sur \([a_1,b_1]\) (en vertu du théorème de la valeur intermédiaire). Ensuite, à chaque itération \(k\) (en commençant par \(k=1\)), nous calculons la valeur se situant au milieu entre \(a_k\) et \(b_k\) \[ c_k=\frac{b_k+a_k}{2}. \qquad{(3.1)}\] Puis, nous évaluons \(g(c_k)\) et si ce n’est pas un zéro, nous étudions son signe. Si \(g(c_k)\) et \(g(a_k)\) sont de signes différents, nous posons \(a_{k+1}=a_k\) et \(b_{k+1}=c_k\). Sinon, nous posons \(a_{k+1}=c_k\) et \(b_{k+1}=b_k\). Puis nous recommençons. 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_k-a_k\) et de la comparer avec une précision \(\varepsilon>0\) que nous aurons choisie en fonction de la précision voulue. Ainsi, lorsque \[ |b_k-a_k|<\varepsilon, \qquad{(3.2)}\] nous pouvons arrêter l’algorithme.
À chaque itération, la taille de l’intervalle contenant le zéro est divisée par deux. 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?).
Lire (à 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 g(a1) * g(b1) < 0)
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é en au plus MAX_ITER
itérations (une constante que vous définirez), la fonction retourne
-1
et *zero
contient la valeur du dernier “zéro” calculé. Ce garde-fou est
indispensable : si epsilon est plus
petit que la précision d’un double au
voisinage du zéro, l’intervalle ne peut plus rétrécir et la boucle ne
s’arrêterait jamais. (N’oubliez pas d’inclure <stdint.h>
pour utiliser le type int32_t.)
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 d’itérations nécessaires pour que l’algorithme converge pour une précision \(\varepsilon\) donnée. On a dès lors:
\[\begin{align} \frac{b_1-a_1}{2^n}&<\varepsilon,\nonumber\\ 2^n&>\frac{b_1-a_1}{\varepsilon},\nonumber\\ n&>\log_2\left(\frac{b_1-a_1}{\varepsilon}\right), \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(0.5\cdot 10^5)\approx 15.6. \qquad{(4.2)}\] Il faut donc au plus \(n=16\) itérations 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.
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.