From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: need help - multiplicity Date: 8 Mar 1999 14:57:19 GMT Newsgroups: sci.math.num-analysis Keywords: Basic comparison of root-finding methods In article <36E1EB3F.6699@agora.ulaval.ca>, Barney writes: |> Hi, |> |> Does anyons have some documentation about multiplicity? multiplicity |> about Newton-Raphson, Bisection, Regula Falsi, Steffensen and Secant |> methods. |> |> What is the method which converges more quickly between : |> |> -Secant and Bisection? and why? |> -Newton-Raphson and Regula Falsy? and why? |> any basic numerical analysis text has this. I assume you mean "order of convergence" by "multiplicity" multiplicity is a property of the zero x* of f sought. x* is of multiplicity m if and only if f(x)=(x-x*)^m *g(x) with g(x*) <>0. none of the mentioned methods works well with zeroes of multiplicity >1. regula falsi and bisection assume m odd (change of sign). For m>1 there will be premature or erratic termination due to evaluation errors in f. Newton converges , but only with order 1, but can be modified such that quadratic convergence is retained. (multiply correction by m. Requires m to be known.) order of convergence is defined by q-order |x^{k+1}-x*|= O(|x^k-x*|^p) , p> 1 and |x^{k+1}-x*|<= L |x^k-x*| 01 Newton-Raphson, Steffensen have Q-order =2 (proof by Taylors theorem) Newton_Raphson needs f,f' Steffensen needs 2 f (dim=1) Regula falsi has Q-order 1 , needs one f per step, if f''(x*)<>0 one of the end points finally remains fixed. Is often slower than Bisection. Bisection : R-order 1 (you cannot directly relate two successive errors) but inclusion error halfed at least Secant rule (in contrast to Regula falsi, which encloses the zero, taking always the last two estimates to produce the next one) has Q-order (sqrt(5)+1)/2, but needs only one f per step, hence more "efficient" than Newton-Raphson. Proof for secant rule somewhat tricky. see e.g Ortega&Rheinboldt: solution of nonlinear equations in seveal variables. hope this helps peter ============================================================================== From: jthorn@davinci.thp.univie.ac.at (Jonathan Thornburg) Subject: Re: Root finding Date: 2 Aug 1999 16:21:53 +0200 Newsgroups: sci.math.num-analysis Summary: pointer to ++good book, also ++good and freely redistributable code Keywords: root finding, C, Fortran, code, book, Forsythe, Malcolm, Moler, In article <375D7C22.4BE8@phoenix.net>, Lynn Killingbeck wrote: >Read through the section on root finding in 'Numerical Recipes in C', by >Press et al. Perhaps you can find some one (or more) of the many methods >discussed that you can adapt to your purposes. I have not used their C >routines, but generally like their discussion and comparison of various >methods. Unfortunately, the Numerical Recipes authors aren't experts in numerical analysis, and it shows. In the case at hand -- Brent's method for root finding -- Numerical Recipes has just slightly fiddled with Brent's original code... and in certain cases their fiddling may make the method fail. For a very clear discussion of root-finding written by authors who _are_ numerical analysis experts, see @book { Forsythe-Malcolm-Moler, author = "George E. Forsythe and Michael A. Malcolm and Cleve B. Moler", title = "Computer Methods for Mathematical Computations", publisher = "Prentice-Hall", address = "Englewood Cliffs", year = 1977, isbn = "0-13-165332-6", } An additional benefit of Forsythe/Malcolm/Moler's book and software is that unlike the Numerical Recipes software, the FMM software is freely available from Netlib http://www.netlib.org/fmm # double precision http://www.netlib.org/sfmm # single precision and may be (legally) freely redistributed along with your own code. -- -- Jonathan Thornburg http://www.thp.univie.ac.at/~jthorn/home.html Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik "The first strike in the American Colonies was in 1776 in Philadelphia, when [...] carpenters demanded a 72-hour week." -- Anatole Beck