Calculus×Computing
EN

Método de bisección

Nivel FundamentalDificultad ★★★★★Método⌖ Ver en el mapa

¿Qué es?

Mantén un intervalo en el que ff cambie de signo y pártelo por la mitad en cada paso. Lento (un bit por paso) pero imposible de romper: el teorema de Bolzano garantiza una raíz dentro. Es la búsqueda binaria sobre una función continua.

Fórmulas

m=a+b2,[a,b]←{[a,m]f(a)f(m)<0[m,b]f(a)f(m)≥0m = \frac{a + b}{2}, \qquad [a,b] \leftarrow \begin{cases}[a, m] & f(a)f(m) < 0 \\ [m, b] & f(a)f(m) \ge 0\end{cases}
∣xk−x∗∣≤b−a2k+1|x_k - x^\ast| \le \frac{b - a}{2^{k+1}}
error garantizado tras kk pasos

Aplicaciones en informática

  • Cálculo científico★★★★★frecuenteComputación científica y algoritmos

    Los resolvedores robustos (método de Brent) combinan la garantía de la bisección con pasos más rápidos.

  • Ray tracing (trazado de rayos)★★★★★frecuenteGráficos por computador

    Intersecar rayos con superficies implícitas o mapas de alturas a menudo horquilla el impacto y biseca.

  • Análisis de algoritmos y complejidad★★★★★indirectaComputación científica y algoritmos

    La misma idea que la búsqueda binaria (y git bisect): partir por la mitad da O(log⁡n)O(\log n) pasos.

¿Dónde se utiliza?

Temas de informática a los que se llega desde aquí, con la cadena de ideas que lleva a ellos:

λ Computación científica y algoritmos

3D Gráficos por computador

Ejercicios

1Cálculo directo

¿Cuántos pasos de bisección en [1,2][1, 2] garantizan 2\sqrt 2 con error menor que 10−610^{-6}?

Solución

2−(k+1)<10−6  ⟺  k+1>6log⁡210≈19,92^{-(k+1)} < 10^{-6} \iff k + 1 > 6\log_2 10 \approx 19{,}9: k=19k = 19 pasos.

Esta página tiene lo esencial. Un desarrollo más completo (intuición, definición formal, ejemplo resuelto) está en camino.

↑ ↓ para navegar · ↵ · Esc