Algorithme de Gauss-Newton - Définition

Introduction

L'algorithme de Gauss-Newton est une méthode de résolution des problèmes de moindres carrés non-linéaires. Elle peut être vue comme une modification de la méthode de Newton dans le cas multidimensionnel afin de trouver le minimum d'une fonction (à plusieurs variables). Mais l'algorithme de Gauss-Newton est totalement spécifique à la minimisation d'une somme de fonctions au carré et présente le grand avantage de ne pas nécessiter les dérivées secondes, parfois complexes à calculer.

Les problèmes de moindres carrés non-linéaires surviennent par exemple dans les problèmes de régressions non-linéaires, où des paramètres du modèle sont recherchés afin de correspondre au mieux aux observations disponibles.

Cette méthode est due au mathématicien renommé Carl Friedrich Gauss.

Algorithme

Soit m fonctions r_i ( ) de n variables avec m≥n, l'algorithme de Gauss–Newton doit trouver le minimum de la somme des carrés

En débutant avec l'approximation initiale du minimum, la méthode procède par itérations:

où l'incrément vérifie les équations normales

Ici, on note par r le vecteur des fonctions r_i, et par J_r la matrice jacobienne m×n de r par rapport à β, tous les deux évalués en β^s. La matrice transposée est notée à l'aide de l'exposant T.

Dans les problèmes d'ajustement des données, où le but est de trouver les paramètres d'un certain modèle permettant le meilleur ajustement aux observations (x_i,y_i),, les fonctions r_i sont les résidus

Alors, l'incrément peut s'exprimer en fonction de la jacobienne de la fonction f:

Dans tous les cas, une fois connu l'estimation à l'étape s, les équations normales permettent de trouver l'estimation à l'étape suivante; pour résumer, on a:

L'ensemble du terme de droite est calculable car ne dépend que de et permet de trouver l'estimation suivante.

Exemple

Courbe calculée avec et (en bleu) contre les données observées (en rouge).

Dans cet exemple, l'algorithme de Gauss–Newton est utilisé pour ajuster un modèle en minimisant la somme des carrés entre les observations et les prévisions du modèle.

Dans une expérience de biologie, on étudie la relation entre la concentration du substrat [S] et la vitesse de réaction dans une réaction enzymatique à partir de données reportées dans le tableau suivant.

i	1	2	3	4	5	6	7
[S]	0.038	0.194	0.425	0.626	1.253	2.500	3.740
rate	0.050	0.127	0.094	0.2122	0.2729	0.2665	0.3317

On souhaite ajuster les données à la courbe de la forme:

L'estimation par moindres carrés porte sur les paramètres V_max et K_M.

On note x_i et y_i les valeurs de [S] et la vitesse de réaction, pour On pose β₁ = V_max et β₂ = K_M. Nous allons chercher β₁ et β₂ pour minimiser la somme des carrés des résidus

  ( )

La jacobienne du vecteur des résidus r_i par rapport aux inconnus β_j est une matrice dont la ligne n° i est

Commençant avec l'estimation initiale β₁=0,9 et β₂=0,2, il suffit de 5 itérations de l'algorithme de Gauss–Newton pour atteindre les estimations optimales et . Le critère de la somme des carrés des résidus chute de 1,202 à 0,0886 en 5 itérations. Le tableau suivant détaille les cinq itérations:

Itération	Estimation	Somme des carrés des résidus
1	[0,9;0,2]	1,4455000
2	[0,33266;0,26017]	0,0150721
3	[0,34281;0,42608]	0,0084583
4	[0,35778;0,52951]	0,0078643
5	[0,36141;0,55366]	0,0078442
6	[ 0,3618;0,55607]	0,0078440

La figure ci-contre permet de juger de l'adéquation du modèle aux données en comparant la courbe ajustée (bleue) aux observations (rouge).