ｆ（ｘ）＝０の近次解を求める数値計算について

質問

方程式　f(x)=0　
の近次解を求める数値計算に関する質問です。

代表的な計算方法には二分法、はさみうち法、ニュートン法、逐次代入法
などがあるようですが、

f(x)が以下のような関数であるときどのように近似解を求めたらよいでしょうか？

(1)　　f(x)はどのxに対しても常にf(x)≧0となるような関数
(2)　　f(x)=0　となるxはただ一つだけである
(2)　　f(x)は非常に複雑な関数でf(x)を微分するのは困難

趣味で行っている3Dのモデリングに関するプログラム中に必要になった関数で、
このような関数に対し、二分法をベースにしたプログラムをつくってみましたが、
非常にだらだらとしたアルゴリズムでなっとくできません。
この関数に適したよいを御存知の方おられましたら御回答くださいませ。

またもしf(x)が　

(4)　　f(x)= |2x+3| のように　f(x)が0になるまでは単調減少で、0になってからは単調増加である

という条件がさらに加わった場合どうなるかについてもご解答いただけると助かります。

回答No.2

masa2211 · ベストアンサー

＞二分法をベースにしたプログラムをつくってみましたが、
＞非常にだらだらとしたアルゴリズムでなっとくできません。
もし、それが極小値を求めるように二分法を改造したのであれば、
その方法で合っています。
少しでも計算時間を稼ぎたいなら、分割方法を工夫します。
「黄金分割法」を使います。
http://www.sra.co.jp/people/miyata/algorithm/goldsect.txt
※極小（大）値を求めるアルゴリズムで、ｆ（ｘ）が単峰性という以外には制約が無い。

ちなみに、
二分法、はさみうち法：Ｘ＝Ａ、Ｘ＝Ｂで、Ｆ（Ｘ）の正負が入れ替わるように区間を
　　設定する必要があるため、この方法は使えない。
ニュートン法：f(x)の微分が判らない場合、f'(x)＝(f(x+dx)-f(x))/dx
　　で無理やり計算できるから、ニュートン法が使えないわけではない。
　　ただし、f(x)＝0付近において、f'(x)もゼロに近いから、運が悪いと発散して解が求まらない場合があります。
逐次代入法：逐次代入法も、発散と隣り合わせです。
　※ニュートン法も逐次代入法の一種。

＞(4)　　f(x)= |2x+3| のように　f(x)が0になるまでは単調減少で、0になってからは単調増加である
(1)と(2)が成立すれば、必ず(4)が成立するのだけど....
この関数でやっかいな点は、微分が連続関数となっているかどうか。
微分が連続関数：極小値の位置で微分もゼロ。　したがって、f(x)をじかに求める場合、ニュートン法や逐次代入法では発散するかも。
ただし、微分のかわりに差分を使って、差分＝0のｘを求める方法はｏｋ。
微分が極小値の位置で不連続：差分＝0となるｘを求める方法がうまくいかない可能性がある。（２分法ならば無理やりですが解は求まる。）

それやこれやで、発散しないで解にたどり着ける可能性が高い方法は２つ。（計算速度を犠牲にします。）
1つはｆ（ｘ）を直接使い、黄金分割法。
もう1つは、微分のかわりに差分を使い、２分法を用いて差分＝0となるｘを求める。
黄金分割法のほうが計算時間は短かそうです。

お礼

ご回答いただきありがとうございます。
「極小値を求める」という発想が私にはありませんでした。
確かに言われてみれば最小値のときの値が解になっていますね。

問題が切り替わったことに気付かなかったため、
アレでもないコレでもないと困惑していました。
発想を変えることの重要さを改めて実感いたしました。

肝心の計算ですが、黄金分割法で発散することなくもとめることができました。
計算速度にも満足しています。

(4)の条件ですが、たとえばf(x)が高校で学習するような３次関数で
極小値と極小値の値がともに正であるような関数の絶対値を考えたとき
解が１つにも関わらず(4)の条件は当てはまりません。
この場合教えていただいた黄金分割法は単峰性でなくなるため
何らかの工夫が必要になってきますね。

大変参考になりました。ありがとうございます。

回答No.1

Willyt

１，２を充たす函数のｆ（ｘ）＝０を充たすｘの値はその微分値もゼロにするはずです。だから差分がゼロになる点を微分を使わない挟み撃ち法で追っかけるのが有効じゃないでしょうか。

お礼

ご回答いただきありがとうございます。
二分法やはさみうち法の、f(a)・f(b)＜0になると　aとbの間に解が存在するという方法が
f(x)が常にに正だと使えないのが厳しいところですね。

私はf(a)・f(b)＜0の代わりに傾きに着目したそれに変わる方法で二分法をためしたのですが
うまく収束しなかったりして苦労しました。