Re: Secant method vs Newton's method



Bernard Danloy wrote:
In article <45156F04.5050403@xxxxxxxxxxx>, Jentje Goslinga
<goslinga@xxxxxxxxxxx> wrote :


Schizoid Man wrote:

Hi,

Under what circumstances would I prefer the secant method to Newton's method?

Newton's method converges much faster and the number of function calls seem to be the same (if we assume the derivative is a function call).

The natural generalization of the Secant Method to higher order is obtained by using Normalized Inverse Hermite interpolation (NIH).
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 resulting higher order methods have the desirable bracketing property.

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 [-1/2,1/2] 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. I have found NIH to be somewhat better than Brent's algorithm (which is not bad) in the cases which I have tested.
[The other example where I compute the roots of the Secular Function for the Symmetric Eigenvalue Problem should be disregarded since this function is of a non polynomial nature for which the existing methods have been found to be more reliable.]

I have C code for the algorithm and can send it to whomever is interested.

Jen


If i can have sympathy for anyone who has choosen mathematics as a hobby,

Mathematics is about facts, whoever proposes them, regardlesss of their occupation or affiliation. I am not going to comment on whether some nondescript at some nondescript university considers me an amateur. Even then, Weiserstrass and many great mathematicians were amateurs. In any case, this newsgroups is not restricted to non-amateurs.

it is difficult for me to remain silent when i read on your website :

If you have nothing of substance to contribute except some notes about nomenclature and some "gut feelings" that second derivatives are inappropriate, please remain silent.

" It is therefore easier to compute the roots of all polynomials up
to a given order than to compute the roots for a polynomial of given
order in isolation "

Complete non sense ; the classical orthogonal polynomials do have such
nice properties that you can find their zeroes without ever using the
interlacing you are referring to. A job of complexity n^2 is never
easier than a job of complexity n.

I have no idea what you are talking about.

I would also add that the terminology " Hermite polynomial " is not
correct.

I have invented these polynomials and shall call them what I want. Interpolation with derivatives was one of Hermite's main inventions, so I am attaching his name to them.

Hermite polynomials are classical orthogonal polynomials ;
i don't know anybody using the term for the polynomial generated by
Hermite interpolation.

Maybe, what you have experimented has some value ;

There is no need for lazy and condescending comments, please evaluate what I have done before you post.

if it is the case,
you should try to present the principle more clearly and to give the
reasons why it can be expected to work better.

Numerical Analysis does not need reasons and expectations but phrases errors in terms of higher order derivatives, as I have properly done.

When i see some second derivatives in your formulas, i am perplex.

Learn some English before you post.

Bernard Danloy
Department of Mathematical Engineering
University of Louvain-la-Neuve

Jen

.

Relevant Pages

  • Re: Secant method vs Newtons method
    ... The natural generalization of the Secant Method to higher order is ... obtained by using Normalized Inverse Hermite interpolation. ... Interpolation" and present an example where I compute the roots of the ... " It is therefore easier to compute the roots of all polynomials up ...
    (sci.math.num-analysis)
  • Re: Secant method vs Newtons method
    ... The natural generalization of the Secant Method to higher order is obtained by using Normalized Inverse Hermite interpolation. ... 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. ...
    (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)
  • Re: interpolation accuracy, oversampling and fractional interpolation
    ... by Vesma Jussi? ... concept of interpolating using a variety of fitted polynomials is not ... interpolation of segments of your Parks-McClellan kernel (instead ...
    (comp.dsp)
  • Re: parabolic interpolation
    ... I want to do second order ... Cubics work nicely for interpolation because by specifying ... higher-order polynomials have too many ... free parameters, and quadratics too few. ...
    (comp.soft-sys.matlab)