二等分法

反復処理をいつ停止すべきかを決定するには、許容値に関してさまざまな停止条件を考慮する必要があります (${\displaystyle \epsilon }$) BurdenとFaires（2016）は、3つの停止条件を特定しています。^{[ 7 ]}

• 絶対許容範囲：${\displaystyle |p_{N}-p_{N-1}|<\epsilon }$
• 相対許容度：${\displaystyle \left|{\frac {p_{N}-p_{N-1}}{p_{N}}}\right|<\epsilon ,}$||${\displaystyle p_{N}\neq 0}$
• ${\displaystyle |f(p_{N})|<\epsilon .}$

${\displaystyle |f(p_{N})|<\epsilon }$正確な結果が得られない${\displaystyle \epsilon }$ない限り${\displaystyle |f'(p_{N})|\geq 1}$他の2つの可能性は、異なる概念を表しています。絶対差${\displaystyle |c-a|\leq 5\times 10^{-t}}$cとaは同じであると言っています${\displaystyle t}$小数点以下の桁数と相対差${\displaystyle \left|{\frac {c-a}{c}}\right|\leq 5\times 10^{-t}}$cとaは同じであると言っています${\displaystyle t}$有効数字。^{[ 8 ]}根の値について何もわかっていない場合は、相対許容誤差が最適な停止条件です。^{[ 9 ]}

このメソッドへの入力は連続関数です。${\displaystyle f}$そして間隔${\displaystyle [a,b]}$関数値が${\displaystyle f(a)}$そして${\displaystyle f(b)}$ 符号が反対である（区間内に少なくとも1つのゼロ交差がある）。各反復では、以下の手順が実行されます。

1. 計算する${\displaystyle c}$区間の中点、${\displaystyle c={\frac {a+b}{2}}}$;
2. 中点における関数値を計算し、${\displaystyle f(c)}$;
3. もし${\displaystyle f(c)=0}$c を返します。
4. 収束が満足できる場合（つまり、${\displaystyle \left|c-a\right|\leq 5\times 10^{-t}|c|}$）、 戻る${\displaystyle c}$;
5. サインを調べます${\displaystyle f(c)}$どちらかを交換する${\displaystyle a}$または${\displaystyle b}$と${\displaystyle c}$これにより、新しい区間内にゼロ交差が生じる。

二分法を用いて多項式の根を求めると仮定する。

${\displaystyle f(x)=x^{3}-x-2\,.}$

まず、2つの数字${\displaystyle a}$そして${\displaystyle b}$見つけなければならない。${\displaystyle f(a)}$そして${\displaystyle f(b)}$反対の符号を持つ。上記の関数では、${\displaystyle a=1}$そして${\displaystyle b=2}$この基準を満たすため、

${\displaystyle f(1)=(1)^{3}-(1)-2=-2}$

そして

${\displaystyle f(2)=(2)^{3}-(2)-2=+4\,.}$

関数は連続であるため、区間[1, 2]内に根が存在するはずです。この区間で二分法を繰り返し適用すると、近似値の精度が徐々に向上します。

13回の反復の後、約1.521、つまり多項式の根に収束することが明らかになる。

これらの方法の中には、位相次数を計算することに基づくものがある。^{[ 12 ]}

特性二分法は、異なる点における関数の符号のみを使用します。ある整数d ≥ 2に対して、 fを R ^dからR ^dへの関数とします。fの特性多面体^{[ 13 ]} (許容多角形とも呼ばれる) ^{[ 14 ]}は、 R ^d内の2 ^d個の頂点を持つ多面体であり、各頂点vにおいて、 f ( v )の符号の組み合わせが一意です。たとえば、d = 2 の場合、 fの特性多面体は、頂点 (例えば) A、B、C、D を持つ四角形であり、次のようになります。

• 符号f (A) = ( − , − )、つまりf ₁ (A)<0、f ₂ (A)<0。
• f (B) = ( − ,+)の符号、つまりf ₁ (B)<0、f ₂ (B)>0 です。
• 符号f (C) = (+, − )、つまりf ₁ (C)>0、f ₂ (C)<0。
• f (D) = (+,+)の符号、つまりf ₁ (D)>0、f ₂ (D)>0 です。

特性多角形の適切な辺とは、符号ベクトルが1つの符号だけ異なる2つの頂点間の辺のことです。上記の例では、特性四角形の適切な辺はAB、AC、BD、CDです。対角線とは、符号ベクトルがd個すべての符号だけ異なる2つの頂点間の辺のことです。上記の例では、対角線はADとBCです。

各反復において、アルゴリズムは多面体の適切な辺（例えば、A - B）を選択し、その中点（例えば、M）におけるfの符号を計算します。その後、次のように処理を進めます。

• Sign f (M) = Sign(A) の場合、A は M に置き換えられ、より小さな特性多面体が得られます。
• Sign f (M) = Sign(B) の場合、B は M に置き換えられ、より小さな特性多面体が得られます。
• そうでなければ、新たな適切なエッジを選択して再度試みます。

元の特徴多面体の直径（＝最長の真辺の長さ）をDとします。すると、少なくとも${\displaystyle \log _{2}(D/\varepsilon )}$残った多角形の直径が最大で${\displaystyle \varepsilon }$[ ^{14 ]： 11、補題4.7}