Finding the roots of polynomials is a long-standing problem that has been extensively studied throughout the history and substantially influenced the development of mathematics. It involves determining either a numerical approximation or a closed-form expression of the roots of a univariate polynomial, i.e., determining approximate or closed form solutions of x {\displaystyle x} in the equation
a 0 + a 1 x + a 2 x 2 + ⋯ + a n x n = 0 {\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}=0}
where a i {\displaystyle a_{i}} are either real or complex numbers. Efforts to understand and solve polynomial equations led to the development of important mathematical concepts, including irrational and complex numbers, as well as foundational structures in modern algebra such as fields, rings, and groups. Despite being historically important, finding the roots of higher degree polynomials no longer play a central role in mathematics and computational mathematics, with one major exception in computer algebra.
Overview
Closed-form formulas Closed-form formulas for polynomial roots exist only when the degree of the polynomial is less than 5. The quadratic formula has been known since antiquity, and the cubic and quartic formulas were discovered in full generality during the 16th century. When the degree of polynomial is at least 5, a closed-form expression for the roots by the polynomial coefficients does not exist in general, if we only use additions, subtractions, multiplications, divisions, and radicals (taking n-th roots) in the formula. This is due to the Abel-Ruffini theorem. On the other hand, the fundamental theorem of algebra shows that all nonconstant polynomials have at least one root. Therefore, root-finding algorithms consists of finding numerical solutions in most cases.
Numerical algorithms Root-finding algorithms can be broadly categorized according to the goal of the computation. Some methods aim to find a single root, while others are designed to find all complex roots at once. In certain cases, the objective may be to find roots within a specific region of the complex plane. It is often desirable and even necessary to select algorithms specific to the computational task due to efficiency and accuracy reasons. See Root Finding Methods for a summary of the existing methods available in each case.
History
Closed-form formulas The root-finding problem of polynomials was first recognized by the Sumerians and then the Babylonians. Since then, the search for closed-form formulas for polynomial equations lasted for thousands of years.
The quadratics The Babylonians and Egyptians were able to solve specific quadratic equations in the second millennium BCE, and their solutions essentially correspond to the quadratic formula. However, it took 2 millennia of effort to state the quadratic formula in an explicit form similar to the modern formulation, provided by Indian Mathematician Brahmagupta in his book Brāhmasphuṭasiddhānta 625 CE. The full recognition of the quadratic formula requires the introduction of complex numbers, which took another a millennium.
The cubics and the quartics The first breakthrough in a closed-form formula of polynomials with degree higher than two took place in Italy. In the early 16th century, the Italian mathematician Scipione del Ferro found a closed-form formula for cubic equations of the form x 3 + m x = n {\displaystyle x^{3}+mx=n} , where m , n {\displaystyle m,n} are nonnegative numbers. Later, Niccolò Tartaglia also discovered methods to solve such cubic equations, and Gerolamo Cardano summarized and published their work in his book Ars Magna in 1545. Meanwhile, Cardano's student Lodovico Ferrari discovered the closed-form formula of the quartic equations in 1540. His solution is based on the closed-form formula of the cubic equations, thus had to wait until the cubic formula to be published. In Ars Magna, Cardano noticed that Tartaglia's method sometimes involves extracting the square root of a negative number. In fact, this could happen even if the roots are real themselves. Later, the Italian mathematician Rafael Bombelli investigated further into these mathematical objects by giving an explicit arithmetic rules in his book Algebra published in 1569. These mathematical objects are now known as the complex numbers, which are foundational in mathematics, physics, and engineering.
… excerpt ends here. Continue reading the full article.
