Exploring Functions |
It is useful in many scenarios to determine when a given function crosses a threshold value. When the threshold of interest is 0.0, this is known as finding the roots of the function, and any threshold crossing problem can be recast as a root finding problem by subtracting the threshold value from both sides of the equation. If a mathematical formula for the function is available, it is often possible to solve for the roots directly. If not, however, the roots must be found numerically; in other words, we sample the function at discrete values of the independent variable and examine trends in the sampled values in order to narrow in on the locations of the roots to a desired level of precision.
The DoubleFunctionExplorer, DurationFunctionExplorer, and JulianDateFunctionExplorer classes are used to numerically explore functions of double, Duration, and JulianDate, respectively. In addition to finding threshold crossings, these function explorers report local minima and maxima, which are locations where the function has a zero derivative or, informally, where it changes direction. JulianDateFunctionExplorer is used internally by DME Component Libraries to compute Access.
Some of the major capabilities of the function explorers include:
Explore multiple functions simultaneously.
Identify local extrema of the functions.
Identify crossings of thresholds. Multiple threshold values can be specified per function.
Mathematical formulas for the functions are not required.
The derivatives of the functions need not be available.
Full control over how the functions are sampled.
By exploring extrema, threshold crossings are found even when no sample falls on the other side of the threshold.
Predictable behavior even for functions with flat spots and discontinuities, as long as the function can be evaluated over the exploration interval.
The following shows a basic example of using DoubleFunctionExplorer to find the values at which a function crosses a specific threshold:
DoubleFunctionExplorer explorer = new DoubleFunctionExplorer(); explorer.setFindAllCrossingsPrecisely(true); explorer.getFunctions().add(DoubleSimpleFunction.of(x -> 2 * x + 5), 10.0); explorer.setSampleSuggestionCallback(DoubleSampleSuggestionCallback.of((start, stop, lastSample) -> lastSample + 1.0)); ArrayList<Double> thresholdCrossings = new ArrayList<>(); explorer.addThresholdCrossingFound(EventHandler.of((sender, e) -> { thresholdCrossings.add(e.getFinding().getCrossingVariable()); })); explorer.explore(0.0, 10.0); // thresholdCrossings list contains the X values at which the function crosses the threshold.
First, we create a function explorer and indicate that it should find all threshold crossings precisely, by setting the FindAllCrossingsPrecisely (get / set) property. This is discussed in more detail in the next section. Next, we add the function that we are interested in exploring, f(x) = 2 * x + 5, and also indicate the threshold that we are interested in, 10.0. Here, the function is expressed using a lambda expression, but any function that takes a double and returns a double can be used instead. The function is provided as a delegate.
The function explorer explores a function by taking discrete samples of the function's value. Thus, we provide a SampleSuggestionCallback (get / set) that determines the variable values at which to sample the function. The callback is given the beginning and end of the interval being explored and the previous variable value, and is expected to return the next variable value at which to sample. Again, we specify the callback function using a lambda expression, but any compatible function can be used instead. We will talk about sampling in more depth in later sections.
Next, we subscribe to the event that is raised by the function explorer each time that a threshold crossing is found. The event handler, which we express as an anonymous delegate, simply adds the variable value of the threshold crossing to a list.
Finally, we call the explore method to explore the function over the given interval. Each time that the function explorer finds something interesting, it raises the appropriate event and the attached event handlers, if any, are invoked. In this example, the thresholdCrossings collection contains a single variable value, 2.5, after the explore method returns.
All three function explorers raise events in response to the following findings:
Event | Description |
---|---|
Raised each time a function is sampled. | |
Two successive samples lie on opposite sides of a threshold, indicating that a function crosses the threshold over the interval between the two points. When this event is raised, the precise location of the crossing has not yet been identified. | |
The precise location of a threshold crossing has been found. Threshold crossings are only found precisely if the findPreciseCrossing method is called during the ThresholdCrossingIndicated (add / remove) event, or if FindAllCrossingsPrecisely (get / set) is true. | |
Three successive samples form two segments with opposite slope, indicating that a function has a local extremum (minimum or maximum) between the first and last of the three points. When this event is raised, the precise location of the local extremum has not yet been identified. | |
The precise location of an extremum (minimum or maximum) has been found. Extrema are only found precisely if the findPreciseExtremum method is called during the LocalExtremumIndicated (add / remove) event, or if FindAllExtremaPrecisely (get / set) is true. An extremum is also found precisely if ExploreExtremaToFindCrossings (get / set) is true and the extremum, if found, could lie on the opposite side of the threshold, leading to the discovery of additional threshold crossings. |
The links in the table above go to the DoubleFunctionExplorer, but JulianDateFunctionExplorer and DurationFunctionExplorer have equivalent events.
When using the function explorers, you must supply a callback that controls how the functions are sampled. Good sampling is essential to obtaining accurate results. If the function is not sampled often enough, threshold crossings and local extrema might be missed. If it's sampled too often, performance suffers. Ideal sampling is very much dependent on the nature of the function being sampled.
Rather than used a fixed sample step, as shown in the example above, we recommend that you use DoubleFunctionSampling, JulianDateFunctionSampling, or DurationFunctionSampling. A function explorer is configured to use these sampling classes as shown below.
Function2<Double, Double> function = getAnyOldFunction(); DoubleFunctionSampling sampling = new DoubleFunctionSampling(); sampling.setMinimumStep(1.0); sampling.setMaximumStep(100.0); sampling.setDefaultStep(10.0); sampling.setTrendingStep(1.0); DoubleFunctionExplorer explorer = new DoubleFunctionExplorer(); explorer.setSampleSuggestionCallback(DoubleSampleSuggestionCallback.of(sampling.getFunctionSampler(function)::getNextSample)); explorer.getFunctions().add(DoubleSimpleFunction.of(function::evaluate), 1.234);
The sampling types determine the next sample from the getNextSampleSuggestion method on the Function<TIndependent, TDependent> instance passed to getFunctionSampler. Thus, the function itself is in control of how it is sampled. In addition, the sampling types have a MinimumStep (get / set) and MaximumStep (get / set) properties that impose limits on the steps that can be suggested by the function. If the function does not make a valid suggestion, or if no function is supplied to getFunctionSampler, the DefaultStep (get / set) is used.
The sampling types also allow you to specify the size of the TrendingStep (get / set). A trending step occurs at the beginning and end of the exploration interval, and its purpose is to establish the direction in which the function is trending at the endpoints.
Consider exploring the function shown in the figure above. Exploration begins at the leftmost yellow point, and the two yellow points to the right are the next two samples. The slopes of the two lines connecting the three points are shown in red. Because both line segments show a decreasing slope, the function explorer does not know that the function has a local maximum over the interval between these three samples. Worse, the local maximum crosses the threshold, so we'll miss two threshold crossings if we don't recognize that this local maximum exists.
This is a problem only because the leftmost yellow point is the first explored sample. If we had started exploration earlier (such as with the green point in the figure), the slopes formed by the first three points would be opposite, which the function explorer would recognize indicates a local maximum. Finding the local maximum would lead to finding the two crossings as well. But what can we do to find the crossings in the case where we do start with the first yellow point?
As you may have guessed, the answer is to use a trending step. A small step at the beginning of the interval, shown as a blue point, establishes that the function is trending positive at the start of the interval. Then, the second yellow point gives us two segments with opposite slope, indicating a local maximum, and we find the crossings.
The smaller the trending step, the briefer the time the function can spend on the "other" side of the threshold without the two crossings being missed. On the other hand, if the trending step is too small, the values of the function at the start of the exploration interval and at the trending step will be indistinguishable. While the function explorer will consider this configuration, where the first two samples are equal and the third is different, to indicate a local extremum, in the case where the function really is just continuously increasing or decreasing over the interval, we'll waste time searching for an extremum that ends up being at one endpoint or the other.
While sampling a function, a local extremum (minimum or maximum) is indicated when three sampled function values form two line segments with opposite slope. In addition, an extremum is indicated if the first two values or the last two values are equal, but not if all three values are equal. When an extremum is indicated, the LocalExtremumIndicated (add / remove) event is raised, and it is guaranteed that the local extremum exists somewhere between the first and last of the three samples. If the sampling is inadequate, however, it is possible that there is more than one extremum between the first and last samples.
If FindAllExtremaPrecisely (get / set) is true, the exact location of the indicated extremum is found immediately. The precise location of the extremum is also found if ExploreExtremaToFindCrossings (get / set) is true and the extremum is either a maximum and all three samples are below a threshold, or a minimum and all three samples are above it. Finally, the extremum is found precisely if the user explicitly calls the findPreciseExtremum method during the LocalExtremumIndicated (add / remove) event. When the precise location of the extremum is found, the function explorers raise LocalExtremumFound (add / remove).
The precise location of an extremum is found using BrentFindExtremum. The ExtremumConvergenceCriteria (get / set) property controls the criteria used to determine when the extremum has been found to a sufficient level of precision. When set to ConvergenceCriteria.VARIABLE, the extremum search converges when the extremum is bracketed by an interval smaller than ExtremumVariableTolerance (get / set). When set to ConvergenceCriteria.FUNCTION, the extremum search converges when the last sampled function value is within ExtremumValueTolerance (get / set) of the value estimated by fitting a curve to the three points indicating the extremum. Convergence can also be allowed on ConvergenceCriteria.EITHER criteria or can require that ConvergenceCriteria.BOTH criteria are met.
If inadequate sampling leads to a situation where multiple local extrema exist between the three samples indicating an extremum, the function explorers will find only one of the extrema, and they cannot guarantee which one will be found.
When ReportExtremaAtEndpoints (get / set) is set to true, local extrema are also reported at the start and end of the exploration interval. For example, if the function is decreasing at the start of the interval, the first sample is a local maximum. Similarly, if the function is decreasing at the end of the interval, the last sample is a local minimum. If the function is flat at an endpoint, no extrema is reported.
While sampling a function, a threshold crossing is indicated when two sampled function values lie on opposite sides of a threshold value. When a sampled function value lies exactly on the threshold, it is considered either above or below the threshold for the purpose of determining threshold crossings based on the value of the BehaviorWhenOnThreshold (get / set) property.
When an extremum is indicated, the ThresholdCrossingIndicated (add / remove) event is raised, and it is guaranteed that the crossing exists somewhere between the two points. If the sampling is inadequate, however, it is possible that there is more than one crossing between the two samples.
If FindAllCrossingsPrecisely (get / set) is true, the exact location of the indicated crossing is found immediately. The precise location of the crossing is also found if the user explicitly calls the findPreciseCrossing method during the ThresholdCrossingIndicated (add / remove) event. When the precise location of the crossing is found, the function explorers raise ThresholdCrossingFound (add / remove).
The precise location of a crossing is found using BrentFindRoot. The ConvergenceCriteria (get / set) property controls the criteria used to determine when the crossing has been found to a sufficient level of precision. When set to ConvergenceCriteria.VARIABLE, the crossing search converges when the crossing is bracketed by an interval smaller than CrossingVariableTolerance (get / set). When set to ConvergenceCriteria.FUNCTION, the crossing search converges when the last sampled function value is within ValueTolerance (get / set) of the threshold. Convergence can also be allowed on ConvergenceCriteria.EITHER criteria or can require that ConvergenceCriteria.BOTH criteria be met. When the identified crossing does not exactly equal the threshold value, the SolutionType (get / set) property controls whether the reported crossing is slightly above or slightly below the threshold.
When the function is flat at the threshold, it would be reasonable to report any number of samples in the flat region as the threshold crossing. Instead, the function explorers guarantee where the crossing is reported based on the value of the SolutionType (get / set) property. When set to ThresholdCrossingSolutionType.ON_OR_ABOVE_THRESHOLD, and the function is crossing the threshold while increasing, the reported crossing is the earliest sampled variable value that is on the threshold. If the function is crossing the threshold while decreasing, the reported crossing is the latest sampled variable value that is on the threshold. This is consistent with the idea that ThresholdCrossingSolutionType.ON_OR_ABOVE_THRESHOLD implies that a value on the threshold should be treated as if it's above the threshold; the function explorers report the first time that it goes above the threshold and the last time that it remains above the threshold. Similarly, when set to ThresholdCrossingSolutionType.ON_OR_BELOW_THRESHOLD, and the function is crossing the threshold while increasing, the reported crossing is the latest sampled variable value that is on the threshold. If the function is crossing the threshold while decreasing, the reported crossing is the earliest sampled variable value that is on the threshold. Finally, when set to ThresholdCrossingSolutionType.ON_ABOVE_OR_BELOW_THRESHOLD, the function explorers report the earliest crossing, regardless of direction.
If inadequate sampling leads to a situation where multiple crossings occur between the two samples indicating a crossing, the function explorers will find only one of the crossings, and they cannot guarantee which one will be found.