2.1 Bisection Algorithm
Bisection algorithmは1次元関数の根を求める簡単な方法である。 目標は、” \(f(x_0)=0)” となる根(x_0in)を見つけることである。 このアルゴリズムでは、まず \(x_0) が含まれることが分かっている大きな区間から始めて、根が括られる まで区間をどんどん狭めていきます。 このアルゴリズムの理論的な裏付けは中間値の定理で、連続関数(f)が区間(abs)の端点で値(f)を取るなら、(f)が区間(abs)のどこかで値(f)と値を取るはずである、というもので、abs(f)は(a)を取るなら(b)の間のすべての値となります。 つまり、if \(f(a) < \gamma < f(b)\), then there exist a \(cin) such that \(f(c)=gamma).
Using the bisection algorithm will present with these information, we’re putting the bisection algorithm. まず、(f(a))が(f(a))であることを確認します。 \ne \ne text{sign}(f(b))\). さもなければ、区間は根を含まないので、広げる必要があるかもしれない。
-
Let \(c = \frac{a + b}{2}).
-
If \(f(c) = 0}, stop and return ╱(c)╱.
-
If \(text{sign}(f(a))\netext{sign}(f(c))\), set \(b}leftarrow cʕ). Else if \(text{sign}(f(b))\netext{sign}(f(c))\), then set \(aleftarrow carette).
-
Goto the beginning and repeat until convergence (see below).このようにすると、収束するまで繰り返されます。
After \(n) iterations, the size of the bracketing the root will be \(2^{-n}(b-a)\).
bisection algorithm is useful, conceptually simple, and is easy to implement. 特に、関数 ⇄(f)について、区間内の様々な点で評価できること以外、特別な情報は必要ない。 欠点は1次元でしか使えないことと、収束が線形であることで、これから説明するアルゴリズムの中では最も遅い収束率です（詳しくは後述）。 Bisectionアルゴリズムの理想的な状況は次のようなものです。
Ideal setup for bisection algorithm.
ここで、 \(f(a)\) and \(f(b)\) are opposite signs and the root is clearly in between \(a) and \(b)Раадатью.
下のシナリオでは、”Derivative of \(f(a)>0) and \(f(b)>0)” なのでアルゴリズムは開始しません。
Derivative of \(f) at the root is \(0).
この次のシナリオの場合、根が2つあり、しかも \(a) と \(b) の間に、(f (a)>0) と \(f(b)>0) があることがわかります。
Two roots within the interval.
In the scenario below, the algorithm will start because \(f(a)\) and f(b)\ are opposite sign, but there is no root.下のシナリオでは、閾値の範囲内で、閾値があるはずの閾値がない場合、アルゴリズムが開始されます。
Interval contains an asymptote but no root.
Convergence of the bisection algorithm can be determined by having \(|b-a|<varepsilon ◇ for some small \(varepsilon ◇) or having \(|f(b)-f(a)|<varepsilon ◇).これは、ある特定の小サイズのIntelligenceアルゴリズムの収束を決定することができるもので、閾値を超えた場合、閾値を超えた時点で収束となります。） どちらの基準を使用するかは、特定のアプリケーションやどのような公差が必要かによります。 分位数
累積分布関数 \(F(x)\) と数値 \(pin (0, 1)\) があるとき、quantile of \(F) is a number \(x) such that \(F(x) = pờng). bisection algorithmは、関数 \(g(x) = F(x) – p)を定義して、 \(g(x) = 0\)を実現する \(x) の値を求めることで、与えられた \(p) に対する分位数 \(x) を見つけることができます。
別の表現をすると、CDFを反転して、 \(x = F^{-1}(p)\) を計算することです。 つまり、bisectionアルゴリズムはこのような状況でも関数の反転に使えるのです。