非線形方程式 3分法

[しょしょしょしんしゃ]

学校の課題です。
非線形方程式を2分法または3分法(分割数を3にした場合）
を用いて、プログラムを作成して、25の3乗根を求めよ。（x^3-25=0)
という問題で、2分法はできましたが、3分法の求め方が分かりません。
2分法は以下の通りです。

#include<stdio.h>
#include<math.h>
#define f(x) ((x)*(x)*(x)-25)

int main(void){
	float a=2.0,b=3.0,c;
	do{
		c=(a+b)/2.0;
		if(fabs(f(c))<=1.0e-7)break;
		if(f(a)*f(c)<0)b=c;
		if(f(b)*f(c)<0)a=c;
	}while((b-a)>=1.0e-6);
	printf("方程式x^3-25=0の解は%fです\n",c);
	return 0;
}

実行結果は　方程式x^3-25=0の解は2.924108です。
という風になり、3分法も、これに近い値で実行できる。
よろしくお願いします。

[初級者]

３分法について習った内容を教えてください。

[non]

>}while((b-a)>=1.0e-6);
この終了条件は、どうして必要なんだっけ？
>if(fabs(f(c))<=1.0e-7)break;
こっちがあるなら必要がないような気がするけど。もし、振動するのなら、ループ回数を
制限するのかな？でも、３乗根だから収束すると思うけどな。
ただ、有効桁数が1.0e-7まで取れるか心配だけど。
doubleだと単独だと１５桁ぐらいだけど、３乗だから、どうだっけ？

[しょしょしょしんしゃ]

>３分法について習った内容を教えてください。
えーと　申し訳ないのですが、3分法は　高校、大学で習った覚えがないのですが・・・。
　2分法は、平均値の定理で　習った覚えはありますが....
>}while((b-a)>=1.0e-6);
>この終了条件は、どうして必要なんだっけ？
cを計算しf(c)=0ならば解が得られたらのでdo-while文からぬける。
でもきれいに0になるわけではないので、小さくなったらぬけるようにしてあります。
>if(fabs(f(c))<=1.0e-7)break;
これはaとbがほぼ同じになったら計算をやめて解とする。らしいです。

　この部分はたぶん、2分法特有じゃないんですか？
　

[box]

> えーと　申し訳ないのですが、3分法は　高校、大学で習った覚えがないのですが・・・。

ていうか、そもそも３分法というのがあるんでしょうか。

収束条件の話は、どちらか片方があればじゅうぶんだと思います。

[non]

３分法があるかないかは兎も角、
要は、abの区間を３つに分けて、仮にそれをcdとすると、
a-c区間を通る場合は、b=c
d-b区間を通る場合は、a=d
c-d区間を通る場合は、a=c、b=d
にすればいいでしょう。
while(1)にして、収束条件は1.0e-5で。

[box]

あ～なるほど、そういうことですね。
判定のたびに区間が1/3になるので、
二分法より速く収束するのですね。

[しょしょしょしんしゃ]

#include<stdio.h>
#include<math.h>
#define f(x) ((x)*(x)*(x)-25)

int main(void){
	float a=2.0,b=3.0,c,d;

	do{
		d=(a+b)/2.0;
		if(fabs(f(d))<=1.0e-5)break;
		if(f(a)*f(c)<0)b=c;
		if(f(d)*f(b)<0)a=d;
		if(f(c)*f(d)<0)a=c,b=d;
	}while(1);
     printf("方程式x^3-25=0の解は%fです\n",d);
	return 0;
}

つまり、こうゆうことなのですか？
　ちょっと話についていけなくてすみません。
>要は、abの区間を３つに分けて、仮にそれをcdとすると、
うまく　abの区間をわけることができませんでした・・。

[non]

c=a+(b-a)/3,d=a+(b-a)*2/3

[box]

＞うまく　abの区間をわけることができませんでした・・。

高校の数学Ⅰあたりで学ぶ「内分の公式」について調べてみると、
nonさんが示してくださった式の意味がわかるかもしれません。

[しょしょしょしんしゃ]

#include<stdio.h>
#include<math.h>
#define f(x) ((x)*(x)*(x)-25)

int main(void){
	float a=2.0,b=3.0,c=a+(b-a)/3,d=a+(b-a)*2/3;
	int count=0;
	do{
		d=(a+b)/2.0;
		if(fabs(f(d))<=1.0e-5)break;
		if(f(a)*f(d)<0)b=d;
		if(f(b)*f(d)<0)a=d;
    printf("%d方程式x^3-25=0の解は%fです\n",count,d);
	count++;
	}while(1);
     printf("方程式x^3-25=0の解は%fです\n",d);
	return 0;
}

　こんなかんじですかね？
しかし、2分法の場合は２０回繰り返されて、こちらのプログラマムは１８回繰り返されました。
　数は少なくなったのはいいのですが、これでよろしいのでしょうか？

[box]

> 	float a=2.0,b=3.0,c=a+(b-a)/3,d=a+(b-a)*2/3;

ここでせっかく求めた d の値を、

> 		d=(a+b)/2.0;

ここで上書きしてはいけません。
ていうか、２分法のところで

>		c=(a+b)/2.0;

を do 文によるループの「中に」書いた理由がおわかりですか？

[しょしょしょしんしゃ]

#include<stdio.h>
#include<math.h>
#define f(x) ((x)*(x)*(x)-25)

int main(void){
	float a=2.0,b=3.0,c,d;

	do{
        c=a+(b-a)/3;
	    d=a+(b-a)*2/3;
        if(fabs(f(d))<=1.0e-5)break;
		if(f(a)*f(c)<0)b=c;
		if(f(d)*f(b)<0)a=d;
		if(f(c)*f(d)<0)a=c,b=d;
     }while(1);
     printf("方程式x^3-25=0の解は%fです\n",d);
	return 0;
}

　こんな感じでいいでしょうか？　実行は12回繰り返しました。
　ご指摘があれば、直します。
　長い間、御苦労かけました。
　boxさん,nonさんには、多大なご協力感謝しています。

[non]

>if(fabs(f(d))<=1.0e-5)break;
ｃに収束分も加えること。