GNU Scientific Library - Bugs: bug #40092, false position root finding...
You are not allowed to post comments on this tracker with your current authentication level.
bug #40092: false position root finding requires too many function evals
Submitter: | Patrick Alken <psa> | ||
Submitted: | Mon 23 Sep 2013 03:49:24 PM UTC | ||
Category: | Performance | Severity: | 3 - Normal |
Operating System: | Status: | Postponed | |
Assigned to: | None | Open/Closed: | Open |
Release: |
Sat 05 Oct 2013 08:37:39 AM UTC, comment #5: |
Max <nikulin> |
Sat 05 Oct 2013 07:39:29 AM UTC, comment #4: Thank you for your further input.
As you say, the real problem is that the current design is not ideal because it does not make the desired precision available to the iteration routine. And this can result in more iterations than are necessary.
It appears that the residual test is intended to handle this situation but this also involves an extra function evaluation on each iteration because the solvers don't return function values.
This clearly needs fixing but it requires design changes that will break backwards compatibility so we have unfortunately had to put this off to GSL version 2.x.
|
Brian Gladman <gladman>![]() |
Sat 05 Oct 2013 05:35:22 AM UTC, comment #3: I would like to stress the point from the original message.
The minimal step for root finding should not be much less
|
Max <nikulin> |
Sat 05 Oct 2013 05:20:09 AM UTC, comment #2: Brian,
On linux the FPU works in 80 bit extended precision mode
I may reproduce the issue with my example by adding
The bug is apparent if the test function is written
Sorry, I forgot that 64 bit precision may lead to another
|
Max <nikulin> |
Thu 03 Oct 2013 01:16:34 PM UTC, comment #1: Running the supplied program on Windows x64 gives:
# i N_f x_l-r x_i-r x_h-r x_h-x_l
so I cannot reproduce the results set out in this report.
|
Brian Gladman <gladman>![]() |
Mon 23 Sep 2013 03:49:24 PM UTC, original submission:
From M.A.Nikulin@gmail.com:
Hi,
I have noticed that the GSL implementation of the false position method
Since the reference states:
I suppose that it is a design flaw that user supplied tolerance is not
The problem appears if at a certain step the edge of a bracketing
The following program demonstrates the issue. The bisection method
Maxim Nikulin
/* Excessive function evaluations for an almost linear function
double fpol2 (double x, void *params)
struct f_count_wrap_par {
double f_count_wrap (double x, void *params)
int main (void)
Fwrap.function = f_count_wrap;
s = gsl_root_fsolver_alloc (gsl_root_fsolver_falsepos);
Output: iteration, number of function evaluations, shifts from the root
# i N_f x_l-r x_i-r x_h-r x_h-x_l
|
Patrick Alken <psa>![]() |
Depends on the following items: None found
Items that depend on this one: None found
The quick fix may be to check that x_linear differs
from x_left and x_right by some value. Some multiple of
GSL_DBL_EPSILON since required precision is not available
by design.
I do not think that additional tests of function values
may help since the derivative of the function can
be arbitrary large or small close to the root: 1e9*(x - 1)
or 1e-9*(x - 1).
That is why I tried to raise discussion on gsl-help
instead of reporting a bug.