誊肌 †
はじめに †
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 bc
if f(b)とf(c)の射规が佰なる then ac
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
ba+∈惰粗を惰磊る升∷
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ではじめるアルゴリズム掐嚏≠
