二分法

コード例

def f(x):
    return x ** 2 - 2

left = 1
right = 2
for _ in range(50):
    mid = left + (right - left) / 2
    if f(mid) * f(left) >= 0:
        left = mid
    else:
        right = mid

print(left) # 1.414213562373095

なめらかにつながっている曲線（グラフ）が、ある区間でプラスの値からマイナスの値（またはその逆）に変わるなら、その途中で必ずどこか一か所でゼロの点を横切る。この「ゼロの点を横切る場所」が、方程式の解 f(x)=0 となる x の値。

二分法では、この原理を使って以下の手順で解を探しだす。

解を挟む区間を見つける

まず、解が存在しそうな区間 [a, b] を決める。このとき、区間の両端の値 f(a) と f(b) の符号がプラスとマイナスで異なっている必要がある。
区間の中点を調べる

区間の中点 c=(a+b)/2 を計算し、その点での値 f(c) を調べる。
解がある方の半分に区間を狭める
- もし f(c) が f(a) と同じ符号なら、解は右半分の区間 [c, b] にあるはず。
- もし f(c) が f(b) と同じ符号なら、解は左半分の区間 [a, c] にあるはず。
- （もし偶然 f(c) が 0 になれば、それが解となる）
これを繰り返す

新しく狭まった区間で、再び中点を調べて…という作業を、区間の幅が十分に小さくなる（＝答えの精度が十分高くなる）まで繰り返す。