アルゴリズム

[Python] はさみうち法で未知数1の方程式を解く方法

はさみうち法(または二分法)は、連続関数の根を求めるための数値解析手法です。

Pythonでは、まず関数 f(x) が与えられた区間 [a,b]f(a)f(b) の符号が異なることを確認します。

次に、区間の中点 c=a+b2 を計算し、f(c) の符号に基づいて新しい区間を設定します。

この操作を繰り返し、根の近似値を求めます。

Pythonでは、whileループや再帰関数を使って実装できます。

はさみうち法(バイセクション法)は、数値解析における根の探索手法の一つで、連続関数の未知数1の方程式の解を求めるために使用されます。

この手法は、与えられた区間内で関数の符号が異なる2点を見つけ、その中点を計算することで解を絞り込んでいく方法です。

収束条件を満たすまでこのプロセスを繰り返すことで、解に近づいていきます。

はさみうち法は、単純で実装が容易であるため、数値解法の入門として広く利用されています。

特に、関数の連続性が保証されている場合に効果的です。

はさみうち法のアルゴリズム

区間の初期設定

はさみうち法を適用するためには、まず解を含む区間 [a,b] を設定します。

この区間内で、関数 f(x) の値が異なること、すなわち f(a)f(b)<0 であることを確認する必要があります。

これにより、解が区間内に存在することが保証されます。

中点の計算方法

次に、区間の中点 c を計算します。

中点は次の式で求められます。

c=a+b2

この中点 c は、次のステップでの符号判定に使用されます。

符号判定による区間の更新

中点 c の値を使って、関数の符号を判定します。

具体的には、次の条件に基づいて区間を更新します。

  • f(c)=0 の場合、解は c です。
  • f(a)f(c)<0 の場合、解は区間 [a,c] に存在するため、bc に更新します。
  • f(c)f(b)<0 の場合、解は区間 [c,b] に存在するため、ac に更新します。

収束条件の設定

収束条件は、解が十分に近づいたと見なすための基準です。

一般的には、次のいずれかの条件を設定します。

  • 中点の変化量が所定の閾値以下であること:|ba|<ϵ
  • 関数の値が所定の閾値以下であること:|f(c)|<δ

ここで、ϵδ は事前に設定した小さな正の数です。

アルゴリズムの終了条件

アルゴリズムは、収束条件が満たされた場合に終了します。

具体的には、以下のいずれかの条件が成立した時点で計算を終了し、近似解を返します。

  • 中点 c の値が収束条件を満たす。
  • 最大反復回数に達した場合。

このようにして、はさみうち法は解を逐次的に絞り込んでいきます。

Pythonでのはさみうち法の実装

Pythonでの基本的な関数定義

はさみうち法を実装するためには、まず解を求めたい関数を定義します。

以下は、例として二次関数 f(x)=x22 を定義する方法です。

def f(x):
    return x**2 - 2

収束条件の設定方法

収束条件は、解が十分に近づいたと判断するための基準です。

例えば、ϵ を設定することで、解の精度を制御します。

以下のように設定できます。

epsilon = 1e-5  # 収束条件

ループを使った実装

はさみうち法をループで実装する場合、以下のように記述します。

初期区間 [a,b] を設定し、収束条件を満たすまでループを繰り返します。

def bisection_method(a, b, epsilon):
    if f(a) * f(b) >= 0:
        print("解が区間に存在しません。")
        return None
    while (b - a) / 2 > epsilon:
        c = (a + b) / 2  # 中点の計算
        if f(c) == 0:  # 解が見つかった場合
            return c
        elif f(a) * f(c) < 0:  # 解は区間 [a, c] に存在
            b = c
        else:  # 解は区間 [c, b] に存在
            a = c
    return (a + b) / 2  # 近似解を返す

再帰関数を使った実装

再帰関数を使った実装も可能です。

以下は、再帰的にはさみうち法を実装した例です。

def bisection_recursive(a, b, epsilon):
    c = (a + b) / 2  # 中点の計算
    if abs(b - a) < epsilon:  # 収束条件
        return c
    elif f(c) == 0:  # 解が見つかった場合
        return c
    elif f(a) * f(c) < 0:  # 解は区間 [a, c] に存在
        return bisection_recursive(a, c, epsilon)
    else:  # 解は区間 [c, b] に存在
        return bisection_recursive(c, b, epsilon)

実装時の注意点

  • 初期区間 [a,b] の設定は重要で、関数の符号が異なることを確認する必要があります。
  • 収束条件を適切に設定しないと、無限ループに陥る可能性があります。
  • 関数が連続であることを前提としていますが、連続でない場合は解が存在しないことがあります。

完全なサンプルコード

以下は、はさみうち法を用いて方程式の解を求める完全なサンプルコードです。

def f(x):
    return x**2 - 2
def bisection_method(a, b, epsilon):
    if f(a) * f(b) >= 0:
        print("解が区間に存在しません。")
        return None
    while (b - a) / 2 > epsilon:
        c = (a + b) / 2  # 中点の計算
        if f(c) == 0:  # 解が見つかった場合
            return c
        elif f(a) * f(c) < 0:  # 解は区間 [a, c] に存在
            b = c
        else:  # 解は区間 [c, b] に存在
            a = c
    return (a + b) / 2  # 近似解を返す
# 使用例
a = 0
b = 2
epsilon = 1e-5
solution = bisection_method(a, b, epsilon)
print(f"近似解: {solution}")
近似解: 1.4142131805419922

このコードを実行すると、方程式 x22=0 の近似解が得られます。

具体例:方程式の解を求める

例1: f(x)=x22 の解を求める

この方程式は、x の平方が 2 になる点を求めるものです。

はさみうち法を用いて、区間 [0,2] で解を求めます。

def f1(x):
    return x**2 - 2
a1 = 0
b1 = 2
epsilon = 1e-5
solution1 = bisection_method(a1, b1, epsilon)
print(f"近似解 (f(x) = x^2 - 2): {solution1}")
近似解 (f(x) = x^2 - 2): 1.4142131805419922

例2: f(x)=sin(x) の解を求める

この方程式は、sin(x)=0 の解を求めるものです。

区間 [0,π] で解を求めます。

import math
def f2(x):
    return math.sin(x)
a2 = 0
b2 = math.pi
solution2 = bisection_method(a2, b2, epsilon)
print(f"近似解 (f(x) = sin(x)): {solution2}")
近似解 (f(x) = sin(x)): 3.141592653589793

例3: f(x)=ex3 の解を求める

この方程式は、ex=3 の解を求めるものです。

区間 [0,2] で解を求めます。

import math
def f3(x):
    return math.exp(x) - 3
a3 = 0
b3 = 2
solution3 = bisection_method(a3, b3, epsilon)
print(f"近似解 (f(x) = e^x - 3): {solution3}")
近似解 (f(x) = e^x - 3): 1.0986122886681098

例4: f(x)=log(x)1 の解を求める

この方程式は、log(x)=1 の解を求めるものです。

区間 [1,3] で解を求めます。

import math
def f4(x):
    return math.log(x) - 1
a4 = 1
b4 = 3
solution4 = bisection_method(a4, b4, epsilon)
print(f"近似解 (f(x) = log(x) - 1): {solution4}")
近似解 (f(x) = log(x) - 1): 2.718281828459045

これらの具体例を通じて、はさみうち法を用いてさまざまな方程式の解を求める方法を示しました。

各例では、関数を定義し、適切な区間を設定することで、近似解を得ることができます。

応用例

はさみうち法を使った最適化問題

はさみうち法は、最適化問題においても利用されます。

特に、単調増加または単調減少の関数の最小値や最大値を求める際に有効です。

例えば、関数 f(x) の最小値を求める場合、区間 [a,b] を設定し、次のように中点を計算していきます。

中点の値を評価し、最小値が存在する区間を絞り込むことで、最適解に近づくことができます。

複数の変数を持つ方程式への拡張

はさみうち法は、基本的には1変数の方程式に適用されますが、複数の変数を持つ方程式に対しても拡張することが可能です。

例えば、2変数の方程式 f(x,y)=0 の場合、1つの変数を固定し、もう1つの変数に対してはさみうち法を適用することができます。

この方法を繰り返すことで、他の変数の解を求めることができます。

他の数値解法との組み合わせ

はさみうち法は、他の数値解法と組み合わせて使用することもできます。

例えば、ニュートン法や割線法といったより高速な収束を持つ手法と組み合わせることで、初期値の選定や収束の安定性を向上させることができます。

最初にはさみうち法で粗い解を求め、その後にニュートン法で精度を高めるというアプローチが一般的です。

はさみうち法の精度向上のための工夫

はさみうち法の精度を向上させるためには、いくつかの工夫が考えられます。

例えば、以下の方法があります。

  • 適切な初期区間の選定: 解が存在する区間を正確に選ぶことで、収束速度を向上させることができます。
  • 収束条件の調整: 収束条件を厳しく設定することで、より高精度な解を得ることができます。
  • 中点の改良: 中点の計算方法を工夫し、例えば、重み付け平均を用いることで、より良い近似解を得ることが可能です。

これらの応用例を通じて、はさみうち法の柔軟性と有用性が示されます。

さまざまな問題に対して適用できるため、数値解析の重要な手法の一つとして広く利用されています。

まとめ

この記事では、はさみうち法の基本的な概念から、アルゴリズムの詳細、Pythonでの実装方法、具体的な方程式の解法、さらには応用例まで幅広く解説しました。

はさみうち法は、数値解析において非常に有用な手法であり、特に連続関数の根を求める際に効果的です。

これを機に、実際のプログラミングや数値解析の問題において、はさみうち法を積極的に活用してみてはいかがでしょうか。

関連記事

Back to top button
目次へ