Math 2.0

Numerical analysis Nonlinear equations Theorem

Steffensen's method

Builds on Newton's methodAitken's delta-squared processRate of convergence

Statement

Let ff be a real function that is twice continuously differentiable on an open interval II. Let r∈Ir \in I be a simple zero of ff, that is, f(r)=0f(r) = 0 and f′(r)≠0f'(r) \ne 0. For xx with f(x)≠0f(x) \ne 0, put g(x)=f(x+f(x))−f(x)f(x).g(x) = \frac{f(x + f(x)) - f(x)}{f(x)}. Steffensen's method is the iteration xn+1=xn−f(xn)g(xn),x_{n+1} = x_n - \frac{f(x_n)}{g(x_n)}, stopped when f(xn)=0f(x_n) = 0. Then there is δ>0\delta > 0 such that for every x0x_0 with ∣x0−r∣<δ\abs{x_0 - r} < \delta the iterates are defined and converge to rr quadratically.

Remarks

The quantity g(x)g(x) is a difference quotient of ff with step h=f(x)h = f(x). Near rr the step f(x)f(x) is small, and g(x)=f′(x)+O(f(x))g(x) = f'(x) + O(f(x)). So the method behaves like Newton's method, with an error in the slope of the same size as the current error, which keeps the order 22. Each step costs two evaluations of ff and no derivative. The step is exactly Aitken's delta-squared process applied to the points xx, φ(x)\varphi(x), φ(φ(x))\varphi(\varphi(x)) of the fixed-point map φ(x)=x+f(x)\varphi(x) = x + f(x). The method needs x0x_0 close to rr: when f(x0)f(x_0) is large, the point x0+f(x0)x_0 + f(x_0) can be far away and the slope estimate is useless.

Going deeper

For a student

It is the derivative-free counterpart of Newton's method, with the same quadratic order. It also shows how convergence acceleration turns a linearly convergent fixed-point iteration into a quadratically convergent one. Its basin of convergence is often smaller than that of Newton's method.

Reading path

To understand this page from the ground up, read these 8 pages in order. The foundations come first.

Show the path as a graph
Aitken's delta-squared process, concept, no evidence levelAitken's delta-square…conceptLimit point of a set, definition, no evidence levelLimit point of a setdefinitionRate of convergence, concept, no evidence levelRate of convergenceconceptLimit of a function, definition, no evidence levelLimit of a functiondefinitionDerivative, definition, no evidence levelDerivativedefinitionTangent line, concept, no evidence levelTangent lineconceptNewton's method, concept, no evidence levelNewton's methodconceptSteffensen's method, statement, no evidence levelSteffensen's methodstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Aitken's delta-squared process concept
  2. Limit point of a set definition
  3. Rate of convergence concept
  4. Limit of a function definition
  5. Derivative definition
  6. Tangent line concept
  7. Newton's method concept
  8. Steffensen's method statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Steffensen%27s_method
About this page
TagGEFBDG5CJ3
URIm2://GEFBDG5CJ3
Kindstatement, theorem
WritingW0 stub
MSC65H05, 65B99
StatusThis copy of the site has no build data. Run m2 status GEFBDG5CJ3.
AboutNewton's method
UsesNewton's method, Aitken's delta-squared process, Rate of convergence
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.