método PTI

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] 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 en funciones con buen comportamiento, sino que también garantiza un rendimiento rápido en funciones con mal comportamiento donde fallan las interpolaciones. ^[3]

El método ITP sigue la misma estructura de estrategias de bracketing 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 bracketing, 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 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 minmax (Teorema 2.1 de ^[3] ). El método depende de tres hiperparámetros y de dónde está 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íces

Dada una función continua definida desde hasta tal que , donde a costa de una consulta se puede acceder a los valores de en cualquier valor dado . Y, dada una precisión objetivo preespecificada , 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: Encuentre tal que , donde satisfaga . ${\displaystyle {\hat {x}}}$ ${\displaystyle |{\hat {x}}-x^{*}|\leq \epsilon }$ ${\displaystyle x^{*}}$ ${\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 invocado por algoritmos principales 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 toma en cuenta el contexto más amplio. cuenta. 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 la mayoría de las 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

Dada y donde está 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] Calcule la bisección y los puntos de regula falsi: 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] Perturbe 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] Proyecte 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 poner entre paréntesis 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 ) asume los valores iniciales de y se dan y satisfacen donde y ; y devuelve una estimación que satisface en la mayoría de las evaluaciones de funciones. ${\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 ; Mientras ( ) ${\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 }$ Demás ; Proyección: Si entonces , ${\displaystyle x_{t}=x_{1/2}}$ ${\displaystyle |x_{t}-x_{1/2}|\leq r}$ ${\displaystyle x_{\text{ITP}}=x_{t}}$ Demás ; 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}}}$ Si no entonces y , ${\displaystyle y_{\text{ITP}}<0}$ ${\displaystyle a=x_{\text{ITP}}}$ ${\displaystyle y_{a}=y_{\text{ITP}}}$ De lo contrario y ; ; Producción: ${\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: encontrar 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 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 que ofrece el método ITP.

Análisis

La principal ventaja del método ITP es que se garantiza que no requerirá más iteraciones que el método de bisección cuando . Por lo tanto, se garantiza que su rendimiento promedio será mejor que el método de bisección incluso cuando falla la interpolación. Además, si las interpolaciones no fallan (funciones suaves), se garantiza que disfrutará del alto orden de convergencia que los 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 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 se elige que sea . ${\displaystyle n_{0}}$ ${\displaystyle n_{1/2}+n_{0}}$ ${\displaystyle n_{0}}$ ${\displaystyle n_{0}=0}$

Rendimiento medio

Debido a que no requiere más que iteraciones, el número promedio de iteraciones siempre será menor que el del método de bisección para cualquier distribución considerada (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 contribuido por itp [ ^4] en R.

Ver también

• método de bisección
• Método de los jinetes
• Regula falsa
• El método de Brent.

Notas

1. Para obtener una discusión más profunda sobre 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 similares a secantes". Tendencias actuales en el análisis matemático y sus aplicaciones interdisciplinarias . págs. 141–183. doi :10.1007/978-3-030-15242-0_5. ISBN 978-3-030-15241-3. S2CID  202156085.
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 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.
4. Northrop, PJ (2023), itp: el algoritmo de búsqueda de raíces de interpolar, truncar y proyectar (ITP)

enlaces externos

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