Re: Secant method vs Newton's method

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,
it is difficult for me to remain silent when i read on your website :

" 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 would also add that the terminology " Hermite polynomial " is not
correct. 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 ; 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.

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

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

Relevant Pages

  • 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: JSH: Keep it simple
    ... arbitrary rule that you take roots of monic polynomials with integer coefficients. ... integral root is divisible by something that is coprime to ... Your claim regarding rational roots of this polynomial cannot do that, since the standard theory makes no claims regarding common factors among such roots. ...
    (sci.math)
  • Re: Orthogonal polynomials (was Chebyshv, etc.)
    ... Legendre, Chebyshev, Hermite, etc.) have n real roots in the ... This general property of orthogonal polynomials is proved as ... you can simply ignore any zeros ... If alpha is a real root of phi_k, ...
    (sci.math)
  • Re: Question on algebraic numbers
    ... adjoining to Q the roots of all polynomials over Q. ... extensions of Q which have a solvable Galois group. ... solutions by radicals). ...
    (sci.math)
  • Re: New paper, algebraic integers, Galois Theory
    ... > Now consider the case that m, f, and u are algebraic integers, then I ... > something about the factors of roots of monic polynomials with integer ... Note that this claim does not require Galois Theory, ...
    (sci.math)