Método ITP

En análisis numérico , el método ITP ( método de interpolación, truncamiento y proyección ) es el primer algoritmo de búsqueda de raíces que logra la convergencia superlineal del método de la secante ^{[ 1 ]} manteniendo 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 sobre funciones bien comportadas, sino que también garantiza un rendimiento rápido bajo funciones mal comportadas donde las interpolaciones fallan. ^{[ 3 ]}

El método ITP sigue la misma estructura de las estrategias de acotación estándar que mantiene un registro de los límites superior e inferior para la ubicación de la raíz; pero también mantiene un registro de la región donde el rendimiento del peor caso se mantiene acotado superiormente. Como estrategia de acotación, 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 para encontrar la estimación de la 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.${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$y${\displaystyle n_{0}\in [0,\infty )}$dónde${\displaystyle \phi }$es la proporción áurea${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$: 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 ]}

Dada una función continua${\displaystyle f}$definido desde${\displaystyle [a,b]}$a${\displaystyle \mathbb {R} }$ de tal manera que${\displaystyle f(a)f(b)\leq 0}$, donde con el coste de una consulta se puede acceder a los valores de${\displaystyle f(x)}$en cualquier momento dado${\displaystyle x}$Y, dado un objetivo de precisión preespecificado${\displaystyle \epsilon >0}$Un algoritmo de búsqueda de raíces está diseñado para resolver el siguiente problema con la menor cantidad de consultas posible:

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

Este problema es muy común en análisis numérico , informática e 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 padres 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 suma importancia, ya que un enfoque ineficiente podría tener un alto costo computacional cuando se tiene en cuenta el contexto más amplio. Esto es lo que el método ITP intenta hacer al explotar simultáneamente garantías de interpolación, así como garantías óptimas minmax del método de bisección que termina en como máximo ${\displaystyle n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil }$iteraciones cuando se inician en un intervalo${\displaystyle [a_{0},b_{0}]}$.

Dado${\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 }$ y${\displaystyle n_{0}\in [0,\infty )}$ dónde${\displaystyle \phi }$es la proporción áurea${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$, en cada iteración${\displaystyle j=0,1,2\dots }$ El método ITP calcula el punto${\displaystyle x_{\text{ITP}}}$siguiendo tres pasos:

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

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

Aporte:${\displaystyle a,b,\epsilon ,\kappa _{1},\kappa _{2},n_{0},f}$Preprocesamiento:${\displaystyle n_{1/2}=\lceil \log _{2}{\tfrac {b-a}{2\epsilon }}\rceil }$,${\displaystyle n_{\max }=n_{1/2}+n_{0}}$, y ${\displaystyle j=0}$; Mientras (${\displaystyle b-a>2\epsilon }$)Cálculo de parámetros:${\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}}}$; Interpolación:${\displaystyle x_{f}={\tfrac {y_{b}a-y_{a}b}{y_{b}-y_{a}}}}$; Truncamiento:${\displaystyle \sigma ={\text{sign}}(x_{1/2}-x_{f})}$; Si${\displaystyle \delta \leq |x_{1/2}-x_{f}|}$entonces${\displaystyle x_{t}=x_{f}+\sigma \delta }$, Demás${\displaystyle x_{t}=x_{1/2}}$; Proyección: Si${\displaystyle |x_{t}-x_{1/2}|\leq r}$entonces${\displaystyle x_{\text{ITP}}=x_{t}}$, Demás${\displaystyle x_{\text{ITP}}=x_{1/2}-\sigma r}$; Intervalo de actualización:${\displaystyle y_{\text{ITP}}=f(x_{\text{ITP}})}$; Si${\displaystyle y_{\text{ITP}}>0}$entonces${\displaystyle b=x_{ITP}}$y${\displaystyle y_{b}=y_{\text{ITP}}}$, Si no,${\displaystyle y_{\text{ITP}}<0}$entonces${\displaystyle a=x_{\text{ITP}}}$y${\displaystyle y_{a}=y_{\text{ITP}}}$, Demás${\displaystyle a=x_{\text{ITP}}}$y${\displaystyle b=x_{\text{ITP}}}$; ${\displaystyle j=j+1}$; Producción:${\displaystyle {\hat {x}}={\tfrac {a+b}{2}}}$

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

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 de iteraciones que la bisección para obtener una estimación más precisa de la raíz sin sacrificar las garantías de minmax. Otros métodos también podrían alcanzar una velocidad de convergencia similar (como Ridders, Brent, etc.), pero sin las garantías de minmax que ofrece el método ITP.

La principal ventaja del método ITP es que garantiza que no requerirá más iteraciones que el método de bisección cuando${\displaystyle n_{0}=0}$Por lo tanto, su rendimiento promedio está garantizado para 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), entonces se garantiza que tendrá un alto orden de convergencia, al igual que los métodos basados ​​en interpolación.

• El paquete itp ^{[ 4 ]} aportado en R.

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

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