J'ai besoin de trouver toutes les racines d'une fonction scalaire dans un intervalle donné. La fonction peut présenter des discontinuités. L'algorithme peut avoir une précision de ε (par exemple, c'est correct si l'algorithme ne trouve pas deux racines distinctes plus proches que ε).
Un tel algorithme existe-t-il? Pourriez-vous me signaler des articles à ce sujet?
En fait, j'ai une fonction pour trouver un zéro dans un intervalle donné en utilisant l'algorithme de Brent, et une fonction pour trouver un minimum dans un intervalle donné. En utilisant ces deux fonctions, j'ai construit mon propre algorithme, mais je me demandais s'il existait un meilleur algorithme. Mon algorithme est comme ça:
Je commence par un intervalle [a,b]et une fonction f. Si sign(f(a+ε)) ≠ sign(f(b-ε)), je sais qu'il y a au moins un zéro entre aet b, et je trouve z = zero(]a,b[). Je teste si c'est zvraiment un zéro (ça pourrait être une discontinuité), en regardant la valeur de z-εet z+ε. Si c'est le cas, je l'ajoute à la liste des zéros trouvés. Si f(a+ε)et les f(b-ε)deux sont positifs, je cherche m = min(]a, b[). Si c'est f(m)toujours positif, je recherche m = max(]a,b[)car il pourrait y avoir une discontinuité entre aet b. Je fais le contraire si f(a+ε)et f(b-ε)étaient négatifs.
Maintenant, à partir du point que j'ai trouvé ( zou m) je construis une pile contenant les zéros, les discontinuités et les points d'inflexion de ma fonction. Après la première itération, la pile ressemble maintenant [a, z, b]. Je recommence l'algorithme à partir des intervalles ]a,z[et ]z,b[. Lorsque, entre deux points aet b, les extrema ont le même signe que les deux extrémités d'intervalle, et qu'il n'y a pas de discontinuités aux deux extrema, je supprime l'intervalle de la pile. L'algorithme se termine lorsqu'il n'y a plus d'intervalles.
la source
Réponses:
Si vous utilisez Matlab, vous voudrez peut-être essayer le système Chebfun (avertissement: j'étais un développeur actif de ce projet). Il peut trouver toutes les racines d'une fonction unidimensionnelle dans un intervalle fermé ou ouvert à la précision de la machine.
L'idée principale derrière le chercheur de racines Chebfun est d'utiliser une combinaison de bissection récursive et de la matrice des collègues, un analogue de la matrice des compagnons , sur les coefficients d'un interpolant de la fonction cible.
J'ai une version simplifiée du code ici . La fonction
chebrootsprend une fonction anonyme comme première entrée, l'intervalle fini comme deuxième et troisième argument, et un degréNcomme quatrième et dernier argument. Pour des résultats raisonnables, vous pouvez définirNsur100.la source
En général, c'est une quête désespérée - sans quelques informations sur la continuité et / ou la différentiabilité de la fonction, tout pourrait arriver. Considérons par exemple la fonction MATLAB définie sur l'intervalle de 0 à 1:
fonction y = f (x)
y = 1,0;
si (x == 0,01)
y = 0,0;
fin
si (x == 0,013)
y = 0,0;
fin
si (x == 0,753124)
y = 0,0;
fin
En traitant cette fonction comme une zone de bloc, il n'y a aucun moyen de voir qu'elle a des zéros à ces trois points et aucun autre point dans l'intervalle de 0 à 1 sans vérifier chaque nombre à virgule flottante entre 0 et 1.
la source