Recherche de la racine mini d'une fonction inconnue - Le retour

**plegat** · 03/10/2006, 22h17

Bonsoir,

Je reviens sur un de mes précédents post (dispo là), parce que les solutions proposées ne me conviennent plus (bah oui, à force, on devient exigeant

!). Elles fonctionnent très bien, mais je souhaiterais optimiser un peu plus la résolution.

Je vais imager un peu plus que la dernière fois. Je travaille donc avec une matrice dont les termes sont dépendants d'une variable k. Je calcule le déterminant de cette matrice, et je cherche à trouver la valeur minimale de k qui annule ce déterminant (k strictement positif).

L'allure de l'évolution du déterminant en fonction de k peut être assimilé pour ce sujet à une sinusoïde d'amplitude décroissante lorsque k augmente. Evidemment, la période de la sinusoïde varie avec les données de base, donc on ne peut pas trop prévoir la plage de résultat (sauf que ça sera entre 0 et 100000... mais ça fait un peu large!).

Le but de la manoeuvre est donc de trouver la plus petite valeur de k qui annule le déterminant.

J'ai testé, pour le moment:

un algo incrémental: on part de k=0, et on augmente par pas de dk. On détecte la racine dès qu'il y a un changement de signe du déterminant entre deux pas consécutifs (éventuellement, pour améliorer la précision, on revient au pas précédent, on divise le pas par 10, et on recommence). Problème: c'est relativement long si la racine est à 10 et que l'on a besoin d'un pas de 0.001 pour ne pas rater la racine...
un algo type Newton. Très rapide. Rien à dire sur ce point. Problème: ne trouve pas forcément la racine minimale... je l'ai abandonné au profit de l'algo n°1
un algo de résolution par intervalles.. euh, non, pas encore testé... pas tout compris à la méthode... si quelqu'un a une doc explicite à me conseiller...

jobhertz m'avait conseillé à l'époque de me tourner éventuellement vers un algo avec pas adaptatif. Est-ce que ceci pourrait améliorer les choses dans le cas présent? (je n'ai pas trouvé de doc convaincante pour le moment pour répondre moi-même à la question...)

Si vous avez d'autres idées à proposer, je suis preneur.

Merci d'avance.

**jobherzt** · 03/10/2006, 23h23

premiere idée a chaud, pltot que d'utiliser un pas constant, vu que tu travaille sur des ordres de grandeurs large, essaie de passer en logarithme. comme ca, tu auras toujours une bonne precision a ordre de grandeur donné. en gros, au lieu d'ajouter un dx, mutliplie par (1+dx). comme ca, plus x est grand, plus le pas est grand.. ca n'est pas vraiment un pas adaptatif, c'est plus un truc qui marche bien dans certains cas, typiquement quand on manipule des frequences.
Pour un vrai pas adaptatif, l'ide est d'avoir un pas d'autant plus grand que la pente (donc la dérivée) est faible, et reciproquement. mis ca n'est pas garanti.

mais c'est plus ou moins ce que fait newton, c'est curieux qu'il saute une racine ?? tu lui donne bien 0 comme valeur initiale ? c'est peut etre justement un pb d'ordre de grandeur, donc CF plus haut..

**borisd** · 04/10/2006, 00h29

La méthode de Newton permet de trouver une racine, mais pas forcément la plus petite.
Ici, si la fonction est positive en 0 et que sa dérivée s'annule en un point x0 entre 0 et le plus petit k tel que f(k)=0, et si on se retrouve très proche de x0 lors d'une itération, on va certainement sauter vers une autre période, non ?
Il suffit peut-être d'utiliser cette méthode en réduisant le pas quand la dérivée est faible pour réduire les risques de se retrouver sur une autre période ?
[Edit] Par exemple, pour une fonction sinusoidale de péridoe constante, on pourrait remplacer la valeur de la dérivée en x par min(1/2+epsilon,f'(x))

**plegat** · 04/10/2006, 13h01

Envoyé par borisd

Ici, si la fonction est positive en 0 et que sa dérivée s'annule en un point x0 entre 0 et le plus petit k tel que f(k)=0, et si on se retrouve très proche de x0 lors d'une itération, on va certainement sauter vers une autre période, non ?

C'est exactement ça... pour les petites valeurs de x (proche de 0), la dérivée est "faible", ce qui fait qu'on peut très bien basculer sur une autre "période" en cours d'algorithme. Et rien n'empêche de basculer à nouveau ultérieurement, vu que la fonction oscille continûement...

Envoyé par borisd

Il suffit peut-être d'utiliser cette méthode en réduisant le pas quand la dérivée est faible pour réduire les risques de se retrouver sur une autre période ?
[Edit] Par exemple, pour une fonction sinusoidale de péridoe constante, on pourrait remplacer la valeur de la dérivée en x par min(1/2+epsilon,f'(x))

je viens juste d'y penser à basculer en progression itérative quand la dérivée est "faible", et passer en newton dès que la dérivée le permet.... je vais aller tester ça, té! Si j'arrive à trouver une valeur qui fasse la frontière entre "faible" et pas "faible".

**Nemerle** · 04/10/2006, 14h13

As-tu essayé le théorème de Sturm?

http://fr.wikipedia.org/wiki/Th%C3%A...%A8me_de_Sturm

appliqué à la "forme" de ton polynôme en k, cela peut t'aider...

**borisd** · 04/10/2006, 14h36

Envoyé par Nemerle

As-tu essayé le théorème de Sturm?

http://fr.wikipedia.org/wiki/Th%C3%A...%A8me_de_Sturm

appliqué à la "forme" de ton polynôme en k, cela peut t'aider...

En effet, on doit pouvoir utiliser ce théorème dans une méthode dichotomique pour trouver le plus petit x dans [0,somme(|coeffs|)] tel que sigma(0)-sigma(x)=1 (ou le plus grand x tel que sigma(0)-sigma(x)=0).

**Nemerle** · 04/10/2006, 17h43

tout à fait, c'est généralement la dichotomie qui est utilisée

**plegat** · 04/10/2006, 20h45

Envoyé par Nemerle

As-tu essayé le théorème de Sturm?

http://fr.wikipedia.org/wiki/Th%C3%A...%A8me_de_Sturm

appliqué à la "forme" de ton polynôme en k, cela peut t'aider...

Euh... oui... enfin... mon polynôme en k, c'est le déterminant d'un matrice carré de dimension 50 en ce moment... je me vois mal calculer son expression à la mano pour appliquer le théorème...
Je peux descendre jusqu'à une dimension 20 sans trop perdre en précision sur la solution, mais même là, c'est pas calculable comme polynôme...
C'est dommage, mais je me garde quand même ce théorème pour le jour où...

**Nemerle** · 05/10/2006, 09h39

pourquoi cacluler le det à la mano?

La méthode de Kramer est algorithmique!!

**plegat** · 05/10/2006, 21h03

Envoyé par Nemerle

pourquoi cacluler le det à la mano?

La méthode de Kramer est algorithmique!!

Ouaip, ok... même si je passe par une décomposition LU plutôt (d'ailleurs, je crois me souvenir avoir lu sur ce forum qu'il valait mieux passer par une décomposition LU que par Kramer pour calculer un déterminant... mais je ne sais plus si c'est pour une question de rapidité ou de précision...)

Mais bon, là n'est pas la question. Je n'ai pas dû bien comprendre le théorème de Sturm alors. Je l'applique comment si je n'ai que les valeurs numériques de ma fonction? Avec l'expression littérale d'une fonction, ça marche très bien. Mais avec mes nombres... je vois mal... voire pas du tout!

**Nemerle** · 09/10/2006, 14h21

tu changes d'énoncé: avant tu avais un déterminant en k, soit une fct littérale!

Envoyé par plegat

Je vais imager un peu plus que la dernière fois. Je travaille donc avec une matrice dont les termes sont dépendants d'une variable k. Je calcule le déterminant de cette matrice, et je cherche à trouver la valeur minimale de k qui annule ce déterminant (k strictement positif).

Dans le cas où tu as une famille de valeurs de la fonction, déterminer "la + petite racine", n'a pas de sens

il faut que tu "choisisses" le type de fonction associée...

**plegat** · 09/10/2006, 19h47

Envoyé par Nemerle

tu changes d'énoncé: avant tu avais un déterminant en k, soit une fct littérale!

Nan nan nan, je ne change pas l'énoncé!

(ou alors je n'ai pas fait exprès de faire une phrase douteuse...)
Les termes de ma matrice sont des fonctions de k, que je connais littéralement.
Le déterminant de ma matrice est également une fonction de k, que je ne connais pas littéralement. Je pourrais, mais pour avoir l'expression littérale du déterminant d'une matrice 100x100, euh... je ne me le sens pas du tout... c'est faisable, mais honnêtement, j'ai autre chose à foutre (entendre par là, je n'ai pas le budget horaire pour m'atteler à la tâche, et le reste de l'étude à faire avancer...

)

Envoyé par Nemerle

Dans le cas où tu as une famille de valeurs de la fonction, déterminer "la + petite racine", n'a pas de sens il faut que tu "choisisses" le type de fonction associée...

Pas tout compris là...
J'ai une fonction continue de R+ dans R, pour chaque valeur de k une valeur de déterminant, les valeurs pouvant prendre des valeurs positives ou négatives. Qu'est-ce qui m'empêche d'avoir des racines? C'est peut-être le mot "racine" qui prête à confusion? En tous cas, si ma fonction continue passe par des valeurs positives et négatives, c'est bien qu'elle s'annule quelque part...

Je vais préparer un exemple, ça permettra d'avoir un problème pratique et concret...

**plegat** · 19/11/2007, 21h36

Salut,

Je remonte un vieux post du fond des entrailles, juste pour le passer en résolu.
J'ai pu ramener le problème à une recherche de valeurs propres... c'était si simple que je ne l'avais même pas vu...
Donc plus besoin de calculer de déterminant, ni de minimum...

Merci encore à tous ceux qui ont participé