Root

The roots of an equation

$$f(x)=0$$ (1)

are the values of $x$ for which the equation is satisfied. The Fundamental Theorem of Algebra states that every Polynomial equation of degree $n$ has exactly $n$ roots, where some roots may have a multiplicity greater than 1 (in which case they are said to be degenerate).

To find the $n$th roots of a Complex Number, solve the equation $z^n = w$. Then

$$z^n = \vert z\vert^n[\cos(n\theta)+i\sin(n\theta)] = \vert w\vert\,(\cos\phi+i\sin\phi),$$ (2)

so

$$\vert z\vert = \vert w\vert^{1/n}$$ (3)

and

$$\arg(z) = {\phi\over n}.$$ (4)

Rolle proved that any number has $n$ $n$th roots (Boyer 1968, p. 476). Householder (1970) gives an algorithm for constructing root-finding algorithms with an arbitrary order of convergence. Special root-finding techniques can often be applied when the function in question is a Polynomial.

See also Bailey's Method, Bisection Procedure, Brent's Method, Crout's Method, Descartes' Sign Rule, False Position Method, Fundamental Theorem of Symmetric Functions, Graeffe's Method, Halley's Irrational Formula, Halley's Method, Halley's Rational Formula, Horner's Method, Householder's Method, Hutton's Method, Isograph, Jenkins-Traub Method, Laguerre's Method, Lambert's Method, Lehmer-Schur Method, Lin's Method, Maehly's Procedure, Muller's Method, Newton's Method, Polynomial, Ridders' Method, Root Dragging Theorem, Schröder's Method, Secant Method, Sturm Function, Sturm Theorem, Tangent Hyperbolas Method, Weierstraß Approximation Theorem

References

Arfken, G. ``Appendix 1: Real Zeros of a Function.'' Mathematical Methods for Physicists, 3rd ed. Orlando, FL: Academic Press, pp. 963-967, 1985.

Boyer, C. B. A History of Mathematics. New York: Wiley, 1968.

Householder, A. S. The Numerical Treatment of a Single Nonlinear Equation. New York: McGraw-Hill, 1970.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Roots of Polynomials.'' §9.5 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 362-372, 1992.