Analyse numérique

Fiches de cours et sous-notions liées à ce chapitre.

Pas assez de questions pour un entraînement ciblé sur cette notion.

Interpolation

Non commencé

Définitions

L'interpolation construit une fonction simple passant par des points de données $(x_i, y_i)$ . Lagrange : $P(x) = \sum y_i L_i(x)$ avec $L_i(x) = \prod_{j \neq i} \frac{x-x_j}{x_i-x_j}$ ; degré $\leq n-1$ pour $n$ points, unique.

Newton : forme avec différences divisées, ajout facile de points. Splines cubiques : polynômes de degré 3 par morceaux, $C^2$ aux nœuds. Phénomène de Runge : interpolation polynomiale équidistante diverge aux bords pour $f(x) = 1/(1+25x^2)$ . Chebyshev : nœuds $x_k = \cos\frac{(2k+1)\pi}{2n}$ atténuent Runge.

Interpolation : Lagrange (unique degré $\leq n-1$ ), Newton (différences divisées), splines cubiques $C^2$ .

Runge : oscillations aux bords en nœuds équidistants ; nœuds de Chebyshev recommandés.

Formules

$P(x) = \sum_{i=0}^{n-1} y_i \prod_{j \neq i} \frac{x-x_j}{x_i-x_j}$
$\text{Erreur Lagrange : } f(x) - P(x) = \frac{f^{(n)}(\xi)}{n!}\prod(x-x_i)$
$\text{Spline cubique : } S'' \text{ continue aux nœuds}$
$\text{Runge : erreur } \sim 2^n/n \text{ aux bords (équidistant, Runge)}$

Exemples

Exemple 1

Erreur de Lagrange.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) $f(x)-P(x)=\frac{f^{(n)}(\xi)}{n!}\prod(x-x_i)$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Formule d'erreur classique.

Exemple 2

Pourquoi les splines ?

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Degré local $3$ , $C^2$ , erreur $O(h^4)$ : évite Runge global. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Spline cubique : stable et $O(h^4)$ .

À retenir

Méthodes itératives

Non commencé

Définitions

Méthodes itératives résolvent $Ax = b$ sans factorisation directe : Jacobi ( $x_i^{k+1} = (b_i - \sum_{j \neq i} a_{ij}x_j^k)/a_{ii}$ ), Gauss-Seidel (utilise composantes déjà mises à jour), SOR (relaxation). Convergence si $\rho(M) < 1$ ( $M$ matrice d'itération).

Newton-Raphson pour $f(x)=0$ : $x_{n+1} = x_n - f(x_n)/f'(x_n)$ , convergence quadratique près racine simple. GMRES, CG pour grandes matrices creuses. Critère d'arrêt : $\|r_k\|/\|b\| < \varepsilon$ .

Itératif linéaire : Jacobi, Gauss-Seidel, SOR ; CV si $\rho(M)<1$ . Newton : $x-f/f'$ , quadratique si $f'(x^*)\neq 0$ .

Pourquoi c’est central : cette notion structure les preuves et calculs du programme ; maîtriser définitions et hypothèses évite les applications hors cadre.

Formules

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \quad \text{(Newton)}$
$\text{Convergence Newton : quadratique si } f'(x^*) \neq 0$
$\text{Jacobi : } x^{k+1} = D^{-1}(b - (L+U)x^k)$
$\text{CG : pour } A \text{ sdp, convergence en } \leq n \text{ itérations exact}$

Exemples

Exemple 1

Newton pour $\sqrt 2$ : $f(x)=x^2-2$ , $x_0=1$ .

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) $x_{n+1}=(x_n+2/x_n)/2$ : $x_1=1{,}5$ , $x_2=1{,}416\ldots$ (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Convergence quadratique vers $\sqrt 2$ .

Exemple 2

Critère d'arrêt résidu.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Arrêter si $\|r_k\|/\|b\|<\varepsilon$ (ex. $10^{-8}$ ). (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Résidu relatif $<\varepsilon$ .

À retenir

Stabilité numérique

Non commencé

Définitions

Stabilité numérique : sensibilité du résultat aux perturbations (données, arrondi). Problème bien conditionné : petites perturbations $\Rightarrow$ petites erreurs. Nombre de condition $\kappa(A) = \|A\|\|A^{-1}\|$ : $\frac{\|\delta x\|}{\|x\|} \lesssim \kappa(A) \frac{\|\delta b\|}{\|b\|}$ .

$\kappa$ grand $\Rightarrow$ ill-conditionné. Stabilité backward : algorithme calcule solution exacte pour données légèrement perturbées. Annulation catastrophique : soustraction de nombres proches. Analyse d'erreur en arithmétique flottante ( $\varepsilon_{\mathrm{mach}} \approx 10^{-16}$ en double).

Conditionnement $\kappa(A)=\|A\|\|A^{-1}\|$ : amplifie les erreurs relatives. Hilbert mal conditionnée. Annulation catastrophique.

$\varepsilon_{\mathrm{mach}}\approx 10^{-16}$ (double).

Formules

$\kappa(A) = \|A\| \|A^{-1}\| \geq 1$
$\frac{\|\delta x\|}{\|x\|} \leq \kappa(A) \left(\frac{\|\delta A\|}{\|A\|} + \frac{\|\delta b\|}{\|b\|}\right)$
$\kappa_2(A) = \frac{\sigma_{\max}}{\sigma_{\min}}$
$\text{Erreur relative } \sim \kappa \cdot \varepsilon_{\mathrm{mach}} \cdot n$

Exemples

Exemple 1

Interprétation de $\kappa\sim 10^8$ .

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Perte d'environ $8$ chiffres significatifs en résolution. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Perte $\sim\log_{10}\kappa$ chiffres.

Exemple 2

Réécrire $1-\cos x$ pour $x$ petit.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) $1-\cos x = 2\sin^2(x/2)\approx x^2/2$ : évite l'annulation. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

$1-\cos x\approx x^2/2$ .