help-gsl
[Top][All Lists]

## [Help-gsl] (in)accuracy of gsl_poly_complex_solve for repeated roots?

 From: Steven G. Johnson Subject: [Help-gsl] (in)accuracy of gsl_poly_complex_solve for repeated roots? Date: Sun, 05 Jun 2005 16:25:40 -0400 User-agent: Mozilla Thunderbird 1.0 (Macintosh/20041206)

Hi, I noticed that gsl_poly_complex_solve seems to be surprisingly inaccurate. For example, if you ask it for the roots of 1 + 4x + 6x^2 + 4x^3 + x^4, which should have x = -1 as a four-fold root (note that the coefficients and solutions are exactly representable), it gives roots:
```
-0.999903+9.66605e-05i
-0.999903-9.66605e-05i
-1.0001+9.66834e-05i
-1.0001-9.66834e-05i

```
i.e. it is accurate to only 4 significant digits. (On the other hand, when I have 4 distinct real roots it seems to be accurate to machine precision.)
```
```
If this kind of catastrophic accuracy loss is intrinsic to the algorithm when repeated roots are encountered, please note it in the manual.
```
```
However, I suspect that there may be algorithms to obtain higher accuracy for multiple roots. I found the below references in a literature search on the topic, which you may want to look into. (The first reference can be found online at http://www.neiu.edu/~zzeng/multroot.htm)
```
Cordially,
Steven G. Johnson

---------------------------------------------------------------------
```
Algorithm 835: MULTROOT - a Matlab package for computing polynomial roots and multiplicities Zeng, Z. (Dept. of Math., Northeastern Illinois Univ., Chicago, IL, USA) Source: ACM Transactions on Mathematical Software, v 30, n 2, June 2004, p 218-36
```ISSN: 0098-3500 CODEN: ACMSCU
Publisher: ACM, USA

```
Abstract: MULTROOT is a collection of Matlab modules for accurate computation of polynomial roots, especially roots with nontrivial multiplicities. As a blackbox-type software, MULTROOT requires the polynomial coefficients as the only input, and outputs the computed roots, multiplicities, backward error, estimated forward error, and the structure-preserving condition number. The most significant features of MULTROOT are the multiplicity identification capability and high accuracy on multiple roots without using multiprecision arithmetic, even if the polynomial coefficients are inexact. A comprehensive test suite of polynomials that are collected from the literature is included for numerical experiments and performance comparison (21 refs.)
```
---------------------------------------------------------------------
Ten methods to bound multiple roots of polynomials
```
Rump, S.M. (Inst. fur Informatik III, Tech. Univ. Hamburg-Harburg, Hamburg, Germany) Source: Journal of Computational and Applied Mathematics, v 156, n 2, 15 July 2003, p 403-32
```ISSN: 0377-0427 CODEN: JCAMDI
Publisher: Elsevier, Netherlands

```
Abstract: Given a univariate polynomial P with a k-fold multiple root or a k-fold root cluster near some z, we discuss nine different methods to compute a disc near z which either contains exactly or contains at least k roots of P. Many of the presented methods are known and of those some are new. We are especially interested in the behavior of methods when implemented in a rigorous way, that is, when taking into account all possible effects of rounding errors. In other words, every result shall be mathematically correct. We display extensive test sets comparing the methods under different circumstances. Based on the results, we present a tenth, hybrid method combining five of the previous methods which, for give z, (i) detects the number k of roots near z and (ii) computes an including disc with in most cases a radius of the order of the numerical sensitivity of the root cluster. Therefore, the resulting discs are numerically nearly optimal
```

```