Editing Root-finding algorithm (section)

{{Short description|Algorithms for zeros of functions}}
In [[numerical analysis]], a '''root-finding algorithm''' is an [[algorithm]] for finding [[Zero of a function|zeros]], also called "roots", of [[continuous function]]s. A [[zero of a function]] {{math|''f''}} is a number {{math|''x''}} such that {{math|1=''f''(''x'') = 0}}. As, generally, the zeros of a function cannot be computed exactly nor expressed in [[closed form expression|closed form]], root-finding algorithms provide approximations to zeros. For functions from the [[real number]]s to real numbers or from the [[complex number]]s to the complex numbers, these are expressed either as [[floating-point arithmetic|floating-point]] numbers without error bounds or as floating-point values together with error bounds. The latter, approximations with error bounds, are equivalent to small isolating [[interval (mathematics)|intervals]] for real roots or [[disk (mathematics)|disks]] for complex roots.<ref>{{Cite book |last1=Press |first1=W. H. |title=Numerical Recipes: The Art of Scientific Computing |last2=Teukolsky |first2=S. A. |last3=Vetterling |first3=W. T. |last4=Flannery |first4=B. P. |publisher=Cambridge University Press |year=2007 |isbn=978-0-521-88068-8 |edition=3rd |publication-place=New York |chapter=Chapter 9. Root Finding and Nonlinear Sets of Equations |chapter-url=http://apps.nrbook.com/empanel/index.html#pg=442}}</ref>

[[Equation solving|Solving an equation]] {{math|1=''f''(''x'') = ''g''(''x'')}} is the same as finding the roots of the function {{math|1=''h''(''x'') = ''f''(''x'') – ''g''(''x'')}}. Thus root-finding algorithms can be used to solve any [[equation (mathematics)|equation]] of continuous functions. However, most root-finding algorithms do not guarantee that they will find all roots of a function, and if such an algorithm does not find any root, that does not necessarily mean that no root exists.

Most numerical root-finding methods are [[Iterative method|iterative methods]], producing a [[sequence]] of numbers that ideally converges towards a root as a [[Limit of a sequence|limit]]. They require one or more ''initial guesses'' of the root as starting values, then each iteration of the algorithm produces a successively more accurate approximation to the root. Since the iteration must be stopped at some point, these methods produce an approximation to the root, not an exact solution. Many methods compute subsequent values by evaluating an auxiliary function on the preceding values. The limit is thus a [[Fixed point (mathematics)|fixed point]] of the auxiliary function, which is chosen for having the roots of the original equation as fixed points and for converging rapidly to these fixed points.

The behavior of general root-finding algorithms is studied in [[numerical analysis]]. However, for polynomials specifically, the study of root-finding algorithms belongs to [[computer algebra]], since algebraic properties of polynomials are fundamental for the most efficient algorithms. The efficiency and applicability of an algorithm may depend sensitively on the characteristics of the given functions. For example, many algorithms use the [[derivative]] of the input function, while others work on every [[continuous function]]. In general, numerical algorithms are not guaranteed to find all the roots of a function, so failing to find a root does not prove that there is no root. However, for [[polynomial]]s, there are specific algorithms that use algebraic properties for certifying that no root is missed and for locating the roots in separate intervals (or disks for complex roots) that are small enough to ensure the convergence of numerical methods (typically [[Newton's method]]) to the unique root within each interval (or disk).