目次 †
はじめに †
2次方程式を求めるには、「2次方程式の解の公式」（中学校で習う）を利用すればよい。3次方程式にはカルダノの公式、4次方程式にはフェラーリの公式という解を求める公式が存在する。5次方程式以上の解の公式は存在しないことが、すでにアーベルによって証明されている。
5次以上の方程式の解を求める公式はないが、解の存在する場所を絞り込んでいき、最終的に求めることができるアルゴリズムが存在する。そのアルゴリズムのひとつが二分法である。
二分法のアルゴリズム †
まず2つのxの値a,bを取る。このときf(a)とf(b)の符号が異なるように、aとbを選ぶ。そうすると、aとbの間に解が存在する。これは中間値の定理により明らかである。
次に、とりあえず2点の中間点cを求め、f(c)が0かどうかを調べる。もし0であったら、cが解そのものである。0でなければ、aまたはbの代わりにcを使って、もう一度繰り返す。このとき、f(a)とf(c)の符号が同じならばaにcを代入し、f(b)とf(c)の符号が同じならばbにcを代入する。
これを繰り返していけば、解の範囲を次々と半分に絞り込んでいける（これが二分法という名前の由来）。最終的に解を特定できるわけである。
まとめると、二分法のアルゴリズムは次のようになる。
- Input：a,b（「a＜b」∧「f(a)とf(b)の符号が違う」）
- Output：c（f(x)=0の解）
1
2
3
4
5
| while f(c)==0 do
c←(a+b)/2
if f(a)とf(c)の符号が異なる then b←c
if f(b)とf(c)の符号が異なる then a←c
output c
|
この二分法は、連続関数でしか利用できないことに注意。
また、浮動小数点表示によるdouble型の計算は誤差を伴なう。つまり、if( f(x)==0 )とすることで、ゼロの判定ができない。そこで適当な値（＝threshold）を決めて、その値より小さくなったら0と考えることにする。ただし、負の数になることも考えて、次のようにする必要がある。
double threshold = 1E-10; // 「threshold = 0.0000000001」と同じ
if( -threshold < f(x) || f(x) < threshold) // 0の判定
さらに、区間がほぼ0になったらループを終了することをしておく。
double threshold = 1E-10; // 「threshold = 0.0000000001」と同じ
if(b-a < threshold){
break;
}
そして、出力される解cはあくまでaとbの間だけということに注意して欲しい。
Javaによる実装 †
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
-
|
-
|
|
!
|
|
-
|
|
|
|
-
|
|
-
|
|
!
|
-
|
|
!
|
-
|
|
!
|
-
|
|
!
|
-
|
|
!
|
|
|
-
|
-
|
!
|
|
|
-
|
!
|
|
|
|
-
|
-
|
!
|
|
|
|
|
|
|
|
|
!
|
|
|
|
!
!
|
public class Bisection {
static double Func(double x){
double y = (x-1)*(x+2)*(x-3); return y;
}
public static void main(String[] args) {
double threshold = 1E-10;
double a=0,b=1;
double c=0;
try{
a=Double.parseDouble(args[0]);
b=Double.parseDouble(args[1]);
}catch(NumberFormatException e){
System.out.println("入力エラー");
return;
}
if(a>b){
System.out.println("a<bになるように値を選んでください。");
return;
}
if(Func(a)*Func(b)>0){
System.out.println("f(a)とf(b)の符号が同じです。");
return;
}
if(Func(a)==0){
System.out.println(a+"は解です。");
return;
}
if(Func(b)==0){
System.out.println(b+"は解です。");
return;
}
int i=0; while(true){
if(b-a < threshold){
break;
}
c=(a+b)/2; double fc = Func(c);
if(-threshold <= fc && fc <= threshold){
break;
}
double fa=Func(a);
double fb=Func(b);
if(fa*fc < 0){
b=c;
}else if(fb*fc < 0){
a=c;
}
i++;
String si = new java.text.DecimalFormat("00").format(i);
String sa = new java.text.DecimalFormat("0.00000").format(a);
String sb = new java.text.DecimalFormat("0.00000").format(b);
String sc = new java.text.DecimalFormat("0.00000").format(c);
String sf = new java.text.DecimalFormat("0.00000").format(fc);
System.out.println(si+" a="+sa+" b="+sb+" c="+sc+" f(c)="+sf);
}
String s = new java.text.DecimalFormat("0.00000").format(c);
System.out.println(i+"回目 解："+s);
}
}
|
このプログラムは、2つの引数を与えるとその範囲内の解を求めることができる。関数f(x)は関数Func内で指定している。ここでは=(x-1)(x+2)(x-3))
なので、-2,1,3という3つの解を持つ。
二分法では解をひとつずつしか見つけられない。つまりあからじめ3つあることを知らなければ、範囲の指定ができない。例えば、sin(x)やcos(x)は無限の解がたくさんある。そのため、一般の関数の解を求めるためには、これを解決する仕組みを考える必要がある。
二分法を利用したすべての解を求めるアルゴリズム †
すべての解を求めるといっても、sin(x)などは無限の解が存在してしまうので、区間を指定できるようにしておき、その区間内のすべての解を出力するようなアルゴリズムを考える。
- Input：min（区間の最小値）、max（区間の最大値）
- Output：C（解のリスト）
1
2
| while (a=min || a<=max) do
b←a+（区間を区切る幅）
if f(a)とf(b)の符号が異なる then
Bisection(a,b);
|
Bisectionは二分法のアルゴリズムである。途中表示はせずに結果（ひとつの解）だけを出力するとする。またエラーチェックもいらない。
Javaによる実装 †
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
-
|
|
-
|
|
!
|
|
|
-
|
|
|
|
-
|
!
|
-
|
!
|
|
-
|
-
|
!
|
|
|
-
|
!
|
|
|
|
-
|
-
|
!
!
|
|
!
|
|
-
|
|
|
-
|
-
|
|
-
|
|
!
|
|
-
|
|
|
!
!
|
|
|
-
|
|
|
-
|
|
|
|
!
!
!
!
|
public class Bisection2 {
static double Func(double x){
double y = (x-1)*(x+2)*(x-3); return y;
}
static double DoBisection(double a,double b){
double threshold = 1E-10;
double c=0;
if(Func(a)==0){
return a;
}
if(Func(b)==0){
return b;
}
while(true){
if(b-a < threshold){
break;
}
c=(a+b)/2; double fc = Func(c);
if(-threshold <= fc && fc <= threshold){
break;
}
double fa=Func(a);
double fb=Func(b);
if(fa*fc < 0){
b=c;
}else if(fb*fc < 0){
a=c;
}
}
return c;
}
public static void main(String[] args) {
double step=0.1; double min=-100,max=100;
if(args.length==2){
try{
min=Double.parseDouble(args[0]);
max=Double.parseDouble(args[1]);
}catch(NumberFormatException e){
System.out.println("入力エラー");
return;
}
if(min>max){
double tmp=min;
min=max;
max=tmp;
}
}
int ansNo=0; for(double a=min;a<=max;a+=step){
double b=a+step;
if(Func(a)*Func(b)<0){
ansNo++;
double c=DoBisection(a,b);
String sc=new java.text.DecimalFormat("0.0####").format(c);
System.out.println(ansNo+":"+sc);
}
}
}
}
|
参考文献 †
- 『Eclipseによる体験学習 Javaではじめるアルゴリズム入門』
