En el análisis numérico , el método de Brent es un algoritmo híbrido de búsqueda de raíces que combina el método de bisección , el método de la secante y la interpolación cuadrática inversa . Tiene la confiabilidad de la bisección, pero puede ser tan rápido como algunos de los métodos menos confiables. El algoritmo intenta utilizar el método secante de convergencia rápida potencialmente o la interpolación cuadrática inversa si es posible, pero recurre al método de bisección más robusto si es necesario. El método de Brent se debe a Richard Brent [1] y se basa en un algoritmo anterior de Theodorus Dekker . [2] En consecuencia, el método también se conoce comoMétodo Brent-Dekker .
Las mejoras modernas en el método de Brent incluyen el método de Chandrupatla , que es más simple y rápido para funciones que son planas alrededor de sus raíces; [3] [4] Método de Ridders , que realiza interpolaciones exponenciales en lugar de cuadráticas proporcionando una fórmula cerrada más simple para las iteraciones; y el método ITP, que es un híbrido entre regula-falsi y bisection que logra garantías óptimas en el peor de los casos y asintóticas.
El método de Dekker
La idea de combinar el método de la bisección con el método de la secante se remonta a Dekker (1969) .
Suponga que queremos resolver la ecuación f ( x ) = 0. Al igual que con el método de bisección, necesitamos inicializar el método de Dekker con dos puntos, digamos a 0 y b 0 , tales que f ( a 0 ) y f ( b 0 ) tienen signos opuestos. Si f es continua en [ a 0 , b 0 ], el teorema del valor intermedio garantiza la existencia de una solución entre a 0 y b 0 .
Hay tres puntos involucrados en cada iteración:
- b k es la iteración actual, es decir, la estimación actual de la raíz de f .
- a k es el "contrapunto", es decir, un punto tal que f ( a k ) y f ( b k ) tienen signos opuestos, por lo que el intervalo [ a k , b k ] contiene la solución. Además, | f ( b k ) | debe ser menor o igual que | f ( a k ) |, de modo que b k es una estimación mejor para la solución desconocida que a k .
- b k −1 es la iteración anterior (para la primera iteración, establecemos b k −1 = a 0 ).
Se calculan dos valores provisionales para la siguiente iteración. El primero viene dado por interpolación lineal, también conocido como método secante:
y el segundo viene dado por el método de bisección
Si el resultado del método de la secante, s , mentiras estrictamente entre b k y m , entonces se convierte en la siguiente iteración ( b k +1 = s ), de lo contrario se utiliza el punto medio ( b k 1 = m ).
Luego, el valor del nuevo contrapunto se elige de manera que f ( a k +1 ) yf ( b k +1 ) tengan signos opuestos. Si f ( a k ) y f ( b k +1 ) tienen signos opuestos, entonces el contrapunto permanece igual: a k +1 = a k . De lo contrario, f ( b k +1 ) y f ( b k ) tienen signos opuestos, por lo que el nuevo contrapunto se convierte en a k +1 = b k .
Finalmente, si | f ( a k +1 ) | <| f ( b k +1 ) |, entonces a k +1 es probablemente una mejor estimación para la solución que b k +1 , y por lo tanto los valores de a k +1 y b k +1 se intercambian.
Esto finaliza la descripción de una única iteración del método de Dekker.
El método de Dekker funciona bien si la función f se comporta razonablemente bien. Sin embargo, hay circunstancias en las que cada iteración emplea el método de la secante, pero las iteraciones b k convergen muy lentamente (en particular, | b k - b k −1 | puede ser arbitrariamente pequeña). El método de Dekker requiere muchas más iteraciones que el método de bisección en este caso.
El método de Brent
Brent (1973) propuso una pequeña modificación para evitar este problema. Insertó una prueba adicional que debe cumplirse antes de que se acepte el resultado del método de la secante como la siguiente iteración. Deben satisfacerse dos desigualdades simultáneamente: dada una tolerancia numérica específica, si el paso anterior utilizó el método de bisección, la desigualdad
debe mantener para realizar la interpolación; de lo contrario, se realiza el método de bisección y su resultado se utiliza para la siguiente iteración.
Si el paso anterior realizó una interpolación, entonces la desigualdad
se usa en su lugar para realizar la siguiente acción (elegir) interpolación (cuando la desigualdad es verdadera) o método de bisección (cuando la desigualdad no es verdadera).
Además, si el paso anterior utilizó el método de bisección, la desigualdad
debe mantenerse, de lo contrario, se realiza el método de bisección y su resultado se utiliza para la siguiente iteración. Si el paso anterior realizó una interpolación, entonces la desigualdad
se utiliza en su lugar.
Esta modificación asegura que en la k-ésima iteración, se realizará un paso de bisección como máximo iteraciones adicionales, debido a que las condiciones anteriores obligan a que los tamaños de los pasos de interpolación consecutivos se reduzcan a la mitad cada dos iteraciones, el tamaño del paso será menor que , que invoca un paso de bisección. Brent demostró que su método requiere como máximo N 2 iteraciones, donde N denota el número de iteraciones para el método de bisección. Si la función f se comporta bien, entonces el método de Brent generalmente procederá por interpolación lineal o cuadrática inversa, en cuyo caso convergerá superlinealmente .
Además, el método de Brent usa la interpolación cuadrática inversa en lugar de la interpolación lineal (como se usa en el método de la secante). Si f ( b k ), f ( a k ) y f ( b k −1 ) son distintas, aumenta ligeramente la eficiencia. Como consecuencia, la condición para aceptar s (el valor propuesto por interpolación lineal o interpolación cuadrática inversa) debe cambiarse: s debe estar entre (3 a k + b k ) / 4 y b k .
Algoritmo
ingrese a , by (un puntero a) una función para f calcular f ( a )calcule f ( b ) si f ( a ) f ( b ) ≥ 0 entonces función de salida porque la raíz no está entre corchetes.terminar si si | f ( a ) | <| f ( b ) | entonces swap ( un , b ) final si c : = un conjunto mflag repetir hasta que f ( b o s ) = 0 o | b - a | es lo suficientemente pequeño (convergencia) si f ( un ) ≠ f ( c ) y f ( b ) ≠ f ( c ) a continuación, ( interpolación cuadrática inversa ) else ( método secante ) finaliza si si (condición 1) s no está entrey b o (condición 2) (mflag se establece y | s - b | ≥ | b - c | / 2) o (condición 3) (mflag se borra y | s - b | ≥ | c - d | / 2) o (condición 4) (mflag se establece y | b - c | <| δ |) o (condición 5) (mflag se borra y | c - d | <| δ |) entonces ( método de bisección ) establecer mflag else borrar mflag end si calcula f ( s ) d : = c (d se asigna por primera vez aquí; no se usará arriba en la primera iteración porque mflag está establecido) c : = b si f ( a ) f ( s ) <0 entonces b : = s else a : = s end if if | f ( a ) | <| f ( b ) | luego swap ( a , b ) end if end repite la salida b o s (devuelve la raíz)
Ejemplo
Suponga que buscamos un cero de la función definida por f ( x ) = ( x + 3) ( x - 1) 2 .
Tomamos [ a 0 , b 0 ] = [−4, 4/3] como nuestro intervalo inicial.
Tenemos f ( a 0 ) = −25 y f ( b 0 ) = 0.48148 (todos los números en esta sección están redondeados), entonces las condiciones f ( a 0 ) f ( b 0 ) <0 y | f ( b 0 ) | ≤ | f ( a 0 ) | estan satisfechos.
- En la primera iteración, usamos la interpolación lineal entre ( b −1 , f ( b −1 )) = ( a 0 , f ( a 0 )) = (−4, −25) y ( b 0 , f ( b 0 )) = (1.33333, 0.48148), lo que da como resultado s = 1.23256. Este se encuentra entre (3 a 0 + b 0 ) / 4 y b 0 , por lo que se acepta este valor. Además, f (1,23256) = 0,22891, lo que establecer un 1 = un 0 y b 1 = s = 1,23256.
- En la segunda iteración, usamos la interpolación cuadrática inversa entre ( a 1 , f ( a 1 )) = (−4, −25) y ( b 0 , f ( b 0 )) = (1.33333, 0.48148) y ( b 1 , f ( b 1 )) = (1,23256, 0,22891). Esto produce 1,14205, que se encuentra entre (3 a 1 + b 1 ) / 4 y b 1 . Además, la desigualdad | 1,14205 - b 1 | ≤ | b 0 - b −1 | / 2 se satisface, por lo que se acepta este valor. Además, f (1,14205) = 0,083582, por lo que establecer un 2 = un 1 y b 2 = 1,14205.
- En la tercera iteración, usamos la interpolación cuadrática inversa entre ( a 2 , f ( a 2 )) = (−4, −25) y ( b 1 , f ( b 1 )) = (1.23256, 0.22891) y ( b 2 , f ( b 2 )) = (1,14205, 0,083582). Esto produce 1.09032, que se encuentra entre (3 a 2 + b 2 ) / 4 y b 2 . Pero aquí entra en juego la condición adicional de Brent: la desigualdad | 1.09032 - b 2 | ≤ | b 1 - b 0 | / 2 no se satisface, por lo que este valor se rechaza. En cambio, se calcula el punto medio m = −1,42897 del intervalo [ a 2 , b 2 ]. Tenemos f ( m ) = 9,26891, lo que establecer un 3 = un 2 y b 3 = -1,42897.
- En la cuarta iteración, usamos la interpolación cuadrática inversa entre ( a 3 , f ( a 3 )) = (−4, −25) y ( b 2 , f ( b 2 )) = (1.14205, 0.083582) y ( b 3 , f ( b 3 )) = (-1,42897, 9,26891). Esto produce 1,15448, que no está en el intervalo entre (3 a 3 + b 3 ) / 4 y b 3 ). Por lo tanto, se reemplaza por el punto medio m = −2,71449. Tenemos f ( m ) = 3,93934, lo que establecer un 4 = un 3 y b 4 = -2,71449.
- En la quinta iteración, la interpolación cuadrática inversa produce −3,45500, que se encuentra en el intervalo requerido. Sin embargo, la iteración anterior fue un paso de bisección, por lo que la desigualdad | −3,45500 - b 4 | ≤ | b 4 - b 3 | / 2 necesita estar satisfecho. Esta desigualdad es falsa, por lo que usamos el punto medio m = −3,35724. Tenemos f ( m ) = −6.78239, por lo que m se convierte en el nuevo contrapunto ( a 5 = −3.35724) y la iteración permanece igual ( b 5 = b 4 ).
- En la sexta iteración, no podemos usar la interpolación cuadrática inversa porque b 5 = b 4 . Por lo tanto, usamos la interpolación lineal entre ( a 5 , f ( a 5 )) = (−3,35724, −6,78239) y ( b 5 , f ( b 5 )) = (−2,71449, 3,93934). El resultado es s = −2,95064, que satisface todas las condiciones. Pero como la iteración no cambió en el paso anterior, rechazamos este resultado y volvemos a la bisección. Actualizamos s = -3.03587 y f ( s ) = -0.58418.
- En la séptima iteración, podemos usar nuevamente la interpolación cuadrática inversa. El resultado es s = −3,00219, que satisface todas las condiciones. Ahora, f ( s ) = -0,03515, por lo que establecer un 7 = b 6 y b 7 = -3,00219 ( un 7 y b 7 se intercambian de manera que la condición | f ( b 7 ) | ≤ | f ( un 7 ) | está satisfecho). ( Correcto : interpolación lineal)
- En la octava iteración, no podemos usar la interpolación cuadrática inversa porque a 7 = b 6 . La interpolación lineal produce s = −2,99994, que se acepta. ( Correcto :)
- En las siguientes iteraciones, la raíz x = −3 se aproxima rápidamente: b 9 = −3 + 6 · 10 −8 y b 10 = −3 - 3 · 10 −15 . ( Correcto : Iter 9: f ( s ) = −1,4 × 10 −7 , Iter 10: f ( s ) = 6,96 × 10 −12 )
Implementaciones
- Brent (1973) publicó una implementación de Algol 60 .
- Netlib contiene una traducción de Fortran de esta implementación con ligeras modificaciones.
- El método PARI / GP
solve
implementa el método. - Otras implementaciones del algoritmo (en C ++, C y Fortran) se pueden encontrar en los libros de Recetas numéricas .
- La biblioteca Apache Commons Math implementa el algoritmo en Java .
- El módulo de optimización de SciPy implementa el algoritmo en Python (lenguaje de programación)
- La biblioteca estándar de Modelica implementa el algoritmo en Modelica .
- La
uniroot
función implementa el algoritmo en R (software) . - La
fzero
función implementa el algoritmo en MATLAB . - El Boost (bibliotecas C ++) implementa dos algoritmos basados en el método de Brent en C ++ en el kit de herramientas matemáticas:
- Minimización de funciones en minima.hpp con un ejemplo de localización de mínimos de funciones .
- La búsqueda de raíz implementa el TOMS748 más nuevo, un algoritmo más moderno y eficiente que el original de Brent, en TOMS748 , y la búsqueda de raíz Boost.Math que usa TOMS748 internamente con ejemplos .
- El paquete Optim.jl implementa el algoritmo en Julia (lenguaje de programación)
- El sistema de álgebra informática SICMUtils (escrito en Clojure (lenguaje de programación) ) implementa una variante del algoritmo diseñado para la minimización de funciones univariadas.
Referencias
- ^ Brent 1973
- ^ Dekker, 1969
- ^ Chandrupatla, Tirupathi R. (1997). "Un nuevo algoritmo híbrido cuadrático / de bisección para encontrar el cero de una función no lineal sin utilizar derivadas". Avances en software de ingeniería . 28 (3): 145-149. doi : 10.1016 / S0965-9978 (96) 00051-8 .
- ^ "Diez pequeños algoritmos, parte 5: interpolación de extremos cuadráticos y método de Chandrupatla - Jason Sachs" .
- Brent, RP (1973), "Capítulo 4: Un algoritmo con convergencia garantizada para encontrar un cero de una función", Algoritmos para la minimización sin derivadas , Englewood Cliffs, Nueva Jersey: Prentice-Hall, ISBN 0-13-022335-2
- Dekker, TJ (1969), "Encontrar un cero mediante interpolación lineal sucesiva", en Dejon, B .; Henrici, P. (eds.), Aspectos constructivos del teorema fundamental del álgebra , Londres: Wiley-Interscience, ISBN 978-0-471-20300-1
Otras lecturas
- Atkinson, Kendall E. (1989). "Sección 2.8.". Introducción al análisis numérico (2ª ed.). John Wiley e hijos. ISBN 0-471-50023-2.
- Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 9.3. Método Van Wijngaarden-Dekker-Brent" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
- Alefeld, GE; Potra, FA; Shi, Yixun (septiembre de 1995). "Algoritmo 748: Ceros cerrados de funciones continuas". Transacciones ACM en software matemático . 21 (3): 327–344. doi : 10.1145 / 210089.210111 .
enlaces externos
- zeroin.f en Netlib .
- módulo brent en C ++ (también C, Fortran, Matlab) por John Burkardt
- Implementación de GSL .
- Impulsar la implementación de C ++ .
- Python (Scipy) aplicación