二分法アルゴリズムとその例

二分法とは何ですか？

二分法は、多項式または超越方程式の根を求めるための最も基本的な数値計算手法の一つです。この方法は、根を含む区間を挟み込み、根が許容範囲内に収まるまで、その区間を反復ごとに半分ずつに分割していくことで機能します。このように区間を分割していくことから、二分法は「括弧法」とも呼ばれます。

二分法は、その動作原理が二分探索に似ているため、二分探索法、二分法、または二分法とも呼ばれます。この方法は、中間値の定理という強力な理論的基盤に基づいています。中間値の定理は、ある区間内で符号が変化する連続関数は、その区間内のどこかで必ずゼロを横切ることを保証します。

基本的な定義がわかったところで、方程式の根を求めることがなぜ重要なのか、そして二分法がその全体像の中でどのような位置づけにあるのかを探ってみましょう。

方程式の根を求める

本稿では、独立変数が1つの方程式のみに焦点を当てる。このような方程式は、線形方程式と非線形方程式のどちらでもよい。線形方程式は直線のグラフを表し、非線形方程式は曲線やより複雑な形状を表す。

方程式の根とは、その方程式を満たす独立変数の値のことです。例えば、方程式 f(x) = 4 – x の根は² = 0 は 2 です。なぜなら f(2) = 4 – 2 だからです。² = 0。

f(x)を実数連続関数とします。中間値の定理によれば、f(a)f(b) < 0 の場合、方程式 f(x) = 0 は a と b の間に少なくとも 1 つの根を持ちます。言い換えれば、関数 f(x) は a と b の間のどこかに根「c」を持ちます。

この符号変化の性質こそ、二分法がまさに利用しているものです。次のセクションでは、この考え方をグラフでどのように表現するかを示します。

二等分法の図解

以下のグラフは、二分法の動作原理を表しています。グラフから、方程式の実際の解が赤色で示されていることがわかります。

その手順は以下のように要約できます。

• まず、2 つの初期推測値を選択します。₁ およびb₁、f(a₁)f(b₁) < 0。中間値の定理によれば、根は[a₁、b₁].
• 次に、₁ およびb₁これはbです₂初期間隔は今や[a₁、b₂] なぜなら f(a₁)f(b₂) < 0。
• 同様に、所望の許容範囲内で近似解が見つかるまで、区間を何度も半分に縮小していく。

幾何学的な直感が明確になったので、手順を段階的なアルゴリズムとして定式化することができる。

二分法アルゴリズム

方程式 f(x) = 0 の根を求めるために二分法アルゴリズムを適用する手順は次のとおりです。

ステップ1） 初期推定値 a、b と許容率 e を選択します。

ステップ2） f(a)f(b) >= 0 の場合、根はこの区間内に存在しません。その場合、[a, b] 内には解は存在しません。

ステップ3） 中点 c = (a + b)/2 を求めます。

（i）中点f(c)における関数値f(c) = 0の場合、cは根である。ステップ5に進む。
（ii）f(a)f(c) < 0 の場合、根は a と c の間にある。次に、a = a、b = c とおく。
（iii）それ以外の場合は、a = c、b = b と設定する。

ステップ4） 絶対誤差が許容誤差率よりも大きい場合、つまり (b – a) > e の場合は、ステップ 3 に戻ります。

ステップ5） c を近似ルートとして表示します。

二分法アルゴリズムの実際の例を見てみましょう。二分法の公式を用いて、以下の連続関数の根を求めます。

f（x）= x³ - バツ² + 2

二等分法の例

ステップ1） 仮に、

         a = -10、
         b = 10、および
         e = 1% または 0.01。

ステップ2） ここで、f(a)f(b) >= 0 かどうかを確認します。

         f(a) = f(-10) = (-10)³ – (-10)² + 2 = -1098
         f(b) = f(10) = (10)³ - （10）² + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

したがって、上記の関数の根は区間[-10, 10]にあります。

ステップ3） 次に、中点cを計算します。

ここで、次の条件を確認する必要があります。

（i）f(c) = 0かどうか：
         f(c) = f(0) = (0)³ - （0）² + 2 = 2 であり、これは 0 とは等しくない。

（ii）f(a)f(c) < 0 かどうか：
         f(c)f(a) = 2 * (-1098) < 0

条件が満たされました。次の反復処理では、値は次のようになります。

         a = a = -10
         b = c = 0

ステップ4） (b – a) = (0 – (-10)) = 10 > 0.01 であるため、このプロセスが繰り返されます。次の反復処理は以下の表に示されています。

ステップ5） 11回目の反復において、ステップ4の条件が偽となる。したがって、この方程式の近似解は-1.00586となる。

数値例が完成したので、次のセクションでは、制御フロー全体を示す論理図を提示します。

二分法論理図

以下のフローチャートは、二分法における判定ロジックをまとめたもので、括弧チェック、中間点更新、許容誤差テストなどが含まれています。

擬似-Code

以下の擬似コードはアルゴリズムを反映しており、あらゆるプログラミング言語で二分法を実装するための設計図として機能します。

Start
Set a, b, e
if f(a)*f(b) >= 0
    Output("Root does not exist in this interval")
    Stop
while (b-a) > e do
    c ← (a + b)/2
    if f(c) = 0
        break
    end if
    if f(c)*f(a) < 0 then
        b ← c
    else
        a ← c
end while
Output(c)
Stop

C言語での二分法の例/C++

次のC/C++ このプログラムは、二分法を用いて f(x) = x の根を求めます。³ - バツ² [-10, 10]の範囲内で+2。

入力：

#include <bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
    return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
    if (value(a) * value(b) >= 0)
    {
        cout << "The root does not lie in this interval\n";
        return;
    }
    double c = a;
    while ((b-a) >= Error)
    {
        c = (a+b)/2;
        if (value(c) == 0.0)
            break;
        else if (value(c)*value(a) < 0)
            b = c;
        else
            a = c;
    }
    cout << "The root is :" << c;
}
int main()
{
    double a = -10, b = 10;
    bisection_method(a, b);
    return 0;
}

出力：

The root is :-1.00586

二分法の例 Python

その Python 以下のバージョンは、同一のロジックを使用して同じ近似解を生成するため、迅速な実験や教育に最適です。

入力：

def value(x):
    return x*x*x - x*x + 2

def bisection_method(a, b):
    if (value(a) * value(b) >= 0):
        return
    c = a
    while ((b-a) >= 0.01):
        c = (a+b)/2
        if (value(c) == 0.0):
            break
        if (value(c)*value(a) < 0):
            b = c
        else:
            a = c
    print("The root is : ", "%.4f" % c)

a = -10
b = 10
bisection_method(a, b)

出力：

The root is :  -1.0059

二等分法の利点と限界

他の数値解析手法と同様に、二分法にも明確な長所といくつかの実用的な欠点があります。以下の表は、最も重要な長所と短所をまとめたものです。

二等分法の応用

二分法は、堅牢な根探索ステップが必要とされる多くの実用的かつ現代的なコンピューティングシナリオで使用されています。

• エンジニアリングシミュレーション： 熱伝達、流体力学、構造解析において現れる非線形方程式を解く。
• 財務モデリング: 閉形式解が存在しない場合に、利回り、内部収益率、損益分岐点を計算する。
• 機械学習と AI: AI駆動型数値ソルバー内で、閾値の特定、モデルの較正、およびハイパーパラメータの調整を行う。
• コンピュータグラフィックス： 曲線に沿った光線と曲面の交点およびパラメータ値を決定する。
• 組み込みシステム: 低リソース制御器において、速度よりもシンプルさと予測可能性が重視される場合に、根を近似する。

よくあるご質問