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$ , de los números reales a los números reales o de los números complejos a los números complejos, 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, expresados como números de punto flotante o como pequeños intervalos de aislamiento , o discos para raíces complejas (una salida de intervalo o disco es equivalente a una salida aproximada junto con un límite de error). ^[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 permiten resolver cualquier ecuación definida por 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; en particular, si dicho algoritmo no encuentra ninguna raíz, eso no significa que no exista ninguna raíz.

La mayoría de los métodos numéricos de búsqueda de raíces utilizan la iteración , que produce una secuencia de números que, con suerte, converge hacia la raíz como su 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, el estudio de la búsqueda de raíces pertenece generalmente al álgebra computacional , ya que las propiedades algebraicas de los polinomios son fundamentales para los algoritmos más eficientes. La eficiencia de un algoritmo puede depender dramáticamente 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 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 así ubicada.

Métodos de horquillado

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, entonces se ha encontrado una raíz. 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 polinomios existen otros métodos ( regla de signos de Descartes , teorema de Budan y teorema de Sturm ) para obtener información sobre el número de raíces en un intervalo. Conducen a algoritmos eficientes para el aislamiento de raíces reales de polinomios, que aseguran encontrar todas las raíces reales con una precisión garantizada.

Método de bisección

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. $\log _{2}{\frac {ba}{\varepsilon }}$

Posición falsa (regulación falsa)

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

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)$ ; típicamente, esto puede ocurrir si la tasa de variación de $f$ es grande en la vecindad de la raíz.

Método ITP

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 encerrado 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 en funciones suaves y no suaves.

Interpolación

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.

Dos valores permiten interpolar una función por un polinomio de grado uno (es decir, aproximar la gráfica de la función por una recta). Esta es la base del método de la secante . Tres valores definen una función cuadrática , que aproxima la gráfica de la función por una parábola . Este es el método de Müller .

La regla falsa es también un método de interpolación, que se diferencia del método secante en que utiliza, para interpolar mediante una recta, dos puntos que no son necesariamente los dos últimos puntos calculados.

Métodos iterativos

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 ( hasta la precisión deseada) de la función auxiliar, es decir, cuando el nuevo valor calculado es suficientemente cercano a los anteriores.

El método de Newton (y otros métodos similares basados en derivadas)

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 inicia demasiado lejos de una raíz. Sin embargo, cuando converge, es más rápido que el método de bisección y suele ser cuadrático. El método de Newton también es importante porque se generaliza fácilmente a problemas de dimensiones superiores. Los métodos similares a Newton con órdenes de convergencia superiores son los métodos de Householder . El primero después del método de Newton es el método de Halley con orden cúbico de convergencia.

Método de la secante

Sustituyendo la derivada del 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 es aproximadamente 1,6 ( proporción áurea )). Una generalización del método de la secante en dimensiones superiores es el método de Broyden .

El método de Steffensen

Si utilizamos un ajuste polinomial para eliminar la parte cuadrática de la diferencia finita utilizada en el método de la 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.

Método de iteración de punto fijo

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)}$ $f(x)=0$ ${\estilo de visualización x}$ $f(x)=0$ $x=g(x)$ ${\estilo de visualización g(x)}$ $f(x)=0$ $x_{n+1}=g(x_{n})$ $estilo de visualización x_{1}}$ $|g'(raíz)|<1$

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

x_{n+1}=(1/x_{n})-1

x_{n+1}=1/(x_{n}+1)

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

x_{n+1}=x_{n}^{2}+2x_{n}-1

, o

x_{n+1}=\pm {\sqrt {1-x_{n}}}

Interpolación inversa

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.

Combinaciones de métodos

El método de Brent

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

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.

Raíces de polinomios

Encontrar raíces polinómicas es un problema de larga data que ha sido objeto de mucha investigación a lo largo de la historia. Prueba de ello es que hasta el siglo XIX, álgebra significaba esencialmente teoría de ecuaciones polinómicas .

Encontrando raíces en dimensiones superiores

El método de bisección se ha generalizado a dimensiones superiores; estos métodos se denominan métodos de bisección generalizados . ^[2]^[3] 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, ya que requiere evaluar la función en todo el límite del rectángulo.

Otro criterio viene dado por un teorema de Kronecker ^[4] . 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 ^[5] y Kearfott ^[6] . 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. ^[2]^{: 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. ^[7]^{: 11, Lema.4.7} Nótese que ^[7] prueba un límite inferior en el número de evaluaciones, y no un límite superior. $\log _{2}(D/\epsilon )$

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

Véase también

Método de Broyden : método de búsqueda de raíces cuasi-newtonianas para el caso multivariable

Generador de números pseudoaleatorios criptográficamente seguro : tipo de funciones diseñadas para que no puedan resolverse mediante algoritmos de búsqueda de raíces
Biblioteca científica GNU
Método de Graeffe : algoritmo para hallar raíces polinómicas
Método de Lill – Método gráfico para las raíces reales de un polinomio
MPSolve – Software para aproximar las raíces de un polinomio con una precisión arbitrariamente alta
Multiplicidad (matemáticas) : Número de veces que se debe contar un objeto para que sea verdadera una fórmula general.
algoritmo de raíz $n- ésima$
Sistema de ecuaciones polinómicas – Raíces de múltiples polinomios multivariados
Teorema de Kantorovich – Acerca de la convergencia del método de Newton

Referencias

^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Capítulo 9. Búsqueda de raíces y conjuntos no lineales de ecuaciones". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
^ ab Mourrain, B.; Vrahatis, MN; Yakoubsohn, JC (1 de junio de 2002). "Sobre la complejidad de aislar raíces reales y calcular con certeza el grado topológico". Journal of Complexity . 18 (2): 612–640. doi : 10.1006/jcom.2001.0636 . ISSN 0885-064X.
^ Vrahatis, Michael N. (2020). "Generalizaciones del teorema del valor intermedio para aproximar puntos fijos y ceros de funciones continuas". En Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.). Cálculos numéricos: teoría y algoritmos . Apuntes de clase en informática. Vol. 11974. Cham: Springer International Publishing. págs. 223–238. doi :10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5.S2CID211160947 .
^ "Solución iterativa de ecuaciones no lineales en varias variables". Libros guía . Consultado el 16 de abril de 2023 .
^ Stenger, Frank (1 de marzo de 1975). "Cálculo del grado topológico de una aplicación en Rn". Matemáticas numéricas . 25 (1): 23–38. doi :10.1007/BF01419526. ISSN 0945-3245. S2CID 122196773.
^ Kearfott, Baker (1 de junio de 1979). "Un método eficiente de cálculo de grados para un método generalizado de bisección". Numerische Mathematik . 32 (2): 109–127. doi :10.1007/BF01404868. ISSN 0029-599X. S2CID 122058552.
^ ab Vrahatis, MN; Iordanidis, KI (1986-03-01). "Un método generalizado rápido de bisección para resolver sistemas de ecuaciones no lineales". Matemáticas numéricas . 49 (2): 123–138. doi :10.1007/BF01389620. ISSN 0945-3245. S2CID 121771945.
^ Vrahatis, Michael N. (15 de abril de 2020). "Teorema del valor intermedio para símplices para la aproximación simplicial de puntos fijos y ceros". Topología y sus aplicaciones . 275 : 107036. doi : 10.1016/j.topol.2019.107036 . ISSN 0166-8641. S2CID 213249321.

Lectura adicional

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).