Algoritmos 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 reales o de los complejos a los complejos, es un número $x$ tal que $f (x) = 0$ . Como, en general, los ceros de una función no pueden calcularse exactamente ni expresarse en forma cerrada , los algoritmos de búsqueda de raíces proporcionan aproximaciones a ceros, expresados ya sea como números de punto flotante o como pequeños intervalos aislantes , o discos para raíces complejas (un intervalo o la salida del 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 encontrar las raíces de la función $h (x) = f (x) - g (x)$ . Así, 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 , lo que produce una secuencia de números que, con suerte, converge hacia la raíz como límite . Requieren una o más estimaciones iniciales de la raíz como valores iniciales, 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 momento, 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 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 análisis numérico . Sin embargo, en el caso de los polinomios, el estudio de la búsqueda de raíces pertenece generalmente al álgebra informática , 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 trabajan 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 exista. Sin embargo, para los polinomios , existen 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 como 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 bracketing

Los métodos de bracketing determinan intervalos sucesivamente más pequeños (paréntesis) que contienen una raíz. Cuando el intervalo es lo suficientemente pequeño, 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 los polinomios existen otros métodos ( la regla de los signos de Descartes , el teorema de Budan y el 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 polinomios de raíces reales , que garantizan la búsqueda de todas las raíces reales con una precisión garantizada.

método de bisección

El algoritmo de búsqueda de raíces más simple 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)$ tengan signos opuestos (un paréntesis). Sea $c = (a + b)/2$ la mitad del intervalo (el punto medio o el punto que biseca el intervalo). Entonces, $f (a)$ y $f (c)$ , o $f (c)$ y $f (b)$ tienen signos opuestos, y se ha dividido por dos el tamaño del intervalo. Aunque el método de bisección es robusto, gana un bit y sólo un bit de precisión con cada iteración. Por lo tanto, el número de evaluaciones de funciones necesarias para encontrar una raíz aproximada de ε es . Otros métodos, bajo condiciones apropiadas, pueden ganar precisión más rápidamente. $\log _{2}{\frac {ba}{\varepsilon }}$

Posición falsa ( regula falsi )

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 trazada en los puntos finales del intervalo. , eso es

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 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, es posible que no converja en algunas implementaciones ingenuas debido a errores de redondeo que pueden dar lugar a un signo incorrecto para $f (c)$ ; normalmente, esto puede ocurrir si la tasa de variación de $f$ es grande en la vecindad de la raíz.

método PTI

El método ITP es el único método conocido para poner entre paréntesis la raíz con las mismas garantías del peor de los casos del método de bisección, al 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 un rendimiento promedio superior al método de bisección para cualquier distribución continua en la ubicación de la raíz (ver Método ITP#Análisis ). Lo hace realizando un seguimiento tanto del intervalo de horquillado como del intervalo minmax en el que cualquier punto converge tan rápido como el método de bisección. La construcción del punto c consultado sigue tres pasos: interpolación (similar a la regula falsi), truncamiento (ajustando la regula falsi similar a Regula falsi § Mejoras en la regula falsi ) y luego proyección en el intervalo minmax. La combinación de estos pasos produce simultáneamente un método óptimo minmax 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 tanto en funciones suaves como en funciones no suaves.

Interpolación

Muchos procesos de búsqueda de raíces funcionan por interpolación . Consiste en utilizar los últimos valores aproximados calculados de la raíz para aproximar la función por un polinomio de bajo grado, 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 secante . Tres valores definen una función cuadrática , que aproxima la gráfica de la función mediante una parábola . Este es el método de Muller .

Regula falsi es también un método de interpolación, que se diferencia del método de la secante en que utiliza, para interpolar por 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 proceden 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 está suficientemente cerca de los anteriores.

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

El método de Newton supone que la función f tiene una derivada continua . Es posible que el método de Newton no converja 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 tipo 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 secante

Reemplazando 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 de 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 Lo mismo que el método de Newton pero no requiere una derivada.

Método de iteración de punto fijo

Podemos usar la iteración de punto fijo para encontrar la raíz de una función. Dada una función que hemos puesto a cero para encontrar la raíz ( ), reescribimos la ecuación en términos de de modo que se convierta (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 para que podamos realizar la iteración. A continuación, elegimos un valor 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 sólo convergerá si . $f(x)$ $f(x)=0$ $x$ $f(x)=0$ $x=g(x)$ $g(x)$ $f(x)=0$ $x_{n+1}=g(x_{n})$ $x_{1}$ $|g'(raíz)|<1$

Como ejemplo de conversión a , si se nos 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)

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 la 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 estos tres métodos tiene más probabilidades de funcionar mejor y continúa realizando un paso de acuerdo con ese método. Esto proporciona un método robusto y rápido, que por lo tanto goza de considerable popularidad.

Método de los jinetes

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 a la raíz. Esto proporciona una convergencia rápida con una convergencia garantizada de como máximo el doble de iteraciones que el método de bisección.

Raíces de polinomios

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

Encontrar 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 pueda calcularse fácilmente y que garantice la existencia de una raíz.

El teorema de Poincaré-Miranda da 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 triángulo.

Otro criterio viene dado por un teorema de Kronecker. ^[4] Dice que, si el grado topológico de una función f en un rectángulo es distinto de 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} Tenga en cuenta que ^[7] demuestra 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 simples. ^[8] Nuevamente, no se proporciona ningún límite superior para el número de consultas.

Ver también

Método de Broyden : método de búsqueda de raíces de Quasi-Newton 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 encontrar 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 una fórmula general sea verdadera.
algoritmo de raíz $n -ésima$
Sistema de ecuaciones polinomiales – Raíces de múltiples polinomios multivariados
Teorema de Kantorovich – Acerca de la convergencia del método de Newton

Referencias

^ Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Capítulo 9. Búsqueda de raíces y conjuntos de ecuaciones no lineales". Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
^ ab Mourrain, B.; Vrahatis, Minnesota; Yakoubsohn, JC (1 de junio de 2002). "Sobre la complejidad de aislar raíces reales y calcular con certeza el grado topológico". Revista de Complejidad . 18 (2): 612–640. doi : 10.1006/jcom.2001.0636 . ISSN 0885-064X.
^ Vrahatis, Michael N. (2020). "Generalizaciones del teorema del valor intermedio para la aproximación de puntos fijos y ceros de funciones continuas". En Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.). Apuntes de conferencias sobre 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. S2CID 211160947. {{cite book}}: |journal=ignorado ( ayuda ) ; Falta o está vacío |title=( ayuda )
^ "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). "Calcular el grado topológico de un mapeo en Rn". Matemática numérica . 25 (1): 23–38. doi :10.1007/BF01419526. ISSN 0945-3245. S2CID 122196773.
^ Kearfott, panadero (1 de junio de 1979). "Un método eficiente de cálculo de grados para un método generalizado de bisección". Matemática numérica . 32 (2): 109–127. doi :10.1007/BF01404868. ISSN 0029-599X. S2CID 122058552.
^ ab Vrahatis, manganeso; Iordanidis, KI (1 de marzo de 1986). "Un método rápido generalizado de bisección para resolver sistemas de ecuaciones no lineales". Matemática numérica . 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 simplificaciones para aproximación simplificada de puntos fijos y ceros". Topología y sus aplicaciones . 275 : 107036. doi : 10.1016/j.topol.2019.107036. ISSN 0166-8641. S2CID 213249321.

Otras lecturas

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