【Python】二分法【数値解析】

  • 2021年12月18日
  • 2022年8月1日
  • Python
  • 284View
  • 0件

はじめに

Python での二分法の実装例を紹介します。

二分法は求根アルゴリズムの中で最もシンプルなものです。
求根アルゴリズムとは、f(x) = 0 を満たす数式を与えて、x の値を反復で求める手法を言います。

Wikipedia 二分法

サンプルコード

二分法のサンプルコードです。
サンプルの 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

おしまい!