Math 2.0

Numerical analysis Nonlinear equations Theorem

Brent's method

Builds on Intermediate value theoremBisection methodSecant methodInverse quadratic interpolation

Statement

Let f ⁣:[a,b]→ℝf \colon [a, b] \to \R be continuous with f(a)f(b)<0f(a) f(b) < 0, and let ε>0\varepsilon > 0 be a tolerance. Brent's method keeps at each step a bracket, an interval whose endpoints have values of opposite signs. At each step it proposes a new point by inverse quadratic interpolation or by the secant method. It falls back to a bisection step when the proposed point fails tests on its position or on the decrease of the bracket. Then:

  1. Every bracket contains a zero of ff.
  2. The method stops after finitely many evaluations of ff with a bracket of length at most ε\varepsilon, up to the rounding allowance in its tests.
  3. If bisection needs NN steps to reach the tolerance, Brent's method needs at most about N2N^2 evaluations of ff.

Remarks

Claim 1 follows from the intermediate value theorem, since the method only keeps brackets with a sign change. Claims 2 and 3 come from the safeguards: the tests force a bisection step whenever the interpolation steps have not shrunk the bracket enough over the last few steps. The bound in claim 3 is a worst case. For a smooth function with a simple zero, the method ends up taking interpolation steps only, and then it converges superlinearly. So it combines the reliability of bisection with the speed of the interpolation methods. It refines an earlier method of Dekker, which could take a very large number of tiny steps. It is the standard root finder for one equation in many numerical libraries, for example as fzero in MATLAB.

Going deeper

For a student

The main design point is the bracket: the method never gives up the sign change, so convergence is guaranteed for every continuous ff. For well-behaved ff the interpolation steps dominate and the speed is close to that of inverse quadratic interpolation. To use it, one needs a starting interval where ff changes sign.

Reading path

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

  1. Construction of the reals from Cauchy sequences concept
  2. Continuous function concept
  3. Continuously differentiable function concept
  4. Derivative concept
  5. Element definition
  6. Integers object
  7. Inverse function concept
  8. Lagrange interpolation concept
  9. Limit point of a set definition
  10. Ordered field definition
  11. Proposition concept
  12. Rate of convergence concept
  13. Rational numbers object
  14. Real numbers object
  15. Root-finding algorithm concept
  16. Second derivative concept
  17. Sequence definition
  18. Set bounded above definition
  19. Set definition
  20. Ring of integers statement
  21. Limit of a function definition
  22. Secant method statement
  23. Archimedean ordered field definition
  24. Conjunction definition
  25. Disjunction definition
  26. Implication definition
  27. Predicate definition
  28. Real sequence definition
  29. Subsequence definition
  30. Supremum definition
  31. Empty set object
  32. Family of sets definition
  33. Ordered pair definition
  34. Continuity at a point definition
  35. Intersection definition
  36. Union definition
  37. The rationals form a field statement
  38. Inverse quadratic interpolation statement
  39. Existential quantifier definition
  40. Universal quantifier definition
  41. Bounded sequence definition
  42. Cauchy sequence definition
  43. Limit of a sequence definition
  44. Monotone sequence definition
  45. Completeness axiom statement
  46. Cartesian product definition
  47. Continuous function definition
  48. Union of a family of sets definition
  49. Subset definition
  50. The rationals form an ordered field statement
  51. Uniqueness quantifier definition
  52. Every sequence has a monotone subsequence statement
  53. Monotone convergence theorem for sequences statement
  54. Convergent sequence definition
  55. Intermediate value theorem statement
  56. Binary relation definition
  57. Universal set definition
  58. Order on the reals definition
  59. Topological space definition
  60. Bolzano–Weierstrass theorem statement
  61. Complement definition
  62. Function definition
  63. Interval definition
  64. Subspace topology definition
  65. Completeness of the real numbers statement
  66. Metric space definition
  67. Open ball definition
  68. Metric topology definition
  69. Open set definition
  70. Open cover definition
  71. Closed set definition
  72. Compact space definition
  73. Compact set definition
  74. Cantor's intersection theorem statement
  75. Nested intervals theorem statement
  76. Bisection method statement
  77. Brent's method statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Brent%27s_method
About this page
Tag5F76XA1ABC
URIm2://5F76XA1ABC
Kindstatement, theorem
WritingW0 stub
MSC65H05
StatusThis copy of the site has no build data. Run m2 status 5F76XA1ABC.
AboutRoot-finding algorithm
UsesIntermediate value theorem, Bisection method, Secant method, Inverse quadratic interpolation
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • 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.