Algoritmos de búsqueda de raíces

ImprimirCitar

En matemáticas e informática, un algoritmo de búsqueda de raíces es un algoritmo para encontrar ceros, también llamado "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 pueden calcularse con exactitud ni expresarse en forma cerrada, los algoritmos de búsqueda de raíces proporcionan aproximaciones a los ceros, expresados ya sea como números de coma flotante o como pequeños intervalos de aislamiento, 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).

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, convergen 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 subsiguientes evaluando una función auxiliar sobre los valores anteriores. El límite es, pues, 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 usan 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 haya raíz. Sin embargo, para polinomios, existen algoritmos específicos que usan propiedades algebraicas para certificar que no se pierde 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 métodos numéricos (típicamente Newton&# 39; método s) a la raíz única así ubicada.

Métodos de horquillado

Los métodos de horquillado determinan intervalos cada vez 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. Por lo general, utilizan el teorema del valor intermedio, que afirma que si una función continua tiene valores de signos opuestos en los extremos 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 (regla de los 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, lo que asegura encontrar 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)$ tienen signos opuestos (un paréntesis). Sea $c = (a + b)/2$ el medio 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 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. Otros métodos, bajo condiciones apropiadas, pueden ganar precisión más rápidamente.

Posición falsa (regula falsi)

El método de posición falsa, también llamado método regula falsi, es similar al método de bisección, pero en lugar de usar la búsqueda de bisección en el medio del intervalo, usa la intersección x de la línea que conecta los valores de la función trazada en los extremos 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 la bisección y nunca divergerá 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 generar un signo incorrecto para $f (c)< /lapso>; normalmente, 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 poner entre paréntesis la raíz con las mismas garantías en el 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 mejor rendimiento que el método de bisección en promedio para cualquier distribución continua en la ubicación de la raíz (consulte Análisis del método ITP). Lo hace al realizar 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 consultado c sigue tres pasos: interpolación (similar a la regula falsi), truncamiento (ajuste de la regula falsi similar a la 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 en funciones suaves y 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 mediante 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 usa 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 se aproxima a la gráfica de la función por 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 línea, 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 por iteración, un método iterativo de búsqueda de raíces generalmente usa 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 se aproxima lo suficiente a los anteriores.

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

El método de Newton asume 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, por lo general, es 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 más altos son los métodos del jefe de familia. 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

Reemplazando la derivada en el método de Newton con una diferencia finita, obtenemos el método de la secante. Este método no requiere el cálculo (ni la existencia) de un derivado, pero el precio es de convergencia más lenta (el orden es de aproximadamente 1,6 (proporción áurea)). Una generalización del método de la secante en dimensiones superiores es el método de Broyden.

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, para 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 la función ${displaystyle f(x)}$ que hemos establecido a cero para encontrar la raíz ( ${displaystyle f(x)=0}$ ), reescribimos la ecuación en términos de ${displaystyle x}$ así ${displaystyle f(x)=0}$ se convierte en ${displaystyle x=g(x)}$ (nota, a menudo hay muchos ${displaystyle g(x)}$ funciones para cada ${displaystyle f(x)=0}$ función). A continuación, reetiquetar el lado de la ecuación como ${displaystyle x_{n+1}=g(x_{n}}$ para que podamos realizar la iteración. A continuación, elegimos un valor para ${displaystyle x_{1}}$ y realizar la iteración hasta que converge 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 ${displaystyle Silenciog'(root)$ .

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

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

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

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

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

, o

{displaystyle x_{n+1}=pm {cHFF} {1-x_{n}}}

Interpolación inversa

La aparición de valores complejos en los métodos de interpolación se puede evitar interpolando el inverso 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 de la 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

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 qué método de estos tres es probable que funcione mejor y procede con un paso de acuerdo con ese método. Esto proporciona un método robusto y rápido, que por lo tanto goza de una considerable popularidad.

Ridders' método

Ridders' El método 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 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. Un testamento a esto es que hasta el siglo XIX, el álgebra significaba esencialmente teoría de las ecuaciones polinómicas.

Contenido relacionado

Más resultados...