Let $f \in C^0[0, 1]$, and suppose $f \ge 0$. How can I compute $\sup f^{-1}(0)$ efficiently?
10
-
$\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$– Community BotCommented Apr 22, 2022 at 19:11
-
3$\begingroup$ @JoeShmo note the "bot" comment is actually from an anonymous reviewer. Some details that might help a potential answerer: 1. What have you tried already (to avoid getting a suggestion that you already tried, but doesn't work/isn't efficient enough) 2. (May just be me) I'm confused by the meaning of $\sup f^{-1}(0)$. If the sup is the supremum, isn't that the least upper bound of a set? $f^{-1}(0)$ should just be a single value unless I'm misunderstanding. $\endgroup$– TyberiusCommented Apr 23, 2022 at 1:29
-
3$\begingroup$ @Tyberius Yes, $\sup$ is the supremum, or the least upper bound. $\sup f^{-1}(0)$ doesn't have to be a single value - consider $f: [0, 1] \rightarrow [0, 1]$ defined by $f(x) = 0$ for $x \in [0, \frac{1}{2}]$, and $f(x) = 2(x - \frac{1}{2})$ for $x \in (\frac{1}{2}, 1]$. Then $f \in C^0[0, 1],\ f^{-1}(0) = [0, \frac{1}{2}]$, and $\sup f^{-1}(0) = \frac{1}{2}$. I have tried the secant method, and variations of it (the method of false position), as well as playing with several hyper parameters. $\endgroup$– Joe ShmoCommented Apr 23, 2022 at 1:53
-
2$\begingroup$ So you want to find the largest root of $f$. Note that most root-finding algorithms will only reliably find roots with sign changes (with multiplicity one if $f$ were smooth enough to define this). /// All root-finding solvers are in the end local algorithms, as they only use local information to define their steps. They can not give information of how a root is related to other roots. For such global information you would need bounds on the variation of the function and a sufficiently dense sampling. Continuous functions without further qualification can be rather wild. $\endgroup$– Lutz LehmannCommented Apr 23, 2022 at 10:14
-
1$\begingroup$ @LutzLehmann OK, can you refer me to (optimization, most likely) methods that assume continuity? I have access to $f$, but not $\nabla f$, say. I should still probably be able to approximate $\nabla f$ via some numerical method. $\endgroup$– Joe ShmoCommented Apr 23, 2022 at 20:00
|
Show 5 more comments
2 Answers
$\begingroup$
$\endgroup$
1
If you need a certified result, you can try interval methods such as the ones in https://github.com/JuliaIntervals/IntervalRootFinding.jl/ . They are at their best for (at least) piecewise differentiable functions; other types of functions will of course be hard to express as functions in a programming language.
The algorithm will give you a tight inclusion for the set of zeros of a function, in cases that are not problematic numerically, with the guarantee that it's not missing a zero.
answered Apr 26, 2022 at 6:46
-
$\begingroup$ Thanks for the reference, @federico-poloni $\endgroup$– Joe ShmoCommented Apr 26, 2022 at 17:27
$\begingroup$
$\endgroup$
3
For reference, the Method of False Position converged accurately and fast for the function
$\exp \big(-1000 \cdot (f(x) - 0.001) \big) - 1$
-
$\begingroup$ I think that this should be added to the question since it does not answer it. $\endgroup$– nicoguaro ♦Commented Apr 26, 2022 at 21:36
-
$\begingroup$ @nicoguaro this does answer the question. this isn't the only answer, and I welcome more, if anybody has any more answers. If $ℎ(𝑥)= \exp(−1000⋅(f(𝑥)−0.001))−1$, then $ℎ(𝑥)=0⟹𝑓(𝑥)≈0$, and this procedure converges fast (at least in the cases I ran). $\endgroup$– Joe ShmoCommented Apr 27, 2022 at 1:01
-
1$\begingroup$ How does this find the largest root and not some other root? For what function $f$ does this actually converge quickly? What were your bounds with false position? There's a lot missing here before it can be said that this properly answers the question. $\endgroup$ Commented Apr 29, 2022 at 15:56