二分法は、数値形跡における求根アルゴリズムのひとつです。
反復法によって任意の方程式を解くためのアルゴリズムです。
\(x\) の上限と下限を初期値として、区間を半分ずつ狭めていくことにより、\(f(x) = 0\) を満たすような \(x\) を探索する手法です。
求根アルゴリズムの中では最もシンプルな手法です。
プログラム例
プログラム例です。
引数として以下をインプットします。
| 引数 | 説明 |
|---|---|
| f | \(f(x)\) の関数 |
| lower | 下限値 |
| upper | 上限値 |
| torelance | 誤差許容値 |
| max_iter | 最大試行回数 |
C++
#include <cmath>
#include <functional>
double bisection_method(
std::function<double(double)> f,
double lower,
double upper,
double torelance,
std::size_t max_iter) {
double a = lower;
double b = upper;
double fa = f(a);
double fb = f(b);
if (fa * fb > 0.0) {
throw std::runtime_error("f(lower) と f(upper) の符号が同じです");
}
for (std::size_t i = 0; i < max_iter; ++i) {
double c = (a + b) / 2.0;
double fc = f(c);
if (std::abs(fc) < torelance) {
return c;
}
if (fa * fc > 0.0) {
a = c;
fa = fc;
} else {
b = c;
fb = fc;
}
}
throw std::runtime_error("最大試行回数に達しました");
}
実行例
\(f(x) = x^2 – 2\) に対するプログラムの実行例です。
C++
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
double bisection_method(...) {
...
}
double f(double x) {
return x * x - 2.0;
}
int main() {
auto y = bisection_method(f, 1.0, 2.0, 1e-12, 100);
std::cout << std::fixed << std::setprecision(11) << y << std::endl;
// 出力：1.41421356237
return 0;
}
\(\sqrt{2} = 1.414\cdots\) の値が反復によって計算されます。
f の関数定義や、上限、下限を変更することで、多様な方程式の解を計算することができます。
コメント