Discussion :

[membreComplexe12]

Bonjour tous,

je vous explique ma situation, en donnant tous les éléments de mon problème :

- j'ai une équation non linéaire à résoudre (ma fonction ressemble à un polynome mais n'en ai pas toujours un).
- je veux trouver une racine de cette fonction "f" et je sais que la racine est entre les bornes "a=0" et "b=1.5"
- je veux résoudre ce problème avec un algorithme robuste et rapide.

Ce que je fais pour le moment :
- c'est que je pars des bornes "a" et "b" et que je procède par dichotomie jusqu'à obtenir la solution.
- le soucis est que la dichotomie est pas un algo très rapide
- du coup j'ai voulu passer à la méthode de Newton mais il s'avère que proche de la solution la dérivée de la fonction est quasi-nulle. La
conséquence de ceci est que lorsque l'algo de Newton s'approche de la solution il oscille pas mal avant de trouver la solution et le temps de
calcul n'est pas forcement meilleur qu'avec la dichotomie.

Où j'ai besoin de votre aide svp :
1°) tout d'abord je voudrais savoir si vous avez une idée pour résoudre ce problème plus rapidement qu'avec la dichotomie mais avec la même robustesse ?
- j'ai entendu qu'il existe une méthode dit du point fixe mais j'ai regardé sur le net et je ne la comprends pas vraiment et j'ai donc du mal à avoir un avis critique dessus.

2°) sinon j'ai pensé à vérifier à utiliser un algorithme de minimisation :
- je minimise une équation et ceci reviendrait à résoudre f(x)=0, le soucis et que je ne sais pas trop comment m'y prendre et surtout pour la gestion des bornes.
- j'ai entendu parlé de condition de Kuhn et Tucker mais je ne sais pas trop comment le programmer

3°) la dernière chose à laquelle j'ai pensé c'est d'utiliser Newton mais de le modifier :
- par exemple : si lors du pas de temps "n" je sors des bornes alors je divise ce pas de temps par 2 pour ne pas sortir des bornes...

Bref, que pensez vous de toutes ces méthodes et que me conseillerai vous ?
en

[sarmin]

Bonjour,

petite question avant tout : je suppose que ta fonction est à une variable ?
Si oui, dans les algorithme classique, je ne pense pas qu'il y en ait un plus robuste que la dichotomie (en gros, tu coupe a chaque fois ton intervalle en deux et tu regarde le signe de f aux bornes, c'est bien ca ?)

Concernant le point fixe, cela revient en fait à réécrire f(x) = 0 en x = g(x) (par exemple en écrivant x = x + f(x) ce qui est éuivalent à f(x) = 0) et ensuite à itérer x_k+1 = g(x_k)). Cet algorithme fonctionne mais il me semble (pas certain sur le coup mais je sais qu'il y a une condition du style) qu'il est nécessaire que la dérivée de g soit comprise (strictement) entre -1 et 1 pour que ca converge.

Pour l'histoire de minimisation, je n'ai pas bien saisi. Tu veux pas exemple minimiser un truc comme F(x) avec F'(x) = f(x) ? C'est une idée mais je ca me semble tendu. Mais pourquoi pas. Concernant les conditions KKT cela concerne les problème de minimisation avec contraintes (sorte de généralisaiton des multiplicateurs de lagrange). Mais, ici, je ne sais pas bien comment les appliquer.

J'èspère que cela pourra un peu t'aiguiller

[membreComplexe12]

Salut Sarmin, merci beaucoup d'avoir pris le temps de m'aider !
je réponds entre les lignes.

petite question avant tout : je suppose que ta fonction est à une variable ?

oui c'est bien cela

Si oui, dans les algorithme classique, je ne pense pas qu'il y en ait un plus robuste que la dichotomie (en gros, tu coupe a chaque fois ton intervalle en deux et tu regarde le signe de f aux bornes, c'est bien ca ?)

tout à fait. En effet il ne peux pas y avoir plus robuste mais d'autre le sont peut être autant ou on une robustesse proche.... c'est ce que je cherche à savoir

Concernant le point fixe, cela revient en fait à réécrire f(x) = 0 en x = g(x) (par exemple en écrivant x = x + f(x) ce qui est éuivalent à f(x) = 0) et ensuite à itérer x_k+1 = g(x_k)). Cet algorithme fonctionne mais il me semble (pas certain sur le coup mais je sais qu'il y a une condition du style) qu'il est nécessaire que la dérivée de g soit comprise (strictement) entre -1 et 1 pour que ca converge.

=> d'accord avec ton explication je viens de comprendre l'idée de l'algorithme du poids fixe. Je n'avais pas compris auparavant

=> c'est vrai que j'avais cru comprendre qu'il y avait une condition de ce genre pour l'algo du point fixe mais je ne suis pas certain moi non plus...
=> ça me parait super restrictif... quelqu'un pourrait il confirmer ceci ?

Pour l'histoire de minimisation, je n'ai pas bien saisi. Tu veux pas exemple minimiser un truc comme F(x) avec F'(x) = f(x) ? C'est une idée mais je ca me semble tendu. Mais pourquoi pas.

oui c'est exactement ceci à quoi je pensais. En fait dans les algorithmes de minimisation on préfère en général Levenberg Marquardt à Newton car il ne diverge pas celui là
J'avais donc dans l'idée d'utiliser LVBM mais encore faut il arriver à le programmer.... (je suis preneur si quelqu'un sait le faire).

Concernant les conditions KKT cela concerne les problème de minimisation avec contraintes (sorte de généralisaiton des multiplicateurs de lagrange). Mais, ici, je ne sais pas bien comment les appliquer.

oui en fait je connais un peu près ce que c'est : multiplicateur de Lagrange dans le cas de contraintes d'inégalités. Mon soucis est que je n'ai pas compris exactement comment ça marche :
=> si tu peux m'expliquer sur un cas simple je suis preneur aussi

J'èspère que cela pourra un peu t'aiguiller

merci, ça me donne déjà des éléments intéressants

[sarmin]

EDIT : Ouep je confirme pour le point fixe (voir http://perso.uclouvain.be/vincent.le...urs10-1112.pdf slide 13)

Un petit exemple pour KKT :
On veut minimiser la fonction f(x) = x² soit les contraintes x >= 2.
D'abord on réécrit les contraintes sous formes >= 0 : x - 2 >= 0

Ensuite, les conditions KKT ca dit que

Grad(f) = Sum lambda_i Grad(c_i)
avec lambda_i >= 0
et tout en respectant les contraintes

avec c_i les contraintes d'égalités OU d'inégalité (attention au sens).
Ici ca donne

2x = lambda

Ensuite, on discute les cas (c'est là que c'est génant niveau informatique, parce que le nombre de cas à discuter explose rapidement) : si lambda = 0, les contraintes ne sont pas serrée ; si lambda != 0, elle sont serrés (donc les inégalités associées deviennent des égalités.

Ici :
- soit lambda = 0. Mais alors x= 0 -> contraintes violée
- soit lambda != 0. Alors contrainte serrée ; x = 2, lambda = 4 >= 0. C'est bon, l'otimum est x = 2 (ce qui est bien le cas)

[membreComplexe12]

merci beaucoup pour le lien :

1°) du coup la méthode du point fixe c'est pourris ? ça ne marche que pour quelques fonction... par exemple si on veux l'utiliser sur la fonction :

x^0.5

alors ça ne marchera pas car elle n'est pas Lipztiennes

2°) merci pour KKT, c'est exactement ce genre de chose que je veux essayer de programmer

le soucis est que je ne vois pas trop comment faire dans un cas de ce type général :
=> minimiser une fonction f(x) en trouvant x qui se trouve entre les bornes x>0 et x<500. Ensuite j'aimerai bien programmer ceci non pas dans le cas d'une fonction mais dans le cas d'un système linéaire (et donc trouver le vecteur X qui minimise le residu du systeme)

[FR119492]

Salut!
Deux suggestions: la méthode de Ridders et celle de Brent.
Jean-Marc Blanc