MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches

◆ bracketed_newton()

template<typename Function>
requires std::invocable<Function&, double> && std::convertible_to<std::invoke_result_t<Function&, double>, RootSample>
RootResult MayaFlux::Kinesis::bracketed_newton ( Function function,
double lower,
double upper,
double guess,
const RootOptions & options = {} )
nodiscard

Root of an increasing function by Newton steps kept inside a bracket.

Parameters
functionCallable returning a RootSample, value then slope, for a point
lowerLower end of the bracket
upperUpper end of the bracket
guessStarting point, clamped into the bracket
optionsStopping 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)) {
69 return { guess, RootStatus::NO_BRACKET };
70 }
71
72 double lo = lower;
73 double hi = upper;
74
75 if (options.check_bracket) {
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)) {
79 return { guess, RootStatus::NOT_FINITE };
80 }
81 if (at_lower > 0.0 || at_upper < 0.0) {
82 return { guess, RootStatus::NO_BRACKET };
83 }
84 if (at_lower == 0.0 || at_upper == 0.0) {
85 return { at_lower == 0.0 ? lo : hi, RootStatus::CONVERGED };
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)) {
94 return { x, RootStatus::NOT_FINITE };
95 }
96 if (value == 0.0) {
97 return { x, RootStatus::CONVERGED };
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)) {
105 return { x - step, RootStatus::CONVERGED };
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) {
115 return { next, RootStatus::CONVERGED };
116 }
117 x = next;
118 }
119
120 return { x, RootStatus::MAX_ITERATIONS };
121}
std::pair< double, double > RootSample
Value and slope of a function at one point.

Referenced by MayaFlux::Kinesis::Acoustics::reed_mouth_step().

Here is the caller graph for this function: