二分法 (数学)

Bisection method.png

二分法(英语:Bisection method),是一种方程式的近似值求法。

算法

若要求已知函数 f(x) = 0 的根 (x 的解),则:

  1. 先找出一个区间 [a, b],使得f(a)与f(b)异号。根据介值定理,这个区间内一定包含着方程式的根。
  2. 求该区间的中点 ,并找出 f(m) 的值。
  3. f(m) 与 f(a) 正负号相同则取 [m, b] 为新的区间, 否则取 [a, m].
  4. 重复第2和第3步至理想精确度为止。

例子

例: 求方程   的解, 其中 sinh 是双曲正弦、cos 是余弦x弧度量度.

  1. 定义 f(x) =  。因此这里是要求 f(x) = 0 的根。
  2. 画出 y = f(x) 可大约得知其根约在 0.5 和 1 之间,故使初始区间的 [0.5, 1]。
  3. 此区间之中点为 0.75。
  4. f(0.5) ≈ -0.3565, f(0.75) ≈ 0.0906,其正负号不同,故令新区间为 [0.5, 0.75]
  5. 又新区间的中点为 0.625, 而 f(0.625) ≈ -0.1445, 与 f(0.5) 正负号相同,故新区间为 [0.625, 0.75]。
  6. 不断重复运算即得 f(x) = 0 的根约为 0.7033。

伪代码

輸入 f(x) 的定義
輸入 a 和 b 為初始區間
輸入 e 為目標誤差
REPEAT:
  m:= (a + b) / 2
  IF f(m) * f(a) < 0 THEN
    b := m
  ELSE
    a := m
UNTIL (b-a) / 2 < e

参考文献

外部链接

参见