二分法、定点法、ニュートン法の比較

質問

数値解析で、二分法、定点法、ニュートン法（ニュートンラフソン法）でもっとも的確で効率がいいのはどれなのでしょうか。
ニュートン法が早いのはわかるのですが、微分した式を見つけられないこともあることを考えると、安易には決められないように思います。
多項式、三角方程式、指数方程式などタイプによってどの方法が効率的、というふうに決められるのでしょうか？

まとまっていない質問ですみません。わかる方がいらっしゃいましたらよろしくお願いします。

回答No.5

noname#221368

$2です。質問内容から言って、大規模数値問題を解いているのでないと判断し、#2を書きましたが、確認すべきでした。問題が大規模な場合は、#3，#1さんを参考にして下さい。

　以下、小規模を前提にして書きます。まず解が一個の区間への絞り込みですが、ここが一番苦労するところです。そしてどんな計算方法を使うにしろ、一番いいのはやはり、グラフを目で見て判断する事だと思います。昔はグラフを描くのもおおごとでしたが、今ではExcelなどで簡単に描けます。
　ところでExcelなどでグラフを描けるなら、それも自動化できます。実用的には、ある方程式の全ての解でなく、使える解の範囲が最初から決まっているのが普通です。それをここでは、a≦x≦bとします。
　基本的にはa≦x≦bを1000分割くらいしてサンプル点をとり、関数値を調べます。分割の細かさは、経験的に判断してます。このとき重要になるのが、#1さんも仰っていますが、関数に対する習熟度です。例えば関数の定性的性質から、次に述べる値調べを、まるごと省略できるかも知れませんし、細かさに対する指標にもなります。
　サンプル関数値の正負が変化する区間を見つけたら、そこでは単調変化を仮定して、二分法を単純に適用します。解の位置とそこでの関数値を記録します。次にそれらの点を除き、サンプル値が0に近いと思える点を、全てリストします。「どの程度だったら近いのか？」の判断も経験です。
　リスト内の点を含む最少区間をとり、差分を実行しながら二分法を使用します。今度の二分法は、極大・極小点の探索です。差分の幅は、二分法の精度程度にし、差分の正負から極大・極小点を確定して重解とします。そこでの関数値と、差分値を差分幅で割った微分値も記録します。
　以上は、サンプル点の取り方に依存するので、得られた関数値と微分値が、所定の精度で0付近にあるかをチェックします。チェックで不可となった場合は、捨てるか（捨てる条件も考えます）、その区間だけを取り出して、上記と同じ方法を適用して解候補を絞り、全て可となるまで繰り返します。この時も関数の定性的性質から、事前に解の個数がわかっていれば、判定基準の決定打になります。

　・上記繰り返しは、無限ループに陥りやすいので、十分な安全対策が必要です。
　・安全対策の中には、「諦める」という選択肢もあり得ます。
　・事前に解の個数がわかっていない場合、上記方法で解を全て尽くしたという保証は得られません。

　ニュートン法で微分が面倒という話しがありましたが、ある意味で全て数値的に行う方法もあります。大規模計算でない時には、逆にプログラムが面倒なので私は使った事がありませんが、次の本を参考にしてみて下さい。

　・数値計算法の数理，杉原正顕，室田一雄，岩波書店2007年6月

　この本は、コンピューターの有効数字についても、ちゃんとした数学的議論が載っている数少ない本です。

回答No.4

noname#221368

#2です。

　質問者様へ。
　回答者どうしのやり取りは禁止されておりますが、一回だけ許して下さい。

　#3さんへ。
　仰るとおりです。私はせいぜい100回以内の計算量を前提にしていました。一万回ともなると、じゅうぶん初期値を検討したニュートン法を選ぶだろうと思います。
　それと直接関係ないのですが、職業柄どうしても次の点が気になるので、書いてしまいます。Excelの一万個のCellを書き直すという事ですが、以下に述べる事を既に検討済みならば、お許し下さい。

　(1)計算ルーティンをVBAで書いているなら、Applicationとして計算ルーティンを独立させ、ApplicationからExcelを操作する。
　(2)Excelは非表示で起動させ、計算終了後に表示する。
　(3)Excelから直接Dataを読まない。Sheetの該当範囲をExcelにBinary出力させ（これは速いです）、AppにはBinaryファイルを読ませ、Excel Sheetへの入出力は、結果書き込みにとどめる。
　(4)Cellへの読み書きを、CellsやRangeで直接行わない。該当範囲を全部配列に読み込んで操作する。配列＝Range(範囲)，Range(範囲)＝配列で出来ます。
　(5)Excel Chartに頼らない。

　これだけで、かなりのスピードアップが図れると思います。

回答No.3

KappNets

＜現在は、0.1秒が0.001秒に短縮されたとしても、「煙草一本吸えやしない」という気持ちです。現実には、もっと速いと思います。＞

一つの問題を解くだけの時には確かに秒の速度は問題になりません。ところが例えば私のテーマはExcelの２次元的な表の一欄一欄を全部（１万欄？）計算し直して、さらに幾つかのX-Y図をプロットさせるというような仕事です。十指に余るパラメータ（の一つ）をいじるたびに下手をすると何分？か待たされます。パラメータの最適化などを試みる際にはこれを何十回と繰り返さなければなりません。収束計算だけが時間を食っているわけではおそらくないのですが、やはり収束計算の部分は精度や安定性を含めて気になります。

収束計算が遅い場合には近似計算の精度を上げる論文が出たりもします。どれほど問題意識がシリアスかで違ってくるのだろうと思います。

お礼

回答ありがとうございます。
数値計算のプログラムやソフトを使ってやるというよりも、
そのメカニズムについて学校で学んでいるだけなので、実際に多くの計算をやることはないのですが、やはりお仕事などで使うとなると差が出るのですね。参考になります。

回答No.2

noname#221368

#1さんの言うニュートン法の問題（？）から、私は二分法を多用しています（1次元に限る）。二分法の利点は、

　(1)アリゴリズムが簡単
　(2)精度コントロールが意のまま
　(3)重解にも対応できる（関数値が0に近ければ、解とする）
　(4)振動しない

です。欠点は、

　(1')解が一つの区間を選ぶ必要がある
　(2')ニュートン法より遅い

ですが、(1')は安全にニュートン法を実行するのであれば、ニュートン法でも必要と思います。(2')は現実的には問題にならない、というのが私の意見です。例えばニュートン法が二分法より100倍速いとします。　昔はPCが遅かったので、二分法で1時間かかる計算が、ニュートン法で0.6分＝36秒で済むなら、意味がありました。現在は、0.1秒が0.001秒に短縮されたとしても、「煙草一本吸えやしない」という気持ちです。現実には、もっと速いと思います。

お礼

わかりやすい回答をありがとうございます。
（３）の重解にも対応できる、というところをもう少し説明していただけるでしょうか。分かり悪くてすみません；；よろしくお願いします。

回答No.1

KappNets

私はしばしばこの手の計算で悩んだ経験があります。悩んだのは簡単なn次式と指数関数をたし合わせ、さらに全体のルートを取ったような関数です。xの途中で関数の傾きが大きく変化するのです。
ニュートン法の欠点は
(1) 収束しないで振動することがある。
(2) 大体求まった後で最後の詰めのところでなかなか収束しない。
(3) 微分が面倒。
などでしょうか。どろくさい方法で逃げたりもしましたが、結局はうまくやればニュートン法は非常によい方法という結論でした。対策の主なものは
(1) Excelのように出来るだけ有効数字の大きいソフトを用いる。Excelの場合有効数字は15桁ですね。
(2) 最初の出発(仮定)値をしっかり決める。場合によっては近似解をベースに最初の値を条件によって変える。
(3) 微分の解析式はMathematicaを使うと簡単に求まります。学校以外では高価なソフトですが。
(4) ルートを取るか取らないかでも計算時間・精度は変わる。f^0.5=0とf=0は等価ですから、ルートをとらないでも済むなら取らない。
(泥臭い方法：微分がどうしても面倒なときはとりあえず f'= (f(x+0.001)-f(x))/0.001 で計算する。0.001 のままでは精度が足りない時は適宜小さくする。)
(もっと泥臭い方法：xとx+0.001でfを計算して、そこから次はどうするか比例計算で推定する。ただし決してxを大きく変化させない)
ニュートン法ではどうもダメだという時は一時的に他の方法もよいかと思います。ただ論文の値打ちとしては計算速度も早い必要があり、私の場合ニュートン法で何とかn<10(?)で収束するよう出来るだけ粘りました。関数のクセに習熟すると何とかなるものです。

参考URL：

http://akita-nct.jp/yamamoto/lecture/2004/5E/test_2/summarize/html/node6.html

お礼

回答ありがとうございます。
ニュートン法はやはり速く収束するのですね。微分さえ手計算で早く出ればずいぶん楽なのですが・・・。
一つ加えて質問なのですが、複数解あるときには定点法、二分法、ニュートン法ともどの解に収束するか分からないと思うのですが、複数解を求める場合のコツ、あるいはどの方法がBestなどあるのでしょうか。
よろしくお願いします。