1
$\begingroup$

Let $f \in C^0[0, 1]$, and suppose $f \ge 0$. How can I compute $\sup f^{-1}(0)$ efficiently?

$\endgroup$
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 Bot
    Apr 22 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$
    – Tyberius
    Apr 23 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 Shmo
    Apr 23 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$ Apr 23 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 Shmo
    Apr 23 at 20:00

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the reference, @federico-poloni $\endgroup$
    – Joe Shmo
    Apr 26 at 17:27
0
$\begingroup$

For reference, the Method of False Position converged accurately and fast for the function

$\exp \big(-1000 \cdot (f(x) - 0.001) \big) - 1$

$\endgroup$
3
  • $\begingroup$ I think that this should be added to the question since it does not answer it. $\endgroup$
    – nicoguaro
    Apr 26 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 Shmo
    Apr 27 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$ Apr 29 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.