Algoritmo de búsqueda de raíces

En análisis numérico , un algoritmo de búsqueda de raíces es un algoritmo para encontrar ceros , también llamados "raíces", de funciones continuas . Un cero de una función f es un número x tal que f ( x ) = 0 . Como, por lo general, los ceros de una función no se pueden calcular con exactitud ni expresar en forma cerrada , los algoritmos de búsqueda de raíces proporcionan aproximaciones a los ceros. Para funciones de números reales a números reales o de números complejos a números complejos, estos se expresan como números de punto flotante sin límites de error o como valores de punto flotante junto con límites de error. Estas últimas, aproximaciones con límites de error, son equivalentes a pequeños intervalos de aislamiento para raíces reales o discos para raíces complejas. ^[1]

Resolver una ecuación f ( x ) = g ( x ) es lo mismo que hallar las raíces de la función h ( x ) = f ( x ) – g ( x ) . Por lo tanto, los algoritmos de búsqueda de raíces se pueden utilizar para resolver cualquier ecuación de funciones continuas. Sin embargo, la mayoría de los algoritmos de búsqueda de raíces no garantizan que encontrarán todas las raíces de una función, y si dicho algoritmo no encuentra ninguna raíz, eso no significa necesariamente que no exista ninguna raíz.

La mayoría de los métodos numéricos de búsqueda de raíces son métodos iterativos , que producen una secuencia de números que idealmente converge hacia una raíz como límite . Requieren una o más suposiciones iniciales de la raíz como valores de partida, luego cada iteración del algoritmo produce una aproximación sucesivamente más precisa a la raíz. Dado que la iteración debe detenerse en algún punto, estos métodos producen una aproximación a la raíz, no una solución exacta. Muchos métodos calculan valores posteriores evaluando una función auxiliar sobre los valores anteriores. El límite es, por lo tanto, un punto fijo de la función auxiliar, que se elige por tener las raíces de la ecuación original como puntos fijos y por converger rápidamente a estos puntos fijos.

El comportamiento de los algoritmos generales de búsqueda de raíces se estudia en el análisis numérico . Sin embargo, para los polinomios específicamente, el estudio de los algoritmos de búsqueda de raíces pertenece al álgebra computacional , ya que las propiedades algebraicas de los polinomios son fundamentales para los algoritmos más eficientes. La eficiencia y la aplicabilidad de un algoritmo pueden depender sensiblemente de las características de las funciones dadas. Por ejemplo, muchos algoritmos utilizan la derivada de la función de entrada, mientras que otros funcionan en cada función continua . En general, no se garantiza que los algoritmos numéricos encuentren todas las raíces de una función, por lo que no encontrar una raíz no prueba que no haya raíz. Sin embargo, para los polinomios , hay algoritmos específicos que utilizan propiedades algebraicas para certificar que no se omite ninguna raíz y para ubicar las raíces en intervalos separados (o discos para raíces complejas) que son lo suficientemente pequeños para asegurar la convergencia de los métodos numéricos (típicamente el método de Newton ) a la raíz única dentro de cada intervalo (o disco).

Los métodos de corchetes determinan intervalos sucesivamente más pequeños (corchetes) que contienen una raíz. Cuando el intervalo es lo suficientemente pequeño, se considera que se ha encontrado una raíz. Estos métodos generalmente utilizan el teorema del valor intermedio , que afirma que si una función continua tiene valores de signos opuestos en los puntos finales de un intervalo, entonces la función tiene al menos una raíz en el intervalo. Por lo tanto, requieren comenzar con un intervalo tal que la función tome signos opuestos en los puntos finales del intervalo. Sin embargo, en el caso de los polinomios existen otros métodos como la regla de los signos de Descartes , el teorema de Budan y el teorema de Sturm para acotar o determinar el número de raíces en un intervalo. Conducen a algoritmos eficientes para el aislamiento de raíces reales de polinomios, que encuentran todas las raíces reales con una precisión garantizada.

El algoritmo más simple para encontrar raíces es el método de bisección . Sea f una función continua para la cual se conoce un intervalo [ a , b ] tal que f ( a ) y f ( b ) tienen signos opuestos (un corchete). Sea c = ( a + b )/2 el punto medio del intervalo (el punto medio o el punto que divide el intervalo en dos). Entonces, f ( a ) y f ( c ) o f ( c ) y f ( b ) tienen signos opuestos, y uno ha dividido por dos el tamaño del intervalo. Aunque el método de bisección es robusto, gana uno y solo un bit de precisión con cada iteración. Por lo tanto, el número de evaluaciones de función requeridas para encontrar una raíz ε -aproximada es . Otros métodos, en condiciones apropiadas, pueden ganar precisión más rápido.${\displaystyle \log _{2}{\frac {ba}{\varepsilon }}}$

El método de posición falsa , también llamado método de regula falsi , es similar al método de bisección, pero en lugar de utilizar la mitad del intervalo de búsqueda de bisección, utiliza la intersección con el eje x de la línea que conecta los valores de la función graficada en los puntos finales del intervalo, es decir

${\displaystyle c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.}$

La posición falsa es similar al método de la secante , excepto que, en lugar de retener los dos últimos puntos, se asegura de mantener un punto a cada lado de la raíz. El método de la posición falsa puede ser más rápido que el método de bisección y nunca divergirá como el método de la secante. Sin embargo, puede fallar en converger en algunas implementaciones ingenuas debido a errores de redondeo que pueden llevar a un signo incorrecto para f ( c ) . Por lo general, esto puede ocurrir si la derivada de f es grande en la vecindad de la raíz.

El método ITP es el único método conocido para encerrar la raíz con las mismas garantías del peor caso del método de bisección, al mismo tiempo que garantiza una convergencia superlineal a la raíz de funciones suaves como el método de la secante. También es el único método conocido que garantiza superar al método de bisección en promedio para cualquier distribución continua en la ubicación de la raíz (ver Método ITP#Análisis ). Lo hace al realizar un seguimiento tanto del intervalo de encerrar como del intervalo minmax en el que cualquier punto en el mismo converge tan rápido como el método de bisección. La construcción del punto consultado c sigue tres pasos: interpolación (similar a la regula falsi), truncamiento (ajuste de la regula falsi similar a Regula falsi § Mejoras en la regula falsi ) y luego proyección sobre el intervalo minmax. La combinación de estos pasos produce simultáneamente un método mínimo-máximo óptimo con garantías similares a los métodos basados ​​en interpolación para funciones suaves y, en la práctica, superará tanto al método de bisección como a los métodos basados ​​en interpolación aplicados a funciones suaves y no suaves.

Muchos procesos de búsqueda de raíces funcionan mediante interpolación . Esto consiste en utilizar los últimos valores aproximados calculados de la raíz para aproximar la función mediante un polinomio de grado bajo, que toma los mismos valores en estas raíces aproximadas. Luego se calcula la raíz del polinomio y se utiliza como un nuevo valor aproximado de la raíz de la función, y se itera el proceso.

La interpolación de dos valores produce una línea: un polinomio de grado uno. Esta es la base del método de la secante . La regla falsa también es un método de interpolación que interpola dos puntos a la vez, pero se diferencia del método de la secante en que utiliza dos puntos que no son necesariamente los dos últimos puntos calculados. Tres valores definen una curva parabólica: una función cuadrática . Esta es la base del método de Müller .

Aunque todos los algoritmos de búsqueda de raíces se realizan mediante iteración , un método iterativo de búsqueda de raíces generalmente utiliza un tipo específico de iteración, que consiste en definir una función auxiliar, que se aplica a las últimas aproximaciones calculadas de una raíz para obtener una nueva aproximación. La iteración se detiene cuando se alcanza un punto fijo de la función auxiliar con la precisión deseada, es decir, cuando un nuevo valor calculado es suficientemente cercano a los anteriores.

El método de Newton supone que la función f tiene una derivada continua . El método de Newton puede no converger si se comienza demasiado lejos de una raíz. Sin embargo, cuando converge, es más rápido que el método de bisección; su orden de convergencia suele ser cuadrático, mientras que el del método de bisección es lineal. El método de Newton también es importante porque se generaliza fácilmente a problemas de dimensiones superiores. Los métodos de Householder son una clase de métodos similares a Newton con órdenes de convergencia superiores. El primero después del método de Newton es el método de Halley con orden cúbico de convergencia.

Sustituyendo la derivada en el método de Newton por una diferencia finita , obtenemos el método de la secante . Este método no requiere el cálculo (ni la existencia) de una derivada, pero el precio es una convergencia más lenta (el orden de convergencia es la proporción áurea , aproximadamente 1,62 ^[2] ). Una generalización del método de la secante en dimensiones superiores es el método de Broyden .

Si utilizamos un ajuste polinomial para eliminar la parte cuadrática de la diferencia finita utilizada en el método secante, de modo que se aproxime mejor a la derivada, obtenemos el método de Steffensen , que tiene convergencia cuadrática, y cuyo comportamiento (tanto bueno como malo) es esencialmente el mismo que el método de Newton pero no requiere una derivada.

Podemos utilizar la iteración de punto fijo para encontrar la raíz de una función. Dada una función que hemos establecido en cero para encontrar la raíz ( ), reescribimos la ecuación en términos de de modo que se convierte en (tenga en cuenta que a menudo hay muchas funciones para cada función). A continuación, volvemos a etiquetar cada lado de la ecuación como de modo que podamos realizar la iteración. A continuación, elegimos un valor para y realizamos la iteración hasta que converja hacia una raíz de la función. Si la iteración converge, convergerá a una raíz. La iteración solo convergerá si .${\estilo de visualización f(x)}$${\displaystyle f(x)=0}$${\estilo de visualización x}$${\displaystyle f(x)=0}$${\displaystyle x=g(x)}$${\estilo de visualización g(x)}$${\displaystyle f(x)=0}$${\displaystyle x_{n+1}=g(x_{n})}$$estilo de visualización x_{1}}$${\displaystyle |g'(raíz)|<1}$

Como ejemplo de conversión a , si se da la función , la reescribiremos como una de las siguientes ecuaciones.${\displaystyle f(x)=0}$${\displaystyle x=g(x)}$${\displaystyle f(x)=x^{2}+x-1}$

${\displaystyle x_{n+1}=(1/x_{n})-1}$,

${\displaystyle x_{n+1}=1/(x_{n}+1)}$,

$Estilo de visualización x_{n+1}=1-x_{n}^{2}}$,

${\displaystyle x_{n+1}=x_{n}^{2}+2x_{n}-1}$, o

${\displaystyle x_{n+1}=\pm {\sqrt {1-x_{n}}}}$.

La aparición de valores complejos en los métodos de interpolación se puede evitar interpolando la inversa de f , lo que da como resultado el método de interpolación cuadrática inversa . Nuevamente, la convergencia es asintóticamente más rápida que el método secante, pero la interpolación cuadrática inversa a menudo se comporta mal cuando las iteraciones no están cerca de la raíz.

El método de Brent es una combinación del método de bisección, el método de la secante y la interpolación cuadrática inversa . En cada iteración, el método de Brent decide cuál de los tres métodos es el que probablemente dé mejores resultados y procede a realizar un paso de acuerdo con ese método. Esto da como resultado un método robusto y rápido, que por lo tanto goza de considerable popularidad.

El método de Ridders es un método híbrido que utiliza el valor de la función en el punto medio del intervalo para realizar una interpolación exponencial hasta la raíz. Esto proporciona una convergencia rápida con una convergencia garantizada de, como máximo, el doble del número de iteraciones que el método de bisección.

El método de bisección se ha generalizado a dimensiones superiores; estos métodos se denominan métodos de bisección generalizados . ^{[3] [4]} En cada iteración, el dominio se divide en dos partes y el algoritmo decide, basándose en un pequeño número de evaluaciones de funciones, cuál de estas dos partes debe contener una raíz. En una dimensión, el criterio de decisión es que la función tenga signos opuestos. El principal desafío al extender el método a múltiples dimensiones es encontrar un criterio que se pueda calcular fácilmente y que garantice la existencia de una raíz.

El teorema de Poincaré-Miranda proporciona un criterio para la existencia de una raíz en un rectángulo, pero es difícil de verificar porque requiere evaluar la función en todo el límite del rectángulo.

Otro criterio viene dado por un teorema de Kronecker ^[5] . Este dice que, si el grado topológico de una función f en un rectángulo no es cero, entonces el rectángulo debe contener al menos una raíz de f . Este criterio es la base de varios métodos de búsqueda de raíces, como los de Stenger ^[6] y Kearfott ^[7] . Sin embargo, calcular el grado topológico puede llevar mucho tiempo.

Un tercer criterio se basa en un poliedro característico . Este criterio se utiliza mediante un método llamado Bisección Característica. ^{[3] : 19--} No requiere calcular el grado topológico; solo requiere calcular los signos de los valores de la función. El número de evaluaciones requeridas es al menos , donde D es la longitud del borde más largo del poliedro característico. ^{[8] : 11, Lema.4.7} Nótese que ^[8] demuestra un límite inferior en el número de evaluaciones, y no un límite superior. ${\displaystyle \log _{2}(D/\epsilon )}$

Un cuarto método utiliza un teorema de valor intermedio sobre los símplices. ^[9] Nuevamente, no se da ningún límite superior para el número de consultas.

• JM McNamee: "Métodos numéricos para raíces de polinomios - Parte I", Elsevier (2007).
• JM McNamee y Victor Pan: "Métodos numéricos para raíces de polinomios - Parte II", Elsevier (2013).