Puede métodos numéricos ser usado para probar una raíz que NO existe?

Question

Digamos que tengo una función continua $f : I \to \mathbb R$ $I = [a,b]$ y quiero decidir si tiene una raíz o no en $I$. Pretender que puedo evaluar en cualquier lugar, pero no puede usar los métodos analíticos para aprender algo más sobre él.

Yo podría obtener una cuadrícula de puntos de $a = p_1 < \dots < p_n = b$, evaluar $f$ en cada punto, y hacer un diagrama de dispersión con algún tipo de interpolación. A partir de esto puedo encontrar una raíz, pero si no veo una raíz puedo estar nunca seguro de que en realidad no existe? Yo puedo saber que no hay comportamiento salvaje entre algún par de puntos que me perdí? Por ejemplo tal vez para algunos $i$ la función se sumerge por debajo de $0$ muy rápidamente después de $p_i$ y devuelve a la derecha antes de $p_{i+1}$, por lo que se ve plano, pero sólo porque me he perdido algo.

Mi pregunta: ¿cuáles son las circunstancias bajo las cuales se puede utilizar un número finito de precisión finita función de las evaluaciones para demostrar una raíz ¿ no existen?

Mi conjetura es que si $f$ es de Lipschitz, entonces podríamos usar su constante de Lipschitz $K$ hacer nuestra red lo suficientemente fina que no hay manera de que $f$ podría tener una raíz entre pares de puntos de la malla si no visiblemente tener uno en la interpolados diagrama de dispersión. Pero si $K$ es grande o $f$ está realmente cerca de la $0$, entonces podemos tener una situación en la que la red es necesario para ser más fino de precisión finita puede hacer.

También me pregunto si convexidad haría el truco (que ya es más fuerte que la de Lipschitz en $I$ parece como una cosa natural para tratar la siguiente).

Answer 1

Esto me recuerda Kahan de espionaje de la función, lo que demuestra que no hay ningún algoritmo determinista que puede integrar todas las funciones de forma numérica. Podemos aplicar la misma idea a raíz de la existencia de rutina. Considere una función spy, que simplemente registra su entrada. Pasar a su rutina. Ahora utilice el registro producido por spy crear una función continua malicious que utiliza los puntos a (digamos) evaluar siempre a 1 en la red, sin embargo, aún tiene una raíz. Un $C^{\infty}[a, b]$ ejemplo sería el de una invertida de la protuberancia de la función de escala para que se ajuste entre cada par de nodos de la cuadrícula y de la inmersión bajo $0$ en el pico. Estoy seguro de que usted también podría construir una potencia de la serie, que funciona como un adecuado malicious como bueno.

Ahora digamos que usted use un conjunto aleatorio de los nodos. El uso de cualquiera de las secuencias divergentes que se aproximan a la función delta de Dirac (delta de la secuencia), truncar la serie (por lo que cumple con lo que la regularidad criterio desea) y coloque el pico en un punto aleatorio. Ahora usted tiene algunas muy baja probabilidad de que su raíz existencia rutina de encontrar un positivo y un valor negativo de su función, lo que significa, por supuesto, de que no puede probar nada.

Answer 2

En aritmética exacta, una forma de hacer esto es para obtener un módulo de continuidad $\omega_f$. Esto es (no de forma exclusiva), definido por la propiedad de que si $|x-y|<\omega_f(x,\epsilon)$$|f(x)-f(y)|<\epsilon$. (Por supuesto, hay un máximo de $\omega_f$, pero que rara vez lo tienes en la mano.)

Supongamos que usted tiene un $\omega_f$ y evalúe $f$ en algunos puntos de $x_i$. Si $|x_i-x_{i+1}|<\omega_f(x_i,|f(x_i)|)$ todos los $i$, $f$ no tiene ningún cero en el intervalo.

En la inexactitud de la aritmética, se puede hacer algo similar, sólo se necesita exigir que los valores aproximados de $f$ a estar delimitado un poco más alejado de cero, dependiendo de su nivel de precisión.