介绍

二分法（英语：Bisection method），是一种方程式根的近似值求法。

原理

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

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

演示

实现

JavaScript

/**
 *
 * @brief Find real roots of a function in a specified interval [a, b], where f(a)*f(b) < 0
 *
 * @details Given a function f(x) and an interval [a, b], where f(a) * f(b) < 0, find an approximation of the root
 * by calculating the middle m = (a + b) / 2, checking f(m) * f(a) and f(m) * f(b) and then by choosing the
 * negative product that means Bolzano's theorem is applied,, define the new interval with these points. Repeat until
 * we get the precision we want [Wikipedia](https://en.wikipedia.org/wiki/Bisection_method)
 *
 */

const findRoot = (a, b, func, numberOfIterations) => {
  // Check if a given  real value belongs to the function's domain
  const belongsToDomain = (x, f) => {
    const res = f(x)
    return !Number.isNaN(res)
  }
  if (!belongsToDomain(a, func) || !belongsToDomain(b, func)) throw Error("Given interval is not a valid subset of function's domain")

  // Bolzano theorem
  const hasRoot = (a, b, func) => {
    return func(a) * func(b) < 0
  }
  if (hasRoot(a, b, func) === false) { throw Error('Product f(a)*f(b) has to be negative so that Bolzano theorem is applied') }

  // Declare m
  const m = (a + b) / 2

  // Recursion terminal condition
  if (numberOfIterations === 0) { return m }

  // Find the products of f(m) and f(a), f(b)
  const fm = func(m)
  const prod1 = fm * func(a)
  const prod2 = fm * func(b)

  // Depending on the sign of the products above, decide which position will m fill (a's or b's)
  if (prod1 > 0 && prod2 < 0) return findRoot(m, b, func, --numberOfIterations)
  else if (prod1 < 0 && prod2 > 0) return findRoot(a, m, func, --numberOfIterations)
  else throw Error('Unexpected behavior')
}

参考

• Bisection method - Wikiwand (opens new window)
• 二分法 (数学) - Wikiwand (opens new window)