二分法を用いて方程式の根を求めるC++プログラム

関数f(x)と2つの数a、bが与えられ、f(a)・f(b)<0を満たし、関数f(x)が区間[a, b]内に存在するとします。ここでの課題は、二分法(バイセクション法)を用いて、関数f(x)の区間aとbの間に存在する根の値を求めることです。

二分法とは?

二分法とは、「a」と「b」で定義された範囲内において、関数f(x)の根の値を求めるための数値計算手法の一つです。関数の根とは、その値を代入したときにf(x)=0となるような値xのことです。

例

方程式 F(x) = x^3 − 8 を考える
この方程式は、x = 2 のとき F(x) = 2^3 − 8 = 0 となります。
したがって、この関数F(x)の根は 2 です。

ここで、関数f(x)が与えられた区間[a, b]において連続であり、かつf(a)とf(b)の符号が異なる場合、f(m)=0を満たす値mが必ず区間[a, b]の中に存在することが知られています。

つまり、mは関数の根を表す値であり、このような根は複数存在する場合もあります。

下の図は、区間f(a)とf(b)の様子を示したものです。これらの区間の間で根を求めるには、区間を半分に分割し、その中間点を変数mとして格納します。

m = (a + b) / 2

区間を分割すると、下の図に示すように新しい区間が生成されます。この操作を繰り返すことで、根の存在する区間を徐々に狭めていくことができます。

例

入力:x^3 − x^2 + 2 、a = -500 、b = 100
出力:根の値は :-0.991821

入力:x^3 − x^2 + 2 、a = -200 、b = 300
出力:根の値は :-1.0025

以下のプログラムでは、次のようなアプローチを採用しています。

• 方程式と区間a、bの値を入力する
• 区間を m = (a + b) / 2 として分割する
  • f(m) = 0 であれば、mが根であることを出力する
• f(m) ≠ 0 の場合
  • f(a) × f(m) < 0 かどうかを確認する
  • 成立していれば、根はaとmの間に存在する
  • f(b) × f(m) < 0 かどうかを確認する
  • 成立していれば、根はbとmの間に存在する

アルゴリズム

Start
Step 1 -> 関数 double solution(double x)
    x*x*x - x*x + 2 を返す
Step 2 -> 関数 bisection(double a, double b)
    もし solution(a) * solution(b) >= 0 ならば
        「You have not assumed right a and b」を出力して return
    End If
    c = a とする
    (b - a) >= EP である間ループ
        c = (a + b) / 2 とする
        もし solution(c) == 0.0 ならば
            Break
        そうでなく、solution(c) * solution(a) < 0 ならば
            b = c とする
        そうでなければ
            a = c とする
    ループ終了
    根の値を出力
Step 3 -> 関数 int main()
    入力 a = -500、b = 100 を宣言・初期化する
    関数 bisection(a, b) を呼び出す
Stop

C++サンプルコード

#include <iostream>
using namespace std;
#define EP 0.01
// 二分法(Bisection Method)を用いて解を求める対象となる関数の例。
// 対象関数は x^3 - x^2 + 2
double solution(double x) {
   return x*x*x - x*x + 2;
}
// solution(x)の根を許容誤差EP以内で出力する
void bisection(double a, double b) {
   if (solution(a) * solution(b) >= 0) {
      cout << "You have not assumed right a and b\n";
      return;
   }
   double c = a;
   while ((b-a) >= EP) {
      // 中間点を求める
      c = (a+b)/2;
      // 中間点が根かどうかを判定する
      if (solution(c) == 0.0)
         break;
      // 次に反復を続ける側の区間を決定する
      else if (solution(c)*solution(a) < 0)
         b = c;
      else
         a = c;
   }
   cout << "The value of root is : " << c;
}
// main関数
int main() {
   double a =-500, b = 100;
   bisection(a, b);
   return 0;
}

出力

The value of root is : -0.991821

このように二分法では、区間の中間点における関数値の符号を調べながら区間を半分ずつ狭めていくことで、指定した許容誤差EP以内の精度で根の近似値を効率的に求めることができます。ただし、本手法を適用するには、関数が区間内で連続であり、両端点における関数値の符号が異なるという条件を満たす必要がある点に注意してください。