Root Computation (Root Computation)

From Algorithm Wiki
Jump to navigation Jump to search

Description

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

Parameters

No parameters found.

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
Newton's method 1940 $O(n_{max})$ $O({1})$ epsilon, additive Deterministic
Halley's method 1940 $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
Householder's Method 1940(?) $O(d*n_max)$? $O(d)$ 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