Re: [R] Solving 100th order equation

From: Robert A LaBudde <ral_at_lcfltd.com>
Date: Mon, 26 May 2008 03:29:26 -0400

At 03:03 AM 5/26/2008, Peter Dalgaard wrote:
>If you think about it, if you have x^100 in the expression, then
>when you get out to about x=2, you'll need 100 binary digits to
>store the value to integer precision, so anything working with
>standard finite precision arithmetic is going to go wrong because
>the measly "4000" in the equation is going to be completely swamped out.

Actually the precision needed is more than 100 decimal digits. Polynomial roots typically have poor conditioning, and the problem is similar to finding the eigenvalues of a 100x100 Hilbert matrix.

Also, everyone is assuming the polynomial of interest has only a few non-zero coefficients. If you look at the originating email, "....." was used to indicate terms from x^49 down to x^2, so we don't know what the coefficients were.

Finally, either this is an atrocious attempt to use brute force to solve a design problem, or it's a homework problem to illustrate a point. Either way, insufficient information has been supplied to make a sensible comment on how to solve the (unspecified) problem. In fact, the large quantity of responses is more indicative of the open-ended nature of the question than of any relevance to the original problem. We don't even know if complex roots are of interest. And we don't know if the actual problem even has integer coefficients.

All we can say is that finding all of the roots of a general 100-th degree polynomial with arbitrary coefficients is intractable with finite precision.

On the other hand, some problems, such as finding the largest or smallest absolute value root might easy to do. Another might be finding a single root inside a specified circle in the complex plane (use trapezoidal rule and the Cauchy residue theorem on the inverse polynomial). Etc.



Robert A. LaBudde, PhD, PAS, Dpl. ACAFS e-mail: ral_at_lcfltd.com
Least Cost Formulations, Ltd.            URL: http://lcfltd.com/
824 Timberlake Drive                     Tel: 757-467-0954
Virginia Beach, VA 23464-3239            Fax: 757-467-2947

"Vere scire est per causas scire"



R-help_at_r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. Received on Mon 26 May 2008 - 07:40:18 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Mon 26 May 2008 - 08:30:41 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.

list of date sections of archive