Opened 14 years ago
Closed 4 years ago
#4942 closed defect (fixed)
find_root() is broken when interval borders cannot be evaluated
Reported by: | mabshoff | Owned by: | mhansen |
---|---|---|---|
Priority: | critical | Milestone: | sage-8.4 |
Component: | numerical | Keywords: | |
Cc: | kcrisman | Merged in: | |
Authors: | Eran Assaf | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | e6b7c1e (Commits, GitHub, GitLab) | Commit: | e6b7c1e24d19c6bca5c6bd31d8b75b963e046395 |
Dependencies: | Stopgaps: | #12709 |
Description
Reported in http://groups.google.com/group/sage-support/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/(x-1)+1,0, 2) 0.0 sage: find_root(1/(x-1)+1,0.00001, 2) 1.0000000000011564
Cheers,
Michael
Change History (24)
comment:1 Changed 14 years ago by
Milestone: | sage-3.4 → sage-3.3 |
---|
comment:2 Changed 14 years ago by
Owner: | changed from jkantor to mhansen |
---|---|
Status: | new → assigned |
comment:3 Changed 14 years ago by
Milestone: | sage-3.4.1 → sage-3.3 |
---|
comment:4 Changed 14 years ago by
It seems this is a problem with Scipy:
In [16]: def f(x): ....: return 1.0/(x-1.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 14 years ago by
There are at least a couple of issues here. First, brentq is a variant of a bisection-based solver; if you use any bisection-based solver to find a zero of 1/(x-1) 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 14 years ago by
Milestone: | sage-3.4 → sage-3.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 14 years ago by
Priority: | blocker → 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 12 years ago by
Cc: | kcrisman added |
---|---|
Report Upstream: | → N/A |
comment:9 Changed 11 years ago by
Stopgaps: | → #12709 |
---|
comment:10 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:11 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:12 Changed 9 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:13 Changed 8 years ago by
Milestone: | sage-6.3 → sage-6.4 |
---|
comment:14 Changed 4 years ago by
Branch: | → u/assaferan/find_root___is_broken_when_interval_borders_cannot_be_evaluated |
---|
comment:15 Changed 4 years ago by
Authors: | → Eran Assaf |
---|---|
Commit: | → 91f14d3d3a9c48ff38e329425d4b73e133bf6052 |
Status: | new → 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 4 years ago by
Status: | needs_review → needs_work |
---|
comment:17 Changed 4 years 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 4 years ago by
Commit: | 91f14d3d3a9c48ff38e329425d4b73e133bf6052 → 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 4 years ago by
Commit: | 8feb5a96dd1edc16fa59fbd824eafb5942956d2b → 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 4 years ago by
Status: | needs_work → needs_review |
---|
Fixed the bugs and changed behaviour in both cases, as suggested by tscrim
comment:21 Changed 4 years ago by
Reviewers: | → 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 4 years ago by
Commit: | d67280b3a46cc7d95ee2aa1abc8c4d4d6257f963 → 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 4 years ago by
Milestone: | sage-6.4 → sage-8.4 |
---|---|
Status: | needs_review → positive_review |
Thank you. LGTM.
comment:24 Changed 4 years ago by
Branch: | u/assaferan/find_root___is_broken_when_interval_borders_cannot_be_evaluated → e6b7c1e24d19c6bca5c6bd31d8b75b963e046395 |
---|---|
Resolution: | → fixed |
Status: | positive_review → 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