Cours de programmation séquentielle

Calcul du zéros de fonction

Buts

Énoncé

Écrire un programme permettant de calculer les zéros d’une fonction continue. La dite 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.

Introduction théorique: la méthode de la bissection

Illustration de la méthode de la bissection. Source: Wikipedia https://bit.ly/2RcljBW.
Figure 3.1: Illustration de la méthode de la bissection. Source: Wikipedia https://bit.ly/2RcljBW.

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 en é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}\) est de

\[ d_\mathrm{max}=(b_1+a_1)/2^n. \qquad{(3.3)}\]


Travail à réaliser

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:

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}\]

Remarque

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}\]\(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.

Méthodologie

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, El Kharroubi, Heirich, ou Malaspinas).

Exercices supplémentaires

Méthode exhaustive

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 là à un enseignant et implémentez la.

Méthode de Newton

Il existe d’autres méthodes pour déterminer les zéros de fonctions. 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.