２分法で方程式の複数の解を自動的に求めるには？

質問

２分法を授業で習い、アルゴリズムは理解できました。
そして、２分法で方程式の解を求めるプログラムも完成したのですが、

３次方程式などの全ての解を２分法で求める場合、本来ならば、
グラフなどを描き、適切な初期値を自分で変更していく必要があると思います。

しかし、方程式の複数の解を自動的に求めたいのです。

もし、２分法で方程式の複数の解を自動的に求めるアルゴリズムがあれば教えていただけないでしょうか。

よろしくお願いします。

※ 私が作成したプログラム（C言語）も載せておきます。

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

double f(double x)
{
return ((x-1.0)*(x-2.0)*(x-3.0));
}

int main ()
{
int i;
double a,b,x;
double gosa = 1.0e-14;

printf("aの値を入力してください。\n");
scanf("%lf",&a);
printf("bの値を入力してください。\n");
scanf("%lf",&b);

if(f(a)*f(b) >0) printf("aとbの範囲の中に適切な解が存在しません。\n");

while(1){

x = (a+b)/2.0;
printf("%.14f\n",x);

if(fabs(b-a)<gosa) break;

if(f(a)*f(x)<=0){
b = x;
}
else{
a = x;
}

}
return(0);
}

回答No.2

Tacosan · ベストアンサー

#1 では「一般論的には不可能」と書きましたが, 解くべき方程式が「重解を持たない」実係数代数方程式 (つまり「実係数多項式 = 0」の形) で, かつ「係数を与えている」場合にはすべての実解を見つけることが可能です.

これは二分法では「それぞれの解に対し, その解を (そしてその解だけを) 含む区間を決定する」ことができればよいわけですが, そのためには「与えられた区間にどれだけの解を持つか」がわかれば十分です. もちろんこれ自体が一般には無理ですが, 上の条件を満たせば「Strum列」というものを考えることで可能となります.

詳細は参照URL を見てほしいわけですが, ここで「数式として微分する」という操作が必要なので「係数を与える」ことが条件に入ってきます.

参考URL：

http://www.math.meiji.ac.jp/~mk/labo/text/eigen-values/node53.html

お礼

なるほど！
一部の方程式には，Strum列というものを用いることで解を求めることが出来るのですね！
ありがとうございました。
Strum列を用いたアルゴリズムを考えてみます！

回答No.3

asuncion

重箱の隅ですが…

＞if(f(a)*f(b) >0) printf("aとbの範囲の中に適切な解が存在しません。\n");
＞while(1){

解が存在しない、というエラーメッセージを出しておきながら
計算を続ける、というのは本当に適切かどうかというと、
必ずしもそうとは言いきれないような気がしないでもありません。

プログラムを終わらせてしまうか、aとbの再入力を求めるようにする方が
より適切ではないかと思ったりしないわけではありません。

お礼

確かにそうでしたね。。
解が存在しない場合は、プログラムを終了するように変更します。
ご指摘ありがとうございました。

回答No.1

Tacosan

f(x) によってはできるかもしれませんが, 一般論的には不可能でしょう.

二分法では, x^2 = 0 すら解けないわけで.

補足

やはり不可能でしたか。。
それでは、もう1点だけ質問よろしいでしょうか？

(x-1.0)(x-2.0)(x-3.0)=0 という方程式に限定した場合、
この方程式の解のうち、2.0 に最も近い解を一つだけ2分法で自動的に求める。

というアルゴリズムは不可能ですか？