3

My question is motivated by curiosity about the optimization of high-degree polynomial functions.

Let's say your experiment data are modeled by a non-trivial 15th degree polynomial. Taking the derivative of that function would leave you with a 14th degree polynomial. As far as I know, there is simply no way to "manually" find the roots (and therefore critical points) of such a polynomial (please correct me if this is wrong).

However, it seems (Computing roots of high degree polynomial numerically.) that certain programming languages (MATLAB, Mathematica, etc...) have a pretty easy time finding roots of polynomials of much higher degree (up to degree 2000 in less than a minute, apparently).

How do they find those roots, and are they exact values or approximations?

Community
  • 1
jeremy radcliff
  • 4,805
  • 2
    What do you mean by "exact values or approximations"? Computers don't usually output exact values (and the most meaningful way to refer to many number is "the root of this polynomial in this interval"). – Milo Brandt Jan 14 '16 at 22:25
  • 1
    I think he means symbolic computation. – Integral Jan 14 '16 at 22:28
  • 1
    Since there is no closed form solution for determining the roots of polynomials of degree 5 or higher, MATLAB and other programs will give only approximations of the roots of a polynomial unless it fits into special classes where the roots are known (e.g. $z^5-1 = 0.$). Read about Abel's Impossibility Theorem at http://mathworld.wolfram.com/AbelsImpossibilityTheorem.html for reference. – Joel Jan 14 '16 at 22:46
  • 1
    How does Matlab do it numerically (i.e., approximately)? Look at the code: edit roots. – horchler Jan 14 '16 at 23:25
  • @Joel: nonetheless, computation in the field of algebraic real numbers is decidable. Abel's result says that you can't give a closed solution for polynomials of degree greater than 5 using radicals, but that doesn't mean you can't give precise computable descriptions of roots. Google for "root isolation" to learn more. (Or see http://mathoverflow.net/questions/116069/exact-arithmetic-for-real-algebraic-numbers.) – Rob Arthan Jan 14 '16 at 23:28

1 Answers1

4

There's a whole class dedicated to this called Numerical Analysis. Methods like Newton's Method for finding roots are extremely efficient, but this is provided you have the derivative of the function. There are other methods like the Bisection Method where you take an interval and cut the interval in half continuously until you reach the max number of calculations you're willing to do. Bisection is probably the most simple that doesn't fail provided the curve actually does cross in the given interval.

Also, computer algebra systems will give exact results assuming the input is something the terminal knows how to handle. Otherwise, the computer will give approximations in decimal form.

Decaf-Math
  • 4,522
  • 1
    Or the computer might do exact symbolic computations with algebraic reals. See http://mathoverflow.net/questions/116069/exact-arithmetic-for-real-algebraic-numbers – Rob Arthan Jan 14 '16 at 23:30
  • 1
    I am old enough to have studied from FMM. Are the details not taught anymore? Is it all plug-and-chug into MATLAB or R with no understanding of how the algorithms work? (Insert obligatory "you kids get off of my lawn!") – shoover Jan 15 '16 at 01:17
  • The numerical methods class I took was very proofy. That's not to say any of us understood what it all meant, but the details are definitely still taught. – Decaf-Math Jan 15 '16 at 01:18
  • @pyrazolam Level of rigor probably also depends on the major, e.g. electrical engineering vs. applied math. – shoover Jan 15 '16 at 01:24