Question about Interval Root finding

So I am using IntervalRootFinding.jl to find out how many possibly energy states exist for a finite potential well (Quantum mechanichs). The problem is that when I look for roots from -1e100 to 1e100, I get 2 solutions, which is consistent with what a classmate has found. But when I expand the interval to -1e200 to 1e200, I get two more roots I am not sure what to do with.

The last one has the status :unknown, so I can write it off as non-existing. But the other new root from this new interval has the value ø, and status :unique. What does that mean?

The code and outputs are seen below.

image

1 Like

FWIW, from the documentation:

1 Like

\emptyset represents the empty interval, as you can verify as follows

julia> rts = roots(f, -1e200..1e200)
4-element Vector{Root{Interval{Float64}}}:
 Root([15.0645, 15.0646], :unique)
 Root([11.1033, 11.1034], :unknown)
 Root(∅, :unique)
 Root([3.84464, 3.84465], :unique)

julia> a = rts[3].interval
∅

julia> isempty(a)
true

Since empty intervals cannot contain a root, you can safely remove it. I am not sure why the algorithm returns it though. I think empty intervals should be pruned away internally.

Note however, that :unknown means that the interval may or may not contain a root and the algorithm could not decide it, so in general you should not throw it away without some further thinking. In this case you can easily verify that the interval does not indeed contain a root as follows

julia> rts = roots(f, -1e200..1e200)
4-element Vector{Root{Interval{Float64}}}:
 Root([15.0645, 15.0646], :unique)
 Root([11.1033, 11.1034], :unknown)
 Root(∅, :unique)
 Root([3.84464, 3.84465], :unique)

julia> a = rts[2].interval
[11.1033, 11.1034]

julia> f(a)
[-2.00889e+08, -5.91418e+07]

julia> 0 ∈ f(a)
false

Since interval arithmetic sometimes overestimates the range but it never underestimates it, the last line is a rigorous proof that that interval does not indeed contain a root of the function and so it can be safely removed.

7 Likes

Reguarding me saying that I can remove the :unknown root, I knew about the documentation and concluded I could remove it because it fits what I expected, but thanks a lot for the more rigorus way of ruling it out. And thanks you a lot @lferrant for the detailed answer.

1 Like

That is a check that the package itself should do! I regard both of those last two roots as bugs. Thanks for the nice reproducer.

Note that you can also use BigFloats by writing eg big(3..5) as your input interval.

For this particular function it does not make sense to look at negative intervals since you immediately take the square root. But the package did successfully realise that at least!

8 Likes

Reported and being investigated here: Extra roots bug for large intervals · Issue #162 · JuliaIntervals/IntervalRootFinding.jl · GitHub

3 Likes

Wow. I gotta say, I am pretty thrilled that my “newbie-question” could spark what seems like a serious and productive discussion for making this pretty cool package even better. I never thought about numerical root-finding in terms of intervals, but it actually makes a whole lot more sense than to simply state some value that actually has uncertanty (the tolerance) assosciated with it, and often neglecting the uncertanty. Also, I don’t know how this package aims to guarantee finding all roots, but it defenitly feels like a very rigorous and well implemented project from my perspective. So again, pretty thrilled to have been the spark to the great discussion going on over at the issue :slight_smile:

It also feels great to have a contributor who is active and hears the question, and reacts. This is of course not something that can be expected in open-source project, but it has the same positives as great custumer support - that it, it is very appriciated :smiley:. Thanks for your time and effort @dpsanders <3.

4 Likes

I think that in this particular case it is not about uncertainty propagation, but a very elegant and fascinating lifting of the whole problem to mapping sets to sets.

2 Likes