Steffensen's method: Difference between revisions

Revision as of 08:26, 12 August 2008

Revision as of 08:30, 12 August 2008

Line 25:

The method assumes that a [[Indexed family|family]] of [[Bounded set|bounded]] [[linear operators]] <math>\{L(u,v): u, v \in X\}</math> associated with <math>u\ </math> and <math>v\ </math> are can be found to satisfy the condition<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(u)- f(v)=L(u,v)\ (u-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 in the [[Banach space]].

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

: <math>x_{n+1} = x_n + [I - L(f(x_n), x_n)]^{-1}(f(x_n) - x_n), \, </math>&nbsp;,

for <math>n=1,\ 2,\ 3,\ ...</math>, and where <math>I\ </math> is the identity operator. If the operator <math>L\ </math> satisfies

: <math>\|L(u,v)-L(x,y)\| \le K \big( \|u-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>x_\star</math>, that satisifies <math>x_\star = f(x_\star)</math>&nbsp;.

==References==