← Volver a los ejercicios

bisección: el intervalo que encierra la respuesta

La misma jugada de la búsqueda binaria, ahora sin arreglo: una función monótona, un intervalo que se parte a la mitad y un valor que nunca puede escaparse de él. Como sobre los reales no hay igualdad exacta, la salida trae una promesa distinta: un error acotado.

1. Antes de ejecutar, prediga

Función y objetivo:
¿Cuántas vueltas hasta que el intervalo mida menos que ε?

2. Ejecute y mire el intervalo cerrarse

Paso 0 de 0
La barra azul es lo que queda vivo del intervalo original; la marca roja, la mitad que se está evaluando. Fíjese en el pie: la desigualdad f(a) ≤ v ≤ f(b) se cumple en todas las vueltas, aunque el intervalo se encoja.

3. La traza, vuelta por vuelta

[a, b]mitadf(mitad)Decisión

4. Los dos invariantes del while

Al comenzar cada vuelta, ¿qué es siempre cierto de los extremos? (ese será I₁)

¿Y las cotas del intervalo? (ese será I₀; a′ y b′ son los extremos originales)

5. La demostración

Encuentre primero los dos invariantes en la tarjeta 4. El teorema a demostrar: Teorema 1 — los invariantes I₀ e I₁ se cumplen.

Inicialización
Antes de la primera vuelta a = a′ y b = b′. Para I₀: a′ ≤ a′ ≤ b′ ≤ b′, donde la del medio vale porque [a′, b′] es un intervalo. ✓  Para I₁, sustituyendo queda f(a′) ≤ v ≤ f(b′), que es exactamente la precondición del problema. ✓
Estabilidad
Vuelta arbitraria: como el cuerpo se ejecuta, b − a > ε > 0, luego a < b y por lo tanto a < mitad < b. La comparación abre dos casos.

Si f(mitad) < v, la línea 4 deja a = mitad: I₀ pide a′ ≤ mitad ≤ b ≤ b′, que sale de a′ ≤ a < mitad < b ≤ b′; e I₁ pide f(mitad) ≤ v ≤ f(b), donde la izquierda es el caso mismo y la derecha es la que se asumió, porque b no cambió. ✓

Si f(mitad) ≥ v, la línea 5 deja b = mitad, y es simétrico: I₁ pide f(a) ≤ v ≤ f(mitad), con la izquierda asumida (a no cambió) y la derecha dada por el caso. ✓
Terminación
Cada vuelta deja el ancho en exactamente la mitad: de b − a pasa a mitad − a o a b − mitad, y los dos valen (b−a)/2. Tras k vueltas el ancho es (b′ − a′)/2^k, que baja de cualquier ε > 0: el ciclo termina, y lo hace en ⌈log₂((b′−a′)/ε)⌉ vueltas.

Al salir, la condición b − a > ε es falsa, o sea b − a ≤ ε; e I₀ da a ≤ b, o sea b − a ≥ 0. Intersectando: 0 ≤ b − a ≤ ε. E I₁ sigue diciendo f(a) ≤ v ≤ f(b), así que por el teorema del valor intermedio hay una solución dentro del intervalo final. ∎
Teorema 2. La invocación biseccion(v, a, b, eps) sobre una f continua y creciente con f(a) ≤ v ≤ f(b) produce un x̂ que dista a lo sumo ε/2 de una solución de f(x) = v.  Demostración: es trivial a partir de la correctitud de I₀ e I₁: la terminación deja un intervalo de ancho a lo sumo ε que sigue encerrando a v, y el valor de la línea 6 es su centro. ∎

6. ¿Qué promete la salida?

Al terminar, el algoritmo devuelve el centro del intervalo. ¿Qué se puede afirmar de ese número?

7. La trampa

Suponga que llama biseccion(50, 0, 3, 1e-6) con f(x) = x³ + x, donde f(3) = 30 < 50. ¿Qué pasa?