Re: Secant method vs Newton's method


Bernard Danloy wrote:
In article <451B4819.60709@xxxxxxxxxxx>, Jentje Goslinga
<goslinga@xxxxxxxxxxx> wrote :

skipping and forgiving bitchy remarks from both sides

On my website, I present a number of problems in which I have invested thousands of hours and I think it deserves better than some rather negative comments, so I must protest.

The original thread sets Newton's Method against the Secant Method, a point which is presented in every book on numerical analysis.
I am presenting on my web site the NIH method, a natural generalization to higher order of the bracketed Secant Method for root finding, where the Secant Method occurs naturally as the zero order case. I present the error term in terms of higher order derivatives of the inverse function.

I present some numerical examples where I test the first and second order methods against Brent's root finding method.
My main example is the computation of the roots of all the Legendre polynomials up to a certain given order which is a nice example which suits my purposes. The fact that the polynomials are either symmetric or antisymmetric and the fact that the results can be verified by independent means also make this a good example. I do not claim to know the most up to date developments in the theory of orthogonal polynomials and consider this to be totally outside the scope of this discussion. I simply have chosen this example because the roots of the Legendre polynomial of the previous order supply a valid bracketing interval for the roots of the one of the current order, for free, which is useful to illustrate my method.

Considering the nomenclature, I use two point Hermite polynomials which are normalized to the interval [-1/2,+1/2] elsewhere on my web site for the purpose of functional interpolation. I have chosen to call them Normalized Hermite Polynomails, but am open to suggstions and maybe Two-Point Normalized Hermite [Interpolation Polynomials] would be better.
The two root finding methods which I am presenting use these same polynomials to interpolate the inverse of a given function (after transforming the derivatives according to the rules). So the name of the resulting methods could be something like Inverse Interpolation using Normalized Two Point Hermite Polynomials, whatever.

The appearance of higher order derivatives is natural in any higher order method. My normalization approach reduces the problem to a unit square centrered around the origin. Naturally, at some (usually early) steps of the iteration the interpolated result may lie outside the unit square, in which case one simply uses the zero order method which is again the Regula Falsi.

I have tested the NIH methods against Brent's method and found them to be better in the sense of requiring fewer function evaluations. While it is true that I have not tested many root finding problems, I think my results show that the method may deserve better than the "maybe has some value" which you are awarding it. The only point about which one could argue is the additional cost of evaluating derivatives. Brent's method uses a numerically synthesized derivative, so it does not require an explicit derivative computation. However, in most cases the supplemental computation of the derivatives of a complicated function shares many operations with the computation of the function itself. This is also very true in the case of the Legendre polynomials, so the expense of additional drivative evaluations may not be that large.

Maybe, we should try to make this newsgroup a friendlier place.

Jen

.

Relevant Pages

  • Re: Integer-Valued Polynomials
    ... There is a risk of confusion in terminology here. ... refers to root finding, ... has little to do with the question of interpolation. ... Interpolating polynomials in many variables, ...
    (sci.math)
  • Re: Integer-Valued Polynomials
    ... mentioned interpolation and Newton divided ... refers to root finding, ... has little to do with the question of interpolation. ... Interpolating polynomials in many variables, ...
    (sci.math)
  • Re: A Two-Level SOLVER ??
    ... Polynomials are the most easy to use and the most difficult to predict! ... examining/studying/observing the behaviour of derivatives of complex ... I'll seriously consider any non-Frontline VBA Solver algorithm. ... ..constraint: ...
    (microsoft.public.excel.programming)
  • Re: Secant method vs Newtons method
    ... It is found that the Secant Method is obtained using zero order NIH and higher order methods with increasingly higher order error terms are obtained by using First or Second Order NIH. ... The simple innovation which I am using in NIH, and which is indicated by the word Normalized, is that I am using for interpolation the two point Hermite Interpolating Polynomial interpolating the function and some of its derivatives on a normalized interval by simply mapping the bracketing interval to the normalized interval each iteration. ... This allows use of the same interpolation formula every step of the iterative search for the root by evaluating the root of the Hermite polynomial interpolating the inverse function and its first or even second derivatives on two points within the normalized interval. ... I have described this on my website www.numerical-algorithms.com under the section "Root Finding Using Inverse Normalized Hermite Interpolation" and present an example where I compute the roots of the Legendre polynomials. ...
    (sci.math.num-analysis)
  • Re: Integer-Valued Polynomials
    ... variables and for general fields? ... has little to do with the question of interpolation. ... Interpolating polynomials in many variables, ... A tensor product of nonsingular ...
    (sci.math)
Loading