数値解析

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索
ファイル:Ybc7289-bw.jpg
バビロニアの粘土板 YBC 7289 （紀元前1800-1600年頃）
2の平方根の近似値は60進法で4桁、10進法では約6桁に相当する。1 + 24/60 + 51/602 + 10/603 = 1.41421296... [1]。(Image by Bill Casselman)

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

史上最初の数学的記述の一つとして、バビロニアの粘土板 YBC 7289 を挙げることができる。これは六十進法で <math>\sqrt{2}</math> （単位矩形の対角線の長さ）を数値的に近似したものである[1]。三角形の辺の長さを計算できること（そして、平方根を計算できること）は、特に建築において重要である。例えば、縦横それぞれ2メートルの正方形の壁の対角線は <math>\sqrt{8} \approx 2.83</math> メートルとなる[2]。

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

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

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

概要

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

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

歴史

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

計算を能率化しまた計算の誤りをなるべく減らすために、公式や数表を掲載した印刷物である数表が作られた。例えば関数値を小数点以下16桁まで与える数表を使って、必要に応じて補間を行うことで、関数の精度の良い近似値を得ることができた。この分野での典型的な業績の例として、Abramowitz と Stegun の編集したNISTの書籍などが挙げられる（これは1000ページを超えるもので、典型的な公式，計算式、近似式や関数の数表やグラフなどを多数集めている。コンピュータが利用可能になった後には数表そのものは（関数値のルーチンを作る作業者が計算値の検証に使う場合を除いて）あまり役に立つ機会がなくなったが、公式，計算式、近似式が多く集められており，今日でも数値計算分野にとっては有用性がある）。

機械式計算機やリレー式のデジタル計算機も計算のツールとして開発された。そのような計算機が1940年代に電子式のコンピュータへと進化した。デジタル式のコンピュータは数値の計算以外にも使える機材であるが、たとえばENIACの開発目標は、高速な数値計算を行うための機械の実現であった。その後はさらに複雑な計算がより高速に行えるようになっている。（計算機械にはデジタル式以外にもアナログ方式のものがある．例えば計算尺は一種のアナログ式の計算デバイスであるし，機械式や電気式、電子的のアナログ方式のコンピュータもデジタル方式のコンピュータが低価格となりごく当たり前になる以前には良く用いられていた．アナログ方式の弱点は，素子の物理的な特性から決まる誤差やノイズによりある程度以上の高精度な計算を行うことが困難であることや，動作を決めるためのプログラミングは機構や回路そのもので実現するので，ストアドプログラミング方式が実現容易なデジタル方式と違って変更が素早くできないので，用途が専用機械になりがちなことである．）

直接解法と反復解法

直接解法と反復解法

次の式を x について解くことを考える。

3x3+4=28
直接解法
  3x3 + 4 = 28
4を引く 3x3 = 24
3で割る x3 = 8
立方根を求める x = 2

反復解法では、f(x) = 3x3 + 4 に二分法を適用する。初期値として a = 0 と b = 3 を使うと、f(a) = 4、f(b) = 85 である。

反復解法
a b mid f(mid)
0 3 1.5 14.125
1.5 3 2.25 38.17...
1.5 2.25 1.875 23.77...
1.875 2.25 2.0625 30.32...

ここまでで、解は 1.875 と 2.0625 の間にあるとわかる。このアルゴリズムでは、誤差 0.2 未満でこの範囲にある任意の値を返す。

離散化と数値積分

125px

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 での評価は悪条件問題である。

良条件問題: 対照的に関数 <math>f(x)=\sqrt{x}</math> は連続であるため、その評価は良条件である。

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

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

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

離散化

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

誤差の発生と伝播

テンプレート:See also 誤差の研究は、数値解析の重要な一分野である。解に誤差が入り込む原因はいくつかある。

丸め誤差

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

打ち切り誤差

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

離散化誤差

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

モデリング誤差

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

数値的安定性と良条件性

誤差が発生すると、計算を通じてそれが伝播していく。実際、電卓やコンピュータでの（浮動小数点数の）加算は正確ではなく、反復計算をすると計算はさらに不正確になっていく。このような誤差の研究から数値的安定性の概念が生まれた。あるアルゴリズムが数値的に安定であるとは、誤差が発生・伝播したときに計算が進むにつれてその誤差があまり大きくならないことを意味する。これは問題が良条件の場合のみ可能である。良条件とは、データが少しだけ変化したとき、解も少しだけ変化するような性質を持つことを意味する。逆に問題が悪条件であれば、データに含まれる誤差は大きく成長する。

しかし、良条件の問題を解くアルゴリズムは必ずしも数値的に安定とは言えない。数値解析の技術は、良条件の問題を解く安定なアルゴリズムを見つけるためにある。例えば、2の平方根（約 1.41421）の計算は良条件問題であるテンプレート:要出典。この問題を解く多くのアルゴリズムは、初期近似値 x1 から開始して <math>\sqrt{2}</math> になるべく近い値を求めようとする。つまり、x1=1.4 として、よりよい近似値を x2、x3、…と計算していく。有名なアルゴリズムとしてバビロニアの平方根があり、この場合の式は xk+1 = xk/2 + 1/xk である。別の方法として、 たとえば、xk + 1 = (xk 2−2)2 + xk という式を使うとする(仮に Method X とよんでおく)[4]。この2つのアルゴリズムについて、x1 = 1.4 と x1 = 1.42 の場合の反復結果の一部を以下に示す。

バビロニア バビロニア Method X Method X
x1 = 1.4 x1 = 1.42 x1 = 1.4 x1 = 1.42
x2 = 1.4142857... x2 = 1.41422535... x2 = 1.4016 x2 = 1.42026896
x3 = 1.414213564... x3 = 1.41421356242... x3 = 1.4028614... x3 = 1.42056...
... ...
x1000000 = 1.41421... x28 = 7280.2284...

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

研究分野

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

関数の値の計算

補間: 気温の観測値が1:00には20℃、3:00には14℃だったとする。このデータを線型補間すると、2:00の気温は17℃、1:30の気温は18.5℃となる。

補外: ある国の国内総生産が毎年平均5%伸びていて、昨年の値が1000億ドルだったとする。ここで補外すると、今年は1050億ドルとなる。

線型回帰の例

回帰: 線型回帰では、n 個の点が与えられたとき、それら n 個の点のなるべく近くを通る直線を求める。

グラス1杯のレモネードの値段は?

最適化: レモネード売りがレモネードを売っている。1杯1ドルでは、1日に197杯売れる。1杯あたり1セント値段を上げると、1日に売れるレモネードは1杯減る。1杯を1.485ドルにすると売り上げが最大となるが、1セント未満を使った値段は付けられないので、1.49ドルにすると一日の最大売り上げ 220.52 ドルが得られる。

微分方程式: ある部屋で一方からもう一方へ空気が流れるように100個の扇風機を配置し、羽根をそこに落としてみる。何が起きるだろうか? 羽根は空気の流れに従って漂うが、非常に複雑な動きになるかもしれない。その近似としては、羽根が漂っている付近の空気の速度を1秒おきに測定し、シミュレートされた羽根が1秒間は測定された方向にその速度で進むと仮定する。このような手法をオイラー法と呼び、常微分方程式を解くのに使われる。

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

補間、補外、回帰

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

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

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

方程式、方程式系の解

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

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

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

固有値と特異値

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

最適化問題

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

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

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

積分

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

微分方程式

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

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

主な手法

ソフトウェア

テンプレート: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倍以上の差があるものもある。[6]

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

関連項目

脚注

テンプレート:Reflist

参考文献

外部リンク

テンプレート:Spedia

テンプレート:数学
  1. ↑ Photograph, illustration, and description of the root(2) tablet from the Yale Babylonian Collection
  2. ↑ ピタゴラスの定理によれば、各辺が2メートルの正方形の対角線の長さは <math>\sqrt{2^2+2^2}=\sqrt{8}</math> メートルとなる。
  3. ↑ テンプレート:Cite
  4. ↑ これは <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> では発散する。
  5. ↑ The Singular Value Decomposition and Its Applications in Image Compression
  6. ↑ Speed comparison of various number crunching packages
「http://wikippe.e-do-match.com/index.php?title=数値解析&oldid=9812」から取得