General Root Computation (Root Computation)

Description

Given a real continuous function, compute one of the roots.

Related Problems

Related: Root Computation with continuous first derivative

Parameters

$\epsilon$: (additive) tolerance error

$a, b$: endpoint values, with $b>a$

$n_{max}$: maximum number of iterations

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Bisection method	1820	$O(n_{max})$	$O({1})$	epsilon, additive	Deterministic
False position method	1690	$O(n_{max})$	$O({1})$	epsilon, additive	Deterministic
Secant method	1940	$O(n_{max})$	$O({1})$	epsilon, additive	Deterministic
Ridder's method	1979	$O(n_{max})$	$O({1})$	epsilon, additive	Deterministic	Time
Muller's method	1956	$O(n_{max})$	$O({1})$	epsilon, additive	Deterministic	Time
Illinois Algorithm	1971	$O(n_max)$	$O({1})$	epsilon, additive	Deterministic	Time
Anderson–Björck algorithm	1973	$O(n_max)$	$O({1})$	epsilon, additive	Deterministic	Time
ITP Method	1940?	$O(n_0+log((b-a)$/epsilon))	$O({1})$	epsilon, additive	Deterministic
Steffensen's method	1940(?)	$O(n_max)$	$O({1})$	epsilon, additive	Deterministic
Inverse quadratic interpolation	1940(?)	$O(n_max)$	$O({1})$	epsilon, additive	Deterministic
Brent-Dekker Method	1973	$O(n_max)$	$O({1})$	epsilon, additive	Deterministic	Time