• 締切済み

割線法とはさみうち法の収束性について

割線法とはさみうち法の収束性について 球根アルゴリズムに割線法とはさみうち法がありますね。 これら二つのアルゴリズムについて質問です。 まず割線法は必ず根に収束するとは限りません。 割線法が根に収束する（またはしない）条件の導出法を教えてください。 次にはさみうち法ですが、はさみうち法にはいくつか亜種があると思います。 まず一つが、初期値a,bによってはさまれたcを求め、bをcに更新してループを回すやり方です。 このやり方ではaは固定されたままです。if f(a)・f(c)<0 then b=c else a=c という条件分岐はやりません。 この場合、収束性はどうなるでしょうか。 二つ目は、上記の条件分岐をやるやり方です。 このやり方は必ず収束するらしいのですがその証明を教えてください。 よろしくおねがいします。

みんなの回答

  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.1

方法A: 割線法 方法B: はさみうち法で、if f(a)・f(c)<0 then b=c else a=c という条件分岐 方法C: はさみうち法で、初期値a,bによってはさまれたcを求め、bをcに更新してループを回すやり方 の3つを挙げていらっしゃるけれども、それぞれどういう計算をするものなのかを明示しないことには話が始まりません。どうも、普通の意味で仰っているとは思えない。通常「はさみうち法」とは呼ばれない方法Cを挙げていらっしゃるからです。 　連続な実関数f(x)の方程式 　　f(x) = 0 を数値的に解く場合に話を限定しましょう。 方法A: 普通の意味での「割線法」は 　　c := (af(b)-bf(a))/(f(b)-f(a)) 　　a := b 　　b := c 　（ただし" := "は代入操作です。） 方法B：普通の意味での「はさみうち法」は 　　a＜b, f(a)f(b)＜0という条件下で 　　c := (af(b)-bf(a))/(f(b)-f(a)) 　　if (f(c)f(a)＜0) then a := c else b := c すると、上記の方法Cは 方法C： 　　b := (af(b)-bf(a))/(f(b)-f(a)) ということになりますかね。もしそうだとすると、方法Cではf(a)f(b)＜0という条件が満たされず、だからはさみうち法ではない。強いて言えば割線法の一種でしょう。しかし、左辺がたまたま解に近くなっても、f'(b)と(a-b)/f(a)が大きく違っていると次の繰り返しで却って解から離れてしまいかねないのだから、「運が良ければ収束することもないではない」という程度。数値計算法としてはまるでダメですね。 　さて、方法Bは（どれかの）解が存在する領域[a,b]の幅が繰り返しの度に単調に減少して0に収束する。 　もう少し正確に言うと、繰り返しの度にaは非減少、bは非増加であって、b-aは減少。なのでb-aは振動したり発散したりはできない。さて、b-aが0でない値に収束するとしたら、それは（aは非減少、bは非増加だから）aとbがそれぞれある値に収束するということです。その時には 　　f(a)f(b)＜0 であって、しかも 　　c = (af(b)-bf(a))/(f(b)-f(a)) について、c=aまたはc=bでなくてはならない。ところがcにaかbを代入してみれば分かる通り、そういうことは起こりえない。 　ということは、b-aは必ず0に収束する。 　方法A, Cは解が存在する領域[a,b]の幅が繰り返しの度に減少するとは限らない。また、出発値a,b(ただしf(a)f(b)＜0)の間に解が１個だけ存在するなら、方法Bはその解に収束する。けれども、Aではこの条件のもとですら収束が言えない。区間[a,b]の外の影響を受けることがあるからです。収束の条件は方程式と出発値におおいに依存するので、収束条件を簡単に表すことはできないでしょう。（この点はニュートン法も同じことです。）

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • はさみうち法‐2

    F(T)=6.72*10^-4*(1000-T)-5.67*10^-8*0.5*(T^4-600^4) をCでのはさみうち法のプログラムを教えてください 過去のQ＆Aを検索してもでてこなかったのでできればソースを教えてください。

  • はさみうち法

    F(T)=6.72*10^-4*(1000-T)-5.67*10^-8*0.5*(T^4-600^4) をCでのはさみうち法のプログラムを教えてください

  • 数値解析のはさみうち法について

    はさみうち法を使い数値計算をするプログラムで、解の近似値を求める式についてなんですが、 ２点a,bを結んでx軸との交点をｘにした時、 　x=(a * f(b) - b * f(a)) / (f(b) - f(a));と 　x=a-(b-a)/(f(b)-f(a))*f(a); の２通りの式で実行してみると、両方同じ近似値を求めることが出来たのですが、どちらの式も本当に正しい式なのでしょうか？ よろしくお願いします。 　　　　　　　　　　　　

  • 「セカント法」（割線法）についてです.

    非線形方程式の解を求めるアルゴリズム「セカント法」（割線法）についてです。 yahoo知恵袋の方でも質問しているのですが、 非線形方程式の解を求めるアルゴリズム「セカント法」（割線法）についてです。 セカント法で解を求める際、その収束次数は黄金比{（1+√5）/2}になると言われていますが、それを確認する方法はないものでしょうか。 セカント法で求めるプログラムはjavaの方で既に組んでおります。 なにかいいアイデアがあれば是非回答よろしくお願いします。 補足 組んだプログラムは与えられた関数の解と反復回数、それぞれの計算における関数値、真の解との誤差をかえすものです。 お願いします。

  • はさみうち法のプログラム（C言語）について

    調べたりしながら私なりに書いてみたのですが上手くいきません。 「ans=1.048404」とならなければいけないのに 「nan」で返ってきてしまうのです。 どこをどの様に変えたら良いのでしょうか・・・？ ※課題の締め切りが近いので,早急にご回答宜しくお願い致します！ 以下、はさみうちのプログラム↓ #include<stdio.h> #include<math.h> /*初期値x0,*/ /*f(x)を定義*/ double f(double x){ return sqrt(x*x+10.0) - 10.0*exp(-x*x); } /*はさみうち法の関数*/ double hasamiuchi(double x0,double x1,double eps,double imax){ double x2; /*x軸との交点*/ int i; /*繰り返しの回数*/ if(f(x0)*f(x1)>0){/*x0とx1が同符号の場合x1をx0とする*/ x0=x1; } for(i=0;i<imax;i++){ x2=(x1*f(x0)-x0*f(x1))/(f(x0)-f(x1)); /*x0とx1で出来る直線とx軸の交点x2を求める*/ x1=x2; /*x2の値を次のループにおけるx1とする*/ } if(fabs(x1-x0)<eps) return x2; /*収束したら解x2を返す*/ return 0.0/0.0; /*収束しなかったらnanを返す*/ } int main(void){ printf("ans = %f\n", hasamiuchi(2.0,1.0,1e-6,20));/*値を代入してはさみうちの実行*/ return 0; }

  • ニュートン法の２次収束性

    http://otasuke.goo-net.com/search.php3?dummy=%83%81%81%5B%83%8B&kw=%82P%8E%9F%8E%FB%91%A9&stage_id=0&submit_search=%8F%88%97%9D%92%86... http://maya.phys.kyushu-u.ac.jp/~knomura/education/numerical-physics/text1/node5.html を参考にしながら２次収束について勉強しているのですが 明らかに|a_n+1 - a| <= M|a_n - a|^2 (0<M<1)…(1)と|a_n+1 - a| <= M|a_n - a| (0<M<1)…(2)とを比べた時に|a_n - a|の方が２乗してない分値が小さいわけですよね？だから、収束性が(2)のものよりだんぜん良い気がするのですが ・・・・ 詳しい解説できる方、ご協力おねがいします。

  • ε-δ論法で、「収束しない」を証明することについて

    ε-δ論法で、「収束しない」を証明することについて 「収束する」ことを証明するのは、ε-δの条件に当てはまるようなあるδ＞0が存在することを証明する、ってことだったんですが （ここまでで間違ってたらすみません） 「収束しない」を証明するには「収束する」を否定するのだから 例えば、x→aのときf(x)がＡに収束しないを示すのは ∃ε＞０、∀δ＞０、０＜｜x－a｜＜δ,∃ｘ⇒｜f(x)－Ａ｜＜ε を満たせばよい、というのは分かるのですが、結局これは何を示せばよいのですか・・・？ εが存在することですか？ｘが存在することですか？ それとも何か別の・・・？

  • C言語　二分法　プログラム

    C言語での二分法の解法になやんでいます。 f(x)=X２乗-2でf(x)=0の解を2分法により求める場合のプログラムを教えて下さい。 収束条件|ak-bk|<10^-6と|f(ck+1)|<10^-6のいずれかを満足。また、解を求める過程として、k,ak,bk,|ak-bk|, ck+1, f(ck+1) (k=0,1,2,3...)も示してくれないでしょうか。よろしくお願いします。 注： a,b,cに付属するk,k+1はa,b,cの下側に付く小文字です。(a1,a2... ak, ak+1. b1 b2... bk, bk+1)

  • ニュートン法(2次)よりも高次収束の漸化式を求める方法は？

    ニュートン法はf(x)をテイラー展開した中の初めの2項を用いることで Xn+1 = Xn - f(Xn)/f'(Xn) という漸化式を取得します。これは2次に収束する漸化式です。 さらにベイリー法ではテイラー展開の第三項までとニュートン法の漸化式を用い3次収束の漸化式 Xn+1 = Xn - 2f'(Xn)*f(Xn)/(2f'(Xn)*f'(Xn)-f''(Xn)*f(Xn)) を得ています。 という所までは分かり、いざ3次の漸化式を作ろうと思ってもうまくいきません。 例えば http://www.finetune.co.jp/~lyuka/technote/fract/sqrt.html にはAの逆数1/Aを求めるための漸化式が5次まで掲載されています。 Aの逆数はf(x)=1-1/(1-Ax)を用いることで2次までは求まります。しかし3次以降をどうやって導くのかが分かりません。どなたか導き方のヒントでも構いませんので教えていただけないでしょうか？よろしくお願いします。 p.s. 平方根の逆数の係数（5/16や35/128など=(2n)!/(n!*n!*2^(n+1)）から考えるに f(x)のn回微分＝-n!*a^n*(1-ax)^(-n-1) とテイラー展開でなんとかなるような気もするのですが．．．

  • 広義積分が収束する範囲について

    広義積分が収束する範囲について この問題がわかりませんでしたので質問させていただきます。 回答を書き記します。 次の広義積分が収束するようなパラメータの範囲を定めよ。 I=∬D dxdy/|x|^(a)+|y|^(b) D:x^2+y^2≦1 回答 a>0,b>0のとき I1=∫（０→１）ｄｙ ∫（０→１）ｄｘ/x^(a)+y^(b) を考えればよい。 x/y^(b/a)=tとおく。 dx/x^(a)+y^(b)=1/y^(λ)×dt/t^(a)+1 となるようにすると λ+b/a-b=0 すなわち λ=b/a(a-1) I=∫（０→１）ｄｙ/y^λ×∫（０→y^(-b/a))×dt/t^a+1 ここでy～0のとき ∫（０→y(-b/a)) dt/t^a+1 ～Cy^(-b(1-a)/a), a<1のとき ～C|logy| a=1のとき ～C a>1のとき となる。 a<1なら Ｉ1～C∫（０→１）ｄｙ で明らかに収束 a=1のときλ＝０で Ｉ１～C∫（０→１）|logy|dyとなりこれも収束 またa>1の場合は Ｉ１～C∫（０→１）ｄｙ/y^λ 以上よりこれが収束するための必要かつ十分な条件はλ<1 すなわち b/a(a-1)<1 ab<a+b a=0 またはb=0のとき Ｉ1=∬D dxdy/1+|y|^b などとなり明らかに収束 以上より a≦0 またはb≦０ または ab<a+b ここまでが回答です。 私はＩをだすところまでは出来たのですが 「ｙ～０のとき～」の文より↓がお手上げです 記号の意味を調べてみたのですが 漸近的に等しい？？という意味で出てきました。 少し自分の力ではここからは解けそうにもありません。 よろしければ「ｙ～０のとき～」から説明をお願いします。 よろしくお願いします

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する