Steffensen's method: Difference between revisions

Revision as of 00:47, 12 July 2008

Revision as of 01:17, 12 July 2008

Line 17:

==Generalised definition==

Steffensen's method can also be used more abstractly, to find the locations a different kind function <math>f\ </math>, that produce the same output as input: <math>x = f(x)\ </math>, called "[[fixed point]]s". Steffensen's method finds [[fixed point]]s of a [[Map (mathematics)|mapping]] &fnof;<math>f\ </math>. In theSteffensen's original definitiondescription, &fnof;<math>f\ </math> was supposed to be a real function, but the method has been generalised for functions <math>f : X \to X </math> on a [[Banach space]] <math>X</math>.

The method assumes that a [[Indexed family|family]] <math>\{F(x',x''):x', x'' \in X\}</math> of [[Bounded set|bounded]] [[linear operators]] <math>\{L(calledu,v): ''dividedu, difference'')v \in X\}</math> associated with ''x''<nowikimath>'u\ </nowikimath> and ''x''<nowikimath>''v\ </nowikimath> isare can be found to knownsatisfy whichthe satisfiescondition<ref>L. W. Johnson; D. R. Scholz (1968) On Steffensen's Method, ''SIAM Journal on Numerical Analysis'' (June 1968), vol.&nbsp;5, no.&nbsp;2., pp. 296-302. Stable URL: [http://links.jstor.org/sici?sici=0036-1429%28196806%295%3A2%3C296%3AOSM%3E2.0.CO%3B2-H]</ref>

:<math>f(x'u)- f(x''v)=FL(x'u,x''v)\ (x'u-x''v). \,</math>&nbsp;.

In the original form (given in the section above), where the function <math>f\ </math> simply takes in and produces real numbers, the operators are ''divided differences''. In the general form, the operators <math>L\ </math> are the analogue of divided differences.

:<math>f(x')- f(x'')=F(x',x'')(x'-x''). \,</math>

Steffensen's method is then very similar to the Newton's method, except that it uses the divided difference<math>FL(f(x),x)\ </math> instead of the derivative <math>Df(x)\ </math>. It is thus defined by

: <math>x_{k+1} = x_k + [I - FL(f(x_k), x_k)]^{-1}(f(x_k) - x_k), \, </math>

for ''k'' = 1, 2, 3, ...&nbsp;. If the operator ''F'' satisfies

: <math>\|FL(x'u,x''v)-FL(y'x,y'')\| \le K \big( \|u-x'-y'\| + \|x''v-y''\| \big) </math>

for some constant ''<math>K''\ </math>, then the method converges quadratically to a fixed point of &fnof; if the initial approximation <math>x_0</math> is sufficiently close to the desired solution <math>\xi</math>, that satisifies <math>\xi = f(\xi)</math>.

==References==