Classe des problèmes algorithmiques

[invite75a796c1]

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?

parce que le pré supposé de la méthode était :

si vous savez trouver les zéros de f

je disais bien que je ce que j'ajoutais était trivial.

Mais par ailleurs, qui saurait résoudre par une méthode numérique économe une équation quelconque sans aucune info ( continue, dérivable , bornes des dérivées , combien de fois , etc ) ? Analytiquement, c'est encore plus difficile en dehors des cas d'école ...

@ ABN84 :
Le mieux serait d'en savoir plus sur les fonctions à traiter , même en simplifiant.
Et si ce ne sont pas des fonctions , il faut reposer la question car elle ne serait pas claire
-----

[invitea726d297]

Bonjour,
On pourrait envisager une méthode graphique.
On crée un tableau dont la dimension est le nombre de variables, c'est à dire au moins 2. On suppose que l'on connaisse les limites de l'étude. Ce tableau sera en quelque sorte un raster à n dimensions.
Par une simple itération on renseigne le tableau.
La représentation de la fonction est celle de la frontière de changement de signe.
Donc, à partir d'un point quelconque on peut déterminer les 2*n bornes de non-changement de signe.
Par un étude locale, type Newton, on pourra affiner la valeur numérique des bornes.

[invite179e6258]

mais justement je ne suis pas sûr qu'il existe des algorithmes permettant de trouver à coup sûr tous les zéros d'une fonction. Si c'est un polynôme on connaît le nombre maximal de zéros et on peut par des minorations connaître un intervalle compact qui contienne tous les zéros, mais autrement c e n'est pas simple. Pense à la fonction x -> sin(1/x) qui est continue sur x>0, je ne vois pas comment un algorithme numérique pourrait trouver tous les zéros (en un temps fini)

[obi76]

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

Imaginons que vous preniez un intervalle ([0 1]) dans lequel il y a 3 racines, la fonction est positive en 0. Dans ce cas, en 0 vous avez un "+" et en 1 vous pouvez avoir un "-", vote technique permettra de dire "dans cet intervalle, il y a un zéro" et vous n'en trouverez qu'un sur les 3...

[obi76]

Pense à la fonction x -> sin(1/x) qui est continue sur x>0, je ne vois pas comment un algorithme numérique pourrait trouver tous les zéros (en un temps fini)

un algorithme qui trouve une infinité de solutions, ça me parait difficile...

[invite75a796c1]

Ah, nouvelle information : Il s'agit de fonctions de plusieurs variables

J'avais trop vite lu ... c'est vous qui avez raison, il s'agit de fonction multi variables

Toujours à condition de savoir trouver tous les 0 ( des couples ) : c'est juste beaucoup plus compliqué mais l'idée est la même.
Au lieu de partitionner un segment, ce sera un plan ou plus, puis faire un crible partition par partition

( nos messages se croisent )

[invite75a796c1]

Imaginons que vous preniez un intervalle ([0 1]) dans lequel il y a 3 racines, la fonction est positive en 0. Dans ce cas, en 0 vous avez un "+" et en 1 vous pouvez avoir un "-", vote technique permettra de dire "dans cet intervalle, il y a un zéro" et vous n'en trouverez qu'un sur les 3...

où est la 3ème racine ? avec 3 racines, il y a 4 intervales, fussent il réduits à 1 point.

je ne suis pas sûr que nous parlions de la même chose... à ce stade de la conversation, f était une fonction de x seul et tous ses zéros de l'intervalle de départ étaient connus

[obi76]

où est la 3ème racine ? avec 3 racines, il y a 4 intervales, fussent il réduits à 1 point.

je ne suis pas sûr que nous parlions de la même chose... à ce stade de la conversation, f était une fonction de x seul et tous ses zéros de l'intervalle de départ étaient connus

je commence à me poser la question effectivement...

pour un algorithme qui trouve tous les 0, il faut nécessairement trouver des intervalles, chacun ne contenant qu'un seul zéro. Comment faites-vous pour certifier que chaque intervalle n'a qu'un seul zéro ?

[invitea726d297]

Pour argumenter mon hypothèse, je vais prendre un exemple.
En matière de CAO, il est nécessaire de savoir si tel point est à l'intérieur d'une zone. On connait le contour de la zone et la convention de sens de rotation. En d'autres termes, la description de la zone peut être très compliquée, avoir des trous etc.
Si on veut dessiner la ligne, éventuellement constituée de segments disjoints, qui appartient à une zone, on se trouve dans cette situation.
Certes, c'est problème assez difficile, mais parfaitement résolu.

[invite75a796c1]

Comment faites-vous pour certifier que chaque intervalle n'a qu'un seul zéro ?

c'est tautologique : les bornes sont les zéros ( que j'ai peut être hativement considérés en nombre fini )

Bien sûr, la difficulté première est de savoir les zéros.

Il faudrait reformuler la question avec plus d'infos sur la fonction et l'ensemble de départ.

[gg0]

Comment faites-vous pour certifier que chaque intervalle n'a qu'un seul zéro ?

Par exemple en montrant que la fonction est strictement croissante sur l'intervalle qui contient le 0.
Inapplicable pour sin(1/x) sur ]0;a[.

Bon, tant que ABN84 ne réduit pas le domaine, on parle en l'air !

Cordialement.