2分法で方程式の解の近似値を求める

　2分法を使って方程式の近似解を求めてみましょう。ロジックは単純だけれど、効率的に解を計算できます。

水色の線はｙ＝ｆ(ｘ)のグラフです。グラフとｘ軸（左右に延びている直線）の交点の目盛りが方程式ｆ(ｘ)＝0 の解なのでした。まず、ｆ(ｐ)＜0、ｆ(ｑ)＞0となるｐ、ｑを適当に選びます（ｆ(ｐ)＞0、ｆ(ｑ)＜0でもよい）。図のｒはｒ＝(ｐ＋ｑ)／2、つまりｘ＝ｐである点からｘ＝ｑである点までの線分の中点の座標です。ｐ、ｑよりもｒの方が解に近いですよね。これを繰り返します。つまり、今度はｒ、ｑを相手にするのです。ｓ＝(ｒ＋ｑ)／2 が次の近似値です。こうして一時的に近似値が解から離れてしまうこともあります。でも問題ありません。区間が1回の操作で半分の長さになりますから、最初の区間の幅が1なら10回で 1／1024 ≒ 0.001 です。たった10回の計算で誤差はこのくらいに収まるのです。

　試してみましょう。Pythonで、√2 を求めてみます。

import sys
import math

def f(x): #f(ｘ)＝0の解は√2
    return x * x - 2
#
p = 0 #f(p), f(q)が異符号になるよう、p, q の初期値を決める
q = 3
#
for i in range(100):
    r = (p + q) / 2
    p1 = f(p)
    q1 = f(q)
    r1 = f(r)
    if r1 > 0:
        if p1 > 0:
            p = r
        else: #p1 <= 0
            q = r
    else: #r1 <= 0
        if p1 > 0:
            q = r
        else: #p1 <= 0
            p = r
print('解 x = ', r)
sys.exit()

実行結果は以下の通りです。
解 x = 1.414213562373095

スバラシイ！！　とにかく区間を半分にしながらｆ(ｖ)＞0、ｆ(ｗ)＜0となるｖ、ｗを次々に決めることを繰り返すだけです。
　解の近似値を求めるのにニュートン法というのもあります。
www.omoshiro-suugaku.com
ニュートン法ではグラフの接線を使います。こちらの方が効率はよいですが、導関数を使いますしその分、今回紹介した2分法よりもロジックは少し複雑です。また、導関数を求めにくいこともあるでしょう。2分法ではそういう心配はいりません。