Root finding

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.

Continue reading

翻看了以前写的使用Newton-Raphson Method求一个数的开方,想到其实也可以用中值定理来实现。 中值定理:f(x)是一个连续性的函数,在[u,v]区间内,当c的值位于f(u)和f(v)之间时,至少存在一个点,满足f(x) = c 当f(u)和f(v)一正一负时,那么在[u,v]之间至少有一个根的存在,这个定理本来就是拿来证明根的存在的,但是其实也可以用来求解根。

Continue reading

Author's picture

Guangchuang Yu

Bioinformatics Professor @ SMU

Bioinformatics Professor

Guangzhou