Método de bisección

En matemáticas, el método de bisección es un método de búsqueda de raíces que se aplica a cualquier función continua para la cual se conocen dos valores con signos opuestos. El método consiste en bisecar repetidamente el intervalo definido por estos valores y luego seleccionar el subintervalo en el que la función cambia de signo, y por tanto debe contener una raíz. Es un método muy simple y robusto, pero también relativamente lento. Debido a esto, a menudo se utiliza para obtener una aproximación aproximada de una solución que luego se utiliza como punto de partida para métodos que convergen más rápidamente. El método también se denomina método de reducción a la mitad del intervalo, método de búsqueda binaria o método de dicotomía.

Para los polinomios, existen métodos más elaborados para probar la existencia de una raíz en un intervalo (regla de los signos de Descartes, teorema de Sturm, teorema de Budan). Permiten ampliar el método de bisección a algoritmos eficientes para encontrar todas las raíces reales de un polinomio; consulte Aislamiento de raíz real.

El método

El método es aplicable para resolver numéricamente la ecuación f(x) = 0 para la variable real x, donde f es una función continua definida en un intervalo [a, b] y donde f(a ) y f(b) tienen signos opuestos. En este caso se dice que a y b están entre paréntesis de una raíz ya que, según el teorema del valor intermedio, la función continua f debe tener al menos una raíz en el intervalo (a, b).

En cada paso, el método divide el intervalo en dos partes/mitades calculando el punto medio c = (a+b) / 2 del intervalo y el valor de la función f(c) en ese punto. Si c es una raíz, entonces el proceso se realizó correctamente y se detiene. De lo contrario, ahora sólo hay dos posibilidades: o f(a) y f(c) tienen signos opuestos y entre paréntesis una raíz, o f(c) y f(b) tienen signos opuestos y entre paréntesis una raíz . El método selecciona el subintervalo que se garantiza que será un paréntesis como nuevo intervalo que se utilizará en el siguiente paso. De esta manera, un intervalo que contiene un cero de f se reduce en ancho en un 50% en cada paso. El proceso continúa hasta que el intervalo sea suficientemente pequeño.

Explícitamente, si f(c)=0 entonces c puede tomarse como solución y el proceso se detiene. De lo contrario, si f(a) y f(c) tienen signos opuestos, entonces el método establece c como el nuevo valor para b, y si f(b) y f( c) tienen signos opuestos, entonces el método establece c como el nuevo a. En ambos casos, los nuevos f(a) y f(b) tienen signos opuestos, por lo que el método es aplicable a este intervalo más pequeño.

Tareas de iteración

La entrada para el método es una función continua f, un intervalo [a, b] y los valores de la función f(a) y f(b). Los valores de la función son de signo opuesto (hay al menos un cruce por cero dentro del intervalo). Cada iteración realiza estos pasos:

1. Cálculo c, el punto medio del intervalo, c = a + b/2.
2. Calcular el valor de la función en el punto medio, f()c).
3. Si la convergencia es satisfactoria (es decir, c - a es lo suficientemente pequeño, of()c) la vida es suficientemente pequeña, el regreso c y dejar de iterar.
4. Examinar el signo de f()c) y reemplazar (a, f()a) o (b, f()b) con (c, f()c)) para que haya un cruce cero dentro del nuevo intervalo. ME = bfe

Al implementar el método en una computadora, puede haber problemas con la precisión finita, por lo que a menudo hay pruebas de convergencia adicionales o límites al número de iteraciones. Aunque f es continua, la precisión finita puede impedir que el valor de una función sea cero. Por ejemplo, considere f(x) = cos x; no hay ningún valor de coma flotante que se aproxime a x = π/ 2 eso da exactamente cero. Además, la diferencia entre a y b está limitada por la precisión del punto flotante; es decir, a medida que la diferencia entre a y b disminuye, en algún momento el punto medio de [a, b] será numéricamente idéntico a (dentro de la precisión de punto flotante de) a o b.

Algoritmo

El método puede escribirse en pseudocódigo de la siguiente manera:

entrada: Función f,
valores de punto final a, b,
tolerancia TOL,
máximas NMAXcondiciones: a c) b,
o f()a) 0 y f()b) f()a) f()b) 0
Producto: valor que difiere de una raíz de f()x) = 0 por menos que TOLN ← 1
mientras N ≤ NMAX do // limitar las iteraciones para prevenir el bucle infinito c ←a + b)/2 // nuevo punto medio si f()c= 0 ob – a)/2 TOL entonces // solución encontradaProducto(s)c)
 Para. terminar si N ← N + 1 // aumento paso contador si signo(f()c) = signo(f()a) entonces a ← c más b ← c // nuevo intervaloterminar mientrasProducto("Method falló.") // Número máximo de pasos excedidos

Ejemplo: encontrar la raíz de un polinomio

Supongamos que se utiliza el método de bisección para encontrar la raíz del polinomio.

${\displaystyle f(x)=x^{3}-x-2\,}$

Primero, dos números ${\displaystyle a}$ y ${\displaystyle b}$ hay que encontrar tal ${\displaystyle f(a)}$ y ${\displaystyle f(b)}$ tienen señales opuestas. Para la función anterior, ${\displaystyle a=1}$ y ${\displaystyle b=2}$ satisfacer este criterio, como

${\displaystyle f(1)=(1)^{3}-(1)-2=-2}$

y

${\displaystyle f(2)=(2)^{3}-(2)-2=+4\,}$

Debido a que la función es continua, debe haber una raíz dentro del intervalo [1, 2].

En la primera iteración, los puntos finales del intervalo que entrelazan la raíz son ${\displaystyle A_{1}=1}$ y ${\displaystyle B_{1}=2}$, así que el punto medio es

${\displaystyle c_{1}={\frac {2+1}{2}=1.5}$

El valor de la función en el punto medio es ${\displaystyle f(c_{1})=(1.5)^{3}-(1.5)-2=-0.125}$. Porque... ${\displaystyle f(c_{1}}$ es negativo, ${\displaystyle a=1}$ es reemplazado por ${\displaystyle a=1.5}$ para la próxima iteración para asegurar que ${\displaystyle f(a)}$ y ${\displaystyle f(b)}$ tienen señales opuestas. Mientras esto continúa, el intervalo entre ${\displaystyle a}$ y ${\displaystyle b}$ se volverá cada vez más pequeño, convergendo en la raíz de la función. Vea esto sucede en la tabla de abajo.

Iteración	${\displaystyle a_{n}$	${\displaystyle B_{n}$	${\displaystyle c_{n}$	${\displaystyle f(c_{n}}$
1	1	2	1,5	−0.125
2	1,5	2	1.75	1.6093750
3	1,5	1.75	1.625	0,660156
4	1,5	1.625	1.5625	0.2521973
5	1,5	1.5625	1.5312500	0,0591125
6	1,5	1.5312500	1.5156250	0.0−340538
7	1.5156250	1.5312500	1.5234375	0,0122504
8	1.5156250	1.5234375	1.5195313	0.0−109712
9	1.5195313	1.5234375	1.5214844	0,0006222
10	1.5195313	1.5214844	1.5205078	0.00−51789
11	1.5205078	1.5214844	1.5209961	0.00−22794
12	1.5209961	1.5214844	1.5212402	0.00−08289
13	1.5212402	1.5214844	1.5213623	0,000-1034
14	1.5213623	1.5214844	1.5214233	0,0002594
15	1.5213623	1.5214233	1.5213928	0,0000780

Después de 13 iteraciones, se hace evidente que hay una convergencia hacia aproximadamente 1,521: una raíz del polinomio.

Análisis

Se garantiza que el método convergerá a una raíz de f si f es una función continua en el intervalo [a, b] y f(a) y f(b) tienen signos opuestos. El error absoluto se reduce a la mitad en cada paso, por lo que el método converge linealmente. Específicamente, si c₁ = a+b/2 es el punto medio del intervalo inicial, y c_n es el punto medio del intervalo en el nésimo paso, entonces la diferencia entre c_n y una solución c está limitada por

${\displaystyle Silencio. - ¿Qué?$

Esta fórmula se puede utilizar para determinar, de antemano, un límite superior en el número de iteraciones que el método de bisección necesita para converger a una raíz dentro de una cierta tolerancia. El número n de iteraciones necesarias para lograr una tolerancia requerida ε (es decir, un error garantizado como máximo ε), está limitado por

${\displaystyle n\leq n_{1/2}\equiv \left\lceil \log _{2}\left({\frac {\epsilon Está bien.$

donde el tamaño inicial del soporte ${\displaystyle \epsilon ¿Qué?$ y el tamaño requerido del corchete ${\displaystyle \epsilon \leq \epsilon _{0}$ La principal motivación para utilizar el método de bisección es que en el conjunto de funciones continuas, ningún otro método puede garantizar la producción de una estimación c_n a la solución c que en peor caso tiene una ${\displaystyle \epsilon }$ error absoluto con menos de n_1/2 iteraciones. Esto también es cierto en varias hipótesis comunes sobre la función f y el comportamiento de la función en el barrio de la raíz.

Sin embargo, a pesar de que el método de bisección es óptimo con respecto al peor desempeño del caso bajo criterios de error absoluto, es subóptimo con respecto al rendimiento promedio bajo supuestos estándar, así como al rendimiento asintótico. Alternativas populares al método de bisección, como el método de la secante, Ridders' El método o el método de Brent (entre otros), normalmente funcionan mejor ya que compensan el peor desempeño para lograr órdenes más altos de convergencia hacia la raíz. Y se puede lograr una mejora estricta del método de bisección con un orden de convergencia más alto sin tener que sacrificar el peor desempeño del método ITP.

Generalización a dimensiones superiores

El método de bisección se ha generalizado a funciones multidimensionales. Estos métodos se denominan métodos de bisección generalizados.

Métodos basados en el cálculo de grados

Algunos de estos métodos se basan en calcular el grado topológico.

Método de bisección característico

El método de bisección característica utiliza sólo los signos de una función en diferentes puntos. Deje que f sea una función de R^d a R^d, para algún entero d ≥ 2. A poliedro característico (también llamado polígono admisible) de f es un poliedro en R^d , que tiene 2^d vértices, de modo que en cada vértice v, la combinación de signos de f(v) es único. Por ejemplo, para d=2, un poliedro característico de f es un cuadrilátero con vértices (digamos) A,B,C,D, tal que:

• Signatura fA) = (-,-), es decir, f₁(A)₂(A) 0.
• Signatura f(B) = (-,+), es decir, f₁(B)₂(B) título0.
• Signatura f(C) = (+,-), es decir, f₁(C) título, f₂(C) 0.
• Signatura f(D) = (+,+), es decir, f₁(D) título, f₂(D) título0.

Una arista propia de un polígono característico es una arista entre un par de vértices, de modo que el vector de signo difiere en un solo signo. En el ejemplo anterior, los bordes propios del cuadrilátero característico son AB, AC, BD y CD. Una diagonal es un par de vértices, de modo que el vector de signos difiere en todos los signos d. En el ejemplo anterior, las diagonales son AD y BC.

En cada iteración, el algoritmo elige un borde adecuado del poliedro (por ejemplo, A--B) y calcula los signos de f en su punto medio (por ejemplo, M). Luego se procede de la siguiente manera:

• Si Sign f(M) = Sign(A), entonces A es reemplazado por M, y obtenemos un poliedro característico más pequeño.
• Si Sign f(M) = Sign(B), entonces B es reemplazado por M, y obtenemos un poliedro característico más pequeño.
• Else, escogemos un nuevo borde apropiado e intentamos de nuevo.

Suponga el diámetro (= longitud del borde apropiado más largo) de la característica original poliedro es ${\displaystyle D}$. Entonces, al menos ${\displaystyle \log _{2}(D/\varepsilon)}$ bisecciones de bordes se requieren para que el diámetro del polígono restante sea al máximo ${\displaystyle \varepsilon }$.