Root-finding algorithm: Difference between revisions

Revision as of 13:53, 16 May 2018

Revision as of 21:00, 5 June 2018

Line 1:

In [[mathematics]] and [[computing]], a '''root-finding algorithm''' is an [[algorithm]] for finding roots of [[continuous function]]s. A [[root of a function|root]] of a [[function (mathematics)|function]] {{math|''f''}}, from the [[real number]]s to real numbers or from the [[complex number]]s to the complex numbers, is a number {{math|''x''}} such that {{math|1=''f''(''x'') = 0}}. As, generally, the roots of a function cannot be computed exactly, nor expressed in [[closed form expression|closed form]], root-finding algorithms provide approximations to roots, expressed either as [[floating point]] numbers or as small isolating [[interval (mathematics)|intervals]], or [[disk (mathematics)|disks]] for complex roots (an interval or disk output being equivalent to an approximate output together with an error bound).

[[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 allow solving any [[equation (mathematics)|equation]] defined by continuous functions. However, most root-finding algorithms do not guarantee that they will find all the roots; in particular, if such an algorithm does not find a root, that does not mean that athe root does not exist.

Most numerical root-finding methods use [[iteration]], producing a [[sequence]] of numbers that hopefully converge towards the 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.