El método de Steffensen.

Algoritmo de búsqueda de raíces similar a Newton que no utiliza derivadas

En análisis numérico , el método de Steffensen es un método iterativo para encontrar raíces que lleva el nombre de Johan Frederik Steffensen y que es similar al método de Newton , pero con ciertas ventajas situacionales. En particular, el método de Steffensen logra una convergencia cuadrática similar , pero sin utilizar derivadas , como requiere el método de Newton .

Descripción sencilla

La forma más simple de la fórmula del método de Steffensen ocurre cuando se usa para encontrar un cero de una función real , es decir, para encontrar el valor real que satisface Cerca de la solución que se supone que la función satisface aproximadamente, esta condición es adecuada como corrección. función 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 inicial debe estar muy cerca de la solución real y la convergencia a la solución puede ser lenta. Los ajustes del tamaño del paso del método, que se mencionan más adelante, pueden mejorar la convergencia en algunos de estos casos. ${\displaystyle \ f\,;}$ ${\displaystyle x_{\star }}$ ${\displaystyle \ f(x_{\star })=0~.}$ ${\displaystyle \ x_{\star }\,,}$ ${\displaystyle \ f\ }$ ${\displaystyle \ -1<f'(x_{\star })<0\,;}$ ${\displaystyle \ f\ }$ ${\displaystyle ~x~}$ ${\displaystyle \ x_{0}\ }$ ${\displaystyle \ x_{\star }\,,}$

Dado un valor inicial adecuado, se puede generar una secuencia de valores utilizando la siguiente fórmula. Cuando funciona, cada valor de 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, mediante esta fórmula: ^[1] ${\displaystyle \ x_{0}\,,}$ ${\displaystyle \ x_{0},\ x_{1},\ x_{2},\dots ,\ x_{n},\ \dots \ }$ ${\displaystyle \ x_{\star }\ }$ ${\displaystyle \ x_{n}\ }$ ${\displaystyle \ x_{n+1}\ }$

${\displaystyle \ x_{n+1}=x_{n}-{\frac {\,f(x_{n})\,}{g(x_{n})}}\ }$

para donde la función de pendiente es una combinación de la función original dada por la siguiente fórmula: ${\displaystyle \ n=0,1,2,3,...\,;}$ ${\displaystyle \ g(x)\ }$ ${\displaystyle \ f\ }$

${\displaystyle \ g(x)={\frac {\,f{\bigl (}x+f(x){\bigr )}\,}{f(x)}}-1\ }$

o quizás más claramente,

${\displaystyle \ g(x)~=~{\frac {\ f(x+h)-f(x)\ }{h}}\ ~~\approx ~~{\frac {\ \operatorname {d} f(x)\ }{\operatorname {d} x}}~\equiv ~f'(x)\,,}$

donde es el tamaño de paso entre el último punto de iteración y un punto auxiliar ubicado en ${\displaystyle \ h=f(x)\ }$ ${\displaystyle \ x\,,}$ ${\displaystyle \ x+h~.}$

Técnicamente, la función se llama diferencia dividida de primer orden de entre esos dos puntos (ya sea de tipo hacia adelante o de tipo hacia atrás , según el signo de ). Prácticamente, es el valor promediado de la pendiente de la función entre el último punto de la secuencia y el punto auxiliar en un paso de tamaño (y dirección) ${\displaystyle \ g\ }$ ${\displaystyle \ f\ }$ ${\displaystyle \ h\ }$ ${\displaystyle \ f'\ }$ ${\displaystyle \ f\ }$ ${\displaystyle \ \left(x,y\right)={\bigl (}x_{n},\ f\left(x_{n}\right){\bigr )}\ }$ ${\displaystyle \ {\bigl (}x,y{\bigr )}={\bigl (}\ x_{n}+h,\ f\left(x_{n}+h\right)\ {\bigr )}\,,}$ ${\displaystyle \ h=f(x_{n})~.}$

Debido a que el valor de es una aproximación de su valor, opcionalmente se puede verificar para ver si cumple con la condición requerida para garantizar la convergencia del algoritmo de Steffensen. Aunque una ligera disconformidad puede no ser necesariamente grave, cualquier desviación importante de la condición advierte que el método de Steffensen es propenso a fallar, y se justifica el uso temporal de algún algoritmo alternativo (por ejemplo, el algoritmo de Illinois más robusto , o simple regula falsi ). ${\displaystyle \ g\ }$ ${\displaystyle \ f'\ ,}$ ${\displaystyle \ -1<g<0\ }$ ${\displaystyle \ f'\ ,}$

Es sólo 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 esa razón cumplir con el requisito de que para todas las demás partes del cálculo, solo se utilizará el método de Steffensen. requiere que la función sea continua y que tenga una solución cercana. ^[1] Existen varias modificaciones modestas del paso en la fórmula de la pendiente , como multiplicarla por ${\displaystyle \ h\ }$ ${\displaystyle \ f\ }$ ${\displaystyle \ -1<f'(x_{\star })<0~.}$ ${\displaystyle \ f\ }$ ${\displaystyle \ h\ }$ ${\displaystyle \ g\ }$ 1 /2o 3 /4, para dar cabida a funciones que no cumplen del todo con el requisito. ${\displaystyle \ f\ }$

Ventajas y desventajas

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 de una ecuación con la misma "rápida". En este caso, rápidamente significa que para ambos métodos, la cantidad de dígitos correctos en la respuesta se duplica con cada paso. Pero la fórmula del método de Newton requiere una evaluación tanto de la derivada de la función como de la función, mientras que el método de Steffensen sólo se requiere a sí mismo. Esto es importante cuando el derivado no está disponible de manera fácil o eficiente. ${\displaystyle ~f~}$ ${\displaystyle ~f'~}$ ${\displaystyle ~f~,}$ ${\displaystyle ~f~}$

El precio de la convergencia rápida es la evaluación de la doble función: deben calcularse ambas, lo que puede llevar mucho tiempo si se trata de una función complicada. A modo de comparación, el método de la secante sólo necesita una evaluación de función por paso. El método de la secante aumenta el número de dígitos correctos en "sólo" un factor de aproximadamente 1,6 por paso, pero se pueden realizar 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] en el uso práctico, el método de la secante en realidad converge más rápido que el método de Steffensen, cuando ambos algoritmos tienen éxito: El método de la secante alcanza un factor de aproximadamente (1,6 ) ² ≈ 2,6 veces más dígitos por cada dos pasos (dos evaluaciones de funciones), en comparación con el factor de Steffensen de 2 para cada paso (dos evaluaciones de funciones). ${\displaystyle ~f(x_{n})~}$ ${\displaystyle ~f(x_{n}+h)~}$ ${\displaystyle ~f~}$

Al igual que la mayoría de los otros algoritmos iterativos de búsqueda de raíces , la debilidad crucial del método de Steffensen es elegir un valor inicial "adecuado". 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 ser errática flip-flop entre dos extremos, o divergir hasta el infinito, o ambos. ${\displaystyle ~x_{0}~.}$ ${\displaystyle ~x_{0}~}$ ${\displaystyle ~x_{\star }~,}$ ${\displaystyle ~x_{0},\,x_{1},\,x_{2},\,x_{3},\,\dots ~}$

Derivación mediante 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 concuerdan y están "suficientemente cerca" del límite deseado de la secuencia, podemos asumir lo siguiente: ${\displaystyle x_{n}=p\,-\,p_{n}~.}$ ${\displaystyle ~p_{n},\,p_{n+1},\,p_{n+2}~}$ ${\displaystyle ~p_{n}~}$ ${\displaystyle ~p~,}$

${\displaystyle {\frac {\,p_{n+1}-p\,}{\,p_{n}-p\,}}~\approx ~{\frac {\,p_{n+2}-p\,}{\,p_{n+1}-p\,}}}$

entonces

${\displaystyle (p_{n+1}-p)^{2}~\approx ~(\,p_{n+2}-p\,)\,(\,p_{n}-p\,)~}$

entonces

${\displaystyle p_{n+1}^{2}-2\,p_{n+1}\,p+p^{2}~\approx ~p_{n+2}\;p_{n}-(\,p_{n}+p_{n+2}\,)\,p+p^{2}}$

y por lo tanto

${\displaystyle (\,p_{n+2}-2\,p_{n+1}+p_{n}\,)\,p~\approx ~p_{n+2}\,p_{n}-p_{n+1}^{2}~.}$

Resolviendo para el límite deseado de la secuencia se obtiene: ${\displaystyle ~p~}$

${\displaystyle p~\approx ~{\frac {\,p_{n+2}\,p_{n}-p_{n+1}^{2}\,}{\,p_{n+2}-2\,p_{n+1}+p_{n}\,}}~=~{\frac {\,p_{n}^{2}+p_{n}\,p_{n+2}+2\,p_{n}\,p_{n+1}-2\,p_{n}\,p_{n+1}-p_{n}^{2}-p_{n+1}^{2}\,}{\,p_{n+2}-2\,p_{n+1}+p_{n}\,}}}$

${\displaystyle =~{\frac {\,(\,p_{n}^{2}+p_{n}\,p_{n+2}-2\,p_{n}\,p_{n+1}\,)-(\,p_{n}^{2}-2\,p_{n}\,p_{n+1}+p_{n+1}^{2}\,)\,}{\,p_{n+2}-2\,p_{n+1}+p_{n}\,}}}$

${\displaystyle =~p_{n}-{\frac {\,(\,p_{n+1}-p_{n})^{2}\,}{\,p_{n+2}-2\,p_{n+1}+p_{n}\,}}~,}$

lo que da como resultado la secuencia más rápidamente convergente:

${\displaystyle p~\approx ~p_{n+3}~=~p_{n}-{\frac {\,(\,p_{n+1}-p_{n}\,)^{2}\,}{\,p_{n+2}-2\,p_{n+1}+p_{n}\,}}~.}$

Ejemplo de código

En matlab

Aquí está la fuente para una implementación del método 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 una estimación inicial del punto fijo, p0, y una tolerancia, tol. % Se supone que la función de iteración de punto fijo se ingresa como una 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 tolerancia % deseada, tol. formato compacto % Esto acorta la salida. format long % Esto imprime más 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 logra converger, no nos quedemos % atrapados en un bucle infinito. p1 = f ( p0 ); % calcula las siguientes dos conjeturas para el punto fijo. p2 = f ( p1 ); p = p0 - ( p1 - p0 ) ^ 2 / ( p2 - 2 * p1 + p0 ) % utiliza el método delta cuadrado de Aitken para % encontrar una mejor aproximación a p0. if abs ( p - p0 ) < tol % prueba para ver si estamos dentro de la tolerancia. romper % si lo somos, detener las iteraciones, tenemos nuestra respuesta. final p0 = p ; % actualiza p0 para la siguiente iteración. end if abs ( p - p0 ) > tol % Si no cumplimos con la tolerancia, enviamos un mensaje % de falla. 'no pudo converger en 1000 iteraciones.' fin                                        

En pitón

Aquí está la fuente de una implementación del método de Steffensen en Python .

al  escribir  import  Callable ,  Iterator Func  =  Callable [[ float ],  float ]def  g ( f :  Func ,  x :  float ,  fx :  float )  ->  Func : """Función de diferencia dividida de primer orden.  Argumentos:  f: Entrada de función a g  x: Punto en el que evaluar g  fx: Función f evaluada en x  """  return  lambda  x :  f ( x  +  fx )  /  fx  -  1def  steff ( f :  Func ,  x :  float )  ->  Iterador [ float ]: """Algoritmo de Steffenson para encontrar raíces.  Este generador recursivo produce primero el valor x_{n+1} y luego, cuando el generador itera,  produce x_{n+2} del siguiente nivel de recursividad. Argumentos:  f: Función cuya raíz estamos buscando  x: Valor inicial en la primera llamada, cada nivel n en el que la función recurre x es x_n  """  mientras que  Verdadero :  fx  =  f ( x )  gx  =  g ( f ,  x ,  fx )( x )  if  gx  ==  0 :  break  else :  x  =  x  -  fx  /  gx  # Actualizar a x_{n+1}  yield  x  # Valor de rendimiento

Generalización al espacio de Banach

El método de Steffensen también se puede utilizar para encontrar una entrada para un tipo diferente de función que produzca la misma salida que su entrada: para el valor especial, las soluciones como se llaman puntos fijos . Muchas de estas funciones se pueden usar 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 . ${\displaystyle \ x=x_{\star }\ }$ ${\displaystyle \ F\ }$ ${\displaystyle \ x_{\star }=F(x_{\star })\ }$ ${\displaystyle \ x_{\star }~.}$ ${\displaystyle \ x_{\star }\ }$

A modo de orientación, la función raíz y las funciones de punto fijo están simplemente relacionadas por dónde hay una constante escalar lo suficientemente pequeña en magnitud como para ser estable en iteración, pero lo suficientemente grande como para que la no linealidad de la función sea apreciable. Todas las cuestiones relativas a un espacio de Banach más general frente a números reales básicos se ignoran momentáneamente en aras de la comparación. ${\displaystyle \ f\ }$ ${\displaystyle \ F(x)=x+\varepsilon \ f(x)\ ,}$ ${\displaystyle \ \varepsilon \ }$ ${\displaystyle \ F\ }$ ${\displaystyle \ f\ }$

Este método para encontrar puntos fijos de una función de valor real se ha generalizado para funciones que mapean un espacio de Banach sobre sí mismo o incluso más generalmente que mapean de un espacio de Banach a otro espacio de Banach. El método generalizado supone que una familia de operadores lineales acotados asociados con y se puede idear que (localmente) satisfaga esta condición: ^[2] ${\displaystyle \ F:X\to X\ }$ ${\displaystyle \ X\ }$ ${\displaystyle \ F:X\to Y\ }$ ${\displaystyle \ X\ }$ ${\displaystyle \ Y~.}$ ${\displaystyle \ \{\;G(u,v):u,v\in X\;\}\ }$ ${\displaystyle \ u\ }$ ${\displaystyle \ v\ }$

${\displaystyle \ F\left(u\right)-F\left(v\right)=G\left(u,v\right)\,{\bigl [}\,u-v\,{\bigr ]}\ \qquad \qquad \qquad \qquad }$ ecuación  ( 𝄋 ) .

Si la división es posible en el espacio de Banach , el operador lineal se puede obtener de ${\displaystyle \ G\ }$

${\displaystyle \ G\left(u,v\right)={\bigl [}\ F\left(u\right)-F\left(v\right)\ {\bigr ]}{\bigl [}\ u-v\ {\bigr ]}^{-1}\ ,}$

lo que puede proporcionar alguna idea: expresado de esta manera, el operador lineal puede verse más fácilmente como una versión elaborada de la diferencia dividida analizada en la primera sección anterior. La forma cociente se muestra aquí sólo como orientación; no es obligatorio per se . Tenga en cuenta también que la división dentro del espacio de Banach no es necesaria para que el método elaborado de Steffensen sea viable; el único requisito es que el operador satisfaga la ecuación marcada con el segno , ( 𝄋 ) . ${\displaystyle \ G\ }$ ${\displaystyle \ g\ }$ ${\displaystyle \ G\ }$

Para la función básica de números reales dada en la primera sección, la función simplemente toma y genera números reales. Allí, la función es una diferencia dividida . En la forma generalizada aquí, el operador es el análogo de una diferencia dividida para su uso en el espacio de Banach . El operador es aproximadamente equivalente a una matriz cuyas entradas son todas funciones de argumentos vectoriales y ${\displaystyle \ f\ ,}$ ${\displaystyle \ g\ }$ ${\displaystyle \ G\ }$ ${\displaystyle \ G\ }$ ${\displaystyle \ u\ }$ ${\displaystyle \ v~.}$

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. Tenga en cuenta que para argumentos cercanos a algunas funciones de punto fijo y sus operadores lineales que cumplen la condición marcada ( 𝄋 ) , ¿dónde está la identidad? operador. ${\displaystyle \ G{\bigl (}\,F\left(x\right),\,x\,{\bigr )}\ }$ ${\displaystyle \ F'(x)~.}$ ${\displaystyle \ x\ }$ ${\displaystyle \ x_{\star }\ ,}$ ${\displaystyle \ F\ }$ ${\displaystyle \ G\ }$ ${\displaystyle \ F'(x)\approx G{\bigl (}\,F\left(x\right),\,x\,{\bigr )}\approx I\ }$ ${\displaystyle \ I\ }$

En el caso de que la división sea posible en el espacio de Banach, la fórmula de iteración generalizada viene dada por

${\displaystyle x_{n+1}=x_{n}+{\Bigl [}I-G{\bigl (}F\left(x_{n}\right),x_{n}{\bigr )}{\Bigr ]}^{-1}{\Bigl [}F\left(x_{n}\right)-x_{n}{\Bigr ]}\ ,}$

para En el caso más general en el que la división puede no ser posible, la fórmula de iteración requiere encontrar una solución cercana a la cual ${\displaystyle \ n=1,\,2,\,3,\,...~.}$ ${\displaystyle \ x_{n+1}\ }$ ${\displaystyle \ x_{n}\ }$

${\displaystyle {\Bigl [}I-G{\bigl (}F\left(x_{n}\right),x_{n}{\bigr )}{\Bigr ]}{\Bigl [}x_{n+1}-x_{n}{\Bigr ]}=F\left(x_{n}\right)-x_{n}~.}$

De manera equivalente, se puede buscar la solución a la forma algo reducida. ${\displaystyle \ x_{n+1}\ }$

${\displaystyle {\Bigl [}I-G{\bigl (}F\left(x_{n}\right),x_{n}{\bigr )}{\Bigr ]}x_{n+1}={\Bigl [}F\left(x_{n}\right)-G{\bigl (}F\left(x_{n}\right),x_{n}{\bigr )}\ x_{n}{\Bigr ]}\ ,}$

con todos los valores entre corchetes siendo independientes de Todos los términos entre corchetes solo dependen de Tenga en cuenta, sin embargo, que la segunda forma puede no ser tan numéricamente estable como la primera: porque la primera forma implica encontrar un valor para una (con suerte) pequeña diferencia, puede ser numéricamente más probable evitar cambios excesivamente grandes o erráticos en el valor iterado ${\displaystyle \ x_{n+1}\ :}$ ${\displaystyle \ x_{n}~.}$ ${\displaystyle \ x_{n}~.}$

Si el operador lineal satisface ${\displaystyle ~G~}$

${\displaystyle {\Bigl \|}G\left(u,v\right)-G\left(x,y\right){\Bigr \|}\leq k{\biggl (}{\Bigl \|}u-x{\Bigr \|}+{\Bigr \|}v-y{\Bigr \|}{\biggr )}~}$

para alguna constante real positiva , entonces el método converge cuadráticamente a un punto fijo de si la aproximación inicial es "suficientemente cercana" a la solución deseada que satisface ${\displaystyle \ k~,}$ ${\displaystyle \ F\ }$ ${\displaystyle \ x_{0}\ }$ ${\displaystyle \ x_{\star }\ ,}$ ${\displaystyle \ x_{\star }=F(x_{\star })~.}$

Notas

1. Porque requiere que el cálculo previo de las dos evaluaciones se realice de forma secuencial; el algoritmo per se no se puede acelerar ejecutando las evaluaciones de funciones en paralelo. Ésta es otra desventaja más del método de Steffensen. ${\displaystyle ~f(x_{n}+h)~}$ ${\displaystyle ~h=f(x_{n})~,}$

Referencias

1. Dahlquist, Germund ; Björck, Åke (1974). Métodos numéricos . Traducido por Anderson, Ned. Englewood Cliffs, Nueva Jersey: Prentice Hall. págs. 230-231.
2. 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.