TP3 : Autour de la méthode de Newton

Exercice 1.- Implémentation de la méthode de Newton

On rappelle la méthode de Newton (en pseudo-code):

Data : fonction et dérivée fun et funprime, initialisation x0, tolérance epsilon, nombre maximal d'itérations maxIt

initialisation
x $\longleftarrow$ x0
nbIt $\longleftarrow$ 0

While critère d'arrêt pas satisfait and nbIt < maxIt do
$\qquad$ mettre à jour x
$\qquad$ incrémenter nbIt $\longleftarrow$ nbIt + 1

return x and ...

1. Écrire un fonction newton prenant en argument une fonction fun et sa dérivée funprime une condition initiale x0 une tolérance epsilon pour le critère d'arrêt et un nombre maximal maxIt d'itérations. On choisira d'implémenter ici le critère d'arrêt `$|f(x_n)| < \epsilon$''. La fonctionnewton` renverra

• un booléen b qui vaut True si le critère d'arrêt a été satisfait avant d'atteindre le nombre maximal d'itérations fixé et False sinon,
• le numéro de la dernière itération nbIt,
• la dernière valeur de $x_n$ ($ n = $ nbIt).

import matplotlib.pyplot as plt
import numpy as np

1. Fixer epsilon $= 10^{-6}$ et maxIt $= 50$ (par exemple). Effectuer un premier test avec $f_0 (x) = x^2 - 1$ en partant de x0 = 4.

1. On veut à présent étudier l'influence de la condition initiale x0. Discrétiser uniformément l'intervalle $[-2, 2]$ en un vecteur I0 à $N$ points et appliquer la méthode de Newton à $f_0$ à partir de ces $N$ conditions initiales. Représenter sur une même figure les $N$ points $(x, 0)_{x \in I0}$, en noir si la méthode n'a pas convergé, en rouge si elle a convergé vers la solution négative et en vert si elle a convergé vers la solution négative. On pourra prendre $N = 100$ puis $N=200$ par exemple.

1. Recommencer l'étude précédente avec la fonction $f_1$ définie par $f_1(x) = x^4 - 2x^2 - 1$.

On peut définir la méthode de Newton également pour une fonction holomorphe $f$ par $$ z_{n+1} = z_n - \frac{f(z_n)}{f^\prime(z_n)} $$ On aimerait étudier dans ce cadre l'influence de la condition initiale comme précédemment, dans le cas où $f(z) = z^3 - 1$. On sait que $f$ possède trois racines complexes distinctes $\mathcal{R} = \{z^1, z^2, z^3 \}$ et le but est de représenter (par exemple avec trois couleurs différentes) les trois bassins d'attractions associés à ces trois racines. Soit $z^\ast$ une racine de $f$, on appelle bassin d'attraction de $z^\ast$ l'ensemble des $z_0 \in \mathbb{C}$ tels que la méthode de Newton initialisée à $z_0$ converge vers $z^\ast$.

Exercice 2.- Manipulation d'images en python

1. On commence par importer le module matplotlib.image, puis on importe l'image image0.png et on l'affiche. Quel objet python est img0 ? Recommencer avec le fichier image1.png puis image2.png.

import matplotlib.image as mpimg
img0 = mpimg.imread('image0.png')
plt.imshow(img0)

<matplotlib.image.AxesImage at 0x7f0eff63bcd0>

1. On va coder la couleur d'un pixel par un vecteur $[R, G, B]$ de taille $3$ dit RGB (ou RVB en français rouge-vert-bleu). Chaque coordonnée varie entre $0$ et $1$ (ou $0$ et $255$ selon la convention). $[1, 0, 0]$ code le rouge, $[0, 1, 0]$ le vert, $[0, 0, 1]$ le bleu, $[1, 1, 1]$ le blanc et $[0, 0, 0]$ le noir. Créer une image de taille $N \times N$ pixels entièrement noire, puis blanche, puis rouge.

1. On représente le carré $[-1, 1] \times [-1,1]$ par une image de taille $N \times N$ représenter en rouge sur fond noir (par exemple !) le disque de rayon $0.5$ centré en $0$, puis (sur une nouvelle image) le quart de disque supérieur droit seulement.

Exercice 3.- Fractal de Newton

On revient à la représentation des bassins d'attraction.

1. Définir la fonction f holomorphe telle que $f(z) = z^3 - 1$ ainsi que sa dérivée fprime et un np.array roots de taille $3$ contenant les trois racines distinctes de $f$.

Afin de définir le complexe $z = x + iy$ en Python, on définit z = complex(x, y).

1. Implémenter une méthode de Newton modifiée newtonMod à partir de la fonction newton implémentée à l'exercice $1$. On demande les modifications suivantes : on va utiliser le fait qu'on a une expression algébrique des racines de $f$ afin d'étudier plus simplement la dépendance de la méthode de Newton en la condition initiale et on remplace le critère d'arrêt de l'exercice $1$ par le critère d'arrêt "il existe une racine complexe $r$ de $f$ telle que $|x_n - r| < \epsilon$". On veut que newtonMod retourne les mêmes trois éléments que la fonction newton en changeant le booléen $b$ en un entier pouvant prendre $4$ valeurs selon que la méthode n'a pas convergé (b=-1 par exemple) ou a convergé et dans ce cas b renvoie un numéro correspondant à la racine en question.

1. Discrétiser uniformément l'intervalle $[-1,1]$ avec $N$ points puis le carré $[-1,1] \times [-1,1]$ avec $N \times N$ points. Effectuer la méthode newtonMod à partir en prenant pour condition initiale chacun des $N^2$ points obtenus. Représenter le carré $[-1,1] \times [-1,1]$ par une image de taille $N \times N$ pixels et colorier chaque pixel en noir si la méthode n'a pas convergé et sinon en rouge, vert ou bleu selon la racine vers laquelle elle a convergé. Essayer avec $N = 50$ puis $N = 500$.

1. Sur une nouvelle image, colorier similairement chaque pixel sur une échelle de gris proportionnellement au nombre d'itérations nécessaires à la convergence de la méthode, nbIt/maxIt $\in [0, 1]$.

1. Prenez le temps de la contemplation !

Prolongations.-

Pour ceux qui ont le temps, vous pouvez choisir une (ou même plusieurs) des suggestions suivantes pour approfondir l'étude.

• Choisir un polynôme (différent de celui figurant sur votre feuille de TP) et représenter les bassins d'attractions de la méthode de Newton associée ;
• Faire varier progressivement un coefficient/paramètre définissant votre polynôme et représenter les bassins d'attractions pour différentes valeurs du paramètre ;
• "Ralentir" la méthode de Newton en la remplaçant par $$ F(z) = z - h \frac{P(z)}{P^\prime(z)} $$ pour $h$ de plus en plus petit ;
• Représenter les bassins d'attractions associés à une autre méthode itérative ;
• etc.