Root of an increasing function by Newton steps kept inside a bracket.
- Parameters
-
| function | Callable returning a RootSample, value then slope, for a point |
| lower | Lower end of the bracket |
| upper | Upper end of the bracket |
| guess | Starting point, clamped into the bracket |
| options | Stopping rule |
- Returns
- The root and the status. On MAX_ITERATIONS the root is the last iterate, and on NO_BRACKET or NOT_FINITE it is the guess.
Needs value(lower) <= 0 <= value(upper). A Newton step that leaves the bracket, or comes from a slope that is not positive and finite, is replaced by bisection, so the bracket always narrows and the search ends within max_iterations. Near a root it converges quadratically, and a guess from the previous call, when the function moves slowly between calls, usually finishes in two or three evaluations.
With options.check_bracket set, the ends are evaluated first and a missing sign change returns NO_BRACKET. Turn it off when the bracket is known by construction. A decreasing function is handled by negating it.
Definition at line 65 of file RootFinding.hpp.
66 {})
67{
68 if (!(lower <= upper) || !std::isfinite(lower) || !std::isfinite(upper)) {
70 }
71
72 double lo = lower;
73 double hi = upper;
74
76 const double at_lower =
static_cast<RootSample>(function(lo)).first;
77 const double at_upper =
static_cast<RootSample>(function(hi)).first;
78 if (!std::isfinite(at_lower) || !std::isfinite(at_upper)) {
80 }
81 if (at_lower > 0.0 || at_upper < 0.0) {
83 }
84 if (at_lower == 0.0 || at_upper == 0.0) {
86 }
87 }
88
89 double x = std::clamp(guess, lo, hi);
90 for (uint32_t iteration = 0; iteration < options.
max_iterations; ++iteration) {
91 const auto [value, slope] =
static_cast<RootSample>(function(x));
92
93 if (!std::isfinite(value)) {
95 }
96 if (value == 0.0) {
98 }
99
100 (value < 0.0 ? lo : hi) = x;
101
102 const bool usable = slope > 0.0 && std::isfinite(slope);
103 const double step = usable ? value / slope : 0.0;
104 if (usable && std::abs(step) <= options.
tolerance * std::max(std::abs(x), options.
floor)) {
106 }
107
108 double next = usable ? x - step : lo;
109 if (!usable || next <= lo || next >= hi) {
110 next = 0.5 * (lo + hi);
111 }
112
113 const double reach = options.
tolerance * std::max(std::abs(next), options.
floor);
114 if (std::abs(next - x) <= reach || hi - lo <= reach) {
116 }
117 x = next;
118 }
119
121}
std::pair< double, double > RootSample
Value and slope of a function at one point.
Referenced by MayaFlux::Kinesis::Acoustics::reed_mouth_step().