Re: Are there multiple roots?


"Zeke Zeng" <zzeng@xxxxxxxx> wrote in message
news:Mfidnb8pfK5g43HZnZ2dnUVZ_rKdnZ2d@xxxxxxxxxxxxxx

"Jeremy Watts" <jwatts1970@xxxxxxxxxxx> wrote in message
news:hEUGg.13248$w3.5669@xxxxxxxxxxxxxxxxxxxxxxx

"Zeke Zeng" <zzeng@xxxxxxxx> wrote in message
news:qJ6dnYNfc6fieHbZnZ2dnUVZ_uudnZ2d@xxxxxxxxxxxxxx

As you wrote, the accuracy of the roots computed by Matlab "roots" is a
suspect. My question is: are there multiple roots in your polynomial?
Or
is
your polynomial near a polynomial with multiple roots. If so, the
standard
methods will not find those roots accurately. But you can try MultRoot
package that is designed to catch multiple roots even if the
coefficients
contain noice. You can get it from my website:

http://www.neiu.edu/~zzeng

I'd appreciate your feedback.

Does your package work using the 'companion matrix' method? This will
solve
polynomials of any degree whether they contain repeat roots or not.

In response to the OPs original post I'd say to use the 'companion
matrix'
method alongside the use of Arbitrary Precision Arithmetic (as the OP
said
the time of execution is not important). Java for instance has an APA
feature called 'BigDecimal'



My method is to compute multiple roots WITHOUT extending machine precision
even if the coefficients contain errors.

If the polynomial is "exact", namely no noice in coefficients, then
companion matrix method combined with extended machine precision will
work.
The "attainable accuracy " is the machine precision divided by
multiplicity
in terms of numbers of digits. For example, a root of multiplicity 20 can
get 5 correct digits using 100-digit arithmetic.

If the polynomial is "inexact", then extending machine precision will do
no
good. The attainable accuracy is the accuracy of coefficient divided by
the
multiplicity.

My method is a different approach consists of two stages: compute
multiplicity structure first, and then solve a least squares problem using
the multiplicity constraint. See my paper

"Computing multiple roots of inexact polynomials", Mathematics of
Computation, 74(2005), pp869-903

Example: For polynomial

p(x) = (x-1)^20 * (x-2)^15 * (x-3)^10 * (x-4)^5

expanded with coefficients rounded to machine precision (i.e. inexact). My
method will output the multiplicity structure along with roots for at
least
14 correct digits using machine precision. The companion matrix method
will
not get anywhere close to the roots.

i respect your kung fu... :)





.

Relevant Pages

  • Re: Maxima - precision
    ... You are computing the roots of a polynomial in machine precision. ... But maybe your polynomials are not nasty. ...
    (sci.math.symbolic)
  • Re: Maxima - precision
    ... You are computing the roots of a polynomial in machine precision. ... But maybe your polynomials are not nasty. ...
    (sci.math.symbolic)
  • Re: Are there multiple roots?
    ... the accuracy of the roots computed by Matlab "roots" is a ... are there multiple roots in your polynomial? ... of the roots of the polynomials. ... order 60 with complex coefficients. ...
    (sci.math.num-analysis)
  • Are there multiple roots?
    ... the accuracy of the roots computed by Matlab "roots" is a ... are there multiple roots in your polynomial? ... of the roots of the polynomials. ... order 60 with complex coefficients. ...
    (sci.math.num-analysis)
  • Re: Are there multiple roots?
    ... the accuracy of the roots computed by Matlab "roots" is a ... are there multiple roots in your polynomial? ... polynomials of any degree whether they contain repeat roots or not. ... order 60 with complex coefficients. ...
    (sci.math.num-analysis)
Loading