Necesito encontrar todas las raíces de una función escalar en un intervalo dado. La función puede tener discontinuidades. El algoritmo puede tener una precisión de ε (por ejemplo, está bien si el algoritmo no encuentra dos raíces distintas más cercanas que ε).
¿Existe tal algoritmo? ¿Podría señalarme documentos sobre eso?
En realidad, tengo una función para encontrar un cero en un intervalo dado usando el algoritmo de Brent, y una función para encontrar un mínimo en un intervalo dado. Usando esas dos funciones, construí mi propio algoritmo, pero me preguntaba si existe un algoritmo mejor. Mi algoritmo es así:
Comienzo con un intervalo [a,b]y una función f. Si sign(f(a+ε)) ≠ sign(f(b-ε)), sé que hay al menos un cero entre ay b, y lo encuentro z = zero(]a,b[). Compruebo si zrealmente es un cero (podría ser una discontinuidad), mirando el valor de z-εy z+ε. Si es así, lo agrego a la lista de ceros encontrados. Si f(a+ε)y f(b-ε)ambos son positivos, busco m = min(]a, b[). Si f(m)todavía es positivo, busco m = max(]a,b[)porque podría haber una discontinuidad entre ay b. Hago lo contrario si f(a+ε)y f(b-ε)fueran negativos.
Ahora, desde el punto en que encontré ( zo m) construyo una pila que contiene los ceros, las discontinuidades y los puntos de inflexión de mi función. Después de la primera iteración, ahora se ve la pila [a, z, b]. Comienzo nuevamente el algoritmo a partir de intervalos ]a,z[y ]z,b[. Cuando, entre dos puntos ay b, los extremos tienen el mismo signo que ambos extremos del intervalo, y no hay discontinuidades en ambos extremos, elimino el intervalo de la pila. El algoritmo termina cuando no hay más intervalos.
fuente
Respuestas:
Si está utilizando Matlab, puede probar el sistema Chebfun (descargo de responsabilidad: solía ser un desarrollador activo de este proyecto). Puede encontrar todas las raíces de una función unidimensional en un intervalo cerrado o abierto para la precisión de la máquina.
La idea principal detrás del buscador de raíces Chebfun es usar una combinación de bisección recursiva y Colleague Matrix, un análogo de Companion Matrix , en los coeficientes de un interpolante de la función objetivo.
Tengo una versión simplificada del código aquí . La función
chebrootstoma una función anónima como su primera entrada, el intervalo finito como segundo y tercer argumento, y un gradoNcomo cuarto y último argumento. Para obtener resultados razonables, se puede establecerNa100.fuente
En general, esta es una búsqueda desesperada: sin alguna información sobre la continuidad y / o diferenciabilidad de la función, cualquier cosa podría suceder. Considere, por ejemplo, la función MATLAB definida en el intervalo de 0 a 1:
función y = f (x)
y = 1.0;
si (x == 0.01)
y = 0.0;
final
si (x == 0.013)
y = 0.0;
final
si (x == 0.753124)
y = 0.0;
final
Al tratar esta función como un cuadro de bloque, no hay forma de ver que tiene ceros en estos tres puntos y ningún otro punto en el intervalo de 0 a 1 sin verificar cada número de coma flotante entre 0 y 1.
fuente