Finding polynomial roots is a long-standing problem that has been the object of much research throughout history. A testament to this is that up until the 19th century, algebra meant essentially theory of polynomial equations.
Principles
Finding the root of a linear polynomial (degree one) is easy and needs only one division: the general equation has solution For quadratic polynomials (degree two), the quadratic formula produces a solution, but its numerical evaluation may require some care for ensuring numerical stability. For degrees three and four, there are closed-form solutions in terms of radicals, which are generally not convenient for numerical evaluation, as being too complicated and involving the computation of several th roots whose computation is not easier than the direct computation of the roots of the polynomial (for example the expression of the real roots of a cubic polynomial may involve non-real cube roots). For polynomials of degree five or higher Abel–Ruffini theorem asserts that there is, in general, no radical expression of the roots.
So, except for very low degrees, root finding of polynomials consists of finding approximations of the roots. By the fundamental theorem of algebra, a polynomial of degree has exactly real or complex roots counting multiplicities.
It follows that the problem of root finding for polynomials may be split in three different subproblems; Finding one root Finding all roots Finding roots in a specific region of the complex plane, typically the real roots or the real roots in a given interval (for example, when roots represents a physical quantity, only the real positive ones are interesting).
For finding one root, Newton's method and other general iterative methods work generally well.
For finding all the roots, arguably the most reliable method is the Francis QR algorithm computing the eigenvalues of the Companion matrix corresponding to the polynomial, implemented as the standard method in MATLAB.
The oldest method of finding all roots is to start by finding a single root. When a root has been found, it can be removed from the polynomial by dividing out the binomial . The resulting polynomial contains the remaining roots, which can be found by iterating on this process. However, except for low degrees, this does not work well because of the numerical instability: Wilkinson's polynomial shows that a very small modification of one coefficient may change dramatically not only the value of the roots, but also their nature (real or complex). Also, even with a good approximation, when one evaluates a polynomial at an approximate root, one may get a result that is far to be close to zero. For example, if a polynomial of degree 20 (the degree of Wilkinson's polynomial) has a root close to 10, the derivative of the polynomial at the root may be of the order of this implies that an error of on the value of the root may produce a value of the polynomial at the approximate root that is of the order of
For avoiding these problems, methods have been elaborated, which compute all roots simultaneously, to any desired accuracy. Presently the most efficient method is Aberth method. A free implementation is available under the name of MPSolve. This is a reference implementation, which can find routinely the roots of polynomials of degree larger than 1,000, with more than 1,000 significant decimal digits.
The methods for computing all roots may be used for computing real roots. However, it may be difficult to decide whether a root with a small imaginary part is real or not. Moreover, as the number of the real roots is, on the average, the logarithm of the degree, it is a waste of computer resources to compute the non-real roots when one is interested in real roots.
The oldest method for computing the number of real roots, and the number of roots in an interval results from Sturm's theorem, but the methods based on Descartes' rule of signs and its extensions—Budan's and Vincent's theorems—are generally more efficient. For root finding, all proceed by reducing the size of the intervals in which roots are searched until getting intervals containing zero or one root. Then the intervals containing one root may be further reduced for getting a quadratic convergence of Newton's method to the isolated roots. The main computer algebra systems (Maple, Mathematica, SageMath, PARI/GP) have each a variant of this method as the default algorithm for the real roots of a polynomial.