search

JuliaIntervals / IntervalRootFinding.jl

Library for finding the roots of a function using interval arithmetic
https://juliaintervals.github.io/IntervalRootFinding.jl/
Other
127 stars 26 forks source link

Return semi-infinite intervals when cannot guarantee roots #96

Open dpsanders opened 5 years ago

dpsanders commented 5 years ago

e.g. for f(x) = (x-1)x(x+1) on (-Inf..Inf).

Kolaru commented 5 years ago

Why can't the roots be guaranteed here ?

dpsanders commented 5 years ago

My bad, they apparently can. There are some functions for which it is not possible to exclude "roots at infinity".

Kolaru commented 5 years ago 
julia> roots(x -> 1/x, 1..∞)
1-element Array{Root{Interval{Float64}},1}:
 Root(∅, :unique)

Like that one I guess ?

dpsanders commented 5 years ago

Ouch. Exactly!

dpsanders commented 5 years ago

Even with bisection this fails. I think this is because we keep bisecting intervals even when they are atomic. This needs to be fixed.

dpsanders commented 4 years ago

Currently we get

julia> roots(x -> 1/x, 1..∞)
Root([1.79769e+308, ∞], :unique)

The unique here is wrong -- maybe Newton is not checking strict inclusion?

Krawczyk just hangs.

An example of not being able to guarantee roots is

julia> roots(x -> x^2 - 2x, -Inf..Inf)

When x is a semi-infinite interval, x^2 - 2x always gives -Inf..Inf and nothing can be done, even though for any finite, large interval it can immediately prove that there is no 0.