二分法

二分法を用いて、方程式の根を近似計算する。

二分法のアルゴリズム

2分法は、 \[f(x)=0\] の解が存在する区間を半分ずつに絞って精度を高める手法のことである。

Step1 $f(a)$と$f(b)$の符号が異なるように$a,b$を取る。(つまり$f(a)\cdot f(b) < 0.$) (このとき$f(x)$が連続であれば、かならず開区間$(a,b)$上に零点が存在することになる。)

Step2 $a$と$b$の間の点$c:=(a+b)/2$を考え、$f(c)$を計算する。

Step3 $f(a)\cdot f(c) < 0$ であれば、$b=c$ として、そうでなければ $a=c$ とする。Step1に戻る。

コード例.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double nibunhou(double (*f)(double),double x1, double x2, int n) {
	if (f(x1) * f(x2) > 0) {
		exit(1);
	}
	int i;
	double a = x1;
	double b = x2;
	double c=0;
	for (i = 0; i < n; i++)
	{
		double fa = f(a);
		c = (a+b) / 2;
		double fc = f(c);
		if (fa*fc<=0) {
			b = c;
		}
		else {
			a = c;
		}
	}
	return c;
}

double func(double x) {
	return sin(x);
}
int main()
{
	printf("%.14f\n", nibunhou(func, 3, 4, 10));
	printf("%.14f\n", nibunhou(func, 3, 4, 20));
}

実行結果.

3.14160156250000
3.14159297943115

解説.

nibunhouの第1引数は根を求めたい関数とする。 方程式 \[f(x) = 0\] の解は第2引数と第3引数の間にあるとする。 第4引数の n は2分法をくりかえす回数となる。 上の実行結果では、繰り返しの回数を 10,20 として、 \[\sin x= 0\] の区間$[3,4]$にある零点をそれぞれ近似計算している。 正確な解は、 \[\pi = 3.1415926\cdots \] なので、繰り返しの回数を大きくした結果、精度も確かに良くなっていることが確認できる。

二分法の改良(挟み撃ち法)

自然に思いつくのが、$|f(a)|$と$|f(b)|$の比で、区間を分割する手法である。 同じことであるが、2点$(a,f(a)),(b,f(b))$を直線で結び、$x$軸との交点の座標を 考えることといっても良い。この手法は「挟み撃ち法」と呼ばれている。

2点$(a,f(a)),(b,f(b))$を結ぶ直線の$x$軸との交点の座標$c$は

\[c = \frac{af(b)-bf(a)}{f(b)-f(a)}\]

となる。

コード例.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double hasamiutihou(double (*f)(double), double x1, double x2, int n) {
	if (f(x1) * f(x2) >= 0) {
		exit(1);
	}
	int i;
	double a = x1;
	double b = x2;
	double c = 0;
	for (i = 0; i < n; i++)
	{
		double fa = f(a);
		double fb = f(b);
		c = (a * f(b) - b * f(a)) / (f(b) - f(a));
		double fc = f(c);
		if (fa * fc <= 0) {
			b = c;
		}
		else {
			a = c;
		}
	}
	return c;
}

double func(double x) {
	return sin(x);
}
int main()
{
	printf("%.14f\n", hasamiutihou(func, 3, 4, 3));
	printf("%.14f\n", hasamiutihou(func, 3, 4, 5));
}

実行結果.

3.14159265545897
3.14159265358979

解説.

hasamiutihouも使用法は同じ。 上の実行結果では、繰り返しの回数を 3,5 として、 \[\sin x= 0\] の区間$[3,4]$にある零点をそれぞれ近似計算している。 正確な解は、 \[\pi = 3.141592653589793\cdots \] なので、繰り返し回数5ですでにかなりの精度で近似できていることが分かる。