はじめに
Python での二分法の実装例を紹介します。
二分法は求根アルゴリズムの中で最もシンプルなものです。
求根アルゴリズムとは、f(x) = 0 を満たす数式を与えて、x の値を反復で求める手法を言います。
サンプルコード
二分法のサンプルコードです。
サンプルの main スクリプトでは、√2 の値を、10^-12 の精度で計算するようにしています。
import math
def bisection_method(f, x1, x2, tol, nmax):
assert x1 < x2
y1 = f(x1)
y2 = f(x2)
assert y1 * y2 < 0
n = 1
while n <= nmax:
x = (x1 + x2) / 2
y = f(x)
if y == 0 or (x2 - x1) / 2 < tol:
return x
n += 1
if y * y1 >= 0:
x1 = x
else:
x2 = x
raise RuntimeError(f'number of iterations exceeded nmax {nmax}')
if __name__ == '__main__':
def f(x):
return x - math.sqrt(2)
print(bisection_method(f, 0, 2, 1e-12, 100))
print(math.sqrt(2))❯ python3 bisection_method.py
1.4142135623724243
1.4142135623730951おしまい！