Méthode de bissection

Objectifs d'apprentissage

À la fin de cette leçon, vous serez en mesure de :

• Comprendre le principe de l'alternance de signe
• Implémenter l'algorithme de bissection
• Estimer le nombre d'itérations nécessaires pour atteindre une précision donnée
• Identifier les conditions d'application de la méthode

Principe fondamental : l'alternance de signe

La méthode de bissection (aussi appelée interval-halving method ou méthode de dichotomie) repose sur un principe géométrique simple : si une fonction continue change de signe entre deux points, alors elle s'annule quelque part entre ces deux points.

Idée de la méthode

L'algorithme exploite ce théorème de manière itérative :

1. On part d'un intervalle $[X_1, X_2]$ contenant une racine
2. On coupe l'intervalle en deux au point milieu $X_3$
3. On détermine dans quelle moitié se trouve la racine (par le test de signe)
4. On recommence avec le nouvel intervalle, deux fois plus petit

À chaque itération, l'intervalle de recherche est divisé par 2, d'où le nom de « bissection ».

Condition suffisante de convergence

Cas de figure selon le comportement de F

Examinons différentes configurations possibles pour une fonction F continue sur [X₁, X₂] avec F(X₁) · F(X₂) < 0 :

Algorithme de la méthode de bissection

Pseudo-code

Algorithme : Méthode de bissection
Entrées : F (fonction), X1, X2 (bornes), δ (tolérance sur x), ε (tolérance sur F)
Sortie : X (approximation de la racine)

Précondition : F(X1) · F(X2) ≤ 0

Calculer X3 = (X1 + X2) / 2

Tant que (|X1 - X2| ≥ δ) ET (|F(X3)| ≥ ε) faire
  Calculer X3 = (X1 + X2) / 2

  Si F(X1) · F(X3) ≤ 0 alors
      X2 ← X3    // La racine est dans [X1, X3]
  Sinon
      X1 ← X3    // La racine est dans [X3, X2]
  Fin Si
Fin Tant que

Retourner X = X3

Implémentation en Python

def bissection(f, x1, x2, tol_x=1e-6, tol_f=1e-10, max_iter=100):
  """
  Méthode de bissection pour trouver une racine de f sur [x1, x2].

  Paramètres:
      f : fonction dont on cherche la racine
      x1, x2 : bornes de l'intervalle initial
      tol_x : tolérance sur x (critère d'arrêt)
      tol_f : tolérance sur f(x) (critère d'arrêt)
      max_iter : nombre maximum d'itérations

  Retourne:
      x3 : approximation de la racine
      iterations : liste des itérés successifs
  """
  # Vérification de la condition initiale
  if f(x1) * f(x2) > 0:
      raise ValueError("f(x1) et f(x2) doivent être de signes opposés")

  iterations = []

  for n in range(max_iter):
      x3 = (x1 + x2) / 2
      fx3 = f(x3)
      iterations.append({'n': n+1, 'x3': x3, 'f(x3)': fx3, 'erreur': abs(x2 - x1)})

      # Critères d'arrêt
      if abs(x2 - x1) < tol_x or abs(fx3) < tol_f:
          return x3, iterations

      # Choix du sous-intervalle
      if f(x1) * fx3 <= 0:
          x2 = x3
      else:
          x1 = x3

  return x3, iterations

Définitions importantes

Itération

Itéré d'ordre n

Analyse de l'erreur

Intervalle de confiance

Au départ, la racine $r$ se trouve dans l'intervalle $[X_1, X_2]$. L'erreur maximale sur notre approximation est donc :

Après chaque itération, l'intervalle est divisé par 2, donc l'erreur est également divisée par 2.

Formule de l'erreur à l'itération n

Nombre d'itérations nécessaires

Si on souhaite obtenir une précision $\delta$ sur la racine, on peut calculer le nombre d'itérations nécessaires :

Exemple de calcul

Pour un intervalle initial $[1, 2]$ et une précision souhaitée $\delta = 0.0005$ :

Il faudra donc au moins 11 itérations.

Exemple détaillé

Considérons la fonction :

Cette fonction peut s'écrire sous forme factorisée :

Elle possède donc trois racines exactes : $r_1 = -1$, $r_2 = -\sqrt{3} \approx -1.732$ et $r_3 = \sqrt{3} \approx 1.732$.

Paramètres de l'algorithme

• Intervalle initial : $[X_1, X_2] = [1, 2]$
• Tolérance sur $x$ : $\delta = 0.0005$
• Tolérance sur $F(x)$ : $\varepsilon = 0.00001$

Tableau des itérations

Résultat : La tolérance en $X$ est atteinte en 11 itérations.

L'approximation obtenue est $X \approx 1.732$, très proche de la valeur exacte $\sqrt{3} \approx 1.7320508...$

Visualisation interactive

Le graphique suivant vous permet de visualiser la méthode de bissection en action. Vous pouvez observer comment l'intervalle se réduit à chaque itération.

Avantages et inconvénients

Avantages

• Simplicité : algorithme facile à comprendre et à implémenter
• Robustesse : converge toujours si les conditions sont satisfaites
• Hypothèse faible : ne nécessite que la continuité de $F$
• Convergence garantie : on peut prédire exactement le nombre d'itérations nécessaires

Inconvénients

• Convergence lente : convergence linéaire (l'erreur est divisée par 2 à chaque itération)
• Nécessite un intervalle initial : il faut connaître $X_1$ et $X_2$ tels que $F(X_1) \cdot F(X_2) < 0$
• Une seule racine : ne trouve qu'une racine même si l'intervalle en contient plusieurs
• Pas d'extension directe : difficile à généraliser aux systèmes d'équations

Résumé

Dans cette leçon, nous avons étudié la méthode de bissection :

1. Principe : diviser successivement l'intervalle de recherche par 2 en utilisant le changement de signe

2. Condition suffisante : $F$ continue sur $[X_1, X_2]$ avec $F(X_1) \cdot F(X_2) < 0$

3. Algorithme : calculer le point milieu, tester le signe, choisir le bon sous-intervalle

4. Erreur : $\Delta X^{(n)} = \frac{|X_1 - X_2|}{2^n}$ — convergence linéaire

5. Estimation : $n = \lceil \log_2(|X_1 - X_2|/\delta) \rceil$ itérations pour une précision $\delta$