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.$ Dado que, generalmente, 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 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 la ecuación $f (x) = g (x)$ equivale a 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 pueden utilizarse para resolver cualquier ecuación de funciones continuas. Sin embargo, la mayoría de estos algoritmos no garantizan encontrar todas las raíces de una función, y si no encuentran ninguna, no significa necesariamente que no existan.

La mayoría de los métodos numéricos para encontrar raíces son iterativos , produciendo una secuencia de números que idealmente converge hacia una raíz como límite . Requieren una o más estimaciones iniciales de la raíz como valores de partida, y cada iteración del algoritmo produce una aproximación cada vez más precisa. 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 los valores subsiguientes 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, en el caso específico de los polinomios, 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 aplicabilidad de un algoritmo pueden depender en gran medida 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 con cualquier 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 ninguna. Sin embargo, para los polinomios , existen algoritmos específicos que utilizan propiedades algebraicas para certificar que no se omite ninguna raíz y para localizar las raíces en intervalos separados (o discos para raíces complejas) lo suficientemente pequeños como para asegurar la convergencia de los métodos numéricos (típicamente el método de Newton ) a la única raíz dentro de cada intervalo (o disco).

Métodos de acotación

Los métodos de acotación determinan intervalos sucesivamente más pequeños (paréntesis) que contienen una raíz. Cuando el intervalo es suficientemente pequeño, se considera que se ha encontrado una raíz. Estos métodos suelen utilizar el teorema del valor intermedio , que afirma que si una función continua tiene valores de signo opuesto en los extremos de un intervalo, entonces la función tiene al menos una raíz en dicho intervalo. Por lo tanto, requieren comenzar con un intervalo tal que la función tome signos opuestos en sus extremos. 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. Estos métodos dan lugar a algoritmos eficientes para el aislamiento de raíces reales de polinomios, que encuentran 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 paréntesis). Sea $c = (a + b)/2$ el punto medio del intervalo (el punto medio o el punto que biseca el intervalo). Entonces, o bien $f (a)$ y $f (c)$ , o bien $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 de precisión con cada iteración. Por lo tanto, el número de evaluaciones de la función necesarias para encontrar una raíz ε -aproximada es $\log _{2}{\frac {ba}{\varepsilon }}$ Otros métodos, en condiciones apropiadas, pueden lograr mayor precisión con mayor rapidez.

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 usar el punto medio del intervalo de la búsqueda de bisección, usa la intersección con el eje $x$ de la línea que conecta los valores de la función trazada en los extremos del intervalo, es decir,

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

El método de la posición falsa es similar al método de la secante , con la diferencia de que, en lugar de conservar los dos últimos puntos, se asegura de mantener un punto a cada lado de la raíz. Este método puede ser más rápido que el método de bisección y nunca diverge como el de la secante. Sin embargo, en algunas implementaciones simples, puede fallar en la convergencia debido a errores de redondeo que pueden generar un signo incorrecto para $f (c)$ . Esto suele ocurrir si la derivada de $f$ es grande en las proximidades de la raíz.

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 bajo grado, que toma los mismos valores en dichas 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 el proceso se repite.

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 al utilizar 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 Muller .

Métodos iterativos

Aunque todos los algoritmos de búsqueda de raíces proceden por 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, la cual 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.

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

El método de Newton asume que la función f tiene una derivada continua . Este método 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; 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 al de Newton con órdenes de convergencia más altos. El primero después del método de Newton es el método de Halley, con un orden de convergencia cúbico.

Método de la secante

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 razón áurea , aproximadamente 1,62 ^{[ 2 ]} ). 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 polinómico 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 del 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 $f(x)$ que hemos establecido a cero para encontrar la raíz ( $f(x)=0$ ), reescribimos la ecuación en términos de $x$ de modo que $f(x)=0$ se convierte $x=g(x)$ (nota: a menudo hay muchos $g(x)$ funciones para cada $f(x)=0$ función). A continuación, renombramos cada lado de la ecuación como $x_{n+1}=g(x_{n})$ para que podamos realizar la iteración. A continuación, elegimos un valor para $x_{1}$ y realizar 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 $|g'(root)|<1$ .

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

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 puede evitarse 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 con el método de la secante, pero la interpolación cuadrática inversa suele presentar un comportamiento deficiente 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 combina el 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 determina cuál de los tres métodos ofrece mejores resultados y procede realizando un paso según dicho método. Esto da como resultado un método robusto y rápido, que goza de gran popularidad.

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 en un número de iteraciones como máximo el doble que el del método de bisección.

Raíces de polinomios

Encontrar las raíces de polinomios es un problema de larga data que se ha estudiado extensamente a lo largo de la historia y ha influido sustancialmente en el desarrollo de las matemáticas. Implica determinar una aproximación numérica o una expresión en forma cerrada de las raíces de un polinomio univariado, es decir, determinar soluciones aproximadas o en forma cerrada de $x$ en la ecuación

$a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}=0$

dónde $a_{i}$ son números reales o complejos .

Los esfuerzos por comprender y resolver ecuaciones polinómicas llevaron al desarrollo de importantes conceptos matemáticos, incluidos los números irracionales y complejos, así como estructuras fundamentales en el álgebra moderna, como cuerpos , anillos y grupos .

A pesar de su importancia histórica, encontrar las raíces de polinomios de grado superior ya no desempeña un papel central en las matemáticas y las matemáticas computacionales, con una excepción importante en el álgebra computacional . ^{[ 3 ]}

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 . ^{[ 4 ]}^{[ 5 ]} 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 la función— 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 contorno del rectángulo.

Otro criterio viene dado por un teorema de Kronecker . ^{[ 6 ]} Este teorema establece 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 para encontrar raíces, como los de Stenger ^{[ 7 ]} y Kearfott. ^{[ 8 ]} Sin embargo, calcular el grado topológico puede ser laborioso.

Un tercer criterio se basa en un poliedro característico . Este criterio se utiliza en un método llamado bisección característica. ^{[ 4 ]}^{: 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 $\log _{2}(D/\epsilon )$ , donde D es la longitud de la arista más larga del poliedro característico. ^{[ 9 ]}^{: 11, Lema.4.7} Nótese que Vrahatis e Iordanidis ^{[ 9 ]} demuestran una cota inferior en el número de evaluaciones, y no una cota superior.

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

Véase también

Método de Broyden : método cuasi-Newton para la búsqueda de raíces en el caso multivariable.

Generador de números pseudoaleatorios criptográficamente seguro : tipo de funciones diseñadas para ser irresolubles 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 hallar 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 un objeto debe contarse para que una fórmula general sea verdadera.
algoritmo de la raíz $n -ésima$
Sistema de ecuaciones polinómicas – Raíces de polinomios multivariables múltiples
Teorema de Kantorovich – Sobre 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 sistemas de ecuaciones no lineales» . Numerical Recipes: The Art of Scientific Computing (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
↑ Chanson, Jeffrey R. (3 de octubre de 2024). "Orden de convergencia" . LibreTexts Mathematics . Recuperado el 3 de octubre de 2024 .
↑ Pan, Victor Y. (enero de 1997). "Resolución de una ecuación polinómica: algunos antecedentes y avances recientes" . SIAM Review . 39 (2): 187– 220. doi : 10.1137/S0036144595288554 . ISSN 0036-1445 .
1 2 Mourrain, B.; Vrahatis, MN; Yakoubsohn, JC (2002-06-01). "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.). Computación numérica: teoría y algoritmos . Lecture Notes in Computer Science. Vol. 11974. Cham: Springer International Publishing. pp. 223–238 . doi : 10.1007/978-3-030-40616-5_17 . ISBN 978-3-030-40616-5. S2CID 211160947 .
↑ Ortega, James M.; Rheinboldt, Werner C. (2000). Solución iterativa de ecuaciones no lineales en varias variables . Society for Industrial and Applied Mathematics. ISBN 978-0-89871-461-6.
↑ Stenger, Frank (1975-03-01). "Cálculo del grado topológico de una aplicación en Rn". Numerische Mathematik . 25 (1): 23– 38. doi : 10.1007/BF01419526 . ISSN 0945-3245 . S2CID 122196773 .
↑ Kearfott, Baker (1979-06-01). "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 .
1 2 Vrahatis, MN; Iordanidis, KI (1986-03-01). "Un método generalizado rápido de bisección para resolver sistemas de ecuaciones no lineales". Numerische Mathematik . 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" . Topology and Its Applications . 275 107036. doi : 10.1016/j.topol.2019.107036 . ISSN 0166-8641 . S2CID 213249321 .

Lecturas adicionales

Victor Yakovlevich Pan: "Resolución de una ecuación polinómica: algunos antecedentes y avances recientes", SIAM Review, vol. 39, n.° 2, págs. 187-220 (junio de 1997).
John Michael McNamee: Métodos numéricos para raíces de polinomios - Parte I , Elsevier, ISBN 978-0-444-52729-5 (2007).
John Michael McNamee y Victor Yakovlevich Pan: Métodos numéricos para raíces de polinomios - Parte II , Elsevier, ISBN 978-0-444-52730-1 (2013).

[1] Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Capítulo 9. Búsqueda de raíces y sistemas de ecuaciones no lineales» . Numerical Recipes: The Art of Scientific Computing (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.

[2] Chanson, Jeffrey R. (3 de octubre de 2024). "Orden de convergencia" . LibreTexts Mathematics . Recuperado el 3 de octubre de 2024 .

[Polynomial_root-finding_:1-3] Pan, Victor Y. (enero de 1997). "Resolución de una ecuación polinómica: algunos antecedentes y avances recientes" . SIAM Review . 39 (2): 187– 220. doi : 10.1137/S0036144595288554 . ISSN 0036-1445 .

[:0-4] 1 2 Mourrain, B.; Vrahatis, MN; Yakoubsohn, JC (2002-06-01). "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 .

[5] 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.). Computación numérica: teoría y algoritmos . Lecture Notes in Computer Science. Vol. 11974. Cham: Springer International Publishing. pp. 223–238 . doi : 10.1007/978-3-030-40616-5_17 . ISBN 978-3-030-40616-5. S2CID 211160947 .

[6] Ortega, James M.; Rheinboldt, Werner C. (2000). Solución iterativa de ecuaciones no lineales en varias variables . Society for Industrial and Applied Mathematics. ISBN 978-0-89871-461-6.

[7] Stenger, Frank (1975-03-01). "Cálculo del grado topológico de una aplicación en Rn". Numerische Mathematik . 25 (1): 23– 38. doi : 10.1007/BF01419526 . ISSN 0945-3245 . S2CID 122196773 .

[8] Kearfott, Baker (1979-06-01). "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 .

[:2-9] 1 2 Vrahatis, MN; Iordanidis, KI (1986-03-01). "Un método generalizado rápido de bisección para resolver sistemas de ecuaciones no lineales". Numerische Mathematik . 49 (2): 123– 138. doi : 10.1007/BF01389620 . ISSN 0945-3245 . S2CID 121771945 .

[10] 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" . Topology and Its Applications . 275 107036. doi : 10.1016/j.topol.2019.107036 . ISSN 0166-8641 . S2CID 213249321 .

[ 1 ]

[ 2 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 10 ]