¿Es posible que el método de bisección proporcione ceros "falsos"

Question

He leído sobre el método de bisección para encontrar las raíces de una función en mi libro de texto de análisis numérico y me ha surgido una pregunta.

Dada una función relativamente complicada, las posibilidades de encontrar la raíz exacta (es decir, una raíz que esté completamente representada en la memoria del ordenador, con todas las cifras significativas) son muy bajas. Esto significa que la mayoría de las veces, tendremos un valor para el que la función está muy cerca, pero no es exactamente igual a cero.

Entonces, ¿qué pasaría si la función tuviera una raíz, y otro valor en el que la función se acerca mucho a cero, sin llegar a él? ¿Fallaría el algoritmo? ¿Y cuál es el significado de esa eventual raíz "falsa"; tiene algún valor?

Gracias.

EDIT: aquí hay una imagen que muestra lo que quería decir

Answer 1

El método de bisección sólo se preocupa si la función cambia de signo, por lo que pasa directamente por la raíz "falsa" sin darse cuenta.

Si los coeficientes tienen un ligero error, tal vez la raíz "falsa" debería haber sido una raíz.

Answer 2

Hay que tener en cuenta que el método de bisección encuentra un punto con un cambio de signo en los valores del evaluación numérica de su función. Debido a la cancelación catastrófica que es inevitable para obtener valores pequeños cerca de una raíz, esto puede dar errores amplios incluso para raíces simples. Tomemos por ejemplo el polinomio de Wilkinson reescalado $p(x)=\prod_{k=1}^{20}(x-k/10)$ en doble precisión de coma flotante, después de multiplicarlo como $x^{20}-21x^{19}+a_{18}x^{18}+...+a_1x+a_0$ . Alrededor de la raíz $x=1.9$ la evaluación numérica de una muestra mayor de puntos da esta imagen

de modo que, dependiendo del intervalo inicial, el método de bisección puede terminar en cualquier punto entre $1.8999$ y $1.9003$

---

Para poner esto en perspectiva, la escala $\bar p(x)=|x|^n+|a_{n-1}|\,|x|^{n-1}+..+|a_1|\,|x|+|a_0|$ para esta situación, la evaluación polinómica para $|x|\le 2$ es proporcionada por el límite $\bar p(2)=p(-2)=3.35367..\cdot 10^9$ para que el límite de precisión esperado $\bar p(1.9)\mu$ utilizando una constante de la máquina $\mu=210^{-16}$ se trata, en efecto, de $710^{-7}$ Los errores observados son un poco menores.

Answer 3

Siempre que se evalúe $f\left(\frac {a+b}2\right)$ a algo mayor que cero, el método funcionará bien. Reemplazará $a$ con $\frac {a+b}2$ como el extremo izquierdo del intervalo. El criterio de terminación habitual para la bisección y otros enfoques de horquillado es la longitud del intervalo, no el valor de la función. Seguiría adelante, sabiendo que hay una raíz en algún lugar del intervalo porque los valores de la función en los extremos tienen signos opuestos.

Answer 4

Supongamos que utilizamos un ordenador que tiene $N$ -precisión de bits ( $N\geq4$ ). Si tomamos un número entero cualquiera $n > N$ y aplicamos el algoritmo de bisección a la función $f$ definido en $[0,1]$ por $f(x)=\left(x-\frac12\right)^2\left(x-\frac34\right)-2^{-n}$ entonces el algoritmo dará como resultado $x=\frac12$ como el punto donde $f$ tiene una raíz. Esto se debe a que $f(0)=-\frac3{16}-2^{-n}<0$ , $f(1)=\frac1{16}-2^{-n}>0$ y nuestro ordenador no es capaz de distinguir $\,f\left(\frac12\right)=-2^{-n}$ de cero.

Aquí tenemos un gráfico de nuestra función $f$ si tomamos $n=10$ :

No obstante el resultado de aplicar el algoritmo de bisección a $f$ en $[0,1]$ podemos ver que el único cero de $f$ en $[0,1]$ se encuentra en algún lugar entre $\frac34$ y $1$ .

---

En cuanto al significado de dicha raíz "falsa", yo diría que alude al hecho de que el Teorema del Valor Intermedio es equivalente a la proposición no constructiva conocida como principio menos limitado de la omnisciencia .

Definir una secuencia binaria $\{a_n\}_{n=1}^\infty$ por \begin{equation}a_n=\begin{cases}0 &\text{ iff either } 2k+3 \text{ is the sum of 3 primes for all } k\leq n \text{ or there exists } k<n \text{ s.t. } a_k=1 \\1&\text{ otherwise.}\end{cases} \end{equation} Definir $a=\sum_{n=1}^\infty a_n2^{-n}$ y aplicar el algoritmo de bisección a la función $f$ definido en $[0,1]$ por $f(x)=\left(x-\frac12\right)^2\left(x-\frac34\right)-a$ . Mientras nuestro cálculo esté limitado a una precisión finita, el algoritmo dará como resultado $x=\frac12$ como raíz de $f$ . Esta salida es correcta (lo que entiendo como que es idéntica o aproximadamente cercana a una raíz) si y sólo si la conjetura de impar Goldbach es verdadera.

La forma en que la secuencia binaria $\{a_n\}_{n=1}^\infty$ está definida para invocar el principio limitado de omnisciencia Un principio no constructivo que implica el principio menos limitado de la omnisciencia.

---

Descargo de responsabilidad (en respuesta a las válidas preocupaciones planteadas por Euro Micelli): Mi "respuesta" no trata de proporcionar una afirmación de la pregunta del título, ya que yo diría que la respuesta a la pregunta planteada en el título es "no es sí". Observaré que incluso la precisión arbitraria sigue estando sujeta a la memoria disponible y al tiempo de cálculo (hasta donde yo sé). Me imagino que tenemos dos caras de la misma moneda, el método de bisección no es constructivo y también lo es la definición de la función $f$ en $[0,1]$ . De hecho, hay formas de evitar esa salida falsa, y mi respuesta sólo ha tenido en cuenta el algoritmo subyacente a la demostración del Teorema del Valor Intermedio en el entorno más clásico y básico. Yo respondo a las preguntas en este foro tratando de proporcionar al autor de la pregunta alguna visión y perspectiva, según mi mejor conocimiento, dado el contenido de su mensaje inicial.