Itérative (méthode)

Imaginez que vous cherchiez √2 sans disposer d'une réponse toute faite. Vous partez de 1, puis une même recette transforme chaque estimation en une meilleure : 1 devient 1,5, puis environ 1,4167, puis 1,4142.

Une méthode itérative avance ainsi par corrections successives. Elle ne promet pas que toute recette fonctionne : il faut vérifier que les valeurs se rapprochent bien d'une solution et décider quand l'approximation est assez précise.

Une méthode itérative construit une suite d'approximations. La valeur initiale est notée x₀. Une fonction de mise à jour, notée F, produit ensuite chaque nouvelle valeur à partir de la précédente : $x_{n+1}=F(x_n)x\_\{n+1\}=F(x\_n)$. Si la suite admet une limite L et si F est continue au voisinage de L, cette limite vérifie $L=F(L)L=F(L)$ : c'est un point fixe de F.

Le procédé sert notamment à approcher la solution d'une équation, d'un système linéaire ou d'un problème d'optimisation. Selon le problème, la mise à jour peut être celle de Newton, de Jacobi, de Gauss-Seidel ou une étape de descente. Le point de départ, la règle et le critère d'arrêt font partie de la méthode.

La convergence n'est pas automatique. Elle dépend du domaine choisi, de la règle F et parfois de x₀. Lorsqu'elle a lieu, un calcul numérique s'arrête généralement avant la limite exacte, dès qu'un résidu ou l'écart entre deux itérations respecte une tolérance fixée.

Choisissez une valeur initiale x₀, puis appliquez la même mise à jour pour obtenir x₁, x₂, et ainsi de suite. Après chaque calcul, mesurez un critère d'arrêt annoncé, par exemple le résidu de l'équation ou l'écart entre deux valeurs successives. Arrêtez lorsque ce critère est inférieur à la tolérance choisie. Sinon, poursuivez, sauf si un nombre maximal d'itérations ou un signe de divergence impose l'arrêt.

Pour rechercher un point fixe dans un intervalle fermé, il faut d'abord que la mise à jour soit définie sur cet intervalle et y renvoie toutes les valeurs calculées. Une condition suffisante classique est qu'elle y soit contractante : il existe un nombre q strictement inférieur à 1 tel que $\mathrm{\mid }F(x)-F(y)\mathrm{\mid }\le q\mathrm{\mid }x-y\mathrm{\mid }|F(x)-F(y)|\backslash le\; q|x-y|$ pour tous les nombres x et y de l'intervalle. Le théorème du point fixe de Banach garantit alors un unique point fixe et la convergence depuis tout point initial de cet intervalle.

Si la mise à jour sort du domaine ou amplifie les écarts, la suite peut diverger ou osciller. Il faut alors changer de point de départ, reformuler F ou employer une méthode mieux adaptée. Une tolérance d'arrêt ne remplace jamais cette analyse : une variation momentanément petite ne prouve pas, à elle seule, que la limite cherchée est atteinte.

On cherche la racine positive de 2. Les données sont l'équation x² = 2, la valeur initiale x₀ = 1, l'intervalle [1, 2] et la tolérance de résidu 0,00001. La mise à jour de Newton est la moyenne de l'estimation courante et de 2 divisé par cette estimation : $x_{n+1}=\frac{1}{2}(x_n+\frac{2}{x_n})x\_\{n+1\}=\backslash frac\{1\}\{2\}\backslash left(x\_n+\backslash frac\{2\}\{x\_n\}\backslash right)$. Sur [1, 2], elle renvoie dans [1, 2] et réduit tout écart d'un facteur au plus 1/2 ; la convergence vers l'unique point fixe est donc garantie.

1. À partir de x₀ = 1, on obtient x₁ = (1 + 2) / 2 = 1,5.
2. On obtient ensuite x₂ = (1,5 + 2 / 1,5) / 2 = 17 / 12 ≈ 1,4166667.
3. Puis x₃ = (17 / 12 + 24 / 17) / 2 = 577 / 408 ≈ 1,4142157.

Le contrôle utilise le résidu |x₃² − 2| = 1 / 166464 ≈ 0,0000060. Il est inférieur à 0,00001 : on s'arrête et l'on retient √2 ≈ 1,4142157 avec ce critère. La succession des valeurs rend visible la correction rapide de l'estimation.

Pour résoudre une équation non linéaire, on choisit une mise à jour adaptée et l'on surveille le résidu. Une méthode de bissection est souvent préférable à Newton lorsqu'on dispose d'un encadrement avec changement de signe, mais que le point de départ de Newton paraît incertain.

Pour un grand système linéaire peu dense, Jacobi ou Gauss-Seidel évitent parfois de stocker et de transformer une matrice pleine. Une méthode directe reste préférable lorsque le système est modeste et qu'une factorisation stable fournit rapidement la précision voulue.

En optimisation, chaque itération modifie les variables pour réduire un objectif. Le praticien suit à la fois la valeur de cet objectif, la taille de la mise à jour et le nombre d'itérations, car un seul indicateur peut donner une impression trompeuse d'arrêt.

Méthode directe. Elle atteint, en arithmétique exacte, la solution après un nombre fini d'opérations déterminé par la taille du problème. Une élimination de Gauss sur un système carré est directe ; Jacobi produit au contraire une suite à interrompre selon un critère.

Algorithme récursif. La récursivité décrit la manière dont un programme s'appelle lui-même ; l'itération numérique décrit une suite d'approximations. Une méthode itérative peut être programmée avec une simple boucle, sans appel récursif.

Contraction au seuil. Le critère de Banach exige q < 1. Une borne q = 1 ne garantit ni unicité ni convergence : la mise à jour F(x) = 1 − x sur [0, 1] fait alterner 0 et 1. Il faut une autre preuve ou une autre règle.

Petit pas, mauvais verdict. Deux itérations presque égales peuvent résulter d'une progression très lente ou des limites de l'arrondi. Il faut contrôler un résidu lié au problème et fixer aussi un nombre maximal d'itérations.

Convergence locale. Une règle efficace près d'une solution peut échouer depuis un autre point initial. Pour la mise à jour de l'exemple, la division par x_n interdit x_n = 0 ; travailler dans [1, 2] évite ce cas et fournit un domaine stable.

Arithmétique finie. Sur ordinateur, l'arrondi peut arrêter l'amélioration ou modifier la trajectoire. Le résultat est donc une approximation assortie d'un critère contrôlé, même si la suite mathématique converge exactement.

Le théorème du point fixe précise pourquoi une contraction possède un unique point fixe et pourquoi les approximations successives l'atteignent.