いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

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

 2分法を使って方程式の近似解を求めてみましょう。ロジックは単純だけれど、効率的に解を計算できます。
f:id:Inuosann:20200817200917p:plain:w200
水色の線はy=f(x)のグラフです。グラフとx軸(左右に延びている直線)の交点の目盛りが方程式f(x)=0 の解なのでした。まず、f(p)<0、f(q)>0となるp、qを適当に選びます(f(p)>0、f(q)<0でもよい)。図のrはr=(p+q)/2、つまりx=pである点からx=qである点までの線分の中点の座標です。p、qよりもrの方が解に近いですよね。これを繰り返します。つまり、今度はr、qを相手にするのです。s=(r+q)/2 が次の近似値です。こうして一時的に近似値が解から離れてしまうこともあります。でも問題ありません。区間が1回の操作で半分の長さになりますから、最初の区間の幅が1なら10回で 1/1024 ≒ 0.001 です。たった10回の計算で誤差はこのくらいに収まるのです。

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

import sys
import math

def f(x): #f(x)=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

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