En el análisis numérico , el método de Steffensen es una técnica de búsqueda de raíces que lleva el nombre de Johan Frederik Steffensen, que es similar al método de Newton . El método de Steffensen también logra la convergencia cuadrática , pero sin usar derivadas como lo hace el método de Newton .
Descripción simple
La forma más simple de la fórmula del método de Steffensen ocurre cuando se usa para encontrar los ceros o raíces de una función. ; es decir: encontrar el valor que satisface . Cerca de la solución, la función se supone que satisface aproximadamente esta condición hace adecuado como función de corrección para para encontrar su propia solución, aunque no es necesario que funcione de manera eficiente. Para algunas funciones, el método de Steffensen puede funcionar incluso si no se cumple esta condición, pero en tal caso, el valor inicialdebe estar muy cerca de la solución realy la convergencia a la solución puede ser lenta.
Dado un valor inicial adecuado , una secuencia de valores se puede generar usando la fórmula siguiente. Cuando funciona, cada valor en la secuencia está mucho más cerca de la solución.que el valor anterior. El valor del paso actual genera el valor para el siguiente paso, a través de esta fórmula: [1]
para n = 0, 1, 2, 3, ..., donde la función pendiente es un compuesto de la función original dado por la siguiente fórmula:
o equivalente
- dónde .
La función es el valor medio de la pendiente de la función entre el último punto de secuencia y el punto auxiliar , con el paso . También se denomina diferencia dividida de primer orden de entre esos dos puntos.
Es solo con el propósito de encontrar para este punto auxiliar que el valor de la función debe ser una corrección adecuada para acercarse a su propia solución, y por ello cumplir con el requisito de que . Para todas las demás partes del cálculo, el método de Steffensen solo requiere la funciónser continuo y tener una solución cercana. [1] Varias modificaciones modestas del paso en el cálculo de pendiente existen para acomodar funciones que no cumplen con el requisito.
Ventajas e inconvenientes
La principal ventaja del método de Steffensen es que tiene convergencia cuadrática [1] como el método de Newton, es decir, ambos métodos encuentran raíces en una ecuación.igual de "rápido". En este caso, rápidamente significa que para ambos métodos, el número de dígitos correctos en la respuesta se duplica con cada paso. Pero la fórmula del método de Newton requiere la evaluación de la derivada de la función así como la función , mientras que el método de Steffensen solo requiere sí mismo. Esto es importante cuando el derivado no está disponible de manera fácil o eficiente.
El precio de la convergencia rápida es la evaluación de doble función: Ambos y debe calcularse, lo que puede llevar mucho tiempo si es una función complicada. A modo de comparación, el método de la secante solo necesita una evaluación de función por paso. El método de la secante aumenta el número de dígitos correctos "sólo" en un factor de aproximadamente 1,6 por paso, pero se pueden hacer el doble de pasos del método de la secante en un tiempo determinado. Dado que el método de la secante puede realizar el doble de pasos al mismo tiempo que el método de Steffensen, [a] cuando ambos algoritmos tienen éxito, el método de la secante converge más rápido que el método de Steffensen en la práctica real: el método de la secante alcanza un factor de aproximadamente (1.6) 2 ≈ 2,6 veces más dígitos por cada dos pasos (dos evaluaciones de funciones), en comparación con el factor 2 de Steffensen para cada paso (dos evaluaciones de funciones).
Similar a la mayoría de los otros algoritmos iterativos de búsqueda de raíces , la debilidad crucial en el método de Steffensen es la elección del valor inicial . Si el valor de no está lo suficientemente cerca de la solución real , el método puede fallar y la secuencia de valores puede cambiar entre dos extremos o divergir hasta el infinito.
Derivación utilizando el proceso delta cuadrado de Aitken
La versión del método de Steffensen implementada en el código MATLAB que se muestra a continuación se puede encontrar utilizando el proceso delta cuadrado de Aitken para acelerar la convergencia de una secuencia. Para comparar las siguientes fórmulas con las fórmulas de la sección anterior, observe que . Este método supone comenzar con una secuencia linealmente convergente y aumenta la tasa de convergencia de esa secuencia. Si los signos de de acuerdo y está 'suficientemente cerca' del límite deseado de la secuencia , podemos asumir lo siguiente:
luego
entonces
y por lo tanto
- .
Resolviendo el límite deseado de la secuencia da:
lo que da como resultado la secuencia convergente más rápida:
Implementación en Matlab
Aquí está la fuente para una implementación del método de Steffensen en MATLAB .
función Steffensen ( f, p0, tol ) % Esta función toma como entradas: una función de iteración de punto fijo, f, % y estimación inicial al punto fijo, p0, y una tolerancia, tol.% Se supone que la función de iteración de punto fijo se introduce como% función en línea. % Esta función calculará y devolverá el punto fijo, p, % que hace que la expresión f (x) = p sea verdadera dentro de la deseada % de tolerancia, tol.formato compacto % Esto acorta la salida. format long % Imprime más posiciones decimales. para i = 1 : 1000 % prepárese para hacer un número grande, pero finito, de iteraciones. % Esto es para que si el método no converge, no % estar atrapado en un bucle infinito. p1 = f ( p0 ); % calcula las dos próximas conjeturas para el punto fijo. p2 = f ( p1 ); p = p0 - ( p1 - p0 ) ^ 2 / ( p2 - 2 * p1 + p0 ) % usa el método delta cuadrado de Aitken para % encuentra una mejor aproximación a p0. if abs ( p - p0 ) < tol % prueba para ver si estamos dentro de la tolerancia. break % si lo estamos, detengamos las iteraciones, tenemos nuestra respuesta. final p0 = p ; % actualiza p0 para la siguiente iteración. finalif abs ( p - p0 ) > tol % Si no cumplimos con la tolerancia, generamos un % mensaje de error. 'no pudo converger en 1000 iteraciones.'final
Implementación en Python
Aquí está la fuente para una implementación del método de Steffensen en Python .
def g ( f , x : float , fx : float ): "" "Función de diferencia dividida de primer orden. Argumentos: f (invocable): Entrada de función ag x (float): Punto en el que evaluar g fx (float): Función f evaluada en x "" " return lambda x : f ( x + fx ) / fx - 1def steff ( f , x : float ): "" "Algoritmo de Steffenson para encontrar raíces. Este generador recursivo produce el valor x_n + 1 primero y luego, cuando el generador itera, produce x_n + 2 desde el siguiente nivel de recursividad. Argumentos: f (invocable): función cuya raíz buscamos x (float): valor inicial en la primera llamada, cada nivel n en el que la función recurre x es x_n "" " fx = f ( x ) gx = g ( f , x , fx ) ( x ) si gx ! = 0 : rendimiento x - fx / gx # Primero da x_n + 1 rendimiento de steff ( f , x - fx / gx ) # Luego da un nuevo iterador
Generalización
El método de Steffensen también se puede utilizar para encontrar una entrada para un tipo diferente de función que produce la misma salida que su entrada: por el valor especial . Soluciones comose llaman puntos fijos . Muchas de estas funciones se pueden utilizar para encontrar sus propias soluciones reciclando repetidamente el resultado como entrada, pero la tasa de convergencia puede ser lenta o la función puede no converger en absoluto, dependiendo de la función individual. El método de Steffensen acelera esta convergencia, para hacerla cuadrática .
Este método para encontrar puntos fijos de una función de valor real se ha generalizado para funciones en un espacio de Banach . El método generalizado asume que una familia de operadores lineales acotados asociado con y se puede encontrar para satisfacer la condición [2]
En la forma simple dada en la sección anterior, la función simplemente toma y produce números reales. Ahí, la funciónes una diferencia dividida . En la forma generalizada aquí, el operadores el análogo de una diferencia dividida para su uso en el espacio de Banach . El operadores equivalente a una matriz cuyas entradas son todas funciones de argumentos vectoriales y .
El método de Steffensen es entonces muy similar al método de Newton, excepto que usa la diferencia dividida en lugar de la derivada . Por lo tanto, se define por
por , y donde es el operador de identidad.
Si el operador satisface
por alguna constante , entonces el método converge cuadráticamente a un punto fijo de si la aproximación inicial está 'suficientemente cerca' de la solución deseada , eso satisface .
Notas
- ^ Porque requiere el cálculo previo de , las dos evaluaciones deben realizarse de forma secuencial; el algoritmo en sí no puede acelerarse ejecutando las evaluaciones de funciones en paralelo. Ésta es otra desventaja más del método de Steffensen.
Referencias
- ^ a b c Dahlquist, Germund ; Björck, Åke (1974). Métodos numéricos . Traducido por Anderson, Ned. Englewood Cliffs, Nueva Jersey: Prentice Hall. págs. 230–231 .
- ^ Johnson, LW; Scholz, DR (junio de 1968). "Sobre el método de Steffensen". Revista SIAM de Análisis Numérico . 5 (2): 296-302. doi : 10.1137 / 0705026 . JSTOR 2949443 .