When to use the Secant Method of finding roots?

Hello, everybody. I'm taking my first course in Matlab and our professor has been teaching us about the different processes used to find the roots of an equation. He gave us a problem set which includes finding roots using the Newton-Raphson method, a hybrid of bisection and N-R, and a hybrid of bisection and Secant. The first two were simple, but the third one is tripping me up. I want to use an if-else statement so the program will decide when to use each method, but I can't find any quantitative explanation of when the Secant method should be used. The N-R method had a nice inequality that worked perfectly but I don't see anything so straight forward for this. Does anybody have any insight regarding the Secant method and when exactly it should be used? Thank you!

Answer 1

[Derek O'Connor]

I would like to qualify what John says: "Methods like the secant method are rarely very good choices anyway."

This is arguably true if the Secant Method is used alone. However, it is very useful when used in a "poly-algorithm" such as Matlab's fzero, which as they say is over 40 years old:

Use type fzero to see the code for fzero

%  This algorithm was originated by T. J. Dekker.  An Algol 60 version,
%  with some improvements, is given by R. P. Brent in "Algorithms for
%  Minimization Without Derivatives", Prentice-Hall, 1973.  A Fortran
%  version is in Forsythe, Malcolm and Moler, "Computer Methods
%  for Mathematical Computations", Prentice-Hall, 1976.

Here is the part of fzero pertinent to your question:

      % Choose bisection or interpolation
      if (abs(e) < toler) || (abs(fa) <= abs(fb))
          % Bisection
          d = m;  e = m;
          procedure='bisection';
      else
          % Interpolation
          s = fb/fa;
          if (a == c)
              % Linear interpolation
              p = 2.0*m*s;
              q = 1.0 - s;
          else
              % Inverse quadratic interpolation
              q = fa/fc;
              r = fb/fc;
              p = s*(2.0*m*q*(q - r) - (b - a)*(r - 1.0));
              q = (q - 1.0)*(r - 1.0)*(s - 1.0);
          end;
          if p > 0, q = -q; else p = -p; end;
          % Is interpolated point acceptable
          if (2.0*p < 3.0*m*q - abs(toler*q)) && (p < abs(0.5*e*q))
              e = d;  d = p/q;
              procedure='interpolation';
          else
              d = m;  e = m;
              procedure='bisection';
          end;
      end % Interpolation

      % Next point

The Linear Interpolation above is the (2-point) Secant Method. The Inverse Quadratic may be thought of as an Inverse 3-point Secant Method, which is a very clever idea that should be studied carefully.

As you can see, deciding which method to use at any point in the computation is a very delicate business. Take a look at Forsythe, Malcolm, and Moler, which is an old but excellent book. Dahlquist & Bjorck, Numerical Methods in Scientific Computing, Vol 1, 2008, Sec 6.2.4, has a brief explanation of what they call "hybrid methods".

Writing code for such a method is not for the faint-hearted or the amateur: Richard Brent has been, among other things, one of the best numerical analysts in the past 40 years, and still publishes great papers and software.

None-the-less, trying to write such code is a good exercise that should help you appreciate how difficult it is to write robust and efficient numerical software. This, I presume, is the reason your professor set you this exercise.

Postscript: As you can see from my notes http://www.derekroconnor.net/NA/Notes/NA-4-Latex.pdf, pages 19-20, I never did finish the section on "poly-algorithms" -- faint-heartedness.

Added Reference

Cleve Moler's book Numerical Computing with MATLAB has an excellent discussion of the original Dekker-Brent zeroin and Matlab's version of it, fzero, in Chapter 4, on Zeros and Roots. http://www.mathworks.co.uk/moler/index_ncm.html

Answer 2

[John D'Errico]

Methods like the secant method are rarely very good choices anyway. They are better there as teaching tools to learn about the general techniques. In the end, you are far better off using canned routines like fzero, written by someone with some serious experience in the field and who has worried about robustness to common problems.

Yeah, I know that this seems like a cop out, but my point is that good routines are often hybrid ones. As well, it is often true that you don't personally want to be writing your own numerical analysis routines to solve serious problems. ALWAYS use a canned routine if it is available.

[Rachel]

I don't think you read my elaboration to the question. I'm in a class. I'm trying to create a hybrid method of finding roots as a homework assignment. I know that the Newton-Raphson method is used only when the guess it creates is within the set bounds of the function. There's an inequality to check that, so I made an if-else statement that works perfectly. Now I need to make a hybrid root-finder with the Secant method, but I can't find any qualitative explanation of when it should be used and I need help.