eliyaの日記

■[研究ツール]非線形方程式を解くアルゴリズム 00:42

ふつう、経済モデルのモデルの一階条件は連立非線型方程式になります。計算機で非線型方程式を解くアルゴリズムはいくつかありますが、ユーザーの視点に立って比較した結果をメモしておきます。

方程式の数がひとつの場合

この場合は、確実に答えを得られるアルゴリズムがたくさんある。検討基準は早さと頑健さと実装の容易さになる。

二分法(Bisection)

実装が容易でかつ収束が保証されている。比較的遅い。符号の異なる二点が入力として必要。

割線法(Secant Method)

二分法よりかなり早い。入力点は符号が異なっていなくてもよい。二分法より不安定。Ridderの方法かBrentの方法のほうが優れている。

Regula Falsi法とRidderの方法

Ridderの方法はRegula Falsi法を改善したもの。符合の異なる二点が入力として必要。実装が簡単な割には、Brentの方法並みに早くて頑健。

Brentの方法

上記の方法を賢く組み合わせたもの。これも早くて収束が保証されている。実装は比較的複雑。経済学の論文でよく見る気がする。

ニュートン法

すごく早い。一回のイテレーションで有効数字が倍になる。入力は一点でよい。でも、一階微分を入力に与える必要があり、さらに大域的な頑健性に欠ける。上記の方法で得られた解の有効数字をあげるために最後に使うことも考えられる。

多項式を解く場合

いろいろ賢いアルゴリズムがあるらしい。

複数の方程式を同時に解く場合

一方程式のばあいと異なり、難しい。よいアルゴリズムはない。一般に、最大化問題を解くよりも難しい。最大化問題を解くのは一階条件の連立方程式を解くのと同じように思えるが、最大化問題から導かれた一階条件はさまざまな条件を満たすので、その特性を生かして比較的簡単に解ける。

ニュートン法

利点と欠点は一方程式の場合と同じ。大域的な収束性が悪いのでline searchやtrust region法を使って改善することもできる。計算が大変な微分(ヤコビ行列)とその逆行列が必要なので、擬ニュートン法(Broyden's method)で途中での計算量を減らすこともできる。詳しくは次の二つの本、Newton Methods for Nonlinear ProblemあるいはNumerical Methods for Unconstrained Optimization and Nonlinear Equationsを参考のこと。

参考文献

Numerical Recipes: The Art of Scientific Computing ：第三版 　2007年発行

ニューメリカルレシピ・イン・シー 日本語版―C言語による数値計算のレシピ： 第二版　1993年発行

Numerical Recipes, Second Edition (1992) 英語版の第二版なら無料で読めます。