二分法とは
二分法は、方程式 $f(x) =0$ を数値計算で機械的に解くための計算手法のこと。
解が含まれる区間を何度も二分して狭めていくことで、数値的に解を求められる。
前提条件
- 関数 $f(x)$が連続であること
→連続なら必ず解を求められる
視覚的に考えてみる
解が含まれる区間$[a,b]$を適当に取る。
区間内で$f(x)$の符号が反転するため、$f(a)$と$f(b)$は必ず異符号になるはずである。
$aとb$の中点を新たに$c$とし、区間を二分する。
二分された区間のうち解が含まれている方をさらに二分し、これを繰り返す。
どんどん区間が狭くなり、やがて収束する。
アルゴリズム
- 解が含まれる$x$の区間$[a, b]$を$f(a)\times f(b)<0$となるように適当に定める
- 許容誤差$\varepsilon$を定める（許容誤差：どのくらいの精度で解を求めるか）
- $c = \frac{a + b}{2}$とし、区間を$[a,c]$と$[c,b]$に二分する
- $|f(c)|<\varepsilon$なら$x=c$を解とし、終了。そうでなければ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$で誤差が大きくなってますが、初期値によってこんなこともあるらしい。