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]
mitad
f(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?