Opened 14 years ago

Closed 4 years ago

# find_root() is broken when interval borders cannot be evaluated

Reported by: Owned by: mabshoff mhansen critical sage-8.4 numerical kcrisman Eran Assaf Travis Scrimshaw N/A e6b7c1e e6b7c1e24d19c6bca5c6bd31d8b75b963e046395 #12709

### Description

```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

### comment:1 Changed 14 years ago by mabshoff

Milestone: sage-3.4 → sage-3.3

### comment:2 Changed 14 years ago by mhansen

Owner: changed from jkantor to mhansen new → assigned

### comment:3 Changed 14 years ago by mabshoff

Milestone: sage-3.4.1 → sage-3.3

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

### comment:4 Changed 14 years ago by mhansen

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 cwitty

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 mabshoff

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 was

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:9 Changed 11 years ago by jen

Stopgaps: → #12709

### comment:10 Changed 9 years ago by jdemeyer

Milestone: sage-5.11 → sage-5.12

### comment:11 Changed 9 years ago by vbraun_spam

Milestone: sage-6.1 → sage-6.2

### comment:12 Changed 9 years ago by vbraun_spam

Milestone: sage-6.2 → sage-6.3

### comment:13 Changed 8 years ago by vbraun_spam

Milestone: sage-6.3 → sage-6.4

### comment:14 Changed 4 years ago by assaferan

Branch: → u/assaferan/find_root___is_broken_when_interval_borders_cannot_be_evaluated

### comment:15 Changed 4 years ago by assaferan

Authors: → Eran Assaf → 91f14d3d3a9c48ff38e329425d4b73e133bf6052 new → needs_review

Hi, added two small validity checks:

1. If one of the endpoints is evaluated to NaN we seek a nearby point in the interval which can be evaluated.
2. 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 assaferan

Status: needs_review → needs_work

### comment:17 Changed 4 years ago by tscrim

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 git

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 git

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 assaferan

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 tscrim

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 from `if (full_output):` and the outermost pair from the other `if` statement 4 lines down.

### comment:22 Changed 4 years ago by git

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 tscrim

Milestone: sage-6.4 → sage-8.4 needs_review → positive_review

Thank you. LGTM.

### comment:24 Changed 4 years ago by vbraun

Branch: u/assaferan/find_root___is_broken_when_interval_borders_cannot_be_evaluated → e6b7c1e24d19c6bca5c6bd31d8b75b963e046395 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.