Re: [Maxima-discuss] allroots precision

 Re: [Maxima-discuss] allroots precision From: Henry Baker - 2014-07-07 23:10:48 There are elegant (but not fast) exact polynomial root-location methods. The first step is to eliminate exact repeated roots using gcd(p(x),p'(x)). Then utilize exact methods to determine the exact number of roots within a rectangle in the complex plane with complex rational boundaris (i.e., in Q(i)). Once you have isolated a root within a rational box, you can either do a binary search and/or Newton methods to find it to much higher precision. Once you get close enough, Newton will quickly converge, but you need to get pretty close, and that might take an agonizingly long time if there are a lot of nearby roots. Also, Knuth describes an elegant method for extracting the continued fraction expansion of a polynomial root directly from the polynomial. Continued fractions don't converge as fast as Newton, but this is an interesting method, in any case. At 03:56 PM 7/7/2014, Î£ÏÎ±á¿¦ÏÎ¿Ï ÎÎ±ÎºÏÎ¬ÎºÎ·Ï wrote: >Understood that this is not a solved problem. However, it would be useful to give users who aren't familiar with Jenkins-Traub some guidance. > >I was also surprised that sols:allroots(eq:x^243+23*x-24) gives a warning: >allroots: unexpected error; treat results with caution. >allroots: only 65 out of 243 roots found. > >and the first element of the result list is a reduced polynomial. > >This behavior isn't warned against in the doc at all. > >I was somewhat less surprised that some values for subst(sol,eq) were pretty big -- that's the nature of the beast.... > > -s > >On Mon, Jul 7, 2014 at 6:04 PM, Richard Fateman wrote: >On 7/7/2014 12:54 PM, Raymond Toy wrote: >>>>>>> "Stavros" == Stavros Macrakis <(Î£ÏÎ±á¿¦ÏÎ¿Ï ÎÎ±ÎºÏÎ¬ÎºÎ·Ï)" > writes: >> Â Â Â Stavros> ? allroots and ? bfallroots (unlike ? realroots) say >> Â Â Â Stavros> nothing about the precision of the result, or how to >> Â Â Â Stavros> control it (except the unhelpful "allroots may give >> Â Â Â Stavros> inaccurate results in case of multiple roots"). It would >> Â Â Â Stavros> be helpful if someone knowledgeable about the algorithms >> Â Â Â Stavros> could add some information about precision to the docs. >> >> allroots (and bfallroots) use Jenkins-Traub to compute the >> roots. AFAIK, there are no guarantees on accuracy. I do know accuracy >> degrades for multiple roots (or near multiples). And since deflation >> is used, the accuracy of the later roots is worse than the earlier roots. > >This is a current research topic. (Not Jenkins-Traub, but rootfinding methods). >Given that you cannot necessarily evaluate a polynomial accurately, it can be >difficult Â to find its roots accurately. Â There are methods that find all roots at the >same time, perhaps more accurately and more slowly. > >> Having said that, I think the algorithm does produce a single root, r, >> of the polynomial, P, such that |P(r)| < eps where eps is >> approximately roundoff in computing the polynomial. >> >> Ray