Algoritmo para encontrar el cero de una función

Un algoritmo para encontrar un cero de una función es un método numérico o un algoritmo para encontrar un valor aproximado de una $x que$ satisface $f ( x ) = 0$ , para una función dada $f$ . Aquí $x$ es un número real llamado cero de $f$ o cuando $f$ es polinomio, raíz de $f$ .

Cuando $x$ es un vector, los algoritmos para encontrar $x$ tales que $f ( x ) = 0$ se denominan generalmente "algoritmos para resolver numéricamente un sistema de ecuaciones". Estos algoritmos son una generalización de los algoritmos para encontrar un cero de una función y se pueden aplicar a ecuaciones lineales o no lineales . Ciertos algoritmos para encontrar ceros (como el método de Newton ) se pueden generalizar a la resolución numérica de sistemas de ecuaciones no lineales.

Los algoritmos para encontrar los ceros de una función se estudian en análisis numérico .

Algoritmos específicos

Dicotomía

El método de dicotomía es el algoritmo más simple para encontrar ceros de una función continua : comenzar con dos puntos de $una$ y $b$ que rodean a un cero de la función, y en cada iteración, elija una de las dos intervalos $[ a , c ]$ o $[ c , b ]$ , $c = ( a + b ) / 2$ siendo el punto medio de $una$ y $b$ . El algoritmo se basa en la elección del subintervalo de $[ a , b ]$ que contiene un cero. En la mayoría de los casos, el método de dicotomía garantiza la convergencia a cero cuando la función es continua . Su progresión en la investigación es bastante lenta, ya que su velocidad de convergencia es lineal. Una de las peculiaridades de este algoritmo es que es posible conocer de antemano el número de iteraciones necesarias para determinar la raíz de la ecuación con la precisión deseada.

Newton-Raphson

El método de Newton , también conocido como Newton-Raphson, supone que $f$ es de clase C 1 . La función $f$ se "linealiza" en el valor aproximado actual de cero, utilizando la derivada de la función. Esto da la relación de recurrencia :

x_ {k + 1} = x_k - \ frac {f (x_k)} {f '(x_k)}.

Es posible que el método de Newton no converja si el valor inicial está demasiado lejos de cero. Sin embargo, si converge, es mucho más rápido que el método de dicotomía (su velocidad de convergencia es cuadrática ). Se puede generalizar fácilmente a problemas de dimensiones superiores.

Secante

Si la derivada de la función en el método de Newton se reemplaza por una diferencia finita , obtenemos el método de la secante . Utiliza la relación recurrente:

{\ Displaystyle x_ {n + 1} = x_ {n} - {\ frac {x_ {n} -x_ {n-1}} {f (x_ {n}) - f (x_ {n-1})} } f (x_ {n})}

Este método no requiere el cálculo de una derivada, pero tiene el costo de una velocidad de convergencia más lenta que la de Newton (del orden de 1.618). Sin embargo, como solo requiere una evaluación de función por iteración, generalmente es más rápido que el método de Newton. Su generalización en dimensión mayor que 1 es el método de Broyden (en) .

Regula falsi

El método de posición falsa , también llamado método regula falsi , es similar al método de dicotomía. Sin embargo, no corta el intervalo en dos partes iguales en cada iteración, sino en un punto dado por la fórmula del método de la secante. Este método hereda la robustez del método de dicotomía y la complejidad "super-lineal" del método secante.

El método de Muller

El método de la secante evalúa la raíz de la función $f$ aproximándola por interpolación lineal . El método de Muller evalúa la raíz por interpolación cuadrática utilizando los tres puntos finales calculados. Converge más rápido que el método de la secante (orden de convergencia de 1,84). Requiere la evaluación de una raíz cuadrada en cada iteración. Una peculiaridad de este método es que el término iterado $x n$ puede volverse complejo .

Interpolación cuadrática inversa

La desventaja del método de Müller se puede evitar interpolando la biyección recíproca de $f$ , que conduce al método de interpolación cuadrática inversa . Una vez más, la convergencia es asintóticamente más rápida que el método de la secante, pero a menudo se comporta mal cuando las iteraciones no están cerca de cero.

Método Brent

El método de Brent es una combinación del método de dicotomía, el método de la secante y la interpolación cuadrática inversa. En cada iteración, este método decide cuál de estos tres métodos es más probable que se acerque a cero y realiza un paso utilizando ese método. Esto da como resultado un método robusto y rápido que es muy popular y muy apreciado.

Gradiente conjugado

Otros algoritmos

Otros algoritmos de búsqueda cero son:

método de punto fijo : la ecuación $f ( x ) = 0$ se reformula en la forma $x = g ( x )$ donde $g$ se elige de manera que cualquier secuencia $( x n )$ dada por $x n +1 = g ( x n )$ converge a un cero de $f$ .

Encontrar las raíces de un polinomio

Se ha prestado especial atención al caso especial en el que $f$ es una función polinomial . Por supuesto, se pueden utilizar los métodos descritos en la sección anterior. En particular, es fácil determinar la derivada de un polinomio y el método de Newton es un muy buen candidato. Pero es posible elegir un método que aproveche el hecho de que $f$ es un polinomio.

Una posibilidad es considerar la matriz acompañante asociada con el polinomio. Sabiendo que los valores propios de esta matriz coinciden con las raíces del polinomio, se puede utilizar cualquier algoritmo de búsqueda de valores propios para encontrar valores aproximados de las raíces del polinomio inicial, por ejemplo, el método de potencia iterada .

Otra posibilidad es utilizar el método de Laguerre , que en determinadas condiciones ciertamente converge hacia una de las raíces (convergencia global). Su velocidad de convergencia es cúbica para raíces simples.

Si el polinomio tiene coeficientes racionales y si solo buscamos raíces racionales, entonces se puede utilizar el método de Ruffini .

En todos los casos, las raíces de los valores aproximados del problema de investigación pueden estar mal condicionadas, como lo muestran los polinomios de Wilkinson (in) .

Referencias

(fr) Este artículo está parcial o totalmente extraído del artículo de Wikipedia en inglés titulado “ Algoritmo de búsqueda de raíces ” ( consulte la lista de autores ) .

Ver también

enlaces externos