Método ITP

Algoritmo de búsqueda de raíces

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 basadas en híbridos ( Método de Brent , Ridders , Illinois ), ya que no solo converge de manera superlineal sobre funciones con buen comportamiento sino que también garantiza un rendimiento rápido bajo funciones con mal comportamiento donde las interpolaciones fallan. ^[3]

El método ITP sigue la misma estructura de las estrategias de horquillado estándar que realizan 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 rendimiento en el peor de los casos se mantiene acotado superiormente. 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 de 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 del punto medio de bisección. La vecindad alrededor del punto de bisección se calcula en cada iteración para garantizar la optimalidad minmax (Teorema 2.1 de ^[3] ). El método depende de tres hiperparámetros y donde 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. ^[a] ${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$ ${\displaystyle n_{0}\in [0,\infty )}$ ${\displaystyle \phi }$ ${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$

Problema de búsqueda de raíz

Dada una función continua definida de a tal que , donde al costo de una consulta se puede acceder a los valores de en cualquier . Y, dada una precisión objetivo preestablecida , se diseña un algoritmo de búsqueda de raíces para resolver el siguiente problema con la menor cantidad de consultas posible: ${\displaystyle f}$ ${\displaystyle [a,b]}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle f(a)f(b)\leq 0}$ ${\displaystyle f(x)}$ ${\displaystyle x}$ ${\displaystyle \epsilon >0}$

Definición del problema: Encontrar tal que , donde satisface . ${\displaystyle {\hat {x}}}$ ${\displaystyle |{\hat {x}}-x^{*}|\leq \epsilon }$ ${\displaystyle x^{*}}$ ${\displaystyle f(x^{*})=0}$

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íces 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. Esto es lo que el método ITP intenta hacer explotando simultáneamente las garantías de interpolación, así como las garantías óptimas minmax del método de bisección que termina en como máximo iteraciones cuando se inicia en un intervalo . ${\displaystyle n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil }$ ${\displaystyle [a_{0},b_{0}]}$

El método

Dado , y donde es la proporción áurea , en cada iteración el método ITP calcula el punto siguiendo tres pasos: ${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$ ${\displaystyle n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil }$ ${\displaystyle n_{0}\in [0,\infty )}$ ${\displaystyle \phi }$ ${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$ ${\displaystyle j=0,1,2\dots }$ ${\displaystyle x_{\text{ITP}}}$

Paso 1 del método ITP.

Paso 2 del método ITP.

Paso 3 del método ITP.

Los tres pasos combinados forman el método ITP. La línea azul gruesa representa la "interpolación truncada proyectada" del método.

1. [Paso de interpolación] Calcular los puntos de bisección y de regla falsa: y  ; ${\displaystyle x_{1/2}\equiv {\frac {a+b}{2}}}$ ${\displaystyle x_{f}\equiv {\frac {bf(a)-af(b)}{f(a)-f(b)}}}$
2. [Paso de truncamiento] Perturba el estimador hacia el centro: donde y  ; ${\displaystyle x_{t}\equiv x_{f}+\sigma \delta }$ ${\displaystyle \sigma \equiv {\text{sign}}(x_{1/2}-x_{f})}$ ${\displaystyle \delta \equiv \min\{\kappa _{1}|b-a|^{\kappa _{2}},|x_{1/2}-x_{f}|\}}$
3. [Paso de proyección] Proyectar el estimador al intervalo minmax: donde . ${\displaystyle x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}}$ ${\displaystyle \rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}},|x_{t}-x_{1/2}|\right\}}$

Se consulta el valor de la función en este punto y luego se reduce el intervalo para encerrar la raíz manteniendo el subintervalo con valores de función de signo opuesto en cada extremo. ${\displaystyle f(x_{\text{ITP}})}$

El algoritmo

El siguiente algoritmo (escrito en pseudocódigo ) supone que los valores iniciales de y están dados y satisfacen donde y ; y devuelve una estimación que satisface en la mayoría de las evaluaciones de función. ${\displaystyle y_{a}}$ ${\displaystyle y_{b}}$ ${\displaystyle y_{a}<0<y_{b}}$ ${\displaystyle y_{a}\equiv f(a)}$ ${\displaystyle y_{b}\equiv f(b)}$ ${\displaystyle {\hat {x}}}$ ${\displaystyle |{\hat {x}}-x^{*}|\leq \epsilon }$ ${\displaystyle n_{1/2}+n_{0}}$

Entrada:  ${\displaystyle a,b,\epsilon ,\kappa _{1},\kappa _{2},n_{0},f}$ Preprocesamiento: , , y ; While ( ) ${\displaystyle n_{1/2}=\lceil \log _{2}{\tfrac {b-a}{2\epsilon }}\rceil }$ ${\displaystyle n_{\max }=n_{1/2}+n_{0}}$ ${\displaystyle j=0}$ ${\displaystyle b-a>2\epsilon }$   Cálculo de parámetros: , , ; Interpolación: ; Truncamiento: ; ${\displaystyle x_{1/2}={\tfrac {a+b}{2}}}$ ${\displaystyle r=\epsilon 2^{n_{\max }-j}-(b-a)/2}$ ${\displaystyle \delta =\kappa _{1}(b-a)^{\kappa _{2}}}$  ${\displaystyle x_{f}={\tfrac {y_{b}a-y_{a}b}{y_{b}-y_{a}}}}$  ${\displaystyle \sigma ={\text{sign}}(x_{1/2}-x_{f})}$ Si entonces , ${\displaystyle \delta \leq |x_{1/2}-x_{f}|}$ ${\displaystyle x_{t}=x_{f}+\sigma \delta }$ De lo contrario ; Proyección: Si entonces , ${\displaystyle x_{t}=x_{1/2}}$ ${\displaystyle |x_{t}-x_{1/2}|\leq r}$ ${\displaystyle x_{\text{ITP}}=x_{t}}$ De lo contrario ; Intervalo de actualización :; ${\displaystyle x_{\text{ITP}}=x_{1/2}-\sigma r}$  ${\displaystyle y_{\text{ITP}}=f(x_{\text{ITP}})}$ Si entonces y , ${\displaystyle y_{\text{ITP}}>0}$ ${\displaystyle b=x_{ITP}}$ ${\displaystyle y_{b}=y_{\text{ITP}}}$ De lo contrario, entonces y , ${\displaystyle y_{\text{ITP}}<0}$ ${\displaystyle a=x_{\text{ITP}}}$ ${\displaystyle y_{a}=y_{\text{ITP}}}$ De lo contrario y ; ; Salida: ${\displaystyle a=x_{\text{ITP}}}$ ${\displaystyle b=x_{\text{ITP}}}$ ${\displaystyle j=j+1}$ ${\displaystyle {\hat {x}}={\tfrac {a+b}{2}}}$

Ejemplo: Encontrar la raíz de un polinomio

Supongamos que se utiliza el método ITP para encontrar una raíz del polinomio Usando y encontramos que: ${\displaystyle f(x)=x^{3}-x-2\,.}$ ${\displaystyle \epsilon =0.0005,\kappa _{1}=0.1,\kappa _{2}=2}$ ${\displaystyle n_{0}=1}$

Este ejemplo se puede comparar con el método de bisección § Ejemplo: Hallar 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 minmax. Otros métodos también podrían alcanzar una velocidad de convergencia similar (como Ridders, Brent, etc.) pero sin las garantías minmax dadas por 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 será mejor que el del método de bisección incluso cuando la interpolación falla. Además, si las interpolaciones no fallan (funciones suaves), se garantiza que disfrutará del alto orden de convergencia como métodos basados ​​en interpolación. ${\displaystyle n_{0}=0}$

Rendimiento en el peor de los casos

Debido a que el método ITP proyecta el estimador en el intervalo minmax con una holgura, requerirá como máximo iteraciones (Teorema 2.1 de ^[3] ). Esto es minmax óptimo como el método de bisección cuando se elige que sea . ${\displaystyle n_{0}}$ ${\displaystyle n_{1/2}+n_{0}}$ ${\displaystyle n_{0}}$ ${\displaystyle n_{0}=0}$

Rendimiento promedio

Debido a que no requiere 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] ). ${\displaystyle n_{1/2}+n_{0}}$ ${\displaystyle n_{0}=0}$

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 cercano a cero (Teorema 2.3 de ^[3] ). ${\displaystyle f(x)}$ ${\displaystyle x^{*}}$ ${\displaystyle {\sqrt {\kappa _{2}}}}$ ${\displaystyle n_{0}\neq 0}$ ${\displaystyle n_{0}=0}$ ${\displaystyle (b-a)/\epsilon }$ ${\displaystyle {\tfrac {\epsilon 2^{n_{1/2}}}{b-a}}}$

Software

• El paquete itp ^[4] contribuyó en R.

Véase también

• Método de bisección
• El método de Ridders
• Regla falsa
• El método de Brent

Notas

1. Para una discusión más profunda de los hiperparámetros, consulte la documentación de ITP en la biblioteca kurbo.

Referencias

1. Argyros, IK; Hernández-Verón, MA; Rubio, MJ (2019). "Sobre la convergencia de métodos de tipo secante". Tendencias actuales en análisis matemático y sus aplicaciones interdisciplinarias . pp. 141–183. doi :10.1007/978-3-030-15242-0_5. ISBN 978-3-030-15241-3.S2CID202156085  .​^{[ enlace muerto permanente ]}
2. 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.
3. 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.
4. Northrop, PJ (2023), itp: El algoritmo de búsqueda de raíces Interpolar, Truncar, Proyectar (ITP)

Enlaces externos

• Un método de bisección mejorado, por Kudos