Polynomial inverse

I have a polynomial of the fifth order:

y = ax⁵ + bx⁴ + cx³ + dx² + ex + f

The coefficients a-f are known and I need to calculate x for a given y. I could probably use the Newton-Raphson algorithm or similar, but would prefer a non-iterative solution if possible.

Edit: I guess I didn't think this through enough before posting my question. My polynomial coefficients have been calculated from sampled data and in thi开发者_运维百科s special case there is only one root. It didn't pass my mind that there, of course, might be five different roots in the general case. I think I will fit the sampled data to an inverse polynomial as well, and use that to calculate x from y.

Finding roots of polynomials is difficult and tricky. Getting a stable robust algorithm will get you headache. Newton + root removal seems a great idea, but making this work correctly is really painful.

One obvious problem is the stability of the root removal. One other problem is complex roots. One more difficult problem is (numerically) multiple roots, where you lose a lot of precision.

The state-of-art black box algorithm is Jenkins-Traub. However, it is difficult to implement so you will have to find (or pay for) an implementation somewhere.

Nevertheless, if you have access to a linear alebra package, a simple, robust, stable, and efficient way is to compute the eigenvalues of the companion matrix. This is what eg. GSL does.

J Trana's sort of answered this already, but the answer is that you can't in general find an algorithm for this (this is the mathematical result that made Galois famous).

Also, if this is anything other than a homework problem, you probably don't want an algorithm to solve the thing in radicals anyway, since this will be numerically badly behaved.

Newton-Raphson will only get you one solution. There could be up to 5 of them for a quintic.

If you want all the solutions you either need to pair Newton-Raphson with root-removal or use something a little more robust.

One common method is using Sturm polynomials