método de bisección

Algoritmo para encontrar el cero de una función.

Algunos pasos del método de bisección aplicados en 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 cual se conocen dos valores con signos opuestos. El método consiste en biseccionar 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. ^[1] El método también se denomina método de reducción a 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 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 corchetes 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 en sí 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 ponen entre paréntesis una raíz, o f ( c ) y f ( b ) tienen signos opuestos y entre paréntesis una raíz. ^[5] El método selecciona el subintervalo que se garantiza que será un paréntesis 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 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 de b , y si f ( b ) y f ( c ) tienen signos opuestos, entonces el método establece c como el nuevo a . En ambos casos, las nuevas 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 para el método es una función continua f , un intervalo [ a , b ] y los valores de la función f ( a ) yf ( 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. Calcular c , el punto medio del intervalo, c =a + b/2.
2. Calcule 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ña, o | f ( c )| es suficientemente pequeña), devuelva c y deje de iterar.
4. Examine el signo de f ( c ) y reemplace ( a , f ( a )) o ( b , f ( b )) con ( c , f ( c )) para que haya un cruce por cero dentro del nuevo intervalo. YO = bfe

Al implementar el método en una computadora, puede haber problemas con la precisión finita, por lo que a menudo existen 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 existe ningún valor de coma flotante que se aproxime a x = π /2 y que dé 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 (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 Condiciones NMAX :  a < b , ya sea f ( a ) < 0 y f ( b ) > 0 o f ( a ) > 0 y f ( b ) < 0 salida: valor que difiere de una raíz de f ( x ) = 0 en menos de TOL N ← 1 mientras  N ≤ NMAX  hacer  // limitar las iteraciones para evitar un bucle infinito  c ← ( a + b )/2 // nuevo punto medio  si  f ( c ) = 0 o ( b – a )/2 < TOL  entonces  // solución encontrado Salida( c ) Detener  fin si  N ← N + 1 // incrementar el contador de pasos  si signo( f ( c )) = signo( f ( a )) entonces  a ← c  else  b ← c  // nuevo intervalo final mientras
Salida( "Error en el método.") // se superó el número máximo de pasos

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, se deben encontrar dos números y tales que y tengan signos opuestos. Para la función anterior, y satisface 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 . Debido a que es negativo, se reemplaza por en la siguiente iteración para garantizar que y tenga 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 siguiente tabla. ${\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, resulta 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/2es 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 ^[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 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 _{0}}{\epsilon }}\right)\right\rceil ,}$

donde el tamaño del paréntesis inicial y el tamaño del paréntesis requerido La principal motivación para usar 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 de la solución c que en el peor de los casos tenga un valor absoluto. error 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 desempeño en el peor de los casos bajo criterios de error absoluto, es subóptimo con respecto al desempeño promedio bajo supuestos estándar ^{[11] [12]} , así como también con el desempeño asintótico . ^[13] Las alternativas populares al método de bisección, como el método de la secante , el método de Ridders o el método de Brent (entre otros), generalmente funcionan mejor ya que compensan el peor desempeño del 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 de convergencia más alto sin tener que sacrificar el peor desempeño del 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ómputo de grados.

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

Método de bisección característica.

El método de bisección característico utiliza sólo los signos de una función en diferentes puntos. Dejemos que f sea una función de R ^d a R ^d , para algún número entero d ≥ 2. Un poliedro característico ^[18] (también llamado polígono admisible ) ^[19] de f es un poliedro 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. 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:

• Signo f( A) = (-,-), es decir, f ₁ (A)<0, f ₂ (A)<0.
• Signo f (B) = (-,+), es decir, f ₁ (B)<0, f ₂ (B)>0.
• Signo f (C) = (+,-), es decir, f ₁ (C)>0, f ₂ (C)<0.
• Signo 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 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, tales que el vector de signos difiere en todos los d signos. 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 Signo f(M) = Signo(A), entonces A se reemplaza por M y obtenemos un poliedro característico más pequeño.
• Si Signo f(M) = Signo(B), entonces B se reemplaza por M y obtenemos un poliedro característico más pequeño.
• De lo contrario, elegimos una nueva ventaja adecuada y lo intentamos de nuevo.

Supongamos que el diámetro (= longitud del borde propio más largo) del poliedro característico original es . Entonces, se requieren al menos bisecciones de bordes para que el diámetro del polígono restante sea como máximo . ^{[19] : 11, Lema.4.7} ${\displaystyle D}$ ${\displaystyle \log _{2}(D/\varepsilon )}$ ${\displaystyle \varepsilon }$

Ver 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. Carga y ferias 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. Carga y ferias 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 estar entre corchetes de las raíces de la función.
6. Carga y ferias 1985, pág. 28 para la sección
7. Carga y ferias 1985, pág. 29. Esta versión vuelve a calcular los valores de la función en cada iteración en lugar de llevarlos 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 (1 de diciembre de 1985). "Solución óptima de ecuaciones no lineales". Revista de Complejidad . 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 (1 de diciembre de 1989). "Resultados de casos promedio para un resultado cero". Revista de Complejidad . 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 que preserva la optimización Minmax". Transacciones ACM sobre software matemático . 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, Minnesota; Yakoubsohn, JC (1 de junio de 2002). "Sobre la complejidad de aislar raíces reales y calcular con certeza el grado topológico". Revista de Complejidad . 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 la aproximación de 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 conferencias sobre 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. S2CID  211160947.
17. Kearfott, panadero (1 de junio de 1979). "Un método eficiente de cálculo de grados para un método generalizado de bisección". Matemática numérica . 32 (2): 109–127. doi :10.1007/BF01404868. ISSN  0945-3245. S2CID  122058552.
18. Vrahatis, Michael N. (1 de junio de 1995). "Un método eficiente para localizar y calcular órbitas periódicas de mapeos no lineales". Revista de Física Computacional . 119 (1): 105-119. Código Bib : 1995JCoPh.119..105V. doi :10.1006/jcph.1995.1119. ISSN  0021-9991.
19. Vrahatis, manganeso; Iordanidis, KI (1 de marzo de 1986). "Un método rápido generalizado de bisección para resolver sistemas de ecuaciones no lineales". Matemática numérica . 49 (2): 123-138. doi :10.1007/BF01389620. ISSN  0945-3245. S2CID  121771945.

• Carga, 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

Otras lecturas

• 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 Holistic Numerical Methods Institute