数値解析

出典: Wikipedio

数値解析（すうちかいせき、Numerical Analysis）は、数学および物理学の一分野で、代数的に解を得ることが不可能な解析学上の問題を近似的に解く手法に関する学問。

史上最初の数学的記述の一つとして、バビロニアの粘土板 YBC 7289 を挙げることができる。これは六十進法で <math>\sqrt{2}</math> （単位矩形の対角線の長さ）を数値的に近似したものである<ref>Photograph, illustration, and description of the root(2) tablet from the Yale Babylonian Collection</ref>。三角形の辺の長さを計算できること（そして、平方根を計算できること）は、特に建築において重要である。例えば、縦横それぞれ2メートルの正方形の壁の対角線は <math>\sqrt{8} \approx 2.83</math> メートルとなる<ref>ピタゴラスの定理によれば、各辺が2メートルの正方形の対角線の長さは <math>\sqrt{2^2+2^2}=\sqrt{8}</math> メートルとなる。</ref>。

数値解析は、このような実用的計算の長い伝統に続くものである。バビロニアの <math>\sqrt{2}</math> の近似のように、現代の数値解析も正確な解を求めようとするものではない。何故なら、正確な解を有限時間で求めることは不可能だからである。その代わりに、数値解析の多くは、ある程度の誤差の範囲内の近似解を求めようとする。

数値解析は自然科学および工学のあらゆる分野で応用され、21世紀に入ってからは生命科学や芸術にも科学技術計算が利用されるようになってきた。常微分方程式は天体（惑星、恒星、小宇宙）の軌道の計算に登場する。資産管理には最適化が利用されている。数値線型代数はデータ解析に不可欠である。確率微分方程式とマルコフ連鎖は、医学や生物学における生体細胞のシミュレーションの基本である。

コンピュータが発明される以前、数値的な手法は巨大な数表を使った手計算での内挿によるものが多かった。コンピュータの発達以降は数表が使われることはほとんどなくなり、コンピュータで必要な関数を必要な精度で計算できるようになった。内挿アルゴリズムは、微分方程式などを解く際に現在でも使用されている。

概要

数値解析の目標は、難しい問題への近似解を与える技法の設計と解析である。この考え方を具体化するため、次のような問題と手法を挙げる。

• 気象予報には、高度な数値計算手法が不可欠である。
• ロケットの軌道を計算するためには、常微分方程式の高精度な数値解が必要となる。
• 自動車会社は自動車事故での安全性を向上させるため、衝突のコンピュータシミュレーションを行っている。そのようなシミュレーションには、偏微分方程式の数値計算が不可欠である。
• ヘッジファンドは様々な数値解析ツールを駆使し、他の市場参加者よりも正確に株やデリバティブの価値を計算しようとする。
• 航空会社は、チケット価格設定、航空機や乗務員のスケジュール設定、燃料補給のスケジュール設定などに洗練された最適化アルゴリズムを利用する。この分野はオペレーションズ・リサーチとも呼ばれる。
• 保険会社はアクチュアリー分析に数値解析プログラムを利用する。

歴史

数値解析は、コンピュータの発明以前から多くの国々で行われていた。線型補間は2000年以上前から行われている。ニュートン法、ラグランジュ補間、ガウスの消去法、オイラー法などの名称からも分かるように、歴史上の偉大な数学者の多くは数値解析に夢中だった。

計算を手で行うため、方程式と数表を掲載した分厚い書籍が生み出された。例えば、関数の小数点以下16桁まで計算された数表を使って、与えられた方程式にその値を代入し、関数の正確な近似値を得ることができた。この分野での正統的な業績として、Abramowitz と Stegun が編集したNISTの書籍などを挙げることができる。これは1000ページを超えるもので、典型的な方程式や関数の数表を多数集めている。コンピュータが利用可能になると数表はあまり役に立たなくなったが、方程式を多数集めている点では有用である。

機械式計算機も計算ツールとして開発された。そのような計算機が1940年代に電子式コンピュータへと進化し、コンピュータは数値解析以外にも使えることが明らかとなっていった。しかし、コンピュータの発明は数値解析を目的としていたことは間違いなく、その後はさらに複雑な計算が行えるようになっている。

直接解法と反復解法

時間  0:20 1:00 1:40
km/h  140  150  180 

直接解法は、問題の解を有限個のステップで計算する。その解は、演算精度が無限ならば正確である。例えば、線型方程式系を解くガウスの消去法やQR分解、線形計画問題のシンプレックス法などがある。実際には有限な浮動小数点数が使われるため、得られる解は近似値となる。

これに対して反復解法は一定のステップ数で完了するとは限らない。ある初期予測値から開始して、反復的に計算を行って徐々に解に収束させていく。一般にこの場合、たとえ無限の精度で計算したとしても、有限回の反復では正確な解にたどり着くことはない。例として、ニュートン法、二分法、ヤコビ法などがある。数値線型代数の大規模な問題には、反復解法が一般に必要とされる。

数値解析では、反復解法が直接解法よりも一般的である。いくつかの手法は基本的には直接解法だが、GMRES法 や共役勾配法などのように、反復解法として使うことも多い。これらの技法では厳密解を得るために必要なステップ数が大きくなるため、反復解法として近似解を利用する。

離散化

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

誤差の発生と伝播

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

丸め

全てのデジタルコンピュータのモデルである有限状態機械では、あらゆる実数を正確に表現するのは不可能であるため、丸め誤差が発生する。

打ち切り誤差と離散化誤差

打ち切り誤差は、反復解法で本来は無限に繰り返す反復を中途で打ち切ったときに発生する近似解と厳密解の差である。また、離散化近似を行って得た問題の解は元の連続問題の解とは正確に一致しない。このため、離散化によって離散化誤差が発生する。例えば右の欄にある <math>3x^3+4=28</math> を解く問題で、10回程度の反復では、解は約 1.99 となる。このとき打ち切り誤差は 0.01 である。

誤差が発生すると、計算を通じてそれが伝播していく。実際、電卓やコンピュータでの（浮動小数点数の）加算は正確ではない。そして、a+b+c+d+e のような計算はさらに不正確になっていく。

数値的安定性と良条件性

このような誤差の研究から数値的安定性の概念が生まれた。あるアルゴリズムが数値的に安定であるとは、誤差が発生したときに計算によってその誤差があまりにも大きくならないことを意味する。これは問題が良条件の場合のみ可能である。良条件とは、データが少しだけ変化したとき、解も少しだけ変化するような性質を持つことを意味する。逆に問題が悪条件であれば、データに含まれる誤差は大きく成長する。

しかし、良条件の問題を解くアルゴリズムは必ずしも数値的に安定とは言えない。数値解析の技術は、良条件の問題を解く安定なアルゴリズムを見つけるためにある。例えば、2の平方根（約 1.41421）の計算は良条件問題である。この問題を解く多くのアルゴリズムは、初期近似値 x₁ から開始して <math>\sqrt{2}</math> になるべく近い値を求めようとする。つまり、x₁=1.4 として、よりよい近似値を x₂、x₃、…と計算していく。有名なアルゴリズムとしてバビロニアの平方根があり、この場合の式は x_k+1 = x_k/2 + 1/x_k である。別の Method X では x_{k + 1} = (x_k²−2)² + x_k という式を使う<ref>これは <math>x=(x^2-2)^2+x=f(x)</math> という方程式についての不動点反復法である。この方程式の解には <math>\sqrt{2}</math> もある。<math>f(x)\geq x</math> なので、反復は常に右方向に向かう。そのため、<math>x_1=1.4<\sqrt{2}</math> では収束するが、<math>x_1=1.42>\sqrt{2}</math> では発散する。</ref>。この2つのアルゴリズムについて、x₁ = 1.4 と x₁ = 1.42 の場合の反復結果の一部を以下に示す。

見ての通り、バビロニアの平方根は初期値がどうであっても素早く収束するが、Method X は初期値が1.4の時は収束が遅く、1.42を初期値にすると発散する。したがって、バビロニアの平方根は数値的に安定だが、Method X は数値的に不安定である。

研究分野

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

関数の値の計算

最も単純な問題は、関数のある点での値を求めることである。単純に数式に値を代入する直接的な手法は、効率的でないこともある。多項式の場合、ホーナー法を使うことで乗算と加算の回数を減らすことができる。一般に、浮動小数点演算を使うことで生じる丸め誤差を予測して制御することが重要となる。

補間、補外、回帰

補間が役立つのは、ある未知の関数のいくつかの点の値があるとき、それら以外の中間点でのその関数の値を求める場合である。単純な手法としては線型補間があり、既知の点の間で関数が線型に変化するとみなすものである。これを一般化した多項式補間はもっと正確となることが多いが、ルンゲ現象に悩まされることもある。その他の補間手法としてはスプラインやウェーブレットといった局所化関数を使うものがある。

補外は補間とよく似ているが、未知の関数の値が判っている点の外側の点について値を求めることをいう。

回帰も類似した手法だが、既存のデータが不正確であることを考慮する。いくつかの点とその値があり、それらデータが誤差を含みつつ何らかの関数に従っているとして、その未知の関数を決定する。このための手法として、最小二乗法がよく知られている。

方程式、方程式系の解

基本的な問題のひとつとして、与えられた方程式の解を計算する問題がある。その方程式が線型か否かによって手法が分類される。例えば、<math>2x+5=3</math> は線型だが、<math>2x^2+5=3</math> は線型ではない。

線型方程式系を解く手法については研究が進んでいる。標準的な直接解法としては何らかの行列分解を使うものがあり、ガウスの消去法、LU分解、対称行列やエルミート行列に関するコレスキー分解、非正方行列に関するQR分解がある。反復解法としては、ヤコビ法、ガウス＝ザイデル法、SOR法、共役勾配法があり、大規模な方程式系でよく使われる。

非線型方程式には求根アルゴリズムが用いられる（根とは、関数がゼロとなる変数の値を意味する）。関数が可微分で導関数が分かっている場合には、ニュートン法が利用されることが多い。他にも線型化などの手法がある。

固有値と特異値

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

最適化問題

Template:Main 最適化問題は、与えられた関数が最大（または最小）になる点を問う問題である。多くの場合、解は何らかの制約条件を満たさなければならない。

最適化問題はさらに、関数や制約の形式によっていくつかに分類される。例えば、線形計画問題は関数と制約が共に線型である場合を扱う。線形計画問題の主な解法として、シンプレックス法などを挙げることができる。

ラグランジュの未定乗数法は、制約条件のある最適化問題を制約のない問題に変換するために用いられる。

積分

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

微分方程式

数値解析では、微分方程式（常微分方程式や偏微分方程式）を（近似的に）解く問題も扱う。

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

主な手法

• 数列 - 階差、総和、極限、補間、多項式補間、線形補間、ニュートン補間、ガウス補間、ラグランジュ補間、逆補間、エルミート補間、最小二乗法、スプライン補間、曲線あてはめ、要素内補間､有理関数補間、多次元補間、補外、エイトケン補外、リチャードソン補外
• 微分 - 接線、差分、高速微分法、関数近似、漸近展開、テイラー展開、線型近似、最良近似、チェビシェフ近似、直交多項式近似、有理関数近似

• 積分 - 取り尽くし法、台形公式、シンプソンの公式、ニュートン・コーツの公式、ガウス求積、ロンバーグ積分法（リチャードソン補外）、変数変換に基づく公式（IMT公式、二重指数型関数変換公式等）、振動積分、オイラーの和公式、グレゴリ積分公式、特異性の分離、除去、低減、複素積分路の選択、変更、適応型積分法（自動積分）、乱択アルゴリズム、乱数列、擬似乱数、線形合同法、M系列、メルセンヌ・ツイスタ、モンテカルロ法、メトロポリス法
• 代数方程式
  • ベクトル空間 - 線型写像、線型結合、直交化、グラム・シュミットの正規直交化法、修正グラム・シュミット法、ギブンス回転、ハウスホルダー変換、QR分解
  • 線型方程式 - 線型方程式系、ガウス消去法、LU分解、コレスキー分解、修正コレスキー分解、ブロックLU分解、帯LU分解、スカイライン法、ADI法、スパースLU分解、ヤコビ法、ガウス・ザイデル法、SOR法、共役勾配法、GMRES法、クリロフ部分空間法、条件数、前処理行列、チェビシェフ反復法
  • 非線型方程式 - 解の公式、求根アルゴリズム、スツルムの定理、ホーナー法、減次、二分法、割線法、ニュートン法、逆補間法、ブロイデン法、ベアストウ法、商差法、レーマー法、スミスの定理、複素平面内の二分法（四分法）、平野法、デュラン・カーナー法、ホモトピー法、随伴行列（コンパニオン）法、固有値、スペクトル半径、ケイリー・ハミルトンの定理、対角化、ヤコビ法、三重対角化、ヘッセンベルグ化、QR法、フランシスの複素ヘッセンベルグQR法、実ヘッセンベルグ二重QR法、冪乗法、逆反復法、部分空間法、同時逆反復法、ランチョス法、クリロフ部分空間法、フィルタ対角化法、ホモトピ－法、分割統治法、摂動級数法、特異値分解、擬似逆行列、最適化問題、極値、線形計画問題、双対問題、線形計画法、シンプレックス法、楕円体法、内点法、非線形計画法、ラグランジュの未定乗数法、最急降下法、直線探索法、共役勾配法、メタヒューリスティクス、局所探索法、焼きなまし法（メトロポリス法）、遺伝的アルゴリズム
• 関数方程式
  • 変分法 - 重み付き残差法、ガラーキン法、レイリー・リッツ法
  • 微分方程式
    • 常微分方程式 - オイラー法、 ミルン法、ルンゲ・クッタ法、シンプレクティック法、シンメトリック法、繰返し法（松野法、変形松野法、リープフロッグ・台形法、リープフロッグ・後方差分法）、グラッグ法（リチャードソン補外）、予測子修正子法、ピカールの逐次近似法、射撃法、ラプラス変換法、高階（2,3階）方程式専用の公式、刻み幅の制御、適応型積分法、CFL条件
    • 偏微分方程式 - 差分法、有限要素法、有限体積法、代用電荷法、等角写像法、グリーン関数法、スペクトル法、モンテカルロ法、セル法、全保存型数値積分法、p版有限要素法、メッシュフリー法、メッシュ生成、マルチグリッド法、領域分割法
    • フーリエ級数 - 高速フーリエ変換、離散コサイン変換、畳み込み、ウェーブレット変換、離散ウェーブレット変換、スペクトル法
    • ラプラス変換 - 多重極展開法
  • 積分方程式 - 境界要素法、グリーン関数法
• 統計学 - 統計量、確率分布、多変量解析
• 数値的安定性 - 任意精度演算、精度保証

ソフトウェア

Template:Main 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倍以上の差があるものもある。<ref>Speed comparison of various number crunching packages</ref>

Mathematica や Maple のような数式処理システムの多くは数値解析にも使える。Sage は数値解析と数式処理の両方を備えた統合システムである。また、簡単な問題なら表計算ソフトでも解くことが可能である。

関連項目

• 数 - コンピュータの数値表現、位取り記数法、指数表記、固定小数点数、浮動小数点数、任意精度演算、算術演算、端数処理、近似値、誤差、正確度と精度
• アルゴリズム
• 計算科学
• シミュレーション
• 数値解析ソフトウェア
• 和算

脚注

Template:Reflist

参考文献

• Trefethen, Lloyd N. (2006). "Numerical analysis", 20 pages. To appear in: Timothy Gowers and June Barrow-Green (editors), Princeton Companion of Mathematics, Princeton University Press.

外部リンク

Template:Spedia

• Scientific computing FAQ
• Numerical analysis DMOZ category
• Numerical Computing Resources on the Internet - a list maintained by Indiana University Stat/Math Center
• Java Number Cruncher 典型的数値解析アルゴリズムのダウンロード可能なコード例と実行可能なアプレットがある。
• Numerical Analysis Project by John H. Mathews
• Alternatives to Numerical Recipes

Template:数学af:Numeriese analise ar:تحليل عددي cs:Numerická matematika da:Numerisk analyse de:Numerische Mathematik en:Numerical analysis eo:Cifereca analitiko es:Análisis numérico fa:آنالیز عددی fi:Numeerinen analyysi fr:Analyse numérique he:אנליזה נומרית hi:आंकिक विश्लेषण hu:Newton-módszer it:Analisi numerica ka:რიცხვითი ანალიზი ko:수치 해석 nl:Numerieke wiskunde pl:Analiza numeryczna pt:Análise numérica ro:Analiză numerică ru:Вычислительная математика sr:Нумеричка анализа su:Analisis numeris sv:Beräkningsvetenskap uk:Обчислювальна математика zh:数值分析