En análisis numérico , el método ITP , abreviatura de Interpolate Truncate and Project , es el primer algoritmo de búsqueda de raíces que logra la convergencia superlineal del método secante [1] mientras conserva el rendimiento óptimo [2] en el peor de los casos del método de bisección . [3] También es el primer método con un rendimiento promedio garantizado estrictamente mejor que el método de bisección bajo cualquier distribución continua. [3] En la práctica, funciona mejor que la interpolación tradicional y las estrategias híbridas ( método de Brent ,Ridders , Illinois ), ya que no solo converge superlinealmente en funciones con buen comportamiento, sino que también garantiza un rendimiento rápido en funciones con mal comportamiento en las que fallan las interpolaciones. [3]
El método ITP sigue la misma estructura de las estrategias de horquillado estándar que realiza un seguimiento de los límites superior e inferior para la ubicación de la raíz; pero también realiza un seguimiento de la región donde el desempeño en el peor de los casos se mantiene en el límite superior. Como estrategia de horquillado, en cada iteración el ITP consulta el valor de la función en un punto y descarta la parte del intervalo entre dos puntos donde el valor de la función comparte el mismo signo. El punto consultado se calcula con tres pasos: interpola encontrando la estimación regula falsi , luego perturba / trunca la estimación (similar a Regula falsi § Mejoras en regula falsi ) y luego proyecta la estimación perturbada en un intervalo en la vecindad de la bisección punto medio. La vecindad alrededor del punto de bisección se calcula en cada iteración para garantizar la optimización mínima máx. (Teorema 2.1 de [3] ). El método depende de tres hiperparámetros y dónde es la proporción áurea , los dos primeros controlan el tamaño del truncamiento y el tercero es una variable de holgura que controla el tamaño del intervalo para el paso de proyección.
Problema de búsqueda de raíces
Dada una función continua definido desde a tal que , donde al costo de una consulta se puede acceder a los valores de en cualquier dado . Y, dada una precisión objetivo preespecificada, se diseñó un algoritmo de búsqueda de raíces para resolver el siguiente problema con la menor cantidad de consultas posible:
Definición del problema: encontrar tal que , dónde satisface .
Este problema es muy común en el análisis numérico , la informática y la ingeniería ; y los algoritmos de búsqueda de raíces son el enfoque estándar para resolverlo. A menudo, el procedimiento de búsqueda de raíces es llamado por algoritmos padre más complejos dentro de un contexto más amplio y, por esta razón, resolver problemas de raíz de manera eficiente es de extrema importancia ya que un enfoque ineficiente puede tener un alto costo computacional cuando se toma en cuenta el contexto más amplio. cuenta. Esto es lo que intenta hacer el método ITP al explotar simultáneamente las garantías de interpolación y las garantías óptimas mínimas del método de bisección que termina en como máximo iteraciones cuando se inician en un intervalo .
El método
Dado , y dónde es la proporción áurea , en cada iteración el método ITP calcula el punto siguiendo tres pasos:
- [Paso de interpolación] Calcule la bisección y los puntos regula falsi: y ;
- [Paso de truncamiento] Perturba el estimador hacia el centro: dónde y ;
- [Paso de proyección] Proyecte el estimador al intervalo mínimo máx .: dónde .
El valor de la función sobre este punto se consulta, y luego el intervalo se reduce para poner entre corchetes la raíz manteniendo el subintervalo con valores de función de signo opuesto en cada extremo.
El algoritmo
El siguiente algoritmo (escrito en pseudocódigo ) asume los valores iniciales de y se dan y satisfacen dónde y ; y devuelve una estimación que satisface en como máximo evaluaciones de funciones.
Aporte: Preprocesamiento: , , y ; Tiempo ( ) Cálculo de parámetros: , , ; Interpolación: ; Truncamiento: ; Si luego , Demás ; Proyección: Si luego , Demás ; Intervalo de actualización: ; Si luego y , Elseif luego y , Demás y ; ;Producción:
Ejemplo: encontrar la raíz de un polinomio
Suponga que se usa el método ITP para encontrar una raíz del polinomio Utilizando y encontramos eso:
Iteración | ||||
---|---|---|---|---|
1 | 1 | 2 | 1.43333333333333 | -0,488629629629630 |
2 | 1.43333333333333 | 2 | 1.52713145056966 | 0.0343383329048983 |
3 | 1.43333333333333 | 1.52713145056966 | 1.52009281150978 | -0,00764147709265051 |
4 | 1.52009281150978 | 1.52713145056966 | 1.52137899116052 | -4.25363464540141e-06 |
5 | 1.52137899116052 | 1.52713145056966 | 1.52138301273268 | 1.96497878177659e-05 |
6 | 1.52137899116052 | 1.52138301273268 | <- Criterios de parada satisfechos |
Este ejemplo se puede comparar con el método de bisección § Ejemplo: encontrar la raíz de un polinomio . El método ITP requirió menos de la mitad del número de iteraciones que la bisección para obtener una estimación más precisa de la raíz sin costo en las garantías mínimas. Otros métodos también pueden alcanzar una velocidad de convergencia similar (como Ridders, Brent, etc.) pero sin las garantías mínimas que ofrece el método ITP.
Análisis
La principal ventaja del método ITP es que se garantiza que no requiere más iteraciones que el método de bisección cuando . Por lo tanto, se garantiza que su rendimiento promedio es mejor que el método de bisección incluso cuando falla la interpolación. Además, si las interpolaciones no fallan (funciones suaves), entonces se garantiza que disfrutará del alto orden de convergencia como métodos basados en interpolación.
Rendimiento en el peor de los casos
Debido a que el método ITP proyecta el estimador en el intervalo minmax con un holgura, requerirá como máximo iteraciones (Teorema 2.1 de [3] ). Este es mínimo máximo óptimo como el método de bisección cuando es elegido para ser .
Rendimiento medio
Porque no hace falta más de iteraciones, el número promedio de iteraciones siempre será menor que el del método de bisección para cualquier distribución considerada cuando (Corolario 2.2 de [3] ).
Rendimiento asintótico
Si la función es dos veces diferenciable y la raíz es simple, entonces los intervalos producidos por el método ITP convergen a 0 con un orden de convergencia de Si o si y no es una potencia de 2 con el término no demasiado cerca de cero (Teorema 2.3 de [3] ).
Ver también
Referencias
- ^ Argyros, IK; Hernández-Verón, MA; Rubio, MJ (2019). "Sobre la convergencia de métodos secantes" . Tendencias actuales en el análisis matemático y sus aplicaciones interdisciplinarias : 141-183. doi : 10.1007 / 978-3-030-15242-0_5 . ISBN 978-3-030-15241-3.
- ^ Sikorski, K. (1 de febrero de 1982). "La bisección es óptima" . Numerische Mathematik . 40 (1): 111-117. doi : 10.1007 / BF01459080 . ISSN 0945-3245 . S2CID 119952605 .
- ^ a b c d e f g Oliveira, IFD; Takahashi, RHC (6 de diciembre de 2020). "Una mejora del rendimiento medio del método de bisección preservando la optimización mínima máxima" . Transacciones ACM en software matemático . 47 (1): 5: 1–5: 24. doi : 10.1145 / 3423597 . ISSN 0098-3500 .
enlaces externos
- Un método de bisección mejorado , por Kudos