[R] Solving 100th order equation

[Robert A LaBudde]

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"