Roots | Research & Encyclopedia Articles

Roots

A root of a function f is a number x such that f(x) = 0. The fundamental theorem of algebra states that if f is a polynomial of degree n with complex number coefficients then it has at most n roots. The problem of finding the roots of f has a four thousand year history. The ancient Egyptians (2000 BC) knew how to find the roots of a degree 2 polynomial equation (or quadratic equation) using the quadratic formula. In the 1500s, Girolamo Cardano discovered how to find the roots of any degree 3 polynomial (or cubic equation). Degree 4 polynomials (quartic equations) were soon easy to solve as well. However, Abel proved in 1827 that there is no general formula that can solve a polynomial of degree 5 (quintic equations) or higher. His discovery, in part, led to the development of modern algebra and group theory. Because of Abel's discovery, mathematicians gave up the problem of finding the exact roots of a polynomial and, instead, focused their energy on finding approximate solutions to polynomials.

Isaac Newton used the following method that works for all differentiable functions (see differential calculus). Let x₀ be a number that is guessed to be close to a root of f. Let x₁ = F(x₀) where F(x) = x - f(x)/f'(x). Here, f' stands for the derivative of f. Let x₂ = F(x₁). In general, let x_n = F(x_n-1). Taylor's theorem implies that in a neighborhood of x₀, f(x) is approximately equal to f'(x₀)*(x - x₀) + f(x₀) which is zero when x = F(x₀). If x₀ is chosen close enough to a root, then the sequence of numbers {x_n} converges rapidly (quadratic to be precise) to a root of f. However, if x₀ is badly chosen, the sequence will not converge at all. Consequently, it is often necessary to use some other method for approximating the roots before applying Newton's method. Also, Newton's method requires computing f' which may be difficult for non-polynomial functions. For these functions, there are ways to approximate f'. The secant method uses the fact that f'(x_n) is approximately (f(x_n) - f(x_n-1))/(x_n -x_n-1).

In 20th century, many new methods were discovered for approximating the roots of polynomial equations. Most use the methods of numerical analysis. Some of them find one root at a time. These include the Jenkins-Traub method, Larkin's method and Muller's method. Methods that find all the roots simultaneously include Weyl's method, the Durand-Kerner method, and the divide-and-conquer algorithms. These last ones are well suited for parallel processing which gives them a speed advantage over the iterative methods.

Weyl's method goes like this: Find a square in the complex plane that contains all the zeros of f. Next divide the square into four smaller squares and determine which of these four squares contains zeros of f. If a square contains zeros of f, then divide it into four smaller squares and determine which of the smaller squares contains zeros of f. Continue this process until the desired degree of accuracy is achieved. This algorithm can easily be modified to find only the zeros of f within a specified area.