54 views (last 30 days)

Show older comments

Derek O'Connor
on 5 Feb 2012

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

John D'Errico
on 5 Feb 2012

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.

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!