Opened 11 years ago
Closed 14 months ago
#4942 closed defect (fixed)
find_root() is broken when interval borders cannot be evaluated
Reported by:  mabshoff  Owned by:  mhansen 

Priority:  critical  Milestone:  sage8.4 
Component:  numerical  Keywords:  
Cc:  kcrisman  Merged in:  
Authors:  Eran Assaf  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  e6b7c1e (Commits)  Commit:  e6b7c1e24d19c6bca5c6bd31d8b75b963e046395 
Dependencies:  Stopgaps:  #12709 
Description
Reported in http://groups.google.com/group/sagesupport/browse_thread/thread/40da8039090c3e8a
Hi, I'm trying out SAGE for the first time, so I entered what you suggested (see above). Now, from the plot, it there seems to be no other roots between 0 and 2 so I entered sage: find_root(x^2*log(x,2)1,0, 2) and got the root = 0.0 what am I missing here? TIA, AJG
But note the following:
sage: find_root(1/(x1)+1,0, 2) 0.0 sage: find_root(1/(x1)+1,0.00001, 2) 1.0000000000011564
Cheers,
Michael
Change History (24)
comment:1 Changed 11 years ago by
 Milestone changed from sage3.4 to sage3.3
comment:2 Changed 11 years ago by
 Owner changed from jkantor to mhansen
 Status changed from new to assigned
comment:3 Changed 11 years ago by
 Milestone changed from sage3.4.1 to sage3.3
comment:4 Changed 11 years ago by
It seems this is a problem with Scipy:
In [16]: def f(x): ....: return 1.0/(x1.0)+1.0 ....: In [17]: import scipy.optimize In [18]: scipy.optimize.brentq(f, 0, 2) Out[18]: 0.0 In [19]: f(0.001) Out[19]: 0.0010010010010010895 In [20]: f(2) Out[20]: 2.0 In [21]: scipy.optimize.brentq(f, 0.001, 2) Out[21]: 1.0000000000007283 In [22]: f(1.0000000000007283) Out[22]: 1373048666882.2488
comment:5 Changed 11 years ago by
There are at least a couple of issues here. First, brentq is a variant of a bisectionbased solver; if you use any bisectionbased solver to find a zero of 1/(x1) between 0 and 2, it will narrow down and return something very close to 1. So if we don't like that, we should use a different solver (or at least try to check the output; for instance, a simple check that f(x) is "small" would detect this particular problem).
Second, find_root tries to verify that the function evaluates to different signs at the endpoints of the interval (as required by brentq); but it doesn't check the function evaluation results for NaN. In the original test case, fast_float(f)(0) gives NaN.
comment:6 Changed 11 years ago by
 Milestone changed from sage3.4 to sage3.4.1
Better luck in 3.4.1. Unfortunately this either requires testing of the result of scipy or some deeper surgery in Scipy.
Cheers,
Michael
comment:7 Changed 10 years ago by
 Priority changed from blocker to critical
If we've released for months and months without fixing this, it doesn't make sense to keep it as a blocker.
comment:8 Changed 8 years ago by
 Cc kcrisman added
 Report Upstream set to N/A
comment:9 Changed 8 years ago by
 Stopgaps set to #12709
comment:10 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:11 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:12 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:13 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:14 Changed 15 months ago by
 Branch set to u/assaferan/find_root___is_broken_when_interval_borders_cannot_be_evaluated
comment:15 Changed 15 months ago by
 Commit set to 91f14d3d3a9c48ff38e329425d4b73e133bf6052
 Status changed from new to needs_review
Hi, added two small validity checks:
 If one of the endpoints is evaluated to NaN we seek a nearby point in the interval which can be evaluated.
 If the value of the function at the root found is "large", raise an error that we could not find it.
New commits:
91f14d3  Added two validity checks  handles the case of NaN values and failure of the algorithm to find a root

comment:16 Changed 15 months ago by
 Status changed from needs_review to needs_work
comment:17 Changed 15 months ago by
I am not sure 1 is necessarily the best solution to this because what if you get a function that always evaluates to NaN as you increase/decrease the endpoints? For instance
sage: f(x) = 0.0 / max(0, x)
will be NaN for infinitely many values. So your current test means this runs forever:
sage: find_root(f, 1, 0)
(before it simply gave a wrong value).
Also, I think for 2 you should raise a NotImplementedError
as I think that more accurately reflects the situation.
comment:18 Changed 15 months ago by
 Commit changed from 91f14d3d3a9c48ff38e329425d4b73e133bf6052 to 8feb5a96dd1edc16fa59fbd824eafb5942956d2b
Branch pushed to git repo; I updated commit sha1. New commits:
8feb5a9  Fixed bug in find_root when full_output=True (size check assumed it was false)

comment:19 Changed 15 months ago by
 Commit changed from 8feb5a96dd1edc16fa59fbd824eafb5942956d2b to d67280b3a46cc7d95ee2aa1abc8c4d4d6257f963
Branch pushed to git repo; I updated commit sha1. New commits:
d67280b  Following the suggestion of tscrim, changed handling of NaN case to finding minimal and maximal values, and raising a NotImplementedError when brentq fails to find a root.

comment:20 Changed 15 months ago by
 Status changed from needs_work to needs_review
Fixed the bugs and changed behaviour in both cases, as suggested by tscrim
comment:21 Changed 15 months ago by
 Reviewers set to Travis Scrimshaw
Thanks. Looks better now. A few more little things:
ticket 4942
>:trac:`4942`
in the documentation. Could you add the test from comment:17.
 This change:
Traceback (most recent call last):  ... + ... NotImplementedError: Brent's method failed to find a zero for f on the interval
 Instead of using
...
for imprecision, it would be better to use# abs tol
(or a# rel tol
). if
statements do not need outer parentheses in Python, so remove them fromif (full_output):
and the outermost pair from the otherif
statement 4 lines down.
comment:22 Changed 14 months ago by
 Commit changed from d67280b3a46cc7d95ee2aa1abc8c4d4d6257f963 to e6b7c1e24d19c6bca5c6bd31d8b75b963e046395
Branch pushed to git repo; I updated commit sha1. New commits:
e6b7c1e  Some minor repairs  fixed inadequacies in documentation, added example of a function which evaluates to NaN on the entire interval (following review of tscrim)

comment:23 Changed 14 months ago by
 Milestone changed from sage6.4 to sage8.4
 Status changed from needs_review to positive_review
Thank you. LGTM.
comment:24 Changed 14 months ago by
 Branch changed from u/assaferan/find_root___is_broken_when_interval_borders_cannot_be_evaluated to e6b7c1e24d19c6bca5c6bd31d8b75b963e046395
 Resolution set to fixed
 Status changed from positive_review to closed
This is a critical bug and ought to be fixed in 3.3.
Note that #3870 might be a dupe of this bug.
Cheers,
Michael