[lmi-commits] [lmi] odd/brent a24eea7 3/8: Find a root of cos(x)-0.999

[Greg Chicares]

branch: odd/brent
commit a24eea713879669c8b42a3cea61b7df29073724f
Author: Gregory W. Chicares <gchicares@sbcglobal.net>
Commit: Gregory W. Chicares <gchicares@sbcglobal.net>

    Find a root of cos(x)-0.999
    
    Compare iterations against this published example:
      https://www.embeddedrelated.com/showarticle/855.php
    | Let’s look at a function that’s nasty to solve because of its flatness
    As in the preceding commit, our values for each iteration match the
    online article's. Number of iterations:
      brent: 14 + 2 initial
      chand: 10 + 2 initial
    
    Kahan
      https://people.eecs.berkeley.edu/~wkahan/Math128/LecRlRtF.pdf
    says that root-finding algorithms have three successive phases:
    
    | 1. Flailing: Successive iterates may seem erratic if no Straddle has
    | been found; or else they seem to be taking a long leisurely walk
    | from a poor initial guess; or else they seem to be departing only
    | reluctantly from that initial guess.
    | 2. Converging: Differences between successive iterates are dwindling
    | fast enough, or values of |f(x)| at successive iterates are decaying
    | fast enough, that this phase cannot last long. Higher order iterating
    | formulas are worth their cost only if such extraordinarily high
    | accuracy is sought as would prolong this phase.
    | 3. Dithering: Roundoff, mostly in f(x), makes iterates seem to behave
    | erratically; or one side of a Straddle is doing most the moving as it
    | shrinks intolerably slowly.
    
    Here, Brent spends comparatively more time flailing: both bounds move,
    the upper much more than the lower, as the technique alternates between
    the secant method and bisection. Chandrupatla doesn't use the secant
    method at all, and seems more pessimistic in this example, bisecting
    throughout the Flailing phase and then Converging with IQI. This would
    suggest a hypothesis that bisection is better than linear interpolation
    during Flailing--i.e., that Brent takes a leisurely but fruitful walk
    from one bound, and a reluctant and fruitless walk from the other. But
    is there a robust way to suppress the fruitless one?
---
 zero_test.cpp | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/zero_test.cpp b/zero_test.cpp
index de22b9e..8685f4d 100644
--- a/zero_test.cpp
+++ b/zero_test.cpp
@@ -114,10 +114,10 @@ struct e_functor
 struct e_nineteenth
 {
 //  double operator()(double z) {return std::pow(z, 19);}         // -1.0 , 4.0
-//  double operator()(double z) {return std::cos(z) - 0.999;}     // -0.01, 0.8
+    double operator()(double z) {return std::cos(z) - 0.999;}     // -0.01, 0.8
 //  double operator()(double z) {return std::pow(z - 1.7, 17.0);} //  0.0 , 2.0
 //  double operator()(double z) {return std::pow((z - 1.0), 3);}  //  0.0 , 1.8
-    double operator()(double z) {return std::pow(z, 2.0) - 2.0;}  //  0.0 , 2.0
+//  double operator()(double z) {return std::pow(z, 2.0) - 2.0;}  //  0.0 , 2.0
 };
 
 /// A function that's unfriendly to the secant method.
@@ -275,8 +275,8 @@ int test_main(int, char*[])
     //   195 Brent's table 4.1 (IBM 360)
     //   171 x86_64 brent_zero (IEEE 754)
     //   169 x86_64 decimal_root (differs slightly due to rounding)
-    double lo =   0.0 ;
-    double hi =   2.0 ;
+    double lo =   -0.01;
+    double hi =   0.8 ;
 std::cout << "test genuine brent" << std::endl;
     double d = brent_zero(lo, hi, 1.0e-16, e_19);
 //  LMI_TEST(std::fabs(d) <= epsilon);