Método de bisección

Algoritmo para encontrar el cero de una función

Algunos pasos del método de bisección aplicados sobre el rango inicial [a ₁ ;b ₁ ]. El punto rojo más grande es la raíz de la funció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 que 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 lo tanto, debe contener una raíz . Es un método muy simple y robusto, pero también es relativamente lento. Debido a esto, a menudo se utiliza para obtener una aproximación aproximada a una solución que luego se utiliza como punto de partida para métodos de convergencia más rápida. ^[1] El método también se llama método de división por la mitad del intervalo , ^[2] método de búsqueda binaria , ^[3] o método de dicotomía . ^[4]

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

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 encierran una raíz ya que, por 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 en sí es una raíz, entonces el proceso ha tenido éxito y se detiene. De lo contrario, ahora solo hay dos posibilidades: o f ( a ) y f ( c ) tienen signos opuestos y encierran una raíz, o f ( c ) y f ( b ) tienen signos opuestos y encierran una raíz. ^[5] El método selecciona el subintervalo que se garantiza que es un corchete como el 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 la 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. ^[6]

Tareas de iteración

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

1. Calcular 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 suficientemente pequeño, o | f ( c )| es suficientemente pequeño), devuelve c y deja de iterar.
4. Examine el signo de f ( c ) y reemplace ( a , f ( a )) o ( b , f ( b )) con ( c , f ( c )) de modo que haya un cruce por cero dentro del nuevo intervalo.

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 un valor de función sea cero. Por ejemplo, considere f ( x ) = cos x ; no hay ningún valor de punto flotante que se aproxime a x = π /2 que dé exactamente cero. Además, la diferencia entre a y b está limitada por la precisión de punto flotante; es decir, a medida que la diferencia entre a y b disminuye, en algún punto 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: ^[7]

entrada: Función f , valores de punto final a , b , tolerancia TOL , iteraciones máximas NMAX condiciones:  a < b , o bien f ( a ) < 0 y f ( b ) > 0 o bien f ( a ) > 0 y f ( b ) < 0 resultado: valor que difiere de una raíz de f ( x ) = 0 en menos de TOL N ← 1 while  N ≤ NMAX  do  // limitar iteraciones para evitar un bucle infinito  c ← ( a + b )/2 // nuevo punto medio  if  f ( c ) = 0 or ( b – a )/2 < TOL  then  // solución encontrada Output( c ) Stop  end if  N ← N + 1 // incrementar contador de pasos  if sign( f ( c )) = sign( f ( a )) then  a ← c  else  b ← c  // nuevo intervalo end while
Output("Método fallido.") // número máximo de pasos excedido

Ejemplo: Encontrar la raíz de un polinomio

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

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

En primer lugar, se deben encontrar dos números y de manera que y tengan signos opuestos. Para la función anterior, y satisfacen este criterio, como ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle f(a)}$ ${\displaystyle f(b)}$ ${\displaystyle a=1}$ ${\displaystyle b=2}$

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

y

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

Como 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 encierra la raíz son y , por lo que el punto medio es ${\displaystyle a_{1}=1}$ ${\displaystyle b_{1}=2}$

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

El valor de la función en el punto medio es . Como es negativo, se reemplaza por en la siguiente iteración para garantizar que y tengan signos opuestos. A medida que esto continúa, el intervalo entre y se hará cada vez más pequeño, convergiendo en la raíz de la función. Vea cómo sucede esto en la tabla a continuación. ${\displaystyle f(c_{1})=(1.5)^{3}-(1.5)-2=-0.125}$ ${\displaystyle f(c_{1})}$ ${\displaystyle a=1}$ ${\displaystyle a=1.5}$ ${\displaystyle f(a)}$ ${\displaystyle f(b)}$ ${\displaystyle a}$ ${\displaystyle b}$

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á acotada por ^[8]

${\displaystyle |c_{n}-c|\leq {\frac {|b-a|}{2^{n}}}.}$

Esta fórmula se puede utilizar para determinar, de antemano, un límite superior para 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 _{0}}{\epsilon }}\right)\right\rceil ,}$

donde el tamaño del corchete inicial y el tamaño del corchete requerido La principal motivación para utilizar el método de bisección es que sobre el conjunto de funciones continuas, ningún otro método puede garantizar producir una estimación c _n para la solución c que en el peor de los casos tiene un error absoluto con menos de n _1/2 iteraciones. ^[9] Esto también es cierto bajo varios supuestos comunes sobre la función f y el comportamiento de la función en la vecindad de la raíz. ^{[9] [10]} ${\displaystyle \epsilon _{0}=|b-a|}$ ${\displaystyle \epsilon \leq \epsilon _{0}.}$ ${\displaystyle \epsilon }$

Sin embargo, a pesar de que el método de bisección es óptimo con respecto al peor desempeño en el caso bajo criterios de error absoluto, es subóptimo con respecto al desempeño promedio bajo supuestos estándar ^{[11] [12]} así como al desempeño asintótico . ^[13] Las alternativas populares al método de bisección, como el método secante , el método de Ridders o el método de Brent (entre otros), generalmente funcionan mejor ya que compensan el peor desempeño en el caso para lograr órdenes más altos de convergencia a la raíz. Y, se puede lograr una mejora estricta del método de bisección con un orden más alto de convergencia sin sacrificar el desempeño en el peor caso con el método ITP . ^{[13] [14]}

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 . ^{[15] [16]}

Métodos basados ​​en el cálculo de grados

Algunos de estos métodos se basan en el cálculo del grado topológico , que para una región acotada y una función diferenciable se define como una suma sobre sus raíces: ${\displaystyle \Omega \subseteq \mathbb {R} ^{n}}$ ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}$

${\displaystyle \deg(f,\Omega ):=\sum _{y\in f^{-1}(\mathbf {0} )}\operatorname {sgn} \det(Df(y))}$,

¿Dónde está la matriz jacobiana , , y ${\displaystyle Df(y)}$ ${\displaystyle \mathbf {0} =(0,0,...,0)^{T}}$

${\displaystyle \operatorname {sgn}(x)={\begin{cases}1,&x>0\\0,&x=0\\-1,&x<0\\\end{cases}}}$

es la función signo . ^[17] Para que exista una raíz, es suficiente que , y esto se puede verificar utilizando una integral de superficie sobre el límite de . ^[18] ${\displaystyle \deg(f,\Omega )\neq 0}$ ${\displaystyle \Omega }$

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. Sea f una función de R ^d a R ^d , para algún entero d ≥ 2. Un poliedro característico ^[19] (también llamado polígono admisible ) ^[20] de f es un politopo en R ^d , que tiene 2 ^d vértices, tales que en cada vértice v , la combinación de signos de f ( v ) es única y el grado topológico de f en su interior no es cero (criterio necesario para asegurar la existencia de una raíz). ^[21] Por ejemplo, para d = 2, un poliedro característico de f es un cuadrilátero con vértices (digamos) A,B,C,D, tales que:

• ⁠ ⁠ ${\displaystyle \operatorname {sgn} f(A)=(-,-)}$ , es decir, f ₁ (A)<0, f ₂ (A)<0.
• ⁠ ⁠ ${\displaystyle \operatorname {sgn} f(B)=(-,+)}$ , es decir, f ₁ (B)<0, f ₂ (B)>0.
• ⁠ ⁠ ${\displaystyle \operatorname {sgn} f(C)=(+,-)}$ , es decir, f ₁ (C)>0, f ₂ (C)<0.
• ⁠ ⁠ ${\displaystyle \operatorname {sgn} f(D)=(+,+)}$ , es decir, f ₁ (D)>0, f ₂ (D)>0.

Una arista propia de un polígono característico es una arista entre un par de vértices, de modo que el vector de signos difiere en un solo signo. En el ejemplo anterior, las aristas propias 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 una arista propia del poliedro (por ejemplo, A—B) y calcula los signos de f en su punto medio (por ejemplo, M). Luego procede de la siguiente manera:

• Si ⁠ ⁠ ${\displaystyle \operatorname {sgn} f(M)=\operatorname {sgn}(A)}$ , entonces A se reemplaza por M, y obtenemos un poliedro característico más pequeño.
• Si ⁠ ⁠ ${\displaystyle \operatorname {sgn} f(M)=\operatorname {sgn}(B)}$ , entonces B se reemplaza por M, y obtenemos un poliedro característico más pequeño.
• De lo contrario, elegimos un nuevo borde adecuado y lo intentamos nuevamente.

Supóngase que el diámetro (= longitud de la arista propia más larga) del poliedro característico original es D . Entonces, se requieren al menos bisecciones de aristas para que el diámetro del polígono restante sea como máximo ε . ^{[20] : 11, Lema 4.7} Si el grado topológico del poliedro inicial no es cero, entonces existe un procedimiento que puede elegir una arista tal que el siguiente poliedro también tenga un grado distinto de cero. ^{[21] [22]} ${\displaystyle \log _{2}(D/\varepsilon )}$

Véase también

• Algoritmo de búsqueda binaria
• Algoritmo de Lehmer-Schur , generalización del método de bisección en el plano complejo
• Intervalos anidados

Referencias

1. Burden y Faires 1985, pág. 31
2. "Reducción a la mitad del intervalo (bisección)". Archivado desde el original el 19 de mayo de 2013. Consultado el 7 de noviembre de 2013 .
3. Burden y Faires 1985, pág. 28
4. "Método de dicotomía - Enciclopedia de Matemáticas" www.encyclopediaofmath.org . Consultado el 21 de diciembre de 2015 .
5. Si la función tiene el mismo signo en los puntos finales de un intervalo, los puntos finales pueden o no encerrar raíces de la función.
6. Burden & Faires 1985, pág. 28 para la sección
7. Burden & Faires 1985, pág. 29. Esta versión vuelve a calcular los valores de la función en cada iteración en lugar de trasladarlos a las siguientes iteraciones.
8. Carga y ferias 1985, pág. 31, Teorema 2.1
9. Sikorski, K. (1 de febrero de 1982). "La bisección es óptima". Matemática numérica . 40 (1): 111-117. doi :10.1007/BF01459080. ISSN  0945-3245. S2CID  119952605.
10. Sikorski, K (1985-12-01). "Solución óptima de ecuaciones no lineales". Journal of Complexity . 1 (2): 197–209. doi :10.1016/0885-064X(85)90011-1. ISSN  0885-064X.
11. Graf, Sigfrido; Novak, Erich; Papageorgiou, Anargyros (1 de julio de 1989). "La bisección no es óptima en promedio". Matemática numérica . 55 (4): 481–491. doi :10.1007/BF01396051. ISSN  0945-3245. S2CID  119546369.
12. Novak, Erich (1989-12-01). "Resultados de caso promedio para hallazgo de cero". Journal of Complexity . 5 (4): 489–501. doi : 10.1016/0885-064X(89)90022-8 . ISSN  0885-064X.
13. Oliveira, IFD; Takahashi, RHC (6 de diciembre de 2020). "Una mejora del rendimiento promedio del método de bisección preservando la optimalidad de Minmax". ACM Transactions on Mathematical Software . 47 (1): 5:1–5:24. doi :10.1145/3423597. ISSN  0098-3500. S2CID  230586635.
14. Ivo, Oliveira (14 de diciembre de 2020). "Un método de bisección mejorado". doi :10.1145/3423597. S2CID  230586635.
15. Mourrain, B.; Vrahatis, MN; Yakoubsohn, JC (1 de junio de 2002). "Sobre la complejidad de aislar raíces reales y calcular con certeza el grado topológico". Journal of Complexity . 18 (2): 612–640. doi : 10.1006/jcom.2001.0636 . ISSN  0885-064X.
16. Vrahatis, Michael N. (2020). "Generalizaciones del teorema del valor intermedio para aproximar puntos fijos y ceros de funciones continuas". En Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.). Cálculos numéricos: teoría y algoritmos . Apuntes de clase en informática. Vol. 11974. Cham: Springer International Publishing. págs. 223–238. doi :10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5.S2CID211160947  .​
17. Polymilis, C.; Servizi, G.; Turchetti, G.; Skokos, Ch.; Vrahatis, MN (mayo de 2003). "LOCALIZACIÓN DE ÓRBITAS PERIÓDICAS MEDIANTE LA TEORÍA DE GRADOS TOPOLÓGICOS". Libration Point Orbits and Applications : 665–676. arXiv : nlin/0211044 . doi :10.1142/9789812704849_0031.
18. Kearfott, Baker (1 de junio de 1979). "Un método eficiente de cálculo de grados para un método generalizado de bisección". Numerische Mathematik . 32 (2): 109–127. doi :10.1007/BF01404868. ISSN  0945-3245. S2CID  122058552.
19. Vrahatis, Michael N. (1 de junio de 1995). "Un método eficiente para localizar y calcular órbitas periódicas de aplicaciones no lineales". Journal of Computational Physics . 119 (1): 105–119. Bibcode :1995JCoPh.119..105V. doi :10.1006/jcph.1995.1119. ISSN  0021-9991.
20. Vrahatis, MN; Iordanidis, KI (1986-03-01). "Un método generalizado rápido de bisección para resolver sistemas de ecuaciones no lineales". Matemáticas numéricas . 49 (2): 123–138. doi :10.1007/BF01389620. ISSN  0945-3245. S2CID  121771945.
21. Vrahatis, MN; Perdiou, AE; Kalantonis, VS; Perdios, EA; Papadakis, K.; Prosmiti, R.; Farantos, SC (julio de 2001). "Aplicación del método de bisección característica para localizar y calcular órbitas periódicas en sistemas moleculares". Computer Physics Communications . 138 (1): 53–68. doi :10.1016/S0010-4655(01)00190-4.
22. Vrahatis, Michael N. (diciembre de 1988). "Resolución de sistemas de ecuaciones no lineales utilizando el valor distinto de cero del grado topológico". ACM Transactions on Mathematical Software . 14 (4): 312–329. doi :10.1145/50063.214384.

• Burden, Richard L.; Faires, J. Douglas (1985), "2.1 El algoritmo de bisección", Análisis numérico (3.ª ed.), PWS Publishers, ISBN 0-87150-857-5

Lectura adicional

• Corliss, George (1977), "¿Qué raíz encuentra el algoritmo de bisección?", SIAM Review , 19 (2): 325–327, doi :10.1137/1019044, ISSN  1095-7200
• Kaw, Autar; Kalu, Egwu (2008), Métodos numéricos con aplicaciones (1.ª ed.), archivado desde el original el 13 de abril de 2009

Enlaces externos

• Weisstein, Eric W. "Bisección". MundoMatemático .
• Notas sobre el método de bisección, PPT, Mathcad, Maple, Matlab, Mathematica del Instituto de métodos numéricos holísticos