Formulaire

Ce formulaire rassemble, chapitre par chapitre, ce qu'il faut avoir sous les yeux la veille d'un examen: les définitions opératoires, les constantes, les ordres de convergence avec leurs hypothèses, les coûts en opérations et les formules d'erreur avec leurs constantes. Chaque entrée renvoie au chapitre qui la démontre; les démonstrations, les exemples chiffrés et les pièges sont là-bas, pas ici.

Comment lire les renvois. Dans chaque chapitre, les équations numérotées et les théorèmes partagent la même série: l'équation (2.5) et le théorème 2.5 sont deux objets différents. Ici, un numéro entre parenthèses désigne toujours une équation, un numéro précédé du mot «théorème» toujours un théorème. Les rappels d'algèbre linéaire — normes vectorielles et matricielles induites, rayon spectral, matrices symétriques définies positives, théorème spectral, diagonalisation, matrice de Hilbert — sont rassemblés à l'annexe A et ne sont pas repris ici.

Ce que ce formulaire ne remplace pas. Une formule sans son hypothèse est un piège: la convergence quadratique de Newton suppose une racine simple, l'ordre 4 de la spline suppose la condition encastrée, l'ordre 2 du trapèze suppose $f$ de classe ${\mathcal{C}}^2$ bornée. Chaque ligne porte donc sa condition, et il faut la lire.

Notation, et les symboles qui servent deux fois

Le cours suit la notation usuelle de chaque domaine plutôt qu'une notation uniforme: un même symbole y désigne donc des objets différents selon le chapitre, comme dans toute la littérature. La liste des réutilisations est ci-dessous; c'est la page à lire avant les autres.

Les neuf réutilisations à connaître

Le cas de $\lambda$ n'est pas une collision mais une identité: le $\lambda$ de l'équation-test $y^{\prime }=\lambda y$ est une valeur propre de la jacobienne, et c'est tout le contenu de la réduction du chapitre 10. Le cas de $\rho$ en est une, en revanche, et dans le même chapitre: le rayon spectral $\rho (A)$ et le quotient de Rayleigh $\rho (\mathbf{x})$ cohabitent au chapitre 5, distingués seulement par leur argument — matrice ou vecteur.

1. Arithmétique flottante

Format binary64 (1.4). Mantisse de 53 bits avec le bit caché, soit $53{\log }_{10}2\approx 15,95$ chiffres décimaux — environ 16, jamais 17. Repère: $2^{53}=9007199254740992$ est le dernier entier suivi de son successeur. Amplitude $\approx 1,80\cdot 10^{308}$; plus petit normalisé .

Convention du cours (1.5): ${\epsilon }_{\text{mach}}$ est l'ulp de $1$, et c'est $u$ qui apparaît dans les majorations. Dans $[2^e,2^{e+1}[$ il y a exactement $2^{52}$ nombres machine, espacés de : l'espacement à chaque exposant, l'espacement relatif ne change pas.

Modèle d'arrondi (1.6), théorème 1.1, valable pour tout $x$ sans dépassement de capacité, et aussi pour chaque opération correctement arrondie: $\mathrm{fl}(x\circ y)=(x\circ y)(1+\delta )$, $\circ \in \{+,-,\times ,/\}$, ainsi que pour  ​ (1.8).

Facteur d'amplification d'une somme (1.9), théorème 1.2: l'erreur relative du résultat vaut au plus $K$ fois celle des termes. $K=1$ pour deux termes de même signe; $K\to \infty$ pour une différence de nombres voisins. La soustraction ne crée pas l'erreur, elle la révèle: si $y/2\le x\le 2y$, elle est même exacte (lemme de Sterbenz).

Les trois réécritures stables du chapitre 1 (1.11), (1.13). La cure d'une annulation est toujours algébrique et presque toujours gratuite: on remplace une soustraction par une somme ou une division.

Conditionnement relatif d'une fonction (1.16): facteur par lequel l'erreur relative de la donnée est multipliée. ${\kappa }_{x^n}=|n|$, ${\kappa }_{\sqrt{}}=1/2$, en . ; est bien conditionné () et calculé par un algorithme instable.

Sommation de gauche à droite (1.17): la borne croît linéairement en $n$. Sommation compensée de Kahan: $2u+O(n{u}^2)$, indépendante de $n$ au premier ordre, pour quatre opérations par terme au lieu d'une.

2. Équations non linéaires: les ordres et leurs hypothèses

Bissection (2.5)–(2.6), théorème 2.2: la seule garantie a priori du chapitre, valable sans aucune hypothèse de régularité. Repère: ${\log }_{10}2=0,301$ chiffre décimal par itération, soit 3,32 itérations par chiffre; $20$ itérations pour $10^{-6}$ sur un intervalle de longueur 1. L'erreur effective peut croître d'un pas au suivant: c'est la longueur de l'encadrement qui décroît, pas la distance à la racine.

Théorème du point fixe (2.9), théorème 2.3, sous deux hypothèses: stabilité $g([a,b])\subseteq [a,b]$ et contraction $|g^{\prime }|\le L<1$ sur $[a,b]$. Seule la seconde majoration est calculable. Critère local (théorème 2.4): $|g^{\prime }(x^{\ast })|<1$ attractif, répulsif, indécidable.

Newton (2.12) et sa relation d'erreur exacte (2.15), théorème 2.5. Newton est l'itération de point fixe qui annule $g^{\prime }(x^{\ast })$: avec $g=x-f/f^{\prime }$, on a $g^{\prime }=f{f}^{\prime \prime }/f^{\prime 2}$, nul en . Trois échecs à connaître: tangente presque horizontale (le pas explose), cycle ( depuis donne ), mauvais bassin ( diverge dès ). Garde-fous obligatoires: plafond d'itérations, encadrement conservé, amortissement.

Sécante (2.22), théorème 2.7: la récurrence d'exposants est celle de Fibonacci, d'où $p=\phi$. Indices d'efficacité: $E_{\text{seˊcante}}=\phi =1,618$ contre $E_{\text{Newton}}=2^{1/2}=1,414$. , sauf si est gratuite.

3. Systèmes linéaires: méthodes directes

Théorèmes 3.1 à 3.4. Repères pour $n=1000$: $C(n)=666166500$ contre $2n^2=2\cdot 10^6$ pour un couple de substitutions, soit un rapport de 333 — asymptotiquement $n/3$. Cholesky: , rapport vers 2.

Pivots et déterminant (3.10), théorème 3.1, avec ${\Delta }_k$ le $k$-ième mineur principal dominant et ${\Delta }_0=1$. Avec $s$ échanges de lignes, multiplier par $(-1{)}^s$. La condition est suffisante et (elle coûte plus cher que la factorisation); le remède est le pivotage.

Pivotage partiel (3.17), théorème 3.3: $PA=LU$ existe pour toute matrice inversible, et l'unicité est perdue. Le coût est $O(n^2)$ comparaisons, donc gratuit. Facteur de croissance borné par $2^{n-1}$ en théorie, voisin de 1 en pratique.

Cholesky (3.22)–(3.23). Aucun pivotage n'est nécessaire, parce que $|b_{ik}|\le \sqrt{{\max }_j{a}_{jj}}$ (3.25) borne d'avance toute croissance. Une racine carrée négative en cours de route que n'est pas définie positive: c'est le test de définie positivité le moins cher qui existe.

4. Conditionnement, et méthodes itératives

Normes induites (4.6)–(4.8), théorème 4.2: plus grande somme de ligne, plus grande somme de colonne, plus grande valeur singulière. Sous-multiplicativité $\Vert AB\Vert \le \Vert A\Vert \Vert B\Vert$ et $\Vert I\Vert =1$. Équivalence (4.2): $\Vert \mathbf{x}{\Vert }_{\infty }\le \Vert \mathbf{x}{\Vert }_2\le \sqrt{n}\Vert \mathbf{x}{\Vert }_{\infty }$, , . Enfin pour toute norme induite (4.10).

Conditionnement (4.11). Si $A$ est symétrique, ${\kappa }_2(A)=|{\lambda }_{\max }|/|{\lambda }_{\min }|$. Le déterminant ne mesure rien: $\mathrm{diag}(10^6,10^{-6})$ a un déterminant égal à 1 et ; a un déterminant de et .

Perturbation du second membre (4.12), théorème 4.3, borne atteinte pour certaines données; et perturbation de la matrice (4.16), admise.

La formule à retenir du chapitre 4 (4.18), théorème 4.4: l'encadrement est large de ${\kappa }^2$. Un petit résidu certifie seulement que $\hat{\mathbf{x}}$ est la solution exacte d'un problème voisin — c'est la stabilité inverse, pas la précision. Règle du pouce: on perd ${\log }_{10}\kappa$ chiffres sur seize.

Décomposition $A=M-N$ (4.21)–(4.22). Avec $A=D-E-F$:

Convergence si et seulement si $\rho (B)<1$ (théorème 4.5), linéairement au taux $\rho (B)$: $-1/{\log }_{10}\rho (B)$ balayages par chiffre décimal. Condition suffisante, lisible d'un coup d'œil (théorème 4.6):

et le même $q$ majore $\Vert B_{GS}{\Vert }_{\infty }$. Attention: «Jacobi converge» n'implique pas «Gauss–Seidel converge», ni l'inverse, hors des deux cas classiques (dominance diagonale stricte, et matrices SDP où Gauss–Seidel converge toujours).

Kahan et paramètre optimal (4.30), théorème 4.7. Le point (c) exige une matrice tridiagonale par blocs cohéremment ordonnée, et donne alors $\rho (B_{GS})=\rho (B_J{)}^2$ et $\rho (B_{{\omega }_{\text{opt}}})={\omega }_{\text{opt}}-1$. Ostrowski–Reich: si est SDP, SOR converge pour tout .

Direct ou itératif? Sur une matrice pleine, l'itératif gagne si $K<n/3$ balayages suffisent — et il n'économise aucune mémoire. Sur une matrice creuse à $m$ coefficients par ligne, un balayage coûte $2mn$ et aucune mémoire supplémentaire, tandis que la factorisation subit le remplissage. Le critère d'arrêt est le résidu relatif $\Vert {\mathbf{r}}^{(k)}\Vert /\Vert \mathbf{b}\Vert \le \text{tol}$ (4.31), qui ne borne l'erreur qu'à travers $\kappa$; l'incrément est ici un piège encore pire qu'au chapitre 2, car $\rho (B)$ est souvent proche de 1.

5. Valeurs propres

Gershgorin (5.6), théorème 5.1, pour $2n^2$ additions. Raffinements: une réunion connexe et isolée de $k$ disques contient exactement $k$ valeurs propres (théorème 5.2), donc un disque isolé d'une matrice réelle contient une valeur propre réelle; et les disques des colonnes valent aussi (théorème 5.3), à intersecter. Ce que Gershgorin ne dit pas: que chaque disque contient une valeur propre. Corollaire immédiat: une matrice à diagonale strictement dominante est inversible.

Théorème 5.4 pour la puissance, sous deux hypothèses: ${\lambda }_1$ strictement dominante et $c_1\ne 0$. Si $|{\lambda }_1|=|{\lambda }_2|$ — paire complexe conjuguée, ou — la méthode . Nombre d'itérations pour une tolérance: , soit une dizaine à et plus de treize cents à .

Quotient de Rayleigh (5.12) et sa précision quadratique (5.13), théorème 5.5 — seulement si $A$ est symétrique réelle, car la démonstration utilise deux fois l'orthonormalité de la base propre. Sur une matrice quelconque, la précision n'est que linéaire et $\rho (\mathbf{x})$ peut sortir de l'intervalle des valeurs propres.

Décalage (5.14), estimation ${\lambda }^{(k+1)}=\sigma +1/{\nu }_{k+1}$ (5.16). On factorise $A-\sigma I$ une seule fois ($\frac{2}{3}{n}^3$) et chaque itération coûte deux substitutions. Le mauvais conditionnement de n'est pas un obstacle: l'erreur est parallèle à la direction cherchée, et la normalisation l'efface.

Bauer–Fike (5.21), théorème 5.6, pour $A=V\Lambda V^{-1}$ diagonalisable. Le conditionnement du spectre est celui de la base propre, pas celui de $A$. Si $A$ est symétrique, $V=Q$ orthogonale et ${\kappa }_2(Q)=1$: les valeurs propres sont parfaitement conditionnées, et un petit résidu une petite erreur. Sinon, peut valoir sur une matrice d'apparence anodine.

6. Interpolation polynomiale

Forme de Lagrange (6.5), (6.8), théorème 6.2. Contrôle de recette gratuit: ${\sum }_i{\ell }_i(x)\equiv 1$ (6.7). Coût $\approx 4n^2$ par point d'évaluation, et tout est à refaire si un nœud s'ajoute.

Forme de Newton (6.12), théorème 6.3, avec la récurrence des différences divisées (6.11). Coût: $\frac{3}{2}{n}^2$ une fois pour le tableau, puis $3n$ par point par le schéma de Horner généralisé (6.15). Elle est incrémentale: un nœud de plus coûte une ligne du tableau. La différence divisée est une dérivée déguisée (théorème 6.4):

Le théorème du chapitre 6 (6.17), théorème 6.5, pour $f\in {\mathcal{C}}^{n+1}$. Trois facteurs de natures différentes: $f^{(n+1)}$ vient de la fonction et se subit; $1/(n+1)!$ est la seule force de rappel; $\omega (x)={\prod }_i(x-x_i)$ . Majoration (6.18): . Cas : accroissements finis. Cas confluent: Taylor–Lagrange.

Nœuds de Tchebychev (6.23), racines de $T_{n+1}$, et propriété minimax (6.25), théorème 6.6: c'est la plus petite valeur atteignable par un polynôme unitaire de degré $n+1$. D'où

(6.26) et (6.29) après le changement de variable affine (6.27). Sur des nœuds équidistants, $\max |\omega |/2^{-n}$ vaut $2,22$ à $n=5$, $8,74$ à $n=10$, $44,1$ à $n=15$ — et croît sans limite.

La matrice de Vandermonde prouve l'existence (théorème 6.1) et ne doit jamais servir à calculer: sur les nœuds équidistants de $[0,1]$, ${\kappa }_{\infty }$ vaut $1,25\cdot 10^4$ à $n=5$, $4,00\cdot 10^8$ à et à , où il ne reste plus un chiffre correct.

7. Splines et moindres carrés

Interpolation affine par morceaux (7.3), théorème 7.1: ordre 2, sans aucune condition sur les dérivées d'ordre élevé — c'est pourquoi elle ne connaît pas Runge. Son défaut est sa dérivée discontinue.

Le décompte (7.5), théorème 7.2, pour $n$ intervalles et des morceaux cubiques:

D'où les quatre familles: naturelle ($s^{\prime \prime }(a)=s^{\prime \prime }(b)=0$), encastrée ($s^{\prime }(a)=\alpha$, $s^{\prime }(b)=\beta$), , ( continue en et , donc ). Une spline cubique est et pas davantage: saute d'un morceau à l'autre.

Système des moments $M_i=s^{\prime \prime }(x_i)$ (7.13), tridiagonal et à diagonale strictement dominante d'un facteur 2, donc inversible sans pivotage (théorème 7.3) et résolu par Thomas en $8n-7$ opérations. Puis (7.17):

Erreur de la spline encastrée (7.18), théorème 7.4, admis: ordre 4, avec $\Vert f^{\prime }-s^{\prime }{\Vert }_{\infty }=O(h^3)$ et $\Vert f^{\prime \prime }-s^{\prime \prime }{\Vert }_{\infty }=O(h^2)$. La spline retombe à l' dès que ne s'annule pas aux bords: sur à , elle est fois moins précise que l'encastrée sur les mêmes nœuds. La condition retrouve l'ordre 4 sans rien demander à l'utilisateur.

Équations normales (7.21), théorème 7.5, condition nécessaire et suffisante: le résidu est orthogonal à l'image de $A$, et $A{\mathbf{c}}^{\ast }$ est la projection orthogonale de $\mathbf{y}$. Si $A$ est de rang plein en colonnes, $A^{\mathsf{T}}A$ est SDP et le minimiseur est unique. Pour la droite:

Test de recette, valable dès que la constante est dans la base: ${\sum }_i{r}_i=0$ et ${\sum }_i{x}_i{r}_i=0$. Décomposition et (7.24), qui la constante dans la base.

8. Dérivation et quadrature

Théorèmes 8.1 et 8.2, relations (8.4) à (8.7). La symétrie gagne un ordre: tous les termes pairs du développement s'annulent. La formule décentrée sert au bord d'un domaine, et sa constante est deux fois plus grande que celle de la centrée.

La courbe en V (8.9)–(8.10), théorème 8.3. Les deux termes sont égaux à l'optimum. Avec $M_0\approx M_2$: $h^{\ast }\approx \sqrt{{\epsilon }_{\text{mach}}}\approx 2\cdot 10^{-8}$ et une précision de , soit . Pour la différence centrée, et une précision de , soit deux tiers des chiffres. : à le résultat est zéro.

Le tableau de quadrature

Sur $[a,b]$, avec $m=(a+b)/2$. Les formules simples portent $H=b-a$, sauf Simpson dont l'erreur s'écrit avec la demi-longueur $h=H/2$.

Les nœuds et poids de Gauss sont donnés sur $[-1,1]$; sur $[a,b]$ on applique (8.29), qui multiplie les poids par $(b-a)/2$. Contrôle de recette: la somme des poids transportés vaut $b-a$, puisque la formule est exacte sur $f\equiv 1$. Sur $[0,1]$, Gauss à 3 nœuds a pour nœuds , , et pour poids , de somme 1.

Formules composites (8.17)–(8.20), théorèmes 8.7 et 8.8, avec $h=(b-a)/n$ et $n$ pair pour Simpson. On perd systématiquement un ordre en passant au composite, parce qu'on somme $(b-a)/h$ erreurs locales. Deux identités utiles: $M_n$ et $T_n$ ont des constantes d'erreur dans le rapport , d'où (8.23).

Extrapolation de Richardson (8.24), théorème 8.9, et tableau de Romberg (8.26) avec $R_{k,0}=T_{2^k}$. L'extrapolation est gratuite en évaluations de $f$. Appliquée au trapèze, elle est Simpson: $R_{k,1}=S_{2^k}$. Comme le développement d'Euler–Maclaurin (8.25) ne contient que des puissances de , chaque colonne gagne deux ordres: la colonne est d'ordre . Le tableau n'est pas monotone, et l'on cesse d'extrapoler quand la diagonale cesse de se resserrer.

Quadrature de Gauss (théorème 8.10): degré d'exactitude $2n-1$, et c'est le maximum possible — aucune formule à $n$ nœuds n'est exacte sur ${\prod }_i(t-z_i{)}^2$, de degré $2n$. Tous les poids sont strictement positifs, donc et la formule n'amplifie aucun arrondi. Legendre: , , , , .

9. Équations différentielles: méthodes à un pas

Problème de Cauchy (9.1) et condition de Lipschitz (9.2): existence, unicité sur $[a,b]$ tout entier, et dépendance continue $|y(t)-\tilde{y}(t)|\le {\mathrm{e}}^{L(t-a)}|y_0-{\tilde{y}}_0|$ (théorème 9.1, admis). : , a une infinité de solutions et une méthode numérique en choisira une sans le dire.

L'identité (9.8) engendre tout le chapitre: chaque formule de quadrature du chapitre 8 donne une méthode. Rectangle à gauche $\to$ Euler explicite; à droite $\to$ Euler implicite; trapèze $\to$ Crank–Nicolson; point milieu $\to$ RK2; Simpson $\to$ RK4. Et l'on n'écrit jamais $y_n=y(t_n)$: est calculé, est exact, .

Tableaux de Butcher

Consistance: ${\sum }_i{b}_i=1$, et l'on impose $c_i={\sum }_j{a}_{ij}$. strictement triangulaire inférieure méthode .

Les poids $\frac{1}{6},\frac{1}{3},\frac{1}{3},\frac{1}{6}$ sont , le point milieu comptant deux fois parce qu'il est évalué deux fois. Toute méthode à deux étages est d'ordre 2 si et seulement si et (9.14): c'est une famille à un paramètre.

L'ordre cesse d'égaler le nombre d'étages après 4: il faut 6 étages pour l'ordre 5, 7 pour l'ordre 6, 11 pour l'ordre 8. C'est pourquoi RK4 est resté la méthode par défaut. Un pas implicite coûte trois à dix fois un pas explicite, et le prédicteur $z^{(0)}=y_n+hf(t_n,y_n)$ le place à de la réponse, si bien que deux itérations de Newton suffisent.

Erreur locale de troncature (9.16) — divisée par $h$, convention universelle mais pas unanime, à vérifier dans chaque texte — et l'équation centrale du chapitre: l'erreur nouvelle est l'ancienne transportée, plus la fraîche.

Consistance d'ordre $p$ + stabilité $\Rightarrow$ convergence d'ordre $p$ (9.21), théorème 9.3, via le lemme de Grönwall discret (9.18). La stabilité (9.20) est ici la lipschitzianité de $\Phi$, acquise pour toute méthode de Runge–Kutta explicite à second membre lipschitzien: c'est le chapitre 10 qui remettra ce mot en cause. Pour Euler, ${\tau }_n=\frac{h}{2}{y}^{\prime \prime }({\xi }_n)$ et

(9.22), théorème 9.4. La borne donne l'ordre de façon irréprochable et la taille de façon très grossière — facteur 2 à 3 de marge sur le problème témoin.

Paires emboîtées (9.24)–(9.25): deux méthodes d'ordres $p$ et $p+1$ partageant leurs étages, donc une estimation d'erreur gratuite, et $\sigma \approx 0,9$ avec le facteur bridé entre $0,2$ et $5$. Heun–Euler donne $\mathrm{est}=\frac{h}{2}|k_2-k_1|$. Paires usuelles: RKF45 (6 étages), DOPRI5 (7 étages, , moteur de ), Bogacki–Shampine 3(2).

Un système ou une équation d'ordre $m$ ne change aucune formule: on pose $\mathbf{u}=(y,y^{\prime },\dots ,y^{(m-1)})$ et l'on remplace les valeurs absolues par une norme.

10. Stabilité absolue, multipas, barrières

Équation-test (10.1) et facteur d'amplification (10.4). La réduction est légitime parce que la diagonalisation $A=VD{V}^{-1}$ découple un système linéaire en autant de copies de (10.1) qu'il y a de valeurs propres, et qu'une méthode linéaire survit au même changement de variable. Pour un problème non linéaire, on gèle la jacobienne: c'est une heuristique, et elle prédit juste. Une méthode est d'ordre $p$ si et seulement si $R(z)={\mathrm{e}}^z+O(z^{p+1})$.

Théorèmes 10.1 et 10.2. Pour $\lambda$ réel négatif, Euler explicite exige $h\le 2/|\lambda |$ (10.9), et il y a deux seuils: $h<1/|\lambda |$ donne une suite décroissante de signe constant, $1/|\lambda |<h<2/|\lambda |$ une suite décroissante qui alterne, $h>2/|\lambda |$ une explosion. La région de RK4 coupe l'axe imaginaire en . : quand c'est la stabilité qui fixe le pas, monter en ordre ne sert à rien.

(10.11)–(10.12). Euler implicite est L-stable; le trapèze est A-stable et pas L-stable, car $R(z)\to -1$: les modes rapides sont renvoyés presque intacts avec le signe changé au lieu d'être écrasés. Sur le système raide du chapitre 10 à $h=0,2$, cela lui fait produire $-0,300$ là où la réponse est $+0,00337$. La L-stabilité, qui a l'air d'un raffinement technique, est le critère opérationnel. A($\alpha$)-stabilité: $\mathcal{A}$ contient le secteur $|\arg (-z)|\le \alpha$.

Rapport de raideur (10.15). Un problème est raide lorsque la stabilité impose un pas beaucoup plus petit que la précision ne le demanderait — définition relative à la méthode et à l'objectif, et il faut l'assumer comme telle. Le symptôme n'est pas un petit pas mais l'écart entre les deux exigences: un oscillateur peu amorti a $S=1$ et demande pourtant un petit pas, parce que c'est la fréquence qui commande. Et ce n'est pas la présence de la composante rapide qui impose le pas, c'est la stabilité du schéma vis-à-vis d'elle: une fois ${\mathrm{e}}^{-1001t}$ tombé à $10^{-9}$, un schéma explicite à $h$ trop grand le réanime à partir du bruit d'arrondi.

Méthode multipas linéaire (10.20)–(10.21), normalisée par ${\alpha }_k=1$, explicite si ${\beta }_k=0$, et demandant $k$ valeurs de départ d'ordre au moins égal.

Adams–Bashforth (10.22), explicites, une seule évaluation par pas, d'ordre $k$; Adams–Moulton (10.23), implicites, un ordre de plus à nombre de pas égal et une erreur bien plus petite ($-\frac{1}{24}{h}^4{y}^{(4)}$ pour AM3 contre $\frac{3}{8}{h}^4{y}^{(4)}$ pour AB3). L'appariement (10.24) coûte deux évaluations et donne l'estimateur gratuitement — mais , donc bornée: un prédicteur–correcteur n'est pas un schéma pour problème raide.

BDF (10.25)–(10.26): on interpole les $y$ et l'on impose la dérivée en $t_{n+1}$. Une seule évaluation de $f$, au seul point $t_{n+1}$.

Dans la famille explicite d'Adams, monter en ordre rétrécit la région. C'est pourquoi un code à ordre variable baisse son ordre quand il détecte de la raideur.

Condition des racines (10.29), théorème 10.3: elle est nécessaire à la convergence, quel que soit l'ordre. La racine $\zeta =1$ est la racine principale, imposée par la consistance $\rho (1)=0$; les $k-1$ autres sont parasites. Contre-exemple canonique: $y_{n+2}+4y_{n+1}-5y_n=h(4f_{n+1}+2f_n)$ est consistante d'ordre et a la racine ; . Consistance d'ordre (10.28): pour .

Vocabulaire des bibliothèques. RK45 (Dormand–Prince 4(5), région bornée) pour le non raide; DOP853 pour le non raide à haute précision; BDF (ordres 1 à 5, A($\alpha$)) pour les problèmes raides; Radau (L-stable) pour les raides et oscillants; LSODA bascule Adams $\leftrightarrow$ BDF. Un solveur explicite sur un problème raide ne plante pas: il rame, en réduisant son pas jusqu'à respecter la stabilité. Et rtol/atol contrôlent la précision, jamais la stabilité.

Les données témoins du cours, rassemblées

Tous les nombres ci-dessous sont exacts ou vérifiés en double précision; ils reviennent d'un chapitre à l'autre et aucun chapitre ne les contredit.

Nombre plastique. $f(1)=-1$, $f(2)=5$, $f^{\prime }(x^{\ast })=4,264633$, $f^{\prime \prime }(x^{\ast })=7,948308$, constante de Newton . Newton depuis : résidus , , , , — . Points fixes: converge avec , diverge avec , et le produit des deux vaut (fonctions réciproques).

$LU$ sans pivotage, exacte: ${\ell }_{21}=-3/2$, ${\ell }_{31}=-1$, ${\ell }_{32}=4$; de lignes , , ; ; . Spectre: , , , de rapport . () et ( exactement).

Exactement 748. Aux ordres supérieurs: $28375$, $943656$, $2,907\cdot 10^7$, $3,387\cdot 10^{10}$, $3,536\cdot 10^{13}$ pour — .

Rapports du trapèze: $4,02$; $4,01$; $4,00$. De Simpson: $11,40$; $15,72$; $15,95$ — le 16 n'est atteint qu'asymptotiquement, quand $f^{(4)}({\xi }_n)$ s'est stabilisée.

La ligne $n=5$ est celle qu'il ne faut pas cacher: Tchebychev y est moins bon, parce qu'il dégarnit le centre, où se trouve toute la structure de $f$.

$y(2)=5,305471950534675\dots$, $L=1$, $M=|2-\frac{1}{2}{\mathrm{e}}^2|=1,694528$.

Les rapports sont 1,90; 1,95; 1,97 — et non 2.

À $h=0,2$, la suite est exactement $(-2{)}^n$ pendant que la solution exacte est divisée par ${\mathrm{e}}^3=20,09$ à chaque pas. À $h=0,1$ elle vaut $(-0,5{)}^n$: stable, et pourtant alternée alors que la solution exacte ne change jamais de signe — il faudrait pour être fidèle. Euler implicite est stable pour , et grossièrement imprécis à : contre .

Références

• Quarteroni, A., Sacco, R. et Saleri, F., Méthodes numériques — algorithmes, analyse et applications, Springer, Milan (la référence de ce cours; les chapitres 2 à 11 couvrent l'ensemble du formulaire).
• Rappaz, J. et Picasso, M., Introduction à l'analyse numérique, Presses polytechniques et universitaires romandes, Lausanne.
• Burden, R. L. et Faires, J. D., Numerical Analysis, Cengage, Boston (tables de formules et de tableaux de Butcher en annexe).
• Trefethen, L. N. et Bau, D., Numerical Linear Algebra, SIAM, Philadelphie (chapitres 3 à 5 du cours).
• Hairer, E., Nørsett, S. P. et Wanner, G., Solving Ordinary Differential Equations I et II, Springer, Berlin (chapitres 9 et 10, régions de stabilité et barrières de Dahlquist).
• Higham, N. J., Accuracy and Stability of Numerical Algorithms, 2e éd., SIAM, Philadelphie (modèle d'arrondi, conditionnement, stabilité inverse).