Exercices corrigés — Méthodes numériques

$f(1)=-1<0$, $f(2)=2>0$ : une racine ($\sqrt2$) est encadrée.

Milieu $c=\tfrac{a+b}2$ ; on garde la moitié où $f$ change de signe.

$f(c)>0\Rightarrow$ racine dans $[a,c]$ ; $f(c)<0\Rightarrow$ dans $[c,b]$.

$c_1=\tfrac32$ ($f=\tfrac14>0\Rightarrow[1,\tfrac32]$) ; $c_2=\tfrac54$ ($f=-\tfrac7{16}<0\Rightarrow[\tfrac54,\tfrac32]$) ; $c_3=\tfrac{11}8$ ($f<0\Rightarrow[\tfrac{11}8,\tfrac32]$) ; $c_4=\tfrac{23}{16}$ ($f>0\Rightarrow[\tfrac{11}8,\tfrac{23}{16}]$).

Après $4$ pas : $\sqrt2\in[\tfrac{11}8,\tfrac{23}{16}]$, largeur $\tfrac1{16}$.

$g(x)=\cos x$ : la suite converge si $|g'(\ell)|<1$ au point fixe $\ell$.

$g'(x)=-\sin x$, et $0<\ell<1$ donc $|\sin\ell|<1$.

Itérer depuis $x_0=1$ stabilise vers $\ell\approx0{,}739$.

$g'(x)=-\sin x$ ; au point fixe $\ell\approx0{,}739$, $|g'(\ell)|=\sin\ell\approx0{,}67<1$ : $g$ est contractante, l'itération converge (linéairement).

Itérer $x_{n+1}=\cos x_n$ depuis $x_0=1$ converge vers $\ell\approx0{,}7390851$ (vérifie $\ell=\cos\ell$).

$x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$ avec $f'(x)=2x$.

Simplifier : $x_{n+1}=\tfrac12\big(x_n+\tfrac2{x_n}\big)$.

Itérer en fractions exactes.

$x_{n+1}=x_n-\dfrac{x_n^2-2}{2x_n}=\dfrac12\Big(x_n+\dfrac2{x_n}\Big)$.

$x_1=\tfrac12(1+2)=\tfrac32$ ; $x_2=\tfrac12(\tfrac32+\tfrac43)=\tfrac{17}{12}$ ; $x_3=\tfrac12(\tfrac{17}{12}+\tfrac{24}{17})=\tfrac{577}{408}$.

$x_3=\tfrac{577}{408}\approx1{,}4142157$ : déjà $6$ décimales exactes de $\sqrt2$. Le nombre de décimales double à chaque pas (convergence quadratique).

$f'(x)=3x^2$, $x_{n+1}=x_n-\dfrac{x_n^3-2}{3x_n^2}$.

$x_1=1-\dfrac{1-2}3=1+\tfrac13$.

Puis $x_2$ avec $x_1=\tfrac43$.

$x_1=1-\dfrac{-1}3=\dfrac43$.

$x_2=\dfrac43-\dfrac{(\tfrac43)^3-2}{3(\tfrac43)^2}=\dfrac43-\dfrac{\tfrac{64}{27}-2}{\tfrac{16}{3}}=\dfrac{91}{72}\approx1{,}2639$.

$x_{n+1}=x_n-f(x_n)\dfrac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$.

$f(1)=-1$, $f(2)=2$.

La sécante remplace la dérivée par un taux d'accroissement.

$x_2=2-2\cdot\dfrac{2-1}{2-(-1)}=2-\dfrac23=\dfrac43$.

$x_3=\tfrac43-f(\tfrac43)\dfrac{\tfrac43-2}{f(\tfrac43)-f(2)}=\dfrac75=1{,}4$.

Dichotomie : l'erreur est multipliée par $\tfrac12$ par pas (linéaire).

Newton : l'erreur est (à peu près) élevée au carré par pas (quadratique).

$2^{10}=1024$.

Pour diviser l'erreur par $1000\approx2^{10}$, il faut $\approx10$ pas (un facteur $2$ par pas).

L'erreur passe de $10^{-1}$ à $10^{-2}$, $10^{-4}$, $10^{-8}$… : le nombre de décimales double, $\sim3$ pas suffisent.

$h=\tfrac14$, points $0,\tfrac14,\tfrac12,\tfrac34,1$.

Gauche : somme sur $x_0,\dots,x_3$ ; droite : sur $x_1,\dots,x_4$.

$f$ croissante $\Rightarrow$ gauche sous-estime, droite sur-estime.

$\tfrac14\big(0+\tfrac1{16}+\tfrac4{16}+\tfrac9{16}\big)=\tfrac14\cdot\tfrac{14}{16}=\tfrac7{32}$.

$\tfrac14\big(\tfrac1{16}+\tfrac4{16}+\tfrac9{16}+1\big)=\tfrac14\cdot\tfrac{30}{16}=\tfrac{15}{32}$.

$\tfrac7{32}<\tfrac13<\tfrac{15}{32}$.

$T=h\big[\tfrac{f(x_0)+f(x_n)}2+\sum_{i=1}^{n-1}f(x_i)\big]$, $h=\tfrac14$.

$f(0)=0$, $f(1)=1$, intérieurs $\tfrac1{16},\tfrac4{16},\tfrac9{16}$.

Erreur $=T-\tfrac13$.

$T=\tfrac14\big[\tfrac{0+1}2+\tfrac{1+4+9}{16}\big]=\tfrac14\big[\tfrac12+\tfrac{14}{16}\big]=\tfrac{11}{32}$.

$T-\tfrac13=\tfrac{11}{32}-\tfrac13=\tfrac{33-32}{96}=\tfrac1{96}$ : les trapèzes sur-estiment ($f$ convexe).

$S=\tfrac h3\big(f(x_0)+4f(x_1)+f(x_2)\big)$, $h=\tfrac12$, $x_1=\tfrac12$.

Simpson est exact sur les polynômes de degré $\le3$.

Évaluer pour $f=x^2$ puis $f=x^3$.

$S=\tfrac16\big(0+4\cdot\tfrac14+1\big)=\tfrac16\cdot2=\tfrac13$ = valeur exacte ✓.

$S=\tfrac16\big(0+4\cdot\tfrac18+1\big)=\tfrac16\cdot\tfrac32=\tfrac14$ = valeur exacte ✓ (cubique !).

$h=\tfrac\pi2$, points $0,\tfrac\pi2,\pi$ ; $\sin0=0$, $\sin\tfrac\pi2=1$, $\sin\pi=0$.

Trapèzes : $h[\tfrac{0+0}2+1]$. Simpson : $\tfrac h3(0+4\cdot1+0)$.

Comparer à la valeur exacte $2$.

$T=\tfrac\pi2\big[\tfrac{0+0}2+1\big]=\tfrac\pi2\approx1{,}571$ (erreur $\approx0{,}43$).

$S=\tfrac\pi6(0+4+0)=\tfrac{2\pi}3\approx2{,}094$ (erreur $\approx0{,}094$).

Sur un grand intervalle, une seule parabole approxime mal.

On découpe en $n$ sous-intervalles et on applique la formule sur chacun.

L'erreur en $O(h^4)$ décroît vite quand $n$ augmente.

Composite = somme de Simpson sur des paires de sous-intervalles ; $h=\tfrac\pi n$ petit $\Rightarrow$ erreur $O(h^4)$ minuscule.

Avec $n=8$, Simpson composite donne $\approx2{,}00000$ (erreur $\sim10^{-4}$).

Aucune primitive en termes de fonctions usuelles : seule l'intégration numérique permet de conclure.

Appliquer Simpson composite avec $n$ pair (ex. $n=10$).

C'est lié à la fonction d'erreur (loi normale).

Simpson composite sur $[0,1]$, $h=0{,}1$ : on évalue $e^{-x_i^2}$ aux $11$ nœuds.

$\displaystyle\int_0^1 e^{-x^2}\,dx\approx0{,}7468$.

$y_{n+1}=y_n+h\,f(t_n,y_n)$ avec $f(t,y)=y$.

$y_{n+1}=y_n(1+h)$.

$2$ pas de $t=0$ à $t=1$.

$y_1=y_0(1+\tfrac12)=\tfrac32$ ; $y_2=\tfrac32\cdot\tfrac32=\tfrac94=2{,}25$.

La solution exacte est $e\approx2{,}718$ : Euler sous-estime (erreur $\approx0{,}47$, ordre $1$).

$k_1=f(y_n)$, $k_2=f\big(y_n+\tfrac h2 k_1\big)$, $y_{n+1}=y_n+h\,k_2$.

Ici $f(y)=y$.

$k_1=1$, $k_2=1+\tfrac12$.

$k_1=1$ ; $k_2=y_0+\tfrac h2 k_1=1+\tfrac12=\tfrac32$.

$y_1=y_0+h\,k_2=1+\tfrac32=\tfrac52=2{,}5$.

$k_1=y_n$, $k_2=y_n+\tfrac h2k_1$, $k_3=y_n+\tfrac h2k_2$, $k_4=y_n+hk_3$.

$y_{n+1}=y_n+\tfrac h6(k_1+2k_2+2k_3+k_4)$.

Développer pour $f(y)=y$.

En reportant ($y_0=1$) : $y_1=1+h+\tfrac{h^2}2+\tfrac{h^3}6+\tfrac{h^4}{24}$ — exactement le DL de $e^h$ à l'ordre $4$.

$y_1=1+1+\tfrac12+\tfrac16+\tfrac1{24}=\tfrac{65}{24}\approx2{,}7083$.

$y_{n+1}=y_n+h(-2y_n)=(1-2h)y_n$, donc $y_n=(1-2h)^n y_0$.

Stable (décroît vers $0$) ssi $|1-2h|<1$.

Résoudre l'inégalité.

$y_n=(1-2h)^n$ : tend vers $0$ ssi $|1-2h|<1$.

$-1<1-2h<1\Rightarrow 0<h<1$. Pour $h=1{,}5$ : $|1-3|=2>1$, la suite diverge en oscillant — alors que la vraie solution tend vers $0$ !

Solution exacte : $(\cos t,-\sin t)$, donc $x^2+y^2=1$ constant.

Euler : $(x,y)\leftarrow(x+hy,\;y-hx)$.

Calculer le nouveau rayon au carré.

$x_{n+1}^2+y_{n+1}^2=(x+hy)^2+(y-hx)^2=(1+h^2)(x^2+y^2)$.

Le rayon est multiplié par $\sqrt{1+h^2}>1$ à chaque pas : la trajectoire Euler spirale vers l'extérieur au lieu de rester sur le cercle.

(a) Dériver $y$ et vérifier $y'=t-y$ et $y(0)=1$.

(b) Euler ou RK4 pas à pas de $0$ à $2$.

Comparer à la valeur exacte.

$y'=1-2e^{-t}$ et $t-y=t-(t-1+2e^{-t})=1-2e^{-t}$ : égaux ✓ ; $y(0)=0-1+2=1$ ✓.

On itère RK4 (pas $h$ petit) de $t=0$ à $t=2$. Valeur exacte : $y(2)=2-1+2e^{-2}=1+2e^{-2}\approx1{,}2707$.