数値解析
数値解析(すうちかいせき、numerical analysis)は、計算機代数とは対照的に、数値計算によって解析学の問題を近似的に解く数学の一分野である。
(狭義には「数値解析」とは「数値計算方法」の数学的な解析・分析(mathematical analysis of numerical methods)のことであり,広義の意味=数値を使って問題の解析・分析を行う(Analysis by numerical methods)・式でなく数値で計算を行う「数値計算」(numerical computation, numerical calculation)全般とは区別される。しかし世間一般には両者はあまり区別されていない。理学工学等の分野の応用として計算を行う場合には普通は広義の意味で「数値解析」と称している。このWikipediaでも区別がなされていない。本来この頁のタイトルは「数値解析」ではなくて「数値計算」とする方が正しい。その場合の「数値計算」とは問題を解くための計算を数式を使って行うのではなくてもっぱら数値を使って行うのだという意味合いがある。)
数値解析は自然科学および工学のあらゆる分野に応用がある。計算言語学や社会統計学のように、人文科学や社会科学でも重要である。
現在知られている人類史における最初期の数学的記述の一つとして、バビロニアの粘土板 YBC 7289 を挙げることができる。YBC 7289 は正方形の対角線の長さを近似したものと考えられ、結果として \sqrt{2} の(六十進法による)近似値を含んでいる。
電子計算機(コンピュータ)の発明以前、数値計算には数表や補助的な計算機も用いられたものの、アルゴリズムの適用は人の手によるところが大きかった。
コンピュータの発明により、汎用的なプログラミングが可能になり、また人の手より速くより多くの計算を実行できるようになった。種々のアルゴリズムのプログラムが実装され、またコンピュータ自身の特性に合わせてアルゴリズムが考案されるようになった。
数値解析の目標は、難しい問題への近似解を与える技法の設計と解析である。この考え方を具体化するため、次のような問題と手法を挙げる。
気象予報には、高度な数値計算手法が不可欠である。
ロケットの軌道を計算するためには、常微分方程式の高精度な数値解が必要となる。
自動車会社は自動車事故での安全性を向上させるため、衝突のコンピュータシミュレーションを行っている。そのようなシミュレーションには、偏微分方程式の数値計算が不可欠である。
ヘッジファンドは様々な数値解析ツールを駆使し、他の市場参加者よりも正確に株やデリバティブの価値を計算しようとする。
航空会社は、チケット価格設定、航空機や乗務員のスケジュール設定、燃料補給のスケジュール設定などに洗練された最適化アルゴリズムを利用する。この分野はオペレーションズ・リサーチとも呼ばれる。
保険会社はアクチュアリー分析に数値解析プログラムを利用する。
数値的手段による解析のための計算は、コンピュータの発明以前から多くの国々で行われていた。線型補間は2000年以上前から行われている。ニュートン法、ラグランジュ補間、ガウスの消去法、オイラー法などの名称からも分かるように、歴史上の偉大な数学者の多くが数値的手段による解析にも注力した。
計算を能率化しまた計算の誤りをなるべく減らすために、公式や数表を掲載した印刷物である数表が作られた。例えば関数値を小数点以下16桁まで与える数表を使って、必要に応じて補間を行うことで、関数の精度の良い近似値を得ることができた。この分野での典型的な業績の例として、ミルトン・アブラモビッツとアイリーン・ステガンの編集したNISTの書籍などが挙げられる(通称“Abramowitz and Stegun"。これは1000ページを超えるもので、典型的な公式、計算式、近似式や関数の数表やグラフなどを多数集めている。コンピュータが利用可能になった後には数表そのものは(関数値のルーチンを作る作業者が計算値の検証に使う場合を除いて)あまり役に立つ機会がなくなったが、公式、計算式、近似式が多く集められており、今日でも数値計算分野にとっては有用性がある)。
機械式計算機やリレー式のデジタル計算機も計算のツールとして開発された。そのような計算機が1940年代に電子式のコンピュータへと進化した。デジタル式のコンピュータは数値の計算以外にも使える機材であるが、例えばENIACの開発目標は、高速な数値計算を行うための機械の実現であった。その後はさらに複雑な計算がより高速に行えるようになっている。(計算機械にはデジタル式以外にもアナログ方式のものがある。例えば計算尺は一種のアナログ式の計算デバイスであるし、機械式や電気式、電子的のアナログ方式のコンピュータもデジタル方式のコンピュータが低価格となりごく当たり前になる以前には良く用いられていた。アナログ方式の弱点は、素子の物理的な特性から決まる誤差やノイズによりある程度以上の高精度な計算を行うことが困難であることや、動作を決めるためのプログラミングは機構や回路そのもので実現するので、ストアドプログラミング方式が実現容易なデジタル方式と違って変更が素早くできないので、用途が専用機械になりがちなことである。)
直接解法は、問題の解を有限個のステップで計算する。その解は、演算精度が無限ならば正確である。例えば、線型方程式系を解くガウスの消去法やQR分解、線形計画問題のシンプレックス法などがある。実際には有限な浮動小数点数が使われるため、得られる解は近似値となる。
これに対して反復解法は一定のステップ数で完了するとは限らない。ある初期予測値から開始して、反復的に計算を行って徐々に解に収束させていく。一般にこの場合、たとえ無限の精度で計算したとしても、有限回の反復では正確な解にたどり着くことはない。例として、ニュートン法、二分法、ヤコビ法などがある。数値線形代数の大規模な問題には、反復解法が一般に必要とされる。
数値解析では、反復解法が直接解法よりも一般的である。いくつかの手法は基本的には直接解法だが、GMRES法 や共役勾配法などのように、反復解法として使うことも多い。これらの技法では厳密解を得るために必要なステップ数が大きくなるため、反復解法として近似解を利用する。
さらに、連続問題を近似的に離散問題に置き換えて解くことが必要になる。この置き換え操作を「離散化(discretization)」という。たとえば、微分方程式を解く場合が挙げられる。数値的に微分方程式を解くためには、データの数が有限でなければ現実には扱うことができない。そこでたとえば微分方程式の定義領域が連続なものであっても、そのなかから有限個の点を適切に代表点として選び、元の微分方程式をそれらの点での値についてだけの関係に置き換えて扱う。
誤差の研究は、数値解析の重要な一分野である。解に誤差が入り込む原因はいくつかある。
アルゴリズムや計算プログラムに与える入力データ自身が持つ誤差。たとえば入力するデータがそれ自身が既に丸められた値である場合。
あるいは入力する数値を指定された有限桁の浮動小数点数に丸めることでも発生する(たとえば10進数で0.1を入力してもそれをプログラムの内部で2進数にして扱うとすると,0.1は2進数で表現すれば循環小数になるから有限桁数では正確には表せず,それを内部で扱う桁数に丸めて扱うとその段階で丸め誤差が入る。2の平方根や3の自然対数、円周率などの無理数の厳密な値は10進でも2進でも無限に続く小数になるがそれらをプログラム中で有限桁数の小数として近似して扱うならその段階で既に丸め誤差が入る)。あるいは入力が測定や観測から得られるものの場合には,一般的には真の値は未知であり,データ自身が確率的な振る舞いを持った観測誤差を伴う。
有限な素子から構成されているデジタルコンピューターは内部状態の数も有限であり,1つであっても無限の情報(無限の桁数)を持ちうる実数の値を正確に表現することは一般にはできない。
また,ある決まった桁数で表された数値であっても、それらに対する四則演算の結果の値は一般には同じ桁数では正確に表わせないのでそれを決まった有限の桁数に収める(丸める)とすれば、
端数処理にともなう誤差が発生する。この誤差を丸め誤差という。丸め誤差自身は計算を倍精度で行うなど、計算に用いる数値の表現とそれらに対する演算の精度を上げることによって減らすことができる。
打ち切り誤差とは、数学的には繰り返しを無限に続けた極限では真の解を与える計算法を、無限回の操作を行うことは現実にはできないので、繰り返しをある有限回までで打ち切って得られた近似解の真の解との差である。たとえば右の欄にある 3x^3+4=28 を解く問題で、10回程度の反復では、解は約 1.99 となる。このとき打ち切り誤差は 0.01 である。一般には(丸め誤差の影響を無視すれば)反復回数を十分に増やせばこの誤差は減少する。またたとえば収束する無限級数の和を、最初のある項数までの有限部分和に置き換えた場合の誤差も、打ち切り誤差である。
コンピュータは有限個の素子からできていて一般には無限の自由度は扱えないので、本来は連続無限の自由度を持つ問題に対して何らかの近似を導入することにより有限の自由度の問題として定式化する作業のことを問題の離散化という。
たとえは微分方程式は独立変数も従属変数も連続量であるが、それに対して計算点として有限個の分点を代表として選び、微分方程式中の微分を差分で近似して置き換える「差分近似」を行うと、それにより元の微分方程式とは異なる有限個の自由度に対する差分方程式が得られる。差分方程式はテイラー展開の剰余項を微小であると仮定して無視する近似から得られるものであるから、通常その解は元の微分方程式の解には一致しない。このように離散化近似によって得られる近似解の持つ元の方程式の真の解に対する誤差のことを離散化誤差という。この種類の誤差を減らすためには、より高次の離散化近似方法をとる、近似に用いる自由度(計算点の個数)をより多くするなどの方法がある。(なお微分方程式の離散化の方法は差分法だけではなくて、問題の性質や近似手法に応じていろいろなものがある。)
上述までの誤差は、与えられたモデルを「正しく」解いているか、という観点からの誤差であるが、その対立概念として、元の基礎方程式に関して、「正しい」式を解いているか、という問題がある。例えば非線形現象を線形近似することなどがこれに相当する。これは数値解析というより、元の問題が属する科学分野の問題ではあるが、基礎方程式が誤っている(実現象のモデルとして不適切である)場合には上述の誤差を減らしても解が実現象を正しく表すとは限らないため、解の誤差評価をする際には必ず検討しなければならないことである。この検証過程では定式化や仮説における誤り、モデルの適用限界などに対する考察が必要になる。
誤差が発生すると、計算を通じてそれが伝播していく。実際、電卓やコンピュータでの(浮動小数点数の)加算は正確ではなく、反復計算をすると計算はさらに不正確になっていく。このような誤差の研究から数値的安定性の概念が生まれた。あるアルゴリズムが数値的に安定であるとは、誤差が発生・伝播したときに計算が進むにつれてその誤差があまり大きくならないことを意味する。これは問題が良条件の場合のみ可能である。良条件とは、データが少しだけ変化したとき、解も少しだけ変化するような性質を持つことを意味する。逆に問題が悪条件であれば、データに含まれる誤差は大きく成長する。
しかし、良条件の問題を解くアルゴリズムは必ずしも数値的に安定とは言えない。数値解析の技術は、良条件の問題を解く安定なアルゴリズムを見つけるためにある。例えば、2の平方根(約 1.41421)の計算は良条件問題である。この問題を解く多くのアルゴリズムは、初期近似値 x1 から開始して \sqrt{2} になるべく近い値を求めようとする。つまり、x1=1.4 として、よりよい近似値を x2、x3、…と計算していく。有名なアルゴリズムとしてバビロニアの平方根があり、この場合の式は xk+1 = xk/2 + 1/xk である。別の方法として、例えば、xk + 1 = (xk2−2)2 + xk という式を使うとする(仮に Method X とよんでおく)(x^2-2)^2+x=f(x) という方程式についての不動点反復法である。この方程式の解には \sqrt{2} もある。f(x)\geq x なので、反復は常に右方向に向かう。そのため、x_1=1.4<\sqrt{2} では収束するが、x_1=1.42>\sqrt{2} では発散する。。この2つのアルゴリズムについて、x1 = 1.4 と x1 = 1.42 の場合の反復結果の一部を以下に示す。
見ての通り、バビロニアの平方根は初期値がどうであっても素早く収束するが、Method X は初期値が1.4の時は収束が遅く、1.42を初期値にすると発散する。したがって、バビロニアの平方根は数値的に安定だが、Method X は数値的に不安定である。
近似値の計算を行うのと同時に計算に含まれる丸め誤差、打切り誤差、離散化誤差をすべて(数学的な意味で)厳密に評価する技術を精度保証付き数値計算という。
区間演算やアフィン演算のような手法では、近似値の代わりに真値を含む区間を与える。
さまざまな数値計算法について結果の精度を保証をするものにする動きが進みつつある。例えば微分方程式の分野では解析的な方法では解の存在の証明が困難な問題に対する数値的なアプローチが確立されつつある。
力学系の研究にも応用されており、有力な道具として注目されている。
20世紀後半以降、多くの数値計算アルゴリズムはコンピュータ上に向けて実装され、実行されてきた。Netlib には数値解析用の各種ルーチンのソースコードがあり、その多くはFORTRANとC言語により書かれている。各種の数値解析アルゴリズムを実装した商用ライブラリ製品としては IMSL や NAG などがある。オープンな(ソースコードが開示されていて、利用や改変の際の自由度が高い)ものの例としては GNU Scientific Library を挙げることができる。
MATLABは行列計算を中心とする数値計算用の商用プログラミング言語として有名だが、他にも商用ではSAS(統計解析用)
、SPSS(統計解析用)、S-PLUS、IDL などがある。
フリーソフトとして、「MATLAB」と互換性の高い Scilab・GNU Octave・FreeMat、「S言語」や「S-PLUS」の言語仕様に準じるR言語、SPSS の代替を目指す PSPP や gretl、そのほか(C++ライブラリ)、Pythonのライブラリ・パッケージである (SciPy、NumPy) など、様々な数値解析ソフトウェアが使われている。
性能も様々で、ベクトルや行列の演算は一般に高速だが、スカラーのループは10倍以上の差があるものもある。
Mathematica や Maple のような数式処理システム(記号処理システム)は多くの場合に浮動小数点数値の計算機能も含むので数値計算用途にも(性能や効率を問わなければ)一応は使える。SageMath は数値計算と数式処理計算の両方を備えた統合システムである。また、簡単な問題であればMicrosoft Excelなどの表計算ソフトを用いてでも扱える場合がある。
IMA Journal of Numerical Analysis
International Journal for Numerical Methods in Engineering
日本シミュレーション学会(JSST)
情報処理学会ハイパフォーマンス・コンピューティング研究会(HPC) ※ 旧「数値解析研究会」(NA)を含めて統合。
京都大学数理解析研究所 ※ 数学全般の研究所ではあるが、数値解析に関係した研究集会の開催や講究録の発行もしている。
Society for Industrial and Applied Mathematics (SIAM)
Association for Computing Machinery (ACM)
The Institute of Electrical and Electronics Engineers, Inc.(IEEE)
International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics (SCAN)