Interpolation[edit]
Many root-finding processes work by interpolation. This consists in using the last computed approximate values of the root for approximating the function by a polynomial of low degree, which takes the same values at these approximate roots. Then the root of the polynomial is computed and used as a new approximate value of the root of the function, and the process is iterated.
Two values allow interpolating a function by a polynomial of degree one (that is approximating the graph of the function by a line). This is the basis of the secant method. Three values define a quadratic function, which approximates the graph of the function by a parabola. This is Muller's method.
Regula falsi is also an interpolation method, which differs from the secant method by using, for interpolating by a line, two points that are not necessarily the last two computed points.
Combinations of methods[edit]
Brent's method[edit]
Brent's method is a combination of the bisection method, the secant method and inverse quadratic interpolation. At every iteration, Brent's method decides which method out of these three is likely to do best, and proceeds by doing a step according to that method. This gives a robust and fast method, which therefore enjoys considerable popularity.
Ridders' method[edit]
Ridders' method is a hybrid method that uses the value of function at the midpoint of the interval to perform an exponential interpolation to the root. This gives a fast convergence with a guaranteed convergence of at most twice the number of iterations as the bisection method.
Finding roots in higher dimensions[edit]
The bisection method has been generalized to higher dimensions; these methods are called generalized bisection methods.[2][3] At each iteration, the domain is partitioned into two parts, and the algorithm decides - based on a small number of function evaluations - which of these two parts must contain a root. In one dimension, the criterion for decision is that the function has opposite signs. The main challenge in extending the method to multiple dimensions is to find a criterion that can be computed easily, and guarantees the existence of a root.
The Poincaré–Miranda theorem gives a criterion for the existence of a root in a rectangle, but it is hard to verify, since it requires to evaluate the function on the entire boundary of the rectangle.
Another criterion is given by a theorem of Kronecker.[4] It says that, if the topological degree of a function f on a rectangle is non-zero, then the rectangle must contain at least one root of f. This criterion is the basis for several root-finding methods, such as by Stenger[5] and Kearfott.[6] However, computing the topological degree can be time-consuming.
A third criterion is based on a characteristic polyhedron. This criterion is used by a method called Characteristic Bisection.[2]: 19-- It does not require to compute the topological degree - it only requires to compute the signs of function values. The number of required evaluations is at least , where D is the length of the longest edge of the characteristic polyhedron.[7]: 11, Lemma.4.7 Note that [7] prove a lower bound on the number of evaluations, and not an upper bound.
A fourth method uses an intermediate-value theorem on simplices.[8] Again, no upper bound on the number of queries is given.
