Numerical root finding methods use iteration, producing a sequence of numbers that hopefully converge towards a limits which is a root. This post only focuses four basic algorithms on root finding, and covers bisection method, fixed point method, Newton-Raphson method, and secant method.
The simplest root finding algorithms is the bisection method. It works when f
is a continuous function and it requires previous knowledge of two initial gueeses, u
and v
, such that f(u)
and f(v)
have opposite signs. This method is reliable, but converges slowly. For detail, see https://guangchuangyu.github.io/cn/2008/11/bisect-to-solve-equation/ .
Root finding can be reduced to the problem of finding fixed points of the function g(x) = c*f(x) +x
, where c
is a non-zero constant. It is clearly that f(a) = 0
if and only if g(a) = a
. This is the so called fixed point algorithm.