MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches
RootFinding.hpp
Go to the documentation of this file.
1#pragma once
2
3/**
4 * @file RootFinding.hpp
5 * @brief Roots of scalar functions held inside a bracket.
6 */
7
8namespace MayaFlux::Kinesis {
9
10/**
11 * @enum RootStatus
12 * @brief How a root search ended.
13 */
20
21/** @brief Value and slope of a function at one point. */
22using RootSample = std::pair<double, double>;
23
24/** @brief The best point found and how the search ended. */
25using RootResult = std::pair<double, RootStatus>;
26
27/**
28 * @struct RootOptions
29 * @brief Stopping rule of a root search.
30 *
31 * The search stops when a step, or the bracket, is no wider than
32 * tolerance times the larger of the iterate and floor.
33 */
35 double tolerance { 1.0e-12 };
36 double floor { 1.0e-14 };
37 uint32_t max_iterations { 64 };
38 bool check_bracket { true };
39};
40
41/**
42 * @brief Root of an increasing function by Newton steps kept inside a bracket.
43 * @param function Callable returning a RootSample, value then slope, for a point
44 * @param lower Lower end of the bracket
45 * @param upper Upper end of the bracket
46 * @param guess Starting point, clamped into the bracket
47 * @param options Stopping rule
48 * @return The root and the status. On MAX_ITERATIONS the root is the last
49 * iterate, and on NO_BRACKET or NOT_FINITE it is the guess.
50 *
51 * Needs value(lower) <= 0 <= value(upper). A Newton step that leaves the
52 * bracket, or comes from a slope that is not positive and finite, is replaced
53 * by bisection, so the bracket always narrows and the search ends within
54 * max_iterations. Near a root it converges quadratically, and a guess from the
55 * previous call, when the function moves slowly between calls, usually
56 * finishes in two or three evaluations.
57 *
58 * With options.check_bracket set, the ends are evaluated first and a missing
59 * sign change returns NO_BRACKET. Turn it off when the bracket is known by
60 * construction. A decreasing function is handled by negating it.
61 */
62template <typename Function>
63 requires std::invocable<Function&, double>
64 && std::convertible_to<std::invoke_result_t<Function&, double>, RootSample>
66 Function function, double lower, double upper, double guess, const RootOptions& options = {})
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}
122
123} // namespace MayaFlux::Kinesis
RootStatus
How a root search ended.
RootResult bracketed_newton(Function function, double lower, double upper, double guess, const RootOptions &options={})
Root of an increasing function by Newton steps kept inside a bracket.
std::pair< double, double > RootSample
Value and slope of a function at one point.
std::pair< double, RootStatus > RootResult
The best point found and how the search ended.
Stopping rule of a root search.