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 contenant une racine
2. On coupe l'intervalle en deux au point milieu
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 se trouve dans l'intervalle . 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 sur la racine, on peut calculer le nombre d'itérations nécessaires :

Exemple de calcul

Pour un intervalle initial et une précision souhaitée :

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 : , et .

Paramètres de l'algorithme

• Intervalle initial :
• Tolérance sur :
• Tolérance sur :

Tableau des itérations

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

L'approximation obtenue est , très proche de la valeur exacte

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
• 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 et tels que
• 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 : continue sur avec

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

4. Erreur : — convergence linéaire

5. Estimation : itérations pour une précision