Anomaly relating to certain polynomials.

[Guv]

A while ago I wrote a VB program to find the roots of polynomials. It easily found all the roots for polynomials of order 20-40, and I think might handle order 100 and beyond.

Recently I discovered a polynomial for which it determined one of the roots to about 15 digits of precision (the practical limit for a PC). When evaluated for that root, the result was over 100,000 instead of being a close approximation to zero.

At first I thought there was a bug in the program. After doing a lot of analysis and testing of the code, I realized that the anomaly was due to numerical calculation problems. The following special polynomial is an example which might cause this anomaly.

• x⁵⁰ - 10⁵¹ = 0
  
  The derivative of P(x) = x⁵⁰ - 10⁵¹ is 50*x⁴⁹
  
  This polynomial has a root at approximately 10.47
  
  Near that root the derivative is incredibly large, indicating an almost vertical slope near the root.
  
  The error when you evaluate the polynomial could be 50*x⁴⁹ times the error in the calculation of the root. An error in the root of 10^-20 could result in an error greater than 10²⁵

the precision of the polynomial evaluation is not predictable, but can be many orders of magnitude greater than the error in the precision of the root for high order polynomials.

[kedaman]

You could always manually calculate the digits in a string.

[krtxmrtz]

You could always manually calculate the digits in a string.

To evaluate such large numbers maybe you can try something on these lines:

x⁵⁰ = 10^{50 log x}

Also, to avoid directly solving the equation involving the large numbers, you can divide it. Solving

x⁵⁰ - 10⁵¹ = 0

is equivalent to solving:

(x/10)⁵⁰ - 10 = 0

or

0.1 * (x/10)⁵⁰ - 1 = 0

[Guv]

You folks seem to be misunderstanding the nature of this anomaly.

There is no problem finding a very precise approximation to the roots of these polynomials. I know that my VB program gives about 15 digit precision. I verify precision by comparing the sum and product of the roots with polynomial coefficients.

The problem is in evaluating the polynomial for certain roots. With a root accurate to 15 digits, the polynomial evaluation can be many orders of magnitude greater (or less) than zero. The following approximates the error in evaluating the polynomial at (root + Error).

• Polynomial(root + Error) = Polynomial(root) + Error * Derivative(root)

If the derivative near the root is larger than one, the error in evaluating the polynomial is larger than the error in the root approximation. If the derivative near the root is (for example) 10⁵⁰, the error in polynomial evaluation can be orders of magnitude from zero even if approximation to the root is precise to 15 or 20 digits.

[krtxmrtz]

The problem is in evaluating the polynomial for certain roots. With a root accurate to 15 digits, the polynomial evaluation can be many orders of magnitude greater (or less) than zero.

Yes, the root may be (is) pretty accurate yet the absolute value of the polynomial for the calculated root may still be very large.

I assume the problem is your (Newton?) algorithm quits if after so many loops x is lower than a very small value. Interesting challenge, I don't know if I'll be able to help but I'll think about it.