Método de Steffensen

El método de Steffensen (per Johan Frederik Steffensen) és un algoritme per a obtindre els zeros d'una funció. El método de Steffensen es pot considerar com una combinació del método de punt fix i del método d'Aitken. Com el método de Aitken essencialment accelera la convergència d'un atre método, es pot definir este método com el método de punt fix accelerat.

Ventages

El método de Steffensen presenta una convergència ràpida i no requerix, com en el cas del método de Newton, l'evaluació de derivada alguna. Presenta ademés, la ventaja adicional de que el procés de iteración només necessita un punt inicial.

Una atra ventaja del método de Steffensen és que -de la mateixa manera que el de Newton- té convergència quadràtica. És dir, abdós métodos permeten trobar les raïls d'una funció f "ràpidament" - en este cas ràpidament significa que en cada iteración, el número de dígits correctes en la resposta es duplica. Pero la fòrmula per al método de Newton requerix l'evaluació de la derivada de la funció, el método de Steffensen no, per lo que este últim pot ser programat per a una funció genèrica, mentres que la funció complixca la restricció mencionada anteriorment.

El preu de la convergència ràpida és una doble evaluació de la funció: tant $f(x_n)$ com $f(x_n+h)$ deuen ser calculades, lo que podria dur un temps considerable depenent de la funció f. Per comparació, el método de la secante només necessita una evaluació de la funció per cada pas, aixina que en dos evaluacions de la funció del método de la secante es poden fer dos passos, i eixos dos passos aumenten el número de dígits correctes en un factor d'1,6. En un sol pas de temps el método de Steffensen (o de Newton) aumenta els dígits correctes en un factor de 2, lo que és només una miqueta millor.

De la mateixa manera que el método de Newton i atres métodos cuadráticamente convergents, la debilitat fonamental en el método de Steffensen és l'elecció del valor inicial $x_0$. Si el valor de $x_0$ no està "lo suficientment prop" de la solució, el método pot fallar i la seqüència de valors $x_0,x_1,x_2,x_3,\dots$ o be pot oscilar entre dos valors, o be divergir cap a infinit (abdós alternatives poden succeir).

Es calcula el següent punt de iteración a partir de l'expressió:

$x_{n+1}=x_n-\frac{[f(x_n){]}^2}{f(x_n+f(x_n))-f(x_n)}$

Algoritme

Per a una successió {x_n}, obtinguda pel método del punt fix x_n+1 = f(x_n), partim de tres punts:^{cita requerida}

i₀= f(x₀)

z₀= f(i₀)

a on x₀ és el punt inicial. Obtenint aixina:

x₁ = x₀ – (i₀ –x₀)^1/2

z₀ – 2i₀ – x₀

En forma general:

X_n+1 = x_n – (i_n – x_n)^1/2

z_n – 2* i_n – x_n

A on si |x_n+1 – x_n| = error < Tol llavors se satisfà la tolerància.

Còdic Matlab

function [x,n_iter]=steffensen(x0,f,tol,nmax) 
x1=feval(f,x0);
x2=feval(f,x1);
x_nou=x0-(x1-x0)^2/(x2-2x1+x0)
error= abs(x2-x_nou);
i=1;
	while(i<=nmax & error>=tol)
		x0=x_nou;
		x1=feval(f,x0);
        x2=feval(f,x1);
		x_nou=x0-(x1-x0)^2/(x2-2x1+x0);
		error= abs(x0-x_nou);
		i=i+1;
	end
	n_iter=i-1;
	x=x0;
end

^{cita requerida}