Résolution numérique d'équations

Pour appliquer la méthode de dichotomie sur $[a,b]$, quelle condition doit vérifier $f$ ?

La dichotomie nécessite seulement la continuité de $f$ et un changement de signe entre $a$ et $b$ ($f(a)f(b)<0$), garantissant par le théorème des valeurs intermédiaires l'existence d'une racine.

Après combien d'étapes de dichotomie sur $[0,1]$ est-on certain que l'intervalle a une longueur $\leq0{,}01$ ?

Après $n$ étapes, la longueur de l'intervalle est $\dfrac{b-a}{2^n} = \dfrac{1}{2^n}$. On veut $\dfrac{1}{2^n}\leq0{,}01 \iff 2^n\geq100$. Comme $2^6=64<100$ et $2^7=128\geq100$, il faut $n=7$ étapes.

Vrai ou faux : la méthode de Newton converge toujours, quel que soit le point de départ $x_0$.

Faux. La convergence de Newton n'est garantie que localement, c'est-à-dire pour $x_0$ suffisamment proche de la racine $\alpha$. Un mauvais choix de $x_0$ peut faire diverger la suite ou la faire converger vers une autre racine.

Donner la formule de récurrence de la méthode de Newton pour résoudre $f(x)=0$.

La formule de Newton-Raphson est $x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$, obtenue en cherchant le zéro de la tangente au graphe de $f$ en $x_n$.

Calculer une itération de Newton pour $f(x)=x^2-9$ en partant de $x_0=4$.

$f(4)=16-9=7$. $f'(x)=2x$, donc $f'(4)=8$. $x_1 = 4 - \dfrac{7}{8} = 3{,}125$ (la vraie racine est $3$, donc cette première itération s'en approche déjà).

Montrer que la méthode de Newton appliquée à $f(x)=x^2-a$ (pour $a>0$) donne la formule récursive $x_{n+1} = \dfrac12\left(x_n + \dfrac{a}{x_n}\right)$ (méthode de Héron pour calculer $\sqrt a$).

$f(x)=x^2-a$, $f'(x)=2x$. $x_{n+1} = x_n - \dfrac{x_n^2-a}{2x_n} = \dfrac{2x_n^2 - (x_n^2-a)}{2x_n} = \dfrac{x_n^2+a}{2x_n} = \dfrac12\left(x_n+\dfrac{a}{x_n}\right)$. C'est exactement la méthode de Héron (connue depuis l'Antiquité) pour approcher $\sqrt a$, et elle converge en fait très rapidement (quadratiquement, conformément à la théorie de Newton).

Vrai ou faux : si $f'(\alpha)=0$ en la racine $\alpha$ recherchée (racine multiple), la convergence de Newton reste quadratique.

Faux. Lorsque $\alpha$ est une racine multiple ($f(\alpha)=f'(\alpha)=0$), la convergence de Newton devient seulement linéaire (beaucoup plus lente que dans le cas d'une racine simple).

Effectuer deux étapes de dichotomie pour $f(x)=x^3-5$ sur $[1,2]$ (encadrement de $\sqrt[3]5$).

$f(1)=1-5=-4<0$, $f(2)=8-5=3>0$. Étape 1 : $m_0=1{,}5$, $f(1{,}5)=3{,}375-5=-1{,}625<0$ (même signe que $f(1)$), donc on garde $[1{,}5,2]$. Étape 2 : $m_1=1{,}75$, $f(1{,}75)=5{,}359\ldots-5\approx0{,}359>0$ (signe opposé à $f(1{,}5)$), donc on garde $[1{,}5,1{,}75]$. La racine cubique de $5$ ($\approx1{,}71$) est bien dans cet intervalle.

Pourquoi dit-on que la convergence de la dichotomie est \"linéaire\" alors que celle de Newton est \"quadratique\" ? Expliquer la différence pratique.

Convergence linéaire (dichotomie) : l'erreur $e_n = |m_n-\alpha|$ vérifie $e_{n+1} \approx \frac12 e_n$ — elle est multipliée par une constante fixe ($\frac12$) à chaque étape, indépendamment de sa taille actuelle. Il faut donc un nombre constant d'itérations supplémentaires pour gagner un chiffre décimal (environ $3{,}3$ itérations par décimale, car $2^{3{,}3}\approx10$). Convergence quadratique (Newton) : $e_{n+1} \leq C\, e_n^2$ — l'erreur est (à peu près) mise au carré à chaque étape. Si $e_n$ est déjà petit (disons $e_n=10^{-2}$), alors $e_{n+1}$ est de l'ordre de $10^{-4}$, $e_{n+2}$ de l'ordre de $10^{-8}$ : le nombre de décimales correctes double environ à chaque itération, ce qui rend la convergence extrêmement rapide une fois amorcée près de la racine.

Soit $f(x)=x^2+1$. Que se passe-t-il si l'on tente d'appliquer la méthode de dichotomie sur $[-1,1]$ ?

$f(-1)=1+1=2>0$ et $f(1)=1+1=2>0$ : les valeurs aux extrémités sont de même signe, donc l'hypothèse $f(a)f(b)<0$ n'est pas satisfaite. La dichotomie ne peut pas être lancée valablement. C'est cohérent avec le fait que $f(x)=x^2+1>0$ pour tout $x$ réel : cette fonction n'a aucune racine réelle, donc il était impossible de trouver un changement de signe.

Donner un exemple de fonction et de point de départ $x_0$ pour lequel la méthode de Newton ne converge pas (diverge ou cycle), et expliquer pourquoi.

Un exemple classique est $f(x)=x^3-2x+2$ avec $x_0=0$. $f(0)=2$, $f'(0)=-2$, donc $x_1 = 0-\frac{2}{-2}=1$. $f(1)=1-2+2=1$, $f'(1)=3-2=1$, donc $x_2 = 1-\frac11=0$. La suite cycle indéfiniment entre $0$ et $1$ sans jamais converger, parce que $x_0$ n'est pas dans un voisinage où le théorème de convergence locale de Newton s'applique (la tangente y \"renvoie\" exactement au point précédent). Cet exemple illustre concrètement la limite \"convergence locale seulement\" du théorème de Newton.

On veut résoudre $\cos(x)=x$ par Newton. Écrire $f(x)$ et $f'(x)$, et effectuer une itération à partir de $x_0=0{,}7$ (sachant $\cos(0{,}7)\approx0{,}7648$, $\sin(0{,}7)\approx0{,}6442$).

On pose $f(x)=\cos(x)-x$ (résoudre $\cos x=x$ équivaut à $f(x)=0$). $f'(x)=-\sin(x)-1$. $f(0{,}7) \approx 0{,}7648-0{,}7=0{,}0648$. $f'(0{,}7) \approx -0{,}6442-1=-1{,}6442$. $x_1 = 0{,}7 - \dfrac{0{,}0648}{-1{,}6442} \approx 0{,}7+0{,}0394 \approx 0{,}7394$, déjà proche de la valeur connue $\approx0{,}7391$ (constante de Dottie).

Vrai ou faux : combiner dichotomie puis Newton (dichotomie d'abord pour encadrer grossièrement, puis Newton pour affiner) est une stratégie pertinente en pratique.

Vrai. C'est une stratégie courante en analyse numérique : la dichotomie offre une convergence garantie (mais lente) pour obtenir rapidement un bon point de départ proche de la racine, puis Newton prend le relais pour bénéficier de sa convergence quadratique rapide, sans risquer la divergence d'un mauvais point de départ.

Soit $f(x)=x^2-2$. Montrer que si $x_n>\sqrt2$, alors $x_{n+1}$ (obtenu par Newton) vérifie aussi $x_{n+1}>\sqrt2$ et $x_{n+1}<x_n$ — la suite décroît tout en restant au-dessus de $\sqrt2$.

Par la formule de Héron (vue à l'exercice 6), $x_{n+1} = \dfrac12\left(x_n+\dfrac{2}{x_n}\right)$. $x_{n+1}\geq\sqrt2$ : par l'inégalité arithmético-géométrique, $\dfrac{x_n+2/x_n}{2} \geq \sqrt{x_n\cdot\frac{2}{x_n}} = \sqrt2$, avec égalité ssi $x_n=2/x_n \iff x_n=\sqrt2$. Comme $x_n>\sqrt2$ par hypothèse, l'inégalité est stricte : $x_{n+1}>\sqrt2$. Décroissance : $x_n - x_{n+1} = x_n - \dfrac12\left(x_n+\dfrac2{x_n}\right) = \dfrac12\left(x_n-\dfrac2{x_n}\right) = \dfrac{x_n^2-2}{2x_n}$. Comme $x_n>\sqrt2>0$, on a $x_n^2>2$ et $x_n>0$, donc cette quantité est strictement positive : $x_n>x_{n+1}$. Conclusion : la suite $(x_n)$ est strictement décroissante et minorée par $\sqrt2$, donc elle converge (théorème des suites monotones bornées), nécessairement vers $\sqrt2$ (point fixe de la récurrence).

Combien d'étapes de dichotomie sont nécessaires sur $[0,1]$ pour garantir une précision de $10^{-6}$ ? Comparer (en ordre de grandeur) au nombre d'itérations de Newton nécessaires pour la même précision en partant d'une erreur initiale de $10^{-1}$ avec une constante $C=1$ dans l'estimation quadratique.

Dichotomie : $\dfrac{1}{2^n}\leq10^{-6} \iff 2^n\geq10^6 \iff n \geq \log_2(10^6) = 6\log_2(10) \approx 6\times3{,}32=19{,}93$, donc $n=20$ étapes. Newton : avec $e_0=10^{-1}$ et $e_{n+1}\leq C\,e_n^2=e_n^2$ : $e_1\leq(10^{-1})^2=10^{-2}$, $e_2\leq(10^{-2})^2=10^{-4}$, $e_3\leq(10^{-4})^2=10^{-8}$. Donc $3$ itérations suffisent largement pour atteindre une précision de $10^{-6}$, contre $20$ étapes pour la dichotomie : un facteur d'environ $7$ en nombre d'itérations, illustrant concrètement la supériorité pratique de la convergence quadratique une fois la phase d'amorçage passée.