diff options
Diffstat (limited to 'gsl-1.9/poly/TODO')
-rw-r--r-- | gsl-1.9/poly/TODO | 130 |
1 files changed, 130 insertions, 0 deletions
diff --git a/gsl-1.9/poly/TODO b/gsl-1.9/poly/TODO new file mode 100644 index 0000000..dbbc4c7 --- /dev/null +++ b/gsl-1.9/poly/TODO @@ -0,0 +1,130 @@ +* Estimate error on general poly roots using Newton method? Allow for +multiple roots and higher derivatives + +* Newton-Maehly (Newton with implicit deflation) + +* Jenkins-Traub + +* Brian Smith's adaptation of Laguerre's method + +* Hirano's method, SIAM J Num Anal 19 (1982) 793-99 by Murota + +* Carstensen, Petkovic, "On iteration methods without derivatives for +the simultaneous determination of polynomial zeros", J. Comput. Appl. +Math., 45 (1993) 251-267 + +* Investigate this, + + > NA Digest Sunday, July 11, 1999 Volume 99 : Issue 28 + > + > From: Murakami Hiroshi <nadigest@tmca.ac.jp> + > Date: Sun, 11 Jul 1999 18:56:54 +0900 (JST) + > Subject: Code for Wilf's Complex Bisection Method + > + > A sample demo source of root finding method for the general complex + > coefficient polynomial is placed to URL <ftp://ftp.tmca.ac.jp/wilf.taz>. + > It is about 8KB in size and is a tar and gnu-zipped file. + > The algorithm is taken from the following reference: + > HERBERT S.WILF,"A Global Bisection Algorithm for Computing the Zeros + > of Polynomials in the Complex Plane",ACM.vol.25,No.3,July 1978,pp.415-420. + > + > The Wilf's method is the complex plane version of the Sturm bi-section + > method for the real polynomial. And theoretically very interesting. + > For the given complex interval (complex rectilinear region and sides are + > parallel to the x-y axis), the procedure gives the count of the complex + > roots of the polynomial inside the interval. Thus, successive bi-section + > or quad-section of the interval can give the sequence of the shrinking + > intervals containing the root inside to attain the required accuracies. + > The source code is written mostly Fortran77 language, however some + > violations are intensionally left as: 1: The DO-ENDDO loop structure. + > 2: The longer than 6 letter names. 3: The use of under-score letter. + > 4: The use of include statement. + > The code will be placed in the public domain. + > + +* Investigate this + +From: "Steven G. Johnson" <stevenj@alum.mit.edu> +To: help-gsl@gnu.org +Subject: [Help-gsl] (in)accuracy of gsl_poly_complex_solve for repeated + roots? +Date: Sun, 05 Jun 2005 16:25:40 -0400 +Precedence: list +Envelope-to: bjg@network-theory.co.uk + +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 + + + +_______________________________________________ +Help-gsl mailing list +Help-gsl@gnu.org +http://lists.gnu.org/mailman/listinfo/help-gsl |