Bonjour,
me réferent à ce lien sur la théorie de la complexité http://fr.wikipedia.org/wiki/Th%C3%A...es_algorithmes
2 classes de problèmes sont identifées:
- décision
- recherche de solution
Je trouve qu'il manque une classe:
ex:
Q: existe-t-il une solution pour x^2<-1?
R: non
--> problème de décision
Q: trouver une solution à x^2<1
R: 0.5 R:0 R:-0.8...
--> problème de recherche de solution
Q: trouver toutes les solutions de x^2<1
R:]-1,1[
--> problème de ?
Bonsoir.
C'est un problème de recherche de solutions (les solutions étant des intervalles ou des réunions d'intervalles). Les logiciels de calcul formel travaillent ainsi.
Cordialement.
Bonsoir,
J'associe la recherche de solution unitaire(dans la sens "trouver une solution") aux algorithmes d'optimisation de type: Newton, Simplex, nelder-mead, pso, genetique, grogrammation dynamique, LMI...
en gros des algorithmes qui cherchent un zéro ou un minimum d'une fonction.
Quel type d'algo est associé à la recherche d'intervalle?
Tout dépend de la typologie.
Si les types sont peu nombreux et très stricts, de nombreux algorithmes ne sont d'aucun type.
Je ne vois pas trop l'intérêt de cette question ...
Bonjour,
Je n'ai rien compris de cette réponseEnvoyé par gg0
je cherche de la littérature pour résoudre un problème d’ingénierie auquel je suis confronté.Je ne vois pas trop l'intérêt de cette question ...
Le plus souvent mes problèmes sont du type:
trouver la commande qui minimise la consommation d'energie d'une batterie sous la contrainte [...], ce qui pour moi se traduit par une recherche de minimum d'une fonction de pénalité sous certaines contraintes sous forme d'inéquations. Si j'ai l'expression analytique de la fonction de pénalité, de son gradient et de son hessien, j'utilise la méthode de Newton, dans le cas contraire, j'utilise soit la programmation dynamique soit un algorithme évolutionnaire basé populations (génétiques, ou essaim particulaire).
Une autre classe de problème aux quels je suis confronté est de type: trouver un x tel que f(x)<a, dans ce cas, si ça peut s'ecrire sous forme de LMI linéaire, les algorithmes pour résoudre des LMI existent sinon, je fais tourner un algo d'otim (Newton ou Metaheuristique) sur f et j'utilise comme fonction d'arrêt f(x)<0
Ces deux types de problèmes sont des choses aux quelles je suis habitué. Actuellement, je suis confronté à un problème de type trouver tous les x qui respectent f(x)<a, f pouvant avoir plusieurs minimas.
Je n'ai jamais répondu à ce type de problèmes précedemment, et je cherche des mots clés pour commencer à chercher sur ieeexplore
Ok !
Dans ton premier message, tu as présenté (sans le vouloir) un problème très différent (*). Je ne suis pas spécialiste du sujet, mais "résolution d'inéquation" me semble approprié. Un forum d'informatique sera sans doute plus précis.
Cordialement.
(*) trouver parmi deux classes d'algorithmes où placer un problème.
En utilisant des outils de calcul formel (Maple, Mupad...), on peut résoudres des inéquations simples.
Mais dès que celles-ci deviennent complexes et non linéaires, ils n'y arrivent plus.
De la même façon que la méthode de Newton-Raphson (et analogues) permet de donner une solution approchée de la solution d'une équation non linéaire, je voudrais savoir s'il existe un équivalent pour les inéquations
Bonjour,
J'ai suivi avec intérêt ce sujet depuis le début.
Avez-vous consulté les études réalisées par J.Jacquelin ?
D'autre part, l'outil informatique ne peut que calculer ce qu'un utilisateur lui demande. En d'autres termes, si vous savez résoudre un certain problème, alors vous pouvez faire le module qui fera le calcul à votre place. Les logiciels dont vous parlez ne sont que des boites à outils. Soit l'outil dont vous avez besoin existe, mais apparemment ce n'est pas le cas, soit il n'existe pas mais ces logiciels ont les outils capables de le fabriquer, enfin, dernière hypothèse, ces outils-là n'existe pas.
Dans tous les cas, si vous pouvez décrire le problème et sa solution, c'est à dire écrire l'algorithme pour faire le module, alors, il peut être réalisé avec des langages de bas niveau.
Mais à mon avis, aucun langages ne pourra résoudre un problème s'il n'a pas été résolu formellement par l'auteur du logiciel.
Bonjour,
En fait, tout dépend des relations dont vous disposez pour améliorer votre position après des tests. Un préalable intéressant , dans ce cas , serait de savoir le nombre de minima et tout ce qui génère des conditions d'arrêt local. Arrangez pour converger vers un petit nombre d'options à explorer complètement.
Si vous n'en avez pas, je ne vois rien d'autre à faire que tout tester. Il n'y a pas de solution universelle miracle ; beaucoup de ces problèmes sont NP complets.
Ma question concerne l'existance de travaux sur ce type d'algorithmes.Dans tous les cas, si vous pouvez décrire le problème et sa solution, c'est à dire écrire l'algorithme pour faire le module, alors, il peut être réalisé avec des langages de bas niveau.
Pour être concrêt:
imaginons:
f=x^4-15*x^2+5*x-20;
on calcule la jacobienne de f:
J=4*x^3 - 30*x + 5;
si je veux trouver une solution pour f(x)=0, un algorithme possible est:
selon la valeur de x0, la réponse sera soit 3.88 soit -4.16Code:x=x0; for i=1..100 x=x-f(x)/J(x); end
Je voudrais savoir s'il existe un algorithme qui puisse à partir de l'expression de f résoudre f<0
la réponse attendue est ]-4.16,3.88[
D'abord, je crois qu'il faut préciser le sens d'algorithme.
Un algorithme est une suite d'ordres logiques qui comporte un début et une fin.
Ce terme n'a rien à voir avec l'informatique.
Par contre, si on doit faire un traitement informatique, on commence par écrire une algorithme : je fais ci, je fait ça, si il y a tel cas, je ferai ceci, sinon, je ferai cela.
Ensuite, naturellement, on va le traduire en code suivant le langage que l'on préfère et qui semble le plus adapté.
Il y a lieu de préciser que l'algorithme est souvent (ou quelque-fois) difficile à faire, l'écriture du code n'est qu'une traduction dans un langage compréhensible par une machine.
Avec l'exemple que vous donnez, l'algorithme est vraiment facile à faire et le code ne serait qu'une simple traduction.
Et comme dit Mike.p, il n'y a pas de solution miracle, il faut savoir résoudre le problème pour pouvoir demander à la machine de faire le calcul.
A aucun moment, je n'ai parlé d'Informatique, je parle d'algo au sens mathématique du terme.D'abord, je crois qu'il faut préciser le sens d'algorithme.
Un algorithme est une suite d'ordres logiques qui comporte un début et une fin.
Ce terme n'a rien à voir avec l'informatique.
L'algorithme que j'ai présenté est l'algorithme de Newton basique ( http://en.wikipedia.org/wiki/Newton%27s_method ) qui sert à résoudre des équations non linéaires.
Non!il n'y a pas de solution miracle, il faut savoir résoudre le problème pour pouvoir demander à la machine de faire le calcul.
L’existence même d'algorithmes comme celui de Newton est la preuve du contraire, il existe certaines fonctions pour lesquelles on ne peut pas trouver de solutions analytiques. alors que par un algorithme comme celui de Newton-Raphson, on peut approcher très fidèlement la solution.
J'aimerais si vous voulez bien revenir à ma question initiale:
existe-t-il des travaux sur des algorithmes de résolution numérique approchée d'inéquations.
Mon exemple précédent est simple à comprendre.
Ce dont vous parlez c'est le problème de convergence locales et globale de l'algorithme. c'est un vrai problème mais prématuré par rapport à mon besoin, vue que pour le moment,je ne connait aucune classe d'algo pour résoudre des inéquations, une fois j'en aurais identifié un ou plisieurs il conviendra d'en étudier la convergence.
encore une fois, votre message me fait croire que vous pensez que je parle d'algorithmes d'optimisations.Si vous n'en avez pas, je ne vois rien d'autre à faire que tout tester. Il n'y a pas de solution universelle miracle ; beaucoup de ces problèmes sont NP complets.
Bonjour,
oui ça existe, j'ai déjà vu ça quelque part (je ne me rappelle plus du terme)... Il existe un nombre caractéristique d'un polynôme qui permet de savoir le nombre de changement de signe dans un intervalle donné. En utilisant ça on peut remonter à la solution que vous cherchez, c'est pas forcément très simple mais c'est faisable.
EDIT : trouvé : http://fr.wikipedia.org/wiki/Th%C3%A...%A8me_de_Sturm
Dernière modification par obi76 ; 27/08/2013 à 21h22.
\o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/
OK ! écartons l'optimisation et la recherche de minima
Supposez vous avoir l'algorithme pour résoudre f(x) = 0 ?
Si oui, c'est trivial ; il vous suffit de segmenter votre ensemble de départ par les 0 de f et de tester un ( seul ) élément de chaque segment pour en déduire le signe
Non, il peut y avoir un nombre pair de changements de signe dans l'intervalle, dans ce cas votre algorithme les ignorera. Il faut passer par ce que j'ai dit.
\o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/
Heu ...
Des changements de signe entre deux zéros pour une fonction continue ? peu probable
A noter : Si f n'est pas un polynôme, l'algorithme de Sturm ne s'applique plus. C'est pour cela que les logiciels formels ont des incapacités : pas de méthode pour trouver les zéros, pas de résolution d'inéquations.
Non, enfin ce que je veux dire c'est que pour trouver vos intervalles de départ, il faut partir de l'hypothèse que dans chaque intervalle, il n'y a qu'un zéro. Pour en être sur, il faut passer par ce que j'ai dit
\o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/
Bonjour,
Pour OBI, le lien que vous avez présenté traite des fonctions polynomiales, les fonctions non linéaires auxquelles je peux être confronté on souvent des expressions en exp, sin/cos et tanh, donc non couvertes par la démarche présentée. ma fonction illustrative n'est qu'un exemple simple pour comprendre la problèmatique, en réalité, les fonctions que je traite sont non linéaires et multi arguments.
Pour Mike,
contre exemple:
f=x^2+y^2;
resoudre par newton f=1 me donnera un couple de points x,y se trouvant sur le cercle décrit par x^2+y^2=1; par exemple [1,0],[sqrt(2)/2,-sqrt(2)/2]... tout dépendra du point de départ [x0,y0]
comment à partir de cette seule info, pouvez vous sortir le domaine dans lequel f<1?
la solution analytique de f<1, est qqch de type: x=[-1,1], y=[-(1 - x^2)^(1/2), (1 - x^2)^(1/2)]
c'est ce type de solutions que je cherche, mais non pas par des outils de calcul formel (car ils ne pourront pas résoudre les inéquations non linéaires) mais avec une methode de calcul numérique analogue à Newton
Si ce sont pour des fonctions quelconques, alors il faut trouver un moyen de trouver le nombre de changement de signes dans un intervalle.
\o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/
Ah, nouvelle information : Il s'agit de fonctions de plusieurs variables.
Là, je crains qu'il ne faille t'adresser à des spécialistes (qui généralement n'ont pas le temps de fréquenter des forums). En calcul formel (exact) le problème d'obtenir des algorithmes effectifs est ouvert (non résolu). En calcul approché, dès qu'il y a du non linéaire à beaucoup de variables, la stabilité des algorithmes est douteuse. Avec 2 ou 3 variables, il y a sans doute des outils connus (des spécialistes).
Pour ton exemple, la logique est la même : Une fois défini l'ensemble des solutions, il partitionne le plan en plusieurs zones où le signe est constant. Il suffit de tester un point de chaque zone. Pour une fonction simple, on peut trouver des points dans les différentes zones, pour une fonction très compliquée, il devient difficile de savoir même combien il y a de zones.
Cordialement.
et il sagit aussi de fonctions non forcément polynomiales, alors dans ce cas...
Sauf que pour garantir que le signe est constant dans une zone, il faut de toute façons trouver une méthode qui à un intervalle donné te donnent le nombre de zéros de cette fonction (j'insiste sur ce point). Tester si un point dans la zone est d'un certain signe ne peut pas te garantir qu'ils ont tous le même signe dans cet intervalle.Pour ton exemple, la logique est la même : Une fois défini l'ensemble des solutions, il partitionne le plan en plusieurs zones où le signe est constant. Il suffit de tester un point de chaque zone.
Dernière modification par obi76 ; 28/08/2013 à 10h31.
\o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/
pour une fonction de plusieurs variables, l'ensemble des zéros est en général infini non dénombrable, selon la "lisseur" de la fonction cet ensemble sera plus ou moins simple, mais il me semble difficile qu'un algorithme numérique donne des solutions approchées de tous les zéros.
@ Obi76 :
pour une fonction simplement continue, il peut être extrêmement difficile de définir les zones (il n'y a plus de question d'intervalle), mais si elle est suffisamment "lisse", on ne passe pas d'une zone strictement positive à une zone strictement négative sans passer par 0 (couper la frontière des zones). Donc le signe sur une zone est parfaitement déterminé par la valeur en un point.
Par exemple, pour résoudre y-x sin(x)<1, on remarque que y-x sin(x)=1 est une courbe continue du plan, qui définit deux zones : Zone 1 : Celle qui contient l'origine; zone 2 : celle qui contient le point de coordonnées (0,2).
0-0 sin(0) <1
2-0 sin(0) >1
Donc les solutions sont les couples de coordonnées des points de la zone 1.
Remarque : On est bien avancés ! On a trouvé que les solutions sont les (x,y) tels que x est quelconque et y>x sin(x)+1.
En général, les "résolutions" d'inéquations à plusieurs variables sont assez décevantes. Le contre exemple d'ABN84 le montre aussi, car c'est une réécriture de l'inéquation.
Cordialement.
C'est pour ça que dans le cas de polynomes, passer par le théorème de Sturm me paraissait la bonne solution. Maintenant si on complexifie le problème de départ, on va rapidement arriver dans un mur, si ce n'est pas déjà le cas...
\o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/
Salut Obi76
entre 2 zéros ? et alors qu'on ne présume pas de l'alternance des signes mais qu'on effectue un test à chaque intervalle ?!?!
pourtant le signe ne peut changer qu'après un zéro ( on est implicitement dans le continu ) et donc entre 2 zéros le signe est unique.
je dois rater quelque chose ... vos explications sont les bienvenues
mais les intervalles sont des segments dont les bornes sont les zéros ...
le problème c'est que si tu utilises un algorithme itératif qui trouve des zéros de la fonction, comment être sûr qu'entre deux zéros qu'il a trouvés il n'y en pas d'autres?
Bonjour,
mais ce n'est pas une fonction ...
vous voulez l'intervalle des x dont l'image a un certain signe. Donc on devrait avoir une fonction de x qui rende y. Ca n'a plus de sens si un x rend un positif ET un négatif
je vous rappelle que la particularité d'une fonction est d'associer une valeur unique Une équation de cercle n'est pas une fonction
@ Mike.p :
f: (x,y) -->x²+y² est bien une fonction.
Cordialement.
