数値解析

歴史

数値的手段による解析のための計算は、コンピュータの発明以前から多くの国々で行われていた。線型補間は2000年以上前から行われている。ニュートン法、ラグランジュ補間、ガウスの消去法、オイラー法などの名称からも分かるように、歴史上の偉大な数学者の多くが数値的手段による解析にも注力した。
計算を能率化しまた計算の誤りをなるべく減らすために、公式や数表を掲載した印刷物である数表が作られた。例えば関数値を小数点以下16桁まで与える数表を使って、必要に応じて補間を行うことで、関数の精度の良い近似値を得ることができた。この分野での典型的な業績の例として、アブラモビッツとステガンの編集したNISTの書籍などが挙げられる（通称“Abramowitz and Stegun”。これは1000ページを超えるもので、典型的な公式、計算式、近似式や関数の数表やグラフなどを多数集めている。コンピュータが利用可能になった後には数表そのものは（関数値のルーチンを作る作業者が計算値の検証に使う場合を除いて）あまり役に立つ機会がなくなったが、公式、計算式、近似式が多く集められており、今日でも数値計算分野にとっては有用性がある）。
機械式計算機やリレー式のデジタル計算機も計算のツールとして開発された。そのような計算機が1940年代に電子式のコンピュータへと進化した。デジタル式のコンピュータは数値の計算以外にも使える機材であるが、例えばENIACの開発目標は、高速な数値計算を行うための機械の実現であった。その後はさらに複雑な計算がより高速に行えるようになっている。（計算機械にはデジタル式以外にもアナログ方式のものがある。例えば計算尺は一種のアナログ式の計算デバイスであるし、機械式や電気式、電子的のアナログ方式のコンピュータもデジタル方式のコンピュータが低価格となりごく当たり前になる以前には良く用いられていた。アナログ方式の弱点は、素子の物理的な特性から決まる誤差やノイズによりある程度以上の高精度な計算を行うことが困難であることや、動作を決めるためのプログラミングは機構や回路そのもので実現するので、ストアドプログラミング方式が実現容易なデジタル方式と違って変更が素早くできないので、用途が専用機械になりがちなことである。）

離散化と数値積分

2時間のレースで、自動車の速度を3回測定した結果が次表のようになっている。
時間 0:20 1:00 1:40
km/h 140 150 180
離散化とは、この場合、0:00 から 0:40 までの自動車の速度が一定とみなし、同様に 0:40 から 1:20 までと、1:20 から 2:00 までも一定とみなすことである。すると、最初の40分の走行距離は約 (2/3h x 140 km/h)=93.3 km となる。したがって、全走行距離は 93.3 km + 100 km + 120 km = 313.3 km と見積もられる。これがリーマン和を使った一種の数値積分である（走行距離は速度の積分であるため）。
悪条件問題: 関数 f(x) = 1/(x − 1) を考える。f(1.1) = 10 で f(1.001) = 1000 である。x が 0.1 の範囲内で変化したとき、f(x) は約1000も変化する。この f(x) の x = 1 での評価は悪条件問題である。
良条件問題: 対照的に関数  は連続であるため、その評価は良条件である。
直接解法は、問題の解を有限個のステップで計算する。その解は、演算精度が無限ならば正確である。例えば、線型方程式系を解くガウスの消去法やQR分解、線形計画問題のシンプレックス法などがある。実際には有限な浮動小数点数が使われるため、得られる解は近似値となる。
これに対して反復解法は一定のステップ数で完了するとは限らない。ある初期予測値から開始して、反復的に計算を行って徐々に解に収束させていく。一般にこの場合、たとえ無限の精度で計算したとしても、有限回の反復では正確な解にたどり着くことはない。例として、ニュートン法、二分法、ヤコビ法などがある。数値線型代数の大規模な問題には、反復解法が一般に必要とされる。
数値解析では、反復解法が直接解法よりも一般的である。いくつかの手法は基本的には直接解法だが、GMRES法 や共役勾配法などのように、反復解法として使うことも多い。これらの技法では厳密解を得るために必要なステップ数が大きくなるため、反復解法として近似解を利用する。

離散化

さらに、連続問題を近似的に離散問題に変換して解くことも必要となる。この変換過程を「離散化（discretization）」という。例えば、微分方程式を解く場合が挙げられる。微分方程式を数値的に解くには、有限長のデータでなければならず、定義域が連続であっても、有限個の点を選んで値を計算する。

誤差の発生と伝播

誤差の研究は、数値解析の重要な一分野である。解に誤差が入り込む原因はいくつかある。

丸め誤差

全てのデジタルコンピュータのモデルである有限状態機械では、数値を有限の桁数で表現するためあらゆる実数を正確に表現するのは不可能であり、端数処理にともなう誤差が発生する。この誤差を丸め誤差という。この誤差は計算を倍精度で行うなど、コンピュータの計算精度を上げることによって減らすことができる。

打ち切り誤差

打ち切り誤差は、反復解法で本来は無限に繰り返す反復を中途で打ち切ったために発生する近似解と厳密解の差である。例えば右の欄にある  を解く問題で、10回程度の反復では、解は約 1.99 となる。このとき打ち切り誤差は 0.01 である。一般に反復回数をより多くとればこの誤差は減少する。

離散化誤差

多くの問題では基礎方程式は微分方程式である。連続量で表される微分方程式に離散化近似を行うと、元の式と異なる差分方程式が得られる。差分方程式はテイラー展開の高次微小量を無視して得られるため、その解も元の微分方程式の解と正確には一致しない。このように離散化によって発生する誤差を離散化誤差という。この誤差を減らすには、より高次の離散化方法をとる、計算点の個数をできるだけ多くするなどの方法がある。

モデリング誤差

上述までの誤差は、与えられたモデルを「正しく」解いているか、という観点からの誤差であるが、その対立概念として、元の基礎方程式に関して、「正しい」式を解いているか、という問題がある。例えば非線形現象を線形近似することなどがこれに相当する。これは数値解析というより、元の問題が属する科学分野の問題ではあるが、基礎方程式が誤っている（実現象のモデルとして不適切である）場合には上述の誤差を減らしても解が実現象を正しく表すとは限らないため、解の誤差評価をする際には必ず検討しなければならないことである。この検証過程では定式化や仮説における誤り、モデルの適用限界などに対する考察が必要になる。

精度保証付き数値計算

近似値の計算をすると同時に計算に含まれる丸め誤差、打切り誤差、離散化誤差をすべて（数学的な意味で）厳密に評価する技術を精度保証付き数値計算という。
計算する際は数を区間に置き換えて計算(区間演算) し、真値を含む区間を結果として出力する。
精度を保証するという観点から数値計算法全般を見直す動きが数値計算の各方面で起こっている。例えば微分方程式の分野では解の存在証明が困難な解析学上の問題
に対する数値的アプローチが確立されつつある。現代では力学系の研究にも応用されており、有力な道具として注目されている。

研究分野

数値解析は、解こうとしている問題によっていくつかの分野に分かれる。

補間、補外、回帰

補間が役立つのは、ある未知の関数のいくつかの点の値があるとき、それら以外の中間点でのその関数の値を求める場合である。単純な手法としては線型補間があり、既知の点の間で関数が線型に変化するとみなすものである。これを一般化した多項式補間はもっと正確となることが多いが、ルンゲ現象に悩まされることもある。その他の補間手法としてはスプラインやウェーブレットといった局所化関数を使うものがある。
補外は補間とよく似ているが、未知の関数の値が判っている点の外側の点について値を求めることをいう。
回帰も類似した手法だが、既存のデータが不正確であることを考慮する。いくつかの点とその値があり、それらデータが誤差を含みつつ何らかの関数に従っているとして、その未知の関数を決定する。このための手法として、最小二乗法がよく知られている。

方程式、方程式系の解

基本的な問題のひとつとして、与えられた方程式の解を計算する問題がある。その方程式が線型か否かによって手法が分類される。例えば、 は線型だが、 は線型ではない。
線型方程式系を解く手法については研究が進んでいる。標準的な直接解法としては何らかの行列分解を使うものがあり、ガウスの消去法、LU分解、対称行列やエルミート行列に関するコレスキー分解、非正方行列に関するQR分解がある。反復解法としては、ヤコビ法、ガウス＝ザイデル法、SOR法、共役勾配法があり、大規模な方程式系でよく使われる。
非線型方程式には求根アルゴリズムが用いられる（根とは、関数がゼロとなる変数の値を意味する）。関数が可微分で導関数が分かっている場合には、ニュートン法が利用されることが多い。他にも線型化などの手法がある。

固有値と特異値

固有値分解や特異値分解も重要な問題である。例えば、Spectral Image Compression は特異値分解に基づいたアルゴリズムである。これに対応した統計学のツールを主成分分析という。例えば、World Wide Web上での話題トップ100を自動的に抽出し、各Webページをどの話題に属するか分類するといった作業で使われる。

最適化問題

最適化問題は、与えられた関数が最大（または最小）になる点を問う問題である。多くの場合、解は何らかの制約条件を満たさなければならない。
最適化問題はさらに、関数や制約の形式によっていくつかに分類される。例えば、線形計画問題は関数と制約が共に線型である場合を扱う。線形計画問題の主な解法として、シンプレックス法などを挙げることができる。
ラグランジュの未定乗数法は、制約条件のある最適化問題を制約のない問題に変換するために用いられる。

積分

数値積分（数値的求積法）は、定積分の値を求めるものである。一般的手法としては、ニュートン・コーツの公式を使った手法（中点法やシンプソンの公式）やガウスの求積法、二重指数関数型数値積分公式などがある。これらは分割統治戦略に基づくもので、大きな集合についての積分を小さな集合の積分に分割して値を求める。高次元になるとこれらの手法は計算の手間が膨大となるため、モンテカルロ法などの手法が使われる。

微分方程式

数値解析では、微分方程式（常微分方程式や偏微分方程式）を（近似的に）解く問題も扱う。
偏微分方程式を解くには、まず方程式を離散化し、有限次元の部分空間で計算を行う。そのような手法として、有限要素法、差分法、特に工学分野で使われる有限体積法などを挙げることができる。これらの手法は関数解析学の定理などに基づいている。これによって、問題を代数方程式の求根に還元することができる。

ソフトウェア

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、そのほかIT++（C++ライブラリ）、Pythonの派生品 (SciPy、NumPy) など、様々な数値解析ソフトウェアが使われている。
性能も様々で、ベクトルや行列の演算は一般に高速だが、スカラーのループは10倍以上の差があるものもある。
Mathematica や Maple のような数式処理システムの多くは数値計算に使うこともできる。Sage は数値計算と数式処理計算の両方を備えた統合システムである。また、簡単な問題ならば表計算ソフトでも取り扱えることがある。

関連文献

狭義では数値解析と数値計算は異なるが、両者を区別しないことにする。