Algorithmique et programmation (Python)

Dichotomie, Euler, Newton, rectangles/trapèzes, Monte-Carlo, simulation.

Algorithmes de résolution numérique

Dichotomie (zéro d'une fonction): Principe : on encadre le zéro sur [a, b] où f change de signe, puis on teste le milieu m = (a+b)/2. Si f(a)·f(m) < 0 le zéro est dans [a, m], sinon dans [m, b]. On répète jusqu'à la précision souhaitée. Convergence lente mais garantie.
Méthode de Newton (convergence rapide): x_{n+1} = xₙ − f(xₙ)/f'(xₙ). Géométriquement : la tangente en xₙ coupe l'axe des x en x_{n+1}. Convergence très rapide (quadratique) si on part assez près d'un zéro, mais peut diverger si le point de départ est mal choisi.

Méthode d'Euler (équation différentielle): Pour y' = f(t, y) avec y(t₀) = y₀ : on pose y(t+h) ≈ y(t) + h·f(t, y(t)). On avance de pas h pour construire la solution approchée. Plus h est petit, plus l'approximation est précise. Algorithme : boucle for en Python.
Méthode des rectangles (intégrale): ∫[a→b] f(x) dx ≈ h × Σ f(xᵢ) avec h = (b−a)/n et xᵢ = a + ih. On approche l'intégrale par la somme d'aires de rectangles. La méthode des trapèzes est plus précise : h × [f(a)/2 + Σ f(xᵢ) + f(b)/2].
Monte-Carlo (estimation par simulation): On tire aléatoirement N points dans un carré contenant la zone à estimer. L'aire estimée = (proportion de points dans la zone) × (aire du carré). Exemple : estimer π en tirant des points dans [0,1]² et comptant ceux dans le quart de disque de rayon 1.

Simulation d'une variable aléatoire discrète: Méthode de la fonction de répartition inverse : on tire u ~ U([0,1]) via random.random(), puis on cherche le plus petit k tel que F(k) ≥ u, où F est la fonction de répartition. En Python : import random; u = random.random(). Pour simuler X ~ B(n, p) : sum(1 for _ in range(n) if random.random() < p). Pour X ~ U({1,…,n}) : random.randint(1, n).
Simulation d'un échantillon de taille n: Répéter n fois la simulation d'une variable aléatoire pour obtenir un échantillon de taille n. En Python : echantillon = [simulation() for _ in range(n)]. Calcul de la moyenne empirique : sum(echantillon)/n. Comparaison avec l'espérance théorique illustre la loi des grands nombres.
Algorithme de Briggs (racines carrées successives): Permet d'approcher log₁₀(x) par encadrements successifs. Principe : on répète des racines carrées pour réduire x vers 1 en maintenant un compteur. Plus précisément : en posant b = √x, puis b = √b… et en comptant les étapes, on construit une approximation de log₁₀(x). En Python : while x > 1 + epsilon: x = x**0.5; compteur += 1.

: La méthode d'Euler accumule des erreurs à chaque pas — ne pas confondre la solution approchée (en escalier) avec la solution exacte (courbe lisse). Plus h est petit, meilleure est l'approximation.
: Pour simuler une loi binomiale B(n, p) en Python, la méthode directe (n tirages de Bernoulli) est plus lisible qu'une formule fermée. Toujours fixer une graine (random.seed()) pour la reproductibilité en TP.

Flashcards, mode examen et suivi de progression — gratuit pour commencer.