9 Zéro de fonctions
Le but de cette série d’exercices est de déterminer les zéros de manière approchée d’une fonction notamment par la méthode de Newton. Cela permet en particulier de trouver des solutions approchées d’équations non linéaires. Cette méthode est fondamentale autant d’un point de vue numérique qu’analytique.
Exercice 9.1 - Méthode de Newton en une dimension
En une dimension, la méthode de Newton consiste à trouver une solution approchée d’une seule équation. Cette équation peut être mise sous la forme générale \(F(x)=0\) où \(F:\mathbb{R}\to\mathbb{R}\) est une fonction assez régulière, donc le but est de trouver un zéro de la fonction \(F\). L’équation \(F(x)=0\) est équivalente (si \(F^\prime(x) \neq 0\)) à l’équation \(G(x)=x\) où \(G\) est la fonction définie par:
\[ G(x) = x - \frac{F(x)}{F^\prime(x)} \,. \]
La méthode de Newton consiste à trouver un point fixe de \(G\), i.e. résoudre \(G(x)=x\) par itérations successives:
\[ x_{i+1} = G(x_i) = x_i - \frac{F(x_i)}{F^\prime(x_i)} \]
à partir d’une valeur initiale \(x_0\in\mathbb{R}\). Lorsque la suite \((x_i)_ {i\in\mathbb{N}}\) converge, alors la limite \(x\) est une solution de \(G(x)=x\) donc de \(F(x)=0\).
a. Écrire une fonction newton1d(F, DF, x0, eps=1e-10, N=1000) qui pour une fonction \(F\), sa dérivée \(F^\prime\) et une valeur initiale \(x_0\) données calcule les itérations de Newton jusqu’à ce que \(|F(x_{i})| < \varepsilon\) et retourne \(x_{i}\). Si \(N\) itérations n’ont pas suffi à atteindre ce critère de convergence, alors retourner une erreur.
b. En utilisant la fonction définie précédemment, trouver une solution approchée de l’équation \(e^{-x} = x\).
c. Sans utiliser les fonctions sqrt et log ni les puissances fractionnaires, définir une fonction racine(x,n) qui calcule \(\sqrt[n]{x}\).
Parfois, la dérivée de la fonction \(F\) n’étant pas calculable analytiquement, il est alors nécessaire de l’approcher numériquement:
\[ F^\prime(x_i) \approx \frac{F(x_i) - F(x_{i-1})}{x_i-x_{i-1}} \,, \]
ce qui mène à la méthode de la sécante:
\[ x_{i+1} = x_i - F(x_i) \frac{x_i-x_{i-1}}{F(x_i) - F(x_{i-1})} = \frac{x_{i-1}F(x_{i})-x_{i}F(x_{i-1})}{F(x_{i})-F(x_{i-1})} \,, \]
où \(x_0\) et \(x_1\) doivent être choisis.
d. Écrire une méthode secant1d(F, x0, x1, eps=1e-10, N=1000) implémentant la méthode de la sécante et la tester sur l’exemple précédent.
Exercice 9.2 - Méthode de Newton en plusieurs dimensions
La méthode de Newton en une dimension est facilement généralisable à plusieurs dimensions pour résoudre des équations de la forme \(F(\boldsymbol{x})=\boldsymbol{0}\) où \(F:\mathbb{R}^n \to \mathbb{R}^n\) est une fonction assez régulière. Conceptuellement la méthode est identique: l’équation \(F(\boldsymbol{x})=\boldsymbol{0}\) est équivalente à \(G(\boldsymbol{x})=\boldsymbol{x}\) avec la fonction \(G\) définie par:
\[ G(\boldsymbol{x}) = \boldsymbol{x} - \big(F^\prime(\boldsymbol{x})\big)^{-1} F(\boldsymbol{x}) \,, \]
où \(F^\prime(\boldsymbol{x})\) désigne la matrice jacobienne de taille \(n \times n\) de \(F\) en \(x\). Ainsi les itérations de Newton s’écrivent:
\[ \boldsymbol{x}_{i+1} = \boldsymbol{x}_{i} - \big(F^\prime(\boldsymbol{x}_i)\big)^{-1} F(\boldsymbol{x}_i) \,. \]
a. Écrire une fonction newton(F, DF, x0, eps=1e-12, N=10000) implémentant la méthode de Newton en plus d’une dimension.
b. Utiliser la fonction précédente pour résoudre le système suivant:
\[ \begin{align*} \cos(x) & =\sin(y)\,, & e^{-x} & =\cos(y)\,. \end{align*} \]
Exercice 9.3 - Attracteur de la méthode de Newton
Le but de cet exercice est de résoudre l’équation \(z^3 = 1\) dans le plan complexe à l’aide de la méthode de Newton et d’analyser vers laquelle des trois racines de l’unité la méthode va converger suivant le choix du point initial \(z_0\).
a. Si nécessaire adapter la fonction newton1d pour que celle-ci s’applique également aux nombres complexes et la tester pour résoudre \(z^3 = 1\) à partir de différentes valeurs de \(z_0\).
b. Déterminer pour chaque \(z_0 \in \big\{x_0+iy_0: x_0\in[-3,3] \; \text{et} \; y_0\in[-3,3]\big\}\) vers quelle racine de l’unité la méthode de Newton va converger. Représenter graphiquement cet ensemble comme sur la Figure 9.1.
c. ! La méthode précédente a le désavantage de procéder séquentiellement au calcul pour chaque valeur de \(z_0\), ce qui rend cette évaluation assez lente. Proposer une nouvelle implémentation permettant de calculer parallèlement toutes les valeurs de \(z_0\) en utilisant les indexages NumPy.
Exercice 9.4 - Équation différentielle non linéaire !!
Le but est de résoudre l’équation différentielle suivante avec conditions de valeurs limites:
\[ \begin{align*} u^{\prime\prime}(x)+u^{3}(x) & = \sin(x) \,, & u(0) & = u(2\pi) = 0 \,, \end{align*} \]
sur l’intervalle \([0,2\pi]\). Cette équation est un modèle simplifié pour une équation de Schrödinger non linéaire.
La méthode employée est celle des différences finies qui consistent à chercher les valeurs de \(u\) aux points \(x_n = \frac{2\pi n}{N}\) pour \(n=0,1,\dots,N\). Les inconnues sont alors les nombres \(u_n = u(x_n)\) et forment un vecteur de dimension \(N+1\). La méthode des différences finies consiste à approximer la dérivée seconde par:
\[ u^{\prime\prime}(x) \approx \frac{u(x+h)-2u(x)+u(x-h)}{h^{2}} \,, \]
lorsque \(h\) est petit. En prenant \(h=\frac{2\pi}{N}\), alors:
\[ u^{\prime\prime}(x_n) \approx \frac{u_{n+1}-2u_n+u_{n-1}}{h^{2}} \,, \]
et donc l’équation initiale s’approxime par:
\[ \begin{align*} \frac{u_{n+1}-2u_{n}+u_{n-1}}{h^{2}}+u_{n}^{3} & = \sin(x_{n}) \,, & u_{0} & = u_{N} = 0 \,, \end{align*} \]
pour \(n=1,2,\dots,N-1\). Cette équation peut être vue comme une équation du type \(F(\boldsymbol{u})=\boldsymbol{0}\) pour \(\boldsymbol{u} = (u_n)_ {n=0}^{N+1}\) et donc être résolue par la méthode de Newton.
a. Montrer l’approximation suivante:
\[ u^{\prime\prime}(x) = \frac{u(x+h)-2u(x)+u(x-h)}{h^{2}} + O(h^2) \quad \text{lorsque} \quad h \to 0 \,. \]
b. Définir un vecteur x représentant les \(N+1\) points équidistribués dans \([0,2\pi]\) et h la distance entre les points, avec par exemple \(N=200\).
c. Définir une fonction F(u) représentant la fonction \(F:\mathbb{R}^{N+1} \to \mathbb{R}^{N+1}\) permettant de mettre l’équation approchée sous la forme \(F(\boldsymbol{u})=\boldsymbol{0}\).
d. Définir une fonction DF(u) représentant la jacobienne de la fonction précédente.
e. Utiliser la fonction newton définie précédemment pour calculer une solution approchée de l’équation. En changeant de valeurs initiales, est-il possible de trouver d’autres solutions ?