--- title: VISI601_CMI (2b) Calcul scientifique II type: slide slideOptions: transition: slide progress: true slideNumber: true --- # Calcul scientifique II > [name=Jacques-Olivier Lachaud][time=Decembre 2021][color=#907bf7] > (Les images peuvent être soumises à des droits d'auteur. Elles sont utilisées ici exclusivement dans un but pédagogique) ###### tags: `visi601` Retour à [VISI601_CMI (Main) Algorithmique numérique](https://codimd.math.cnrs.fr/s/IWTaBkA9m) --- ## Méthode numérique :::success Pour résoudre un problème bien posé, $F(x,d)=0$, on résoud une suite de problèmes approchés $F_n(x_n,d_n)=0$. On cherche $x_n \rightarrow x$ quand $n \rightarrow \infty$. ::: :::info Une méthode est **consistante** ssi la méthode tend bien vers la solution avec la bonne donnée $d$ et la bonne solution $x$, i.e. $\forall n, F_n(x,d) = F_n(x,d) - F(x,d) \rightarrow 0$ lorsque $n \rightarrow \infty$. ::: :::info Une méthode est **fortement consistante** ssi $\forall n, F_n(x,d)=0$. ::: ==Note== Souvent $F_n$ utilise des résultats précédents, on note $F_n(x_n,x_{n-1},\ldots, d_n)$. --- ## Exemple : méthode de Newton :::warning * Soit $f:\mathbb{R} \rightarrow \mathbb{R}$ la donnée, on cherche une racine $f(x)=0$, donc $F(x,f):= f(x)$ * On choisit $x_0$, et $\forall n > 0, x_n := x_{n-1} - \frac{f(x_{n-1})}{f'(x_{n-1})}$ * Donc on résoud $\forall n >0$, $F_n(x_n, x_{n-1}, f) := x_n - x_{n-1} + \frac{f(x_{n-1})}{f'(x_{n-1})}$ ::: On vérifie que $F_n$ est *fortement consistante*: Si $\alpha$ est racine simple, i.e. $f(\alpha)=0$, $f'(\alpha)\neq 0$, on a bien $F_n(\alpha,\alpha,f)=0$. --- ## Exercices (résoudre f(x)=0) Soit la méthode $F_n$ paramétrée par un coefficient $\lambda>0$, t.q. On choisit $x_0$, et $\forall n > 0, x_n := x_{n-1} - \lambda \frac{f(x_{n-1})}{f'(x_{n-1})}$ Ecrire $F_n$. Est-ce que $F_n$ est consistante ? fortement consistante ? --- ## Exercices (résoudre f(x)=0) Soit la méthode $F_n(a_n,b_n,...,f):= f((a_n+b_n)/2)$ (dite **bissection** ou **dichotomie**), avec $a_0$ et $b_0$ choisis tels que $f(a_0)f(b_0)\le 0$ (de signe contraire), et $$ \begin{bmatrix} a_n \\ b_n \end{bmatrix} := \left\{ \begin{array}{l} \begin{bmatrix} a_{n-1}\\ (a_{n-1}+b_{n-1})/2 \end{bmatrix} \quad\text{si}\quad f\left(\frac{a_{n-1}+b_{n-1}}{2}\right)f(a_n) \le 0\\ \begin{bmatrix} (a_{n-1}+b_{n-1})/2 \\ b_{n-1} \end{bmatrix} \quad \text{sinon.}\end{array}\right. $$ Est-ce que $F_n$ est consistante ? fortement consistante ? --- ## Exercices (trouver un minimum) On cherche le minimum $\alpha$ d'une fonction $g : \mathbb{R} \rightarrow \mathbb{R}$. Quels méthode(s) numérique(s) proposez-vous d'utiliser ? Dans quels cas chacune fonctionnera ? --- ## Stabilité d'une méthode numérique :::info Une méthode numérique est **stable** s'il existe, pour tout $n$, une unique solution $x_n$ correspondant à une donnée $d_n$ et si $x_n$ varie continûment en fonctions des données. ::: ==continuité== : pour une petite variation $\delta d_n$, il existe une petite variation $\delta x_n$, telle que $F_n(x_n + \delta x_n, d_n + \delta d_n ) = 0$ --- ## Convergence d'une méthode numérique :::info La méthode numérique $F_n$ est dite **convergente** vers le problème $F$ ssi: $\forall \epsilon > 0, \exists n_0 = n_0(\epsilon), \exists \delta = \delta(n_0,\epsilon)$ tels que $\forall n \ge n_0, \forall \delta_n : \| \delta_n \| \le \delta \Rightarrow \| x(d) - x_n(d+\delta_n) \| \le \epsilon$, où $d$ est une donnée possible du problème $F(x,d)=0$, $x(d)$ est la solution correspondante et $x_n(d+\delta_n)$ est la solution de $F_n(x,d+\delta_n)$. ::: :::success Pour toute suite de données $d_n$ tendant vers $d$, $\lim_{n \rightarrow +\infty} x_n(d_n) = x(d)$. ::: --- ## Exemple: approximation par boîtes d'une intégrale  $\int_a^b f(t)dt \approx \sum_{i=0}^{n-1} f(c_i)h$, avec $h=\frac{b-a}{n}$ et $c_i:=a+ih$. --- ## Exemple: approximation par boîtes d'une intégrale (II) 1. On a $d=(f,a,b)$ et on écrit $F(x,(f,a,b)):=x-\int_a^b f(t)dt$ 2. La méthode numérique est $F_n(x_n,(f,a,b)):=x_n-\sum_{i=0}^{n-1}f(c_i)h$ 3. La méthode numérique est **stable** ou **bien posée** si $f$ est continue sur $[a,b]$ 4. La méthode numérique **n'est pas fortement consistante** 5. La méthode numérique est **consistante** si $f$ est dérivable. On montre $\left|\int_{c_i}^{c_{i+1}} f(t)dt-hf(c_i) \right| \le |f'(c_i)|\frac{h^2}{2}+o(h^2)$ $F_n$ consistante ssi $F_n(x,(f,a,b)) \rightarrow 0$ lorsque $n \rightarrow 0$ Or $\left| \int_a^b f(t)dt - \sum_{i=0}^{n-1} h f(c_i) \right| \le \sum_{i=0}^{n-1} \left|\int_{c_i}^{c_{i+1}} f(t)dt - h f(c_i) \right| \le K n \frac{h^2}{2} +o(nh^2)$ qui tend vers 0 lorsque $n$ tend vers l'infini car $h=(b-a)/n$ 6. La méthode numérique est aussi **convergente**, (ici idem consistance) --- ## Relation stabilité, consistance et convergence Si $F$ est **bien posé au sens de Hadamard** (résolution d'équations diff. linéaires ) :::success **Convergence** de $F_n$ implique **stabilité** de $F_n$ ::: :::success Si $F_n$ **consistante** avec $F$, alors **stabilité** de $F_n$ implique **convergence** de $F_n$ ::: :::success (Théorème de Lax-Richtmyer pour problème évolutif linéaire) Si $F_n$ **consistante** avec $F$, alors **stabilité** et **convergence** sont équivalents ::: Plus facile en général de montrer **consistance** et **stabilité** que **convergence**.