RE: Root finding page manual suggestion

RE: Root finding page manual suggestion

[Mikael Adlers]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 3371 bytes --]

Hi,
I agree with the warning. The book you refereed to "Numerical recipes" 
by W. H. Press S.A Teukolsky et. al. is not regarded by numerical analysis's

as anything worth reading. The algorithms are old and not 
so good implemented. Even the references are bad (how can anyone 
implement linear algebra algorithms without including any references  
to Golub or van Loan?) The only bright part with the book is that they cover

much in an easy way and book is quite cheap.

Potorti on the other hand refereed to the book "Numerical methods"
by Dalquist and Björck. Two of the most leading numerical analysis's 
in the field of ODE and linear algebra. This book is worth reading but
starts to become quite old. I know that a new book, "Numerical Mathematics"
in several volumes will soon be published by SIAM. I can really 
recommend this book as a reference work when it becomes available.

Regards,
/Mikael Adlers

BTW. the choice of when to use the Newton or the secant method is
still present Numerical Mathematics (together with the derivation 
of the rule).



------------------------------------------------------------------ 
 Mikael Adlers, Ph.D.          email: mikael@mathcore.com 
 MathCore AB                   phone: +4613 32 85 07 
 Wallenbergsgata 4             fax:         21 27 01
 SE-583 35 Linköping, Sweden   http://www.mathcore.com



> -----Original Message-----
> From: Jonathan Leto [ mailto:jonathan@leto.net ] 
> Sent: den 19 oktober 2001 04:08
> To: Francesco Potorti`
> Cc: gsl-discuss@sources.redhat.com
> Subject: Re: Root finding page manual suggestion
> 
> 
> Just as a word of warning, I found a interesting site called 
> "Why not use Numerical Recipes?", written by JPL.
> Link: http://math.jpl.nasa.gov/nr/
> 
> It seems that a few professional numerical analysts have found
> quite a few things wrong with much of the code and theory.
> 
> 
>  Francesco Potorti` (pot@gnu.org) was saying:
> 
> > In the "Root  Finding Algorithms using Derivatives" page one reads that
> > the Newton's method converges  quadratically for single roots, while the
> > secant  method  has 1.6  convergence  order,  and  "can be  useful  when
> > computation of the derivative is costly".
> > 
> > In fact, as far as I know, it is almost always preferable to Newton's
> > method.
> > 
> > Quoting from "Numerical Methods" by Germund Dahlquist and Ake Bjorck,
> > translated by Ned Anderson - Prentice-Hall Inc., 1974.
> > 
> > Chapter 6.4.1. (the end) pg 229
> >   The choice  between the secant  method  and  Newton-Raphson's method
> > depends on the amount of work required to  compute f'(x).  Suppose the
> > amount  of work to  compute f'(x)  is T  times  the amouof  work to
> > compute a value of f(x).   Then an  asymptotic analysis can be used to
> > motivate the rule: if T > 0.44, then use the secant method; otherwise,
> > use Newton-Raphson's method.
> > 
> > I've used this  criterion in some small numerical  program I've written,
> > and it  works ok.   The above  means that Newton's  method wins  only if
> > computing f'(x) is  more than twice faster than  computing f(x), a quite
> > rare occurrence in practice.  I suggest this fact to be mentioned in the
> > manual.
> > 
> > Please Cc to me while replying, as I am not subscribed to the list.
> 
> -- 
> jonathan@leto.net 
> "Wir mussen wissen. Wir werden wissen."
> 
> 
> 

Re: Root finding page manual suggestion

[Brian Gough]

Francesco Potorti` writes:
 > I've used this  criterion in some small numerical  program I've written,
 > and it  works ok.   The above  means that Newton's  method wins  only if
 > computing f'(x) is  more than twice faster than  computing f(x), a quite
 > rare occurrence in practice.  I suggest this fact to be mentioned in the
 > manual.

Thanks for the information, I wasn't aware of that.  I'll add a note
in the manual.  

One factor in favor of Newton's method might be better numerical
stability on roots of higher multiplicity -- the subtraction of
f(a)-f(b) in the secant method could introduce a cancellation error
there.

regards
Brian Gough

Root finding page manual suggestion

[Francesco Potorti`]

In the "Root  Finding Algorithms using Derivatives" page  one reads that
the Newton's method converges  quadratically for single roots, while the
secant  method  has 1.6  convergence  order,  and  "can be  useful  when
computation of the derivative is costly".

In fact, as far as I know, it is almost always preferable to Newton's
method.

Quoting from "Numerical Methods" by Germund Dahlquist and Ake Bjorck,
translated by Ned Anderson - Prentice-Hall Inc., 1974.

Chapter 6.4.1. (the end) pg 229
  The choice  between the secant  method  and  Newton-Raphson's method
depends on the amount of work required to  compute f'(x).  Suppose the
amount  of work to  compute f'(x)  is T  times  the amount of  work to
compute a value of f(x).   Then an  asymptotic analysis can be used to
motivate the rule: if T > 0.44, then use the secant method; otherwise,
use Newton-Raphson's method.

I've used this  criterion in some small numerical  program I've written,
and it  works ok.   The above  means that Newton's  method wins  only if
computing f'(x) is  more than twice faster than  computing f(x), a quite
rare occurrence in practice.  I suggest this fact to be mentioned in the
manual.

Please Cc to me while replying, as I am not subscribed to the list.

Re: Root finding page manual suggestion

[Jonathan Leto]

Just as a word of warning, I found a interesting site called 
"Why not use Numerical Recipes?", written by JPL.
Link: http://math.jpl.nasa.gov/nr/

It seems that a few professional numerical analysts have found
quite a few things wrong with much of the code and theory.


 Francesco Potorti` (pot@gnu.org) was saying:

> In the "Root  Finding Algorithms using Derivatives" page  one reads that
> the Newton's method converges  quadratically for single roots, while the
> secant  method  has 1.6  convergence  order,  and  "can be  useful  when
> computation of the derivative is costly".
> 
> In fact, as far as I know, it is almost always preferable to Newton's
> method.
> 
> Quoting from "Numerical Methods" by Germund Dahlquist and Ake Bjorck,
> translated by Ned Anderson - Prentice-Hall Inc., 1974.
> 
> Chapter 6.4.1. (the end) pg 229
>   The choice  between the secant  method  and  Newton-Raphson's method
> depends on the amount of work required to  compute f'(x).  Suppose the
> amount  of work to  compute f'(x)  is T  times  the amount of  work to
> compute a value of f(x).   Then an  asymptotic analysis can be used to
> motivate the rule: if T > 0.44, then use the secant method; otherwise,
> use Newton-Raphson's method.
> 
> I've used this  criterion in some small numerical  program I've written,
> and it  works ok.   The above  means that Newton's  method wins  only if
> computing f'(x) is  more than twice faster than  computing f(x), a quite
> rare occurrence in practice.  I suggest this fact to be mentioned in the
> manual.
> 
> Please Cc to me while replying, as I am not subscribed to the list.

-- 
jonathan@leto.net 
"Wir mussen wissen. Wir werden wissen."