Discussion :

[ShootDX]

Bonjour à tous!

Voila mon problème: j'ai deux courbes quelconques f et g. Je ne connais pas leur formule: je sais juste que l'ordonnée d'un point quelconque d'abscisse x sur la courbe f ou g est f(x) ou g(x). Je voudrais, à partir de ces données, trouver la/les intersection(s) de ces deux courbes, sachant que l'algorithme doit être rapide (temps réel).

Je précise tout de suite que je suis nul en maths, donc pardonnez-moi d'avance pour les petites imprecisions (et si possible corrigez-moi, j'aime apprendre ).

J'ai trouvé quelques pistes par-ci par-là, comme modéliser f et g avec des polynômes, puis résoudre f(x) = g(x). Sauf que je n'ai aucune expérience avec les polynômes, donc aucune idée de comment les trouver ni de comment résoudre l'équation posée. L'autre idée aurait été de faire une approximation: je cherche une "zone" dans laquelle un des points d'intersection est et je réduit progressivement cette zone.

Merci d'avance pour votre aide!

[Graffito]

Bonjour,

Peux-tu confirmer que au départ on connait seulement un nombre fini de points d'une courbe (N1 pour la courbe f, N2 pour la courbe g) ?

La solution la plus élégante consiste effectivement à déterminer les polynomes y=P1(x) et y=P2(x) (de degré N1 et N2) qui définit chaque courbe, puis à trouver les solutions (x,y) -il peut y en avoir plus d'un couple (x,y) qui réponde au problème-, telles que y=P1(x) et y=P2(x).

Je pense qu'on doit trouver des bibliothèques de code déjà tout fait.

Sinon on peut simplifier le problème en limitant le degré des polygones à traiter en se restreignant à des intervalles de l'axe des X avec un nombre limité de points. Par exemple, si on prend on traite les intervalles le plus simples (2 points pour chaque courbe), on est ramené à l'intersection de 2 droites (programme de seconde). Avec 3 points, on se tretouve avec une équation du second degré, etc ...

[FrancisSourd]

L'approche risque de dépendre fortement du nombre de points que tu peux calculer dans le temps imparti pour le calcul.
Est-ce 5, 10, 100, 1000?

Sais-tu aussi si tes fonctions sont continues?

Sinon, cela revient à chercher les racines de la fonction h(x)=f(x)-g(x).

[Médiat]

Sinon, cela revient à chercher les racines de la fonction h(x)=f(x)-g(x).

Même en supposant que f et g soient des polynomes, à partir de 6 points, il faut un polynome de degré 5 (dans le cas général) et résoudre par radicaux, une équation du 5ième degré est impossible, un certain Evariste Galois nous a démontré cela vers 1830

[FrancisSourd]

Je suis bien d accord. Il faut viser des méthodes d analyse numerique

[ShootDX]

Peux-tu confirmer que au départ on connait seulement un nombre fini de points d'une courbe (N1 pour la courbe f, N2 pour la courbe g) ?

Oui. Mais N1 et N2 sont sans doute trop grand pour pouvoir définir des polynômes de degré N1 et N2.

De plus je précise que c'est une bonne approximation que je cherche, pas une solution formelle.

Par exemple, si on prend on traite les intervalles le plus simples (2 points pour chaque courbe), on est ramené à l'intersection de 2 droites (programme de seconde).

Je pensais appliquer ce principe: je modélise chaque courbe par une série de segments (le nombre de segments dépendera de la précision requise) et je cherche les intersections de ces segments. Sauf qu'il faut que je renouvelle ceci pour chaque paire de segment possible (je ne vois pas comment faire autrement, si ça se trouve il existe une heuristique...), mais ça ne devrait pas poser de problèmes puisqu'il suffit de faires quelques divisions et quelques tests pour être sûr que le point d'intersection est bien sur les segments.

L'approche risque de dépendre fortement du nombre de points que tu peux calculer dans le temps imparti pour le calcul.
Est-ce 5, 10, 100, 1000?

Bon. on va dire autant que je veux

Sais-tu aussi si tes fonctions sont continues?

Dans la plupart des cas oui, donc s'il n'existe pas de solution simple pour les fonctions discontinues, je mettrai en pratique la règle des 80%.

[Matthieu Brucher]

Si N1 et N2 sont grands, ne prends pas de polynômes de degré trop grand. Au delà de 4, c'est bof pour la stabilité - et donc la précision aussi -. En gros, ça revient à faire une interpolation avec des B-Splines.
Tu peux aussi regarder à la reconstruction avec des sinus et des cosinus si tu as un échantillonage uniforme - dans le cas contraire, c'est plus chaud à reconstruire -

[FrancisSourd]

D'après tes réponses, je te conseille vraiment de regarder parmi ces méthodes:
http://fr.wikipedia.org/wiki/Algorithme_de_recherche_d'un_z%C3%A9ro_d'une_fonction
pour rechercher les 0 de la fonction f-g.

A mon avis, la piste "polynôme" est à oublier.

[random]

ben si pour f1 on a y de f1
et pour f2 on a y de f2
il suffit pour des valeurs consécutives de x de verifier si le signe de
ydef1-ydef2 s'inverse avec un pas raisonnable cela devrait pouvoir se faire assez vite

[j.p.mignot]

Si les fonctions sont continues et "pas trop oscillantes", on peut facilement en temps réel vérifier un changement de signe de f-g et si il a lieu estimer la position de l'intersection par interpolation linéaire.
On peu aussi calculer l'intersection de 2 polynômes de degré <=4 ( si on souhaite 1 solution analytique ) construit par moindres carrés entres +- n points autour du point où f-g change de signe.
Toute fois suivant la puissance du processeur, un moindre carré + une équation de degré 3 ou 4 peut être un peut "lourd" pour du real time.
Peut être un degré 1 ou 2 avec +-n points et n <= 2 ou 3 serait acceptable. Cela dépend beaucoup de la stabilité des points, du bruit, de la fréquence de digitalisation,...
Rappel: faire attention à des polynômes de degrés top élevés il y a un risque CERTAIN de très fortes oscillations hors des points où on les forcent => l'estimation du zéro pourrait alors conduire à
1- prendre beaucoup plus de temps
2- fournir un résultat plus incertain

[ShootDX]

Si les fonctions sont continues et "pas trop oscillantes", on peut facilement en temps réel vérifier un changement de signe de f-g et si il a lieu estimer la position de l'intersection par interpolation linéaire.

J'avoue ne pas avoir compris grand chose... Pourrais-tu expliquer un peu plus? De toute façon, une fonction continue n'a plus vraiment de sens en informatique, non?

Sinon la méthode de FrancisSourd (à savoir résoudre f(x) - g(x) = 0) me paraît bonne et assez rapide: je pense que je vais me tourner vers la méthode de Brent décrite dans Numerical Recipes.

[j.p.mignot]

une fonction continue n'a plus vraiment de sens en informatique, non?

Evidement on travail sur des points qui plus est qui sont entachés d'erreurs de codage. Il y a donc une forme de "digitalisation" de la courbe.

Toutefois la notion de continue est tout de même importante.

si on considère f(x) = 10 pour x >=0 et f(x) =-10 pour x <0, f est définie partout et est discontinue en 0
Si maintenant on prend par exemple g(x) = ArcTan(x), toutes les méthodes ci-dessus donneraient (0,0) comme intersection mais du fait de la discontinuité il n'y a pas d'intersection.

Je pense à priori que vos points proviennent de mesures de données physiques qui sont pour l'essentiel continues

Chercher les intersections revient à chercher les x satisfaisant à H(x)= f(x)-g(x)=0
En fait, du au fait que l’on a que des valeurs discrètes de x, on va juste pouvoir voir que
Pour un point Xi, f on à H(Xi) d’un signe et à l’index suivant H(X(i+1)) de l’autre. Le cas limite où H(Xi)=0)[resp. H(X(i+1))=0] donne directement la solution.
Si non, si f et g sont continues (donc H l’est) il existe au moins 1 point entre Xi et X(i+1) où H=0.
Il n’est pas nécessairement unique.
Par exemple si Xi = i*( pi/100) - pi/200, si H(x)=sin(x) H(X0) <0, H(X1)>0 et il y a une seule intersection. Si Xi=-pi/200+100*2pi*i il y aura 200 intersections entre X0 et X1.
C’est pour cela que j’ai dit « pas trop oscillante ». On pourrait plutôt dire suffisamment digitalisée (Nyquist).
Si ses conditions sont satisfaites alors on est dans la situation où
Pour Xi, X(i+1),X(i+2), …H est d’un signe et
Pour X(i-1), X(i-2), … H est de l’autre.
Le plus rapide consiste à prendre la droite passant par les points (Xi, H(Xi)) et ( X(i+1), H(X(i+1)) et d’en rechercher l’intersection avec l’axe des X.
Cela est assez correct si
1- la digitalisation est suffisante ( car ici il n’y a pas de courbure)
2- si les points sont peu bruités
si non afin de limiter l’influence du bruit (incertitudes, digitalisation, …) sur les points, je proposerais de prendre un ensemble de points autour des points Xi et X(i+1) et de faire passer
par ces points, par moindres carrés, une fonction polynomiale (autres modèles aussi possible suivant l'origine des points ) dont on cherchera un zéro. En prenant un degré > 1 on réintroduit la courbure perdue dans le 1er cas.
La je rappelle que
1- le polynôme doit être de degré <=4 si on veut pouvoir en avoir une solution analytique (Gallois)
2- de toute façon éviter des degrés élevés car il y a des risques d’avoir des fit parfait sur les points et des oscillations énormes ailleurs
3- de plus si sur n points on met un polynôme de degré n-1, il n’y aura plus de notion de courbes moyenne en cas de bruit et on fittera sur le bruit. Un degré trop élevé peu conduire à plus de calcul pour moins de précision. En général j’essaie d’éviter de dépasser un degré 3.
4- Du fait du « moyennage », on pourrait fort bien avoir un zéro légèrement hors des limites Xi, X(i+1) prévues

De toutes façon en cas de système bruité, un filtrage préalable peut être extrêmement efficace.

Il faut aussi garder en tête qu'un moindres carrés peut être incompatible avec le real time . D'une part cela représente une quantité significative de calculs, de l'autre le nombre de cycles pour converger n'est pas à priori prédictible.

[DrTopos]

... il faut un polynome de degré 5 (dans le cas général) et résoudre par radicaux, une équation du 5ième degré est impossible, un certain Evariste Galois nous a démontré cela vers 1830

Je crois que c'est plutôt Abel qui a montré cela. Du moins le théorème auquel tu fais allusion porte son nom.

[DrTopos]

Juste une petite remarque, en espérant qu'elle ne va pas trop troubler cette discussion. Mais je crois qu'elle est importante sur le plan conceptuel (et philosophique).

De toute façon, une fonction continue n'a plus vraiment de sens en informatique, non?

Le théorème de Brouwer-Joyal (un méta-théorème en fait) dit au contraire que toute fonction calculable de R vers R est nécessairement continue. La continuité (en ce qui concerne les fonctions de R vers R) a donc un sens en informatique et est même imposée.

Bien entendu, ce théorème s'applique à de vrais réels, pas aux nombres à virgule flottante. Un vrai réel, c'est à dire une classe d'équivalence de suites de Cauchy, ou mieux une coupure de Cantor-Dedeking, peut être représenté par un algorithme prenant en entrée un nombre rationnel 'e' (quotient de deux entiers) et renvoyant un autre rationnel 'a' constituant une approximation de notre réel à 'e' près.

Dès lors il est assez aisé de comprendre qu'une fonction non continue n'est pas calculable. Par exemple, prenons la fonction de Heaviside, x |-> H(x), qui vaut 0 pour x négatif ou nul et 1 pour x strictement positif. Si on essaye de calculer H(x) pour x petit, x peut être tellement petit que la précision à laquelle il faut calculer x pour décider de la valeur de H(x) peut être arbitrairement grande. Dès lors, même si en augmentant indéfiniment la précision du calcul, on obtient toujours 0 pour l'approximation de x, on ne peut à aucun moment affirmer que H(x) est 0. La fonction H n'est donc pas représentable par un algorithme.

Evidemment, le problème est différent avec les nombres à virgule flottante, mais il faut bien comprendre que ces derniers sont très loins d'être des nombres réels. Il y a eu quelques expérimentation faites dans des labos universitaires d'infomatique pour implémenter les vrais réels, comme je les ai décrits ci-dessus (en particulier en Grande Bretagne), mais il semble que cette technologie ne soit pas encore mûre. Les résultats sont toujours rigoureusement exacts, mais les temps de calcul et surtout les stratégies de calcul sont très difficiles à maîtriser.

[ShootDX]

De toutes façon en cas de système bruité, un filtrage préalable peut être extrêmement efficace.

Pour l'instant je ne me préoccupe pas de ce problème de bruitage, puisque mes points sont générés par une fonction du style f(x) = x^2. Mais par la suite je pourrais en effet en avoir besoin. Que me conseillez-vous?

Le théorème de Brouwer-Joyal (un méta-théorème en fait) dit au contraire que toute fonction calculable de R vers R est nécessairement continue. La continuité (en ce qui concerne les fonctions de R vers R) a donc un sens en informatique et est même imposée.

Excusez-moi, je me suis mal exprimé: je voulais dire que, en informatique, lorsqu'on ne fait pas de calcul formel, on est limité par la précision du résultat donc que de toute façon la notion de continuité n'a aucun sens.

Soit E la précision de calcul. Imaginons une fonction qui à x associe 5 et à x+E 6. Eh bien, il n'y a aucun moyen de savoir que c'est une fonction continue ou non, puisque dans l'interval ]x;X+E[ il peut tout se passer.

Dès lors, même si en augmentant indéfiniment la précision du calcul, on obtient toujours 0 pour l'approximation de x, on ne peut à aucun moment affirmer que H(x) est 0. La fonction H n'est donc pas représentable par un algorithme.

Certes, on ne peut à aucun moment dire avec certitude si H(x) est 0 si x est très petit. Ce que je ne comprend pas, c'est cette histoire d'algorithme: cela veut donc dire qu'aucune courbe ne peut être représentée par un algorithme? Soit j'ai pas compris ce qu'était un algorithme, soit il y a un truc qui m'échappe...

(On ne peut pas écrire H(x) = x / racine(x^2) + 1 ?)

[Tellmarch]

joli troll DrTopos, mais partir sur d'autre implémentations des réels n'apporte pas grand chose ici

D'ailleurs pour parler de continuité sur les nombres à virgules flottante moi je munirai plutot notre espace d'une nouvelle topologie discrete ^^

[DrTopos]

Excusez-moi, je me suis mal exprimé: je voulais dire que, en informatique, lorsqu'on ne fait pas de calcul formel, on est limité par la précision du résultat donc que de toute façon la notion de continuité n'a aucun sens.

J'avais bien compris et je suis d'accord. Je voulais surtout faire remarquer que les nombres à virgules flottante ne sont pas des réels, et que ces derniers (les vrais réels) ne sont pas pour autant une utopie en informatique.

(On ne peut pas écrire H(x) = x / racine(x^2) + 1 ?)

Si, on peut très bien le faire, même avec les vrais nombres réels (algorithmiques) que j'évoquais. En effet, il est clair (me semble-t-il) que la valeur de racine(x) peut être calculée avec n'importe quelle précision pourvu qu'on ait accès à une précision aussi grande qu'on veut sur x lui-même. Il en va de même pour la formule que tu donnes, puisque qu'elle est essentiellement une composition de fonctions ayant cette même propriété.

Toutes les fonctions continues 'classiques' sont donc représentables par des algorithems, même avec de vrais réels. Il existe peut-être des fonction continues 'pathologiques' non représentables par des algorithmes, mais j'avoue que je n'en sais rien.

[j.p.mignot]

Je ne suis pas tout à fait d’accord avec l’assertion

La notion de continuité n’a pas de sens

Dans le problème d’intersection qui nous concerne,
Considérons par exemple les fonctions
f(x) = x pour tout x et
g(x) = 1 si x <1/20, g(x)=-1 si x >=1/20
f et g sont définies sur R, g étant discontinue en x=1/20.
Il n’y a pas de point commun entre f et g justement à cause de la discontinuité qui interdit
le droit d’interpoler entre 2 valeurs entourant dans le cas présent 1/20 .
Si on digitalise f et g avec xi = i/10 i=-n..n, sans introduire de discontinuité on trouve une solution à f=g avec le changement de signe de f-g entre les points d'index i=0 et i=1. Il faut donc bien interdire les interpolations dans les intervalles contenant ces discontinuités bien que les courbes / fonctions ne soient définies qu’en des points discrets.

[DrTopos]

joli troll DrTopos, mais partir sur d'autre implémentations des réels n'apporte pas grand chose ici

Il est bien certain que mon intervention ne va pas résoudre le problème initialement posé.
Malgré cela, je suis sûr que quelques uns auront apprécié d'entendre parler d'un théorème peu connnu et d'être mis au courant qu'il existe des recherches sur l'implémentation des vrais réels. Pas aussi troll que cela peut-être (je plaisante bien sûr et toi aussi).

D'ailleurs pour parler de continuité sur les nombres à virgules flottante moi je munirai plutot notre espace d'une nouvelle topologie discrete ^^

Justement, je ne parle pas de continuité sur les nombres a virgule flottante, mais seulement sur les vrais réels. D'ailleurs, le type IEEE754 (si je me souviens bien) qui officialise la définition des nombres à virgule flottante est une structure qui est tout sauf un corps. Aucune opération n'y est bien définie au sens mathématique. C'est l'un des très rares types de données pour lesquels je ne connais pas de caractérisation formelle.

Quant-à la topologie, on peut en reparler quand tu veux....

[Tellmarch]

Toutes les fonctions continues 'classiques' sont donc représentables par des algorithems, même avec de vrais réels. Il existe peut-être des fonction continues 'pathologiques' non représentables par des algorithmes, mais j'avoue que je n'en sais rien.

Bon du coup on va continuer là-dessus ^^
Etant donné une fonction continue f, (avec ton sens de la continuité et des réels), j'ai l'impression que grace à l'a formule de taylor young on peut calculer f' à la précision que l'on veut en tout point. Si f est calculable, f' le serait donc aussi (corrige moi si je me trompe...)
Donc il faut non seulement que la fonction soit continue, mais en fait C-infini, sinon elle n'est pas calculable ?