【二分法とは】pythonプログラムを用いて具体的に解説する

二分法とは

二分法は、方程式 $f(x) =0$ を数値計算で機械的に解くための計算手法のこと。
解が含まれる区間を何度も二分して狭めていくことで、数値的に解を求められる。

前提条件

• 関数 $f(x)$が連続であること
  →連続なら必ず解を求められる

視覚的に考えてみる

解が含まれる区間$[a,b]$を適当に取る。
区間内で$f(x)$の符号が反転するため、$f(a)$と$f(b)$は必ず異符号になるはずである。
$aとb$の中点を新たに$c$とし、区間を二分する。
二分された区間のうち解が含まれている方をさらに二分し、これを繰り返す。
どんどん区間が狭くなり、やがて収束する。

アルゴリズム

1. 解が含まれる$x$の区間$[a, b]$を$f(a)\times f(b)<0$となるように適当に定める
2. 許容誤差$\varepsilon$を定める（許容誤差：どのくらいの精度で解を求めるか）
3. $c = \frac{a + b}{2}$とし、区間を$[a,c]$と$[c,b]$に二分する
4. $|f(c)|<\varepsilon$なら$x=c$を解とし、終了。そうでなければ5へ。
5. 解が含まれる法の区間を採用し、3へ。
   • $f(a) \times f(c)<0$なら bにcを代入
   • $f(c) \times f(b)<0$なら aにcを代入

二分法の特徴

長所

• 必ず解が求まる
• 導関数の計算が不要（ニュートン法などは導関数の計算が必要）

短所

• 収束が遅い（1次収束）
• 初期値が2つ必要

pythonで動かしてみる

bicection.py

import math
import pandas as pd

# 関数f(x)=x^2+2x-1
def f(x):
    return x*x + 2*x - 1

# f(x)=0の解 (0.41くらい)
ans = -1 + math.sqrt(2)

#　許容残差
eps = 0.001

# 初期値
a = 0
b = 1

# 表の作成
col_names = ['n', 'x', 'f(x)', '誤差']
df = pd.DataFrame(columns=col_names)

# 二分法
n = 1

while True:
    c = (a + b)/2
    df1 = pd.DataFrame(data=[[n, c, f(c), ans-c]], columns=col_names)
    df = pd.concat([df, df1], axis=0)
    if f(a) * f(c) < 0:
        b = c
    else:
        a = c
    if abs(f(c)) < eps:
        break
    n += 1

print(df.to_string(index=False))

コピペで動きます。
while文のところが理解できればOK。

実行結果.

n         x      f(x)        誤差
1       0.5      0.25 -0.085786
2      0.25   -0.4375  0.164214
3     0.375 -0.109375  0.039214
4    0.4375  0.066406 -0.023286
5   0.40625 -0.022461  0.007964
6  0.421875  0.021729 -0.007661
7  0.414062 -0.000427  0.000151

実行結果はこんな感じ。
誤差が減少し、$x$が解がだんだん近づいているのがわかると思います。
$n=2$で誤差が大きくなってますが、初期値によってこんなこともあるらしい。