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

質問

割線法とはさみうち法の収束性について
球根アルゴリズムに割線法とはさみうち法がありますね。
これら二つのアルゴリズムについて質問です。

まず割線法は必ず根に収束するとは限りません。
割線法が根に収束する（またはしない）条件の導出法を教えてください。

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

よろしくおねがいします。

回答No.1

stomachman

方法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]の外の影響を受けることがあるからです。収束の条件は方程式と出発値におおいに依存するので、収束条件を簡単に表すことはできないでしょう。（この点はニュートン法も同じことです。）