Hispanopedia Wiki
Articulo de referencia

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

Hispanopedia WikiContenido en espanolLectura gratuita

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.

The behavior of general root-finding algorithms is studied in numerical analysis. However, for polynomials specifically, the study of root-finding algorithms belongs to computer algebra, since algebraic properties of polynomials are fundamental for the most efficient algorithms. The efficiency and applicability of an algorithm may depend sensitively on the characteristics of the given functions. For example, many algorithms use the derivative of the input function, while others work on every continuous function. In general, numerical algorithms are not guaranteed to find all the roots of a function, so failing to find a root does not prove that there is no root. However, for polynomials, there are specific algorithms that use algebraic properties for certifying that no root is missed and for locating the roots in separate intervals (or disks for complex roots) that are small enough to ensure the convergence of numerical methods (typically Newton's method) to the unique root within each interval (or disk).

Bracketing methods

Bracketing methods determine successively smaller intervals (brackets) that contain a root. When the interval is small enough, then a root is considered found. These generally use the intermediate value theorem, which asserts that if a continuous function has values of opposite signs at the end points of an interval, then the function has at least one root in the interval. Therefore, they require starting with an interval such that the function takes opposite signs at the end points of the interval. However, in the case of polynomials there are other methods such as Descartes' rule of signs, Budan's theorem and Sturm's theorem for bounding or determining the number of roots in an interval. They lead to efficient algorithms for real-root isolation of polynomials, which find all real roots with a guaranteed accuracy.

Bisection method

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 esregistro2⁡b−aε{\displaystyle \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,

do=aF(b)−bF(a)F(b)−F(a).{\displaystyle 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ónF(incógnita){\displaystyle f(x)}que hemos establecido a cero para encontrar la raíz (F(incógnita)=0{\displaystyle f(x)=0}), reescribimos la ecuación en términos deincógnita{\displaystyle x}de modo queF(incógnita)=0{\displaystyle f(x)=0}se convierteincógnita=gramo(incógnita){\displaystyle x=g(x)}(nota: a menudo hay muchosgramo(incógnita){\displaystyle g(x)}funciones para cadaF(incógnita)=0{\displaystyle f(x)=0}función). A continuación, renombramos cada lado de la ecuación comoincógnitanorte+1=gramo(incógnitanorte){\displaystyle x_{n+1}=g(x_{n})}para que podamos realizar la iteración. A continuación, elegimos un valor paraincógnita1{\displaystyle 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|gramo′(root)|<1{\displaystyle |g'(root)|<1}.

Como ejemplo de conversiónF(incógnita)=0{\displaystyle f(x)=0}aincógnita=gramo(incógnita){\displaystyle x=g(x)}, si se le da la funciónF(incógnita)=incógnita2+incógnita−1{\displaystyle f(x)=x^{2}+x-1}, la reescribiremos como una de las siguientes ecuaciones.

incógnitanorte+1=(1/incógnitanorte)−1{\displaystyle x_{n+1}=(1/x_{n})-1},
incógnitanorte+1=1/(incógnitanorte+1){\displaystyle x_{n+1}=1/(x_{n}+1)},
incógnitanorte+1=1−incógnitanorte2{\displaystyle x_{n+1}=1-x_{n}^{2}},
incógnitanorte+1=incógnitanorte2+2incógnitanorte−1{\displaystyle x_{n+1}=x_{n}^{2}+2x_{n}-1}, o
incógnitanorte+1=±1−incógnitanorte{\displaystyle 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 deincógnita{\displaystyle x}en la ecuación

a0+a1incógnita+a2incógnita2+⋯+anorteincógnitanorte=0{\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}=0}

dóndeai{\displaystyle 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 menosregistro2⁡(D/ϵ){\displaystyle \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.

Referencias

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

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