3 ms·
Finding exact roots of high-order (>4) polynomials isn't just difficult; it's provably impossible[1]. http://en.wikipedia.org/wiki/Abel-Ruffini_theorem http://
by lmkg 17y ago
Finding exact roots of high-order (>4) polynomials isn't just difficult; it's provably impossible[1].
http://en.wikipedia.org/wiki/Abel-Ruffini_theorem http://en.wikipedia.org/wiki/Abel-Ruffini_theorem
Nonetheless, the iterative approximation algorithms are incredibly efficient and numerically stable. There's one really clever trick that actually uses floating-point imprecision to do something you couldn't do in exact arithmetic (inverting a degenerate matrix), that converges to within machine-epsilon in about three iterations.
[1] In the general case; special cases may be tractable, e.g. x^n-1=0.
- jules 17y agoI don't get why the Abel-Ruffini theorem is relevant here. Plotting sqrt(2) on the picture is impossible too. An n-th root is just shorthand for the root of the polynomial X^n - a. Introducing a shorthand doesn't change your ability to plot it on a picture.
- teeja 17y agoAs I read it, the WP article very nicely points out that exact roots are possible" "The theorem says that not all higher-degree equations have solutions which can be expressed by performing a finite number of operations... Some polynomials of arbitrary degree are indeed solvable with a finite number of such operations."
- btilly 17y agoImpossibility depends on your set of techniques. The Abel-Ruffini theorem only applies if you are trying to solve them in terms of radicals. However exact solutions to any degree polynomial are known in terms of multivariate hypergeometric functions, and also there is another solution in terms of Siegel theta functions.