Principes généraux des algorithmes itératifs

Introduction

Dans de nombreuses situations en informatique et en mathématiques appliquées, il est impossible — ou trop coûteux — de calculer directement la valeur exacte d'une quantité recherchée. On a alors recours à des méthodes itératives : des algorithmes qui construisent progressivement une approximation de la solution, en l'améliorant à chaque étape.

Cette leçon présente l'architecture générale de ces algorithmes, les concepts fondamentaux qui les sous-tendent, ainsi que les conditions nécessaires à leur bon fonctionnement.

Problème général

Soit $z$ une quantité inconnue que l'on souhaite déterminer. Dans bien des cas, le calcul direct de $z$ est soit impossible (solution d'une équation non linéaire), soit trop coûteux (système de grande dimension).

On cherche alors à construire une approximation $\hat{z}$ de $z$, suffisamment proche de la vraie valeur pour être utile en pratique.

L'idée fondamentale est la suivante : plutôt que de chercher $z$ en une seule étape, on construit une suite d'approximations successives $z^{(0)}, z^{(1)}, z^{(2)}, \ldots$ qui se rapprochent progressivement de la solution.

Architecture générale d'un algorithme itératif

Tout algorithme itératif suit une structure canonique composée de trois phases distinctes.

Initialisation

L'algorithme commence par définir un point de départ :

• On initialise le compteur d'itérations : $k = 0$
• On choisit une solution initiale $z^{(0)}$

Boucle itérative

Le cœur de l'algorithme est une boucle forte qui répète les opérations suivantes :

Pour $k = 0, 1, 2, \ldots$, on calcule la nouvelle approximation selon la règle :

où $f$ est la fonction d'itération qui transforme l'estimation courante en une estimation améliorée.

Condition d'arrêt

L'algorithme s'arrête lorsqu'un des critères suivants est satisfait :

• Le nombre maximal d'itérations est atteint
• Un critère de convergence est vérifié

Pseudo-code

def algorithme_iteratif(z_initial, f, epsilon, max_iter):
  """
  Algorithme itératif générique.

  Paramètres :
      z_initial : estimation initiale
      f         : fonction d'itération
      epsilon   : seuil de convergence
      max_iter  : nombre maximal d'itérations

  Retourne :
      z_hat : approximation finale
      k     : nombre d'itérations effectuées
  """
  z_courant = z_initial
  k = 0

  while k < max_iter:
      z_nouveau = f(z_courant)

      # Vérification du critère de convergence
      if abs(z_nouveau - z_courant) < epsilon:
          return z_nouveau, k + 1

      z_courant = z_nouveau
      k += 1

  return z_courant, k

Schéma conceptuel

Le flux d'exécution peut être représenté ainsi :

La fonction d'itération

La fonction $f$ est le cœur de tout algorithme itératif. On l'appelle aussi opérateur d'itération ou application itérative.

Rôle de la fonction d'itération

La fonction $f$ a pour objectif de transformer une estimation $z^{(k)}$ en une estimation $z^{(k+1)}$ plus proche de la solution exacte $z$.

La qualité de l'algorithme dépend entièrement du choix de cette fonction : une bonne fonction d'itération garantit une convergence rapide vers la solution.

Exemples de fonctions d'itération

Exemple concret : la méthode de Babylone

Pour calculer la racine carrée de $a$, on utilise la fonction d'itération :

def racine_babylone(a, epsilon=1e-10, max_iter=100):
  """
  Calcul de la racine carrée par la méthode de Babylone.
  """
  z = a / 2  # Estimation initiale

  for k in range(max_iter):
      z_nouveau = 0.5 * (z + a / z)

      if abs(z_nouveau - z) < epsilon:
          return z_nouveau

      z = z_nouveau

  return z

# Exemple : racine de 2
print(racine_babylone(2))  # Affiche : 1.4142135623730951

Solution initiale

Le choix de la solution initiale $z^{(0)}$ est une étape cruciale qui influence directement le comportement de l'algorithme.

Importance du choix initial

Une solution initiale bien choisie peut :

• Accélérer considérablement la convergence
• Garantir que l'algorithme converge vers la bonne solution
• Réduire le coût de calcul global

Conséquences d'une mauvaise initialisation

Stratégies de choix

En pratique, on peut utiliser différentes approches :

• Utiliser une estimation grossière basée sur le contexte du problème
• Appliquer une méthode rapide mais peu précise pour obtenir un point de départ
• Exploiter les propriétés mathématiques du problème (symétrie, bornes connues)

Structures de données utilisées

Les méthodes itératives manipulent des structures de données simples mais fondamentales.

Types de données

Opérations élémentaires

Les algorithmes itératifs reposent sur des opérations arithmétiques de base :

• Addition et soustraction : mise à jour des estimations
• Multiplication et division : calcul de facteurs de correction
• Produit matriciel : transformation linéaire des vecteurs

import numpy as np

# Scalaire
x = 3.14

# Vecteur
v = np.array([1.0, 2.0, 3.0])

# Matrice
A = np.array([[1, 2], [3, 4]])

# Opérations courantes
w = A @ v[:2]          # Produit matrice-vecteur
norme = np.linalg.norm(v)  # Norme euclidienne
v_normalise = v / norme    # Normalisation

Erreur numérique d'estimation

À chaque itération, l'approximation $z^{(k)}$ diffère de la vraie solution $z$. Cette différence constitue l'erreur d'estimation.

Définition formelle

L'erreur à l'itération $k$ est définie par :

Types d'erreur

Erreur réelle et erreur observable

Un problème pratique se pose : on ne connaît généralement pas la vraie valeur $z$, donc on ne peut pas calculer l'erreur réelle $\Delta z^{(k)}$.

On utilise alors une erreur observable, basée sur la différence entre deux itérations successives :

Bornes sur l'erreur

Dans l'analyse des algorithmes itératifs, on cherche souvent à établir des bornes sur l'erreur d'estimation.

Principe général

L'erreur peut être majorée par une fonction du nombre d'itérations :

où $g(k)$ est une fonction décroissante de $k$.

Exemples de décroissance

Compromis fondamental

Il existe un lien direct entre :

• Le nombre d'itérations $k$
• La précision atteinte $|\Delta z^{(k)}|$
• Le coût de calcul (temps, mémoire)

Plus on effectue d'itérations, plus l'approximation est précise, mais plus le calcul est coûteux. Le choix du critère d'arrêt reflète ce compromis.

Conditions d'arrêt

Un algorithme itératif doit disposer de critères clairs pour déterminer quand s'arrêter.

Stratégies courantes

Nombre maximal d'itérations

On fixe une limite $k_{\max}$ sur le nombre d'itérations :

Seuil sur l'erreur observable

On vérifie si la variation entre deux itérations est suffisamment petite :

Seuil sur l'erreur relative

Pour éviter les problèmes d'échelle :

Comparaison des approches

def critere_arret(z_nouveau, z_courant, k, epsilon, max_iter):
  """
  Vérifie si l'algorithme doit s'arrêter.

  Retourne True si l'un des critères est satisfait.
  """
  # Critère 1 : nombre maximal d'itérations
  if k >= max_iter:
      return True

  # Critère 2 : convergence absolue
  if abs(z_nouveau - z_courant) < epsilon:
      return True

  # Critère 3 : convergence relative
  if abs(z_courant) > epsilon:
      if abs(z_nouveau - z_courant) / abs(z_courant) < epsilon:
          return True

  return False

Convergence

La notion de convergence est centrale dans l'analyse des algorithmes itératifs.

Définition

On dit que la suite $(z^{(k)})_{k \geq 0}$ converge vers $z$ si :

En termes pratiques, cela signifie que l'erreur $|z^{(k)} - z|$ devient arbitrairement petite lorsque $k$ augmente.

Convergence locale et globale

Point fixe

La solution $z$ est souvent un point fixe de la fonction d'itération, c'est-à-dire :

Intuitivement, lorsque la suite atteint la solution, elle y reste car l'application de $f$ ne la modifie plus.

Condition de stabilité

Pour qu'un point fixe soit stable (attractif), une condition suffisante est que la dérivée de $f$ au voisinage de $z$ soit inférieure à 1 en valeur absolue :

Conditions d'application et limites

Les algorithmes itératifs ne fonctionnent pas dans toutes les situations. Il est important de connaître leurs hypothèses et leurs limites.

Hypothèses nécessaires

Pour garantir le bon fonctionnement d'un algorithme itératif, on suppose généralement :

• La fonction d'itération $f$ est bien définie et calculable
• Il existe un point fixe $z$ tel que $f(z) = z$
• Le point fixe est stable (attractif)
• La solution initiale est dans le bassin d'attraction

Cas problématiques

Notions de robustesse

Stabilité : l'algorithme reste borné et ne diverge pas vers l'infini.

Sensibilité : mesure de l'impact des petites perturbations (erreurs d'arrondi, données bruitées) sur le résultat.

Conditionnement : propriété intrinsèque du problème qui indique sa difficulté numérique. Un problème mal conditionné amplifie les erreurs, même avec un bon algorithme.

Paradoxes de l'arithmétique flottante

L'arithmétique des ordinateurs réserve des surprises qui peuvent sembler paradoxales. Ces phénomènes ne sont pas des bugs, mais des conséquences directes de la représentation finie des nombres réels en mémoire.

L'addition n'est pas associative

En mathématiques, $(a + b) + c = a + (b + c)$ toujours. En arithmétique flottante, ce n'est plus garanti.

a = 1e20
b = -1e20
c = 1.0

# Ordre 1 : (a + b) + c
resultat_1 = (a + b) + c
print(f"(a + b) + c = {resultat_1}")  # Affiche : 1.0

# Ordre 2 : a + (b + c)
resultat_2 = a + (b + c)
print(f"a + (b + c) = {resultat_2}")  # Affiche : 0.0

Explication : Dans le premier cas, $a + b = 0$ exactement, puis $0 + 1 = 1$. Dans le second cas, $b + c \approx b$ car $c$ est absorbé par la magnitude de $b$, puis $a + b = 0$.

Le phénomène d'absorption

Quand on additionne un très grand nombre et un très petit nombre, le petit peut être « absorbé » :

alors que mathématiquement le résultat devrait être 1.

L'annulation catastrophique

C'est le phénomène le plus insidieux. Quand on soustrait deux nombres presque égaux, on perd des chiffres significatifs.

import numpy as np

def f_naive(x):
  """Calcul naïf de (1 - cos(x)) / x² pour x petit."""
  return (1 - np.cos(x)) / x**2

def f_stable(x):
  """Version stable utilisant l'identité 1 - cos(x) = 2 sin²(x/2)."""
  return 2 * (np.sin(x/2) / x)**2

# Valeur théorique pour x → 0 : limite = 1/2
x = 1e-8

print(f"Méthode naïve  : {f_naive(x)}")   # Résultat erroné !
print(f"Méthode stable : {f_stable(x)}")  # ≈ 0.5
print(f"Valeur exacte  : 0.5")

Explication : Pour $x = 10^{-8}$, on a $\cos(x) \approx 0.99999999999999995...$ en double précision. La soustraction $1 - \cos(x)$ annule presque tous les chiffres significatifs, ne laissant que du « bruit numérique ».

L'ordre de sommation compte

Pour sommer une série de nombres, l'ordre peut affecter le résultat :

import numpy as np

# Série harmonique : 1 + 1/2 + 1/3 + ... + 1/n
n = 10_000_000

# Somme dans l'ordre croissant (grands d'abord)
somme_croissante = sum(1/k for k in range(1, n+1))

# Somme dans l'ordre décroissant (petits d'abord)
somme_decroissante = sum(1/k for k in range(n, 0, -1))

print(f"Grands d'abord : {somme_croissante:.15f}")
print(f"Petits d'abord : {somme_decroissante:.15f}")
print(f"Différence     : {abs(somme_croissante - somme_decroissante):.2e}")

Implications pour les algorithmes itératifs

Ces paradoxes ont des conséquences directes sur les méthodes numériques :

Résumé

Équations clés

Idées fondamentales

Les algorithmes itératifs constituent une famille puissante de méthodes numériques. Leur efficacité repose sur trois piliers : le choix judicieux de la fonction d'itération, une initialisation appropriée et des critères d'arrêt bien calibrés. La compréhension de la convergence et de ses conditions permet d'utiliser ces algorithmes de manière éclairée et d'anticiper leurs limites.