Re: Convergence of Newton's method for finding a root of a polynomial


"Randy Poe" <poespam-trap@xxxxxxxxx> wrote in message news:1115831183.133305.176320@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> Dirk Van de moortel wrote:
> > "Robert Israel" <israel@xxxxxxxxxxx> wrote in message
> news:d5t9o7$brj$1@xxxxxxxxxxxxxxxxxxxxxxxxx
> > > In article <d5stii$eqm$1@xxxxxxxxxxxxxx>,
> > > Artur Siekielski <gruesome@xxxxxxxxxxxxxxxxxxxx> wrote:
> > > >Hello.
> > > >I am trying to solve a problem of finding all roots of a
> polynomial P. All
> > > >roots of P are real and simple. I know an interval [a,b] where all
> roots are
> > > >contained. I want to use an algorithm which would be good, if I
> could prove
> > > >the following lemma:
> > > >
> > > >If x \in (a,b) and P'(x) != 0, then Newton's method starting from
> x converges
> > > >to some root of P.
> > > >
> > > >Is that true?
> > >
> > > No, it isn't. For example, try the polynomial
> > > P(x) = x^3 - x.
> > > Newton's method starting at x = 1/sqrt(5) cycles with a period of 2
> > > (1/sqrt(5) -> -1/sqrt(5) -> 1/sqrt(5) -> ...)
> >
> > Yes, but P'(x) = 3x^2 -1 is *not* nonzero
> > It is given that P'(x) != 0 in ]a,b[ and that all the roots are in
> [a,b]
> >
>
> Isn't it a necessary and sufficient condition that the
> starting x be within an interval around the root such
> that P''(x) > 0?

Doesn't ring a bell - and seems a bit unlikely.
why P''(x) > 0 and not P''(x) < 0 ?
Take P(x) = x^3 + x + 1.
Even if you start at x=0 for which P''(0) = 0,
you have convergence.

Dirk Vdm


>
> - Randy
>


.

Relevant Pages

  • Re: complex numbers
    ... >> In sci.physics.relativity, Dirk Van de moortel ... roots (multiple roots counted multiply) all in C. ...
    (sci.physics.relativity)
  • Re: Convergence of Newtons method for finding a root of a polynomial
    ... On Wed, 11 May 2005, Dirk Van de moortel wrote: ... >> roots are ... then x0 is a safe starting point for Newton's method. ...
    (sci.math)
  • Re: complex numbers
    ... > In sci.physics.relativity, Dirk Van de moortel ... // Pogo 2.0 = We have met the aliens and they are us! ... Prev by Date: ...
    (sci.physics.relativity)
  • Re: Newton and Einstein
    ... Dirk Van de moortel: ... >> Some people just like to chat, although they have nothing to give. ... Prev by Date: ...
    (sci.physics.relativity)
  • Re: complex numbers
    ... "Dirk Van de moortel" ... >> exact phrase: square root ... because many mistakes are made by doing so: ... Two roots, both -1. ...
    (sci.physics.relativity)
Quantcast