[Math] advice using brent_find_minima()
I'd like to find the root of a function f (find x such that f(x) = 0). Should I pass abs( f ) to brent_find_minima()? I can't find examples... Thanks in advance!
I'd like to find the root of a function f (find x such that f(x) = 0).
Should I pass abs( f ) to brent_find_minima()?
No: that's a truly lousy method for finding the root. If you have one or more derivatives of f then use newton_raphson_iterate or halley_iterate from http://www.boost.org/doc/libs/1_57_0/libs/math/doc/html/math_toolkit/interna... Otherwise use toms748_solve or bracket_and_solve_root from http://www.boost.org/doc/libs/1_57_0/libs/math/doc/html/math_toolkit/interna.... Note that the latter of these two calls the former, which happens to be asymptotically optimal if you have no derivative information. And no, we don't have examples for these as they're "details" that aren't officially part of the library yet. However, we really should do something about that as the code has actually been stable for millennia now ;-) HTH, John.
-----Original Message----- From: Boost-users [mailto:boost-users-bounces@lists.boost.org] On Behalf Of John Maddock Sent: 09 December 2014 12:58 To: boost-users@lists.boost.org Subject: Re: [Boost-users] [Math] advice using brent_find_minima()
I'd like to find the root of a function f (find x such that f(x) = 0).
Should I pass abs( f ) to brent_find_minima()?
No: that's a truly lousy method for finding the root.
If you have one or more derivatives of f then use newton_raphson_iterate or halley_iterate from http://www.boost.org/doc/libs/1_57_0/libs/math/doc/html/math_toolkit/interna... 1/roots.html
Otherwise use toms748_solve or bracket_and_solve_root from http://www.boost.org/doc/libs/1_57_0/libs/math/doc/html/math_toolkit/interna... 1/roots2.html. Note that the latter of these two calls the former, which happens to be asymptotically optimal if you have no derivative information.
And no, we don't have examples for these as they're "details" that aren't officially part of the library yet. However, we really should do something about that as the code has actually been stable for millennia now ;-)
There is an example http://www.boost.org/doc/libs/1_57_0/libs/math/example/root_finding_example.... that you might find helpful. Paul --- Paul A. Bristow Prizet Farmhouse Kendal UK LA8 8AB +44 (0) 1539 561830
Paul A. Bristow <pbristow <at> hetp.u-net.com> writes:
There is an example
http://www.boost.org/doc/libs/1_57_0/libs/math/example/root_finding_example. cpp
that you might find helpful.
Paul
Thanks for the link!
John Maddock <boost.regex <at> virgin.net> writes:
I'd like to find the root of a function f (find x such that f(x) =
0).
Should I pass abs( f ) to brent_find_minima()?
No: that's a truly lousy method for finding the root.
If you have one or more derivatives of f then use newton_raphson_iterate or halley_iterate from
http://www.boost.org/doc/libs/1_57_0/libs/math/doc/html/math_toolkit/inte rnals1/roots.html
Otherwise use toms748_solve or bracket_and_solve_root from
http://www.boost.org/doc/libs/1_57_0/libs/math/doc/html/math_toolkit/inte rnals1/roots2.html.
Note that the latter of these two calls the former, which happens to be asymptotically optimal if you have no derivative information.
And no, we don't have examples for these as they're "details" that aren't officially part of the library yet. However, we really should do something about that as the code has actually been stable for millennia now
HTH, John.
OK, now I got it! You have brent algorithm for finding the minima, but not brent algorithm for finding the root. I don't have derivative for f, so how does toms748_solve compare to [1]? Regards [1] http://en.wikipedia.org/wiki/Brent%27s_method
OK, now I got it! You have brent algorithm for finding the minima, but not brent algorithm for finding the root.
I don't have derivative for f, so how does toms748_solve compare to [1]?
They are very similar and differ only in the interpolation methods used, see http://na.math.kit.edu/alefeld/download/1995_Algorithm_748_Enclosing_Zeros_o... for the details, but TOMS748 claims to be the best of the bunch - albeit I suspect for many problems there is little to choose between them. Certainly TOM748 seems to be very robust, and for most functions will find the root to double precision in about 8-10 calls to f() provided the starting bounds aren't too far apart. Of course in the extreme case that your function is basically a square wave, you can't do better than bisection, which all of these algorithms ultimately fall back to. John.
John Maddock <boost.regex <at> virgin.net> writes:
They are very similar and differ only in the interpolation methods used, see
http://na.math.kit.edu/alefeld/download/1995_Algorithm_748_Enclosing_Zeros_o f_Continuous_Functions.pdf
for the details, but TOMS748 claims to be the best of the bunch - albeit I suspect for many problems there is little to choose between them. Certainly TOM748 seems to be very robust, and for most functions will find the root to double precision in about 8-10 calls to f() provided the starting bounds aren't too far apart. Of course in the extreme case that your function is basically a square wave, you can't do better than bisection, which all of these algorithms ultimately fall back to.
John.
Thanks a lot for the info!
participants (4)
-
dariomt -
dariomt＠gmail.com
-
John Maddock -
Paul A. Bristow