Convergence Gauss-Newton

[president]

Bonjour à tous,

je souhaiterais connaitre la méthode et les conditions pour assurer la convergence d'un algorithme de type Gauss-Newton (utilisant un critère des moindres carrés et linéarisation du premier ordre).

en vous remerciant, :we:

[Dlzlogic]

Bonjour à tous,

je souhaiterais connaitre la méthode et les conditions pour assurer la convergence d'un algorithme de type Gauss-Newton (utilisant un critère des moindres carrés et linéarisation du premier ordre).

en vous remerciant, :we:

Le principe est simple : au voisinage de la solution, la courbe représentative de la fonction peut être assimilée à sa tangente. on peut donc faire une interpolation linéaire.
Le point calculé est utilisé comme point proche de la solution.
Concernant les conditions, c'est un peu plus compliqué, puisque il faut connaitre une valeur approximative de la solution. Donc il faut étudier la fonction, déterminer son domaine de définition, son domaine de dérivabilité etc.
En fait, ça n'a pas grand-chose à voir avec la méthode des moindres carrée. Pour vous aider plus, il faudrait que vous donniez plus de détails.

[president]

Le principe est simple : au voisinage de la solution, la courbe représentative de la fonction peut être assimilée à sa tangente. on peut donc faire une interpolation linéaire.
Le point calculé est utilisé comme point proche de la solution.
Concernant les conditions, c'est un peu plus compliqué, puisque il faut connaitre une valeur approximative de la solution. Donc il faut étudier la fonction, déterminer son domaine de définition, son domaine de dérivabilité etc.
En fait, ça n'a pas grand-chose à voir avec la méthode des moindres carrée. Pour vous aider plus, il faudrait que vous donniez plus de détails.

merci pour cette réponse. Quand je disais connaitre la méthode, je disais connaitre la méthode de preuve de convergence.

En fait, j'utilise un calcul itératif utilisant les moindres carrés non-linéaires.

L'objectif est de minimiser l'écart global entre deux fonctions non-linéaires. Ainsi, je dispose de paramètres, liés aux fonctions, qui peuvent être mis à jour afin de minimiser l'écart global. Étant donné que j'ai affaire à des fonctions non-linéaire, j'utilise le principe des algorithmes de newton où l'on linéarise les fonctions par rapport aux paramètres. Comme on linéarise, le calcul devient itératif. Au final, j'utilise une matrice Jacobienne de dimension mxn avec m le nombre de mesure d'écart à minimiser et n le nombre de paramètres. Le critère de minimisation est le carré de la norme deux de l'écart entre ces deux fonctions, d'où la désignation de moindres carrés. Du coup, le critère est convexe, j'utilise une matrice jacobienne définie positive...
...je me demandais donc comment prouver la convergence de ce calcul, et montrer qu'à chaque itération on minimise toujours le critère...

j'espère avoir été un peu plus clair :lol3:

[Dlzlogic]

Bonjour,
C'est un peu plus clair, mais pas beaucoup plus. Voila ce que j'ai compris
Vous avez 2 fonctions définies sur le même intervalle et dont les représentations graphiques sont voisines.
Ces fonctions ont des paramètres qui vous cherchez à préciser, soit pour l'une, soit pour l'autre, soit pour les deux fonctions.
Pour cela, vous utilisez la méthode des moindres carrés qui, étant donné une série de mesures en sur-nombre, permet de calculer leur valeur en minimisant la somme des carré des écarts.
On démontre que la valeur obtenue est la plus probable. Mais ce sujet est très brulant sur ce forum, et il ne vaut mieux pas le relancer.
Par contre, par MP je vous détailler tout ce que vous voulez.

[Sylviel]

Je te conseillerais d'ouvrir un livre d'optimisation un peu poussée pour regarder les conditions précises de convergence. Ma référence perso est le poly de J.C.Gilbert qui n'est pas encore édité, mais que l'on peut obtenir en lui envoyant un gentil mail. Sinon tu dois pouvoir le trouver dans le livre de Ruszczynski par exemple...

Pour info : il faut que ta fonction soit C^1 dans un voisinage d'un level set, et que J(x_k) soit uniformément injective, où x_k est la suite de point générée par Gauss-Newton. Dans ce cas la convergence est assurée au sens où J(x_k)^t r(x_k) -> 0. Où r est le résidu (ie l'écart dont tu prendras la norme 2) et J sa jacobienne J:=r'.

Tu peux toujours détailler un peu ton problème (en nommant explicitement les choses, en écrivant un vrai problème d'optimisation...), mais tu auras du mal à trouver de l'aide sur un sujet aussi pointu sur ce forum je crains...