Loading AI tools
代数的な方法で解を得ることが不可能な解析学上の問題を数値によって近似的に解く手法に関する学問 ウィキペディアから
数値解析（すうちかいせき、英: numerical analysis）は、計算機代数とは対照的に、数値計算によって解析学の問題を近似的に解く数学の一分野である。 （狭義には「数値解析」とは「数値計算方法」の数学的な解析・分析（mathematical analysis of numerical methods）のことであり，広義の意味＝数値を使って問題の解析・分析を行う（Analysis by numerical methods）・式でなく数値で計算を行う「数値計算」（numerical computation, numerical calculation)全般とは区別される。しかし世間一般には両者はあまり区別されていない。理学工学等の分野の応用として計算を行う場合には普通は広義の意味で「数値解析」と称している。このWikipediaでも区別がなされていない。本来この頁のタイトルは「数値解析」ではなくて「数値計算」とする方が正しい。その場合の「数値計算」とは問題を解くための計算を数式を使って行うのではなくてもっぱら数値を使って行うのだという意味合いがある。）
数値解析は自然科学および工学のあらゆる分野に応用がある。計算言語学[1]や社会統計学[2]のように、人文科学や社会科学でも重要である。
現在知られている人類史における最初期の数学的記述の一つとして、バビロニアの粘土板 YBC 7289 を挙げることができる。YBC 7289 は正方形の対角線の長さを近似したものと考えられ、結果として の（六十進法による）近似値を含んでいる[3]。
電子計算機（コンピュータ）の発明以前、数値計算には数表や補助的な計算機も用いられたものの、アルゴリズムの適用は人の手によるところが大きかった。 コンピュータの発明により、汎用的なプログラミングが可能になり、また人の手より速くより多くの計算を実行できるようになった。種々のアルゴリズムのプログラムが実装され、またコンピュータ自身の特性に合わせてアルゴリズムが考案されるようになった[4]。
数値解析の目標は、難しい問題への近似解を与える技法の設計と解析である。この考え方を具体化するため、次のような問題と手法を挙げる。
数値的手段による解析のための計算は、コンピュータの発明以前から多くの国々で行われていた。線型補間は2000年以上前から行われている。ニュートン法、ラグランジュ補間、ガウスの消去法、オイラー法などの名称からも分かるように、歴史上の偉大な数学者の多くが数値的手段による解析にも注力した[4]。
計算を能率化しまた計算の誤りをなるべく減らすために、公式や数表を掲載した印刷物である数表が作られた。例えば関数値を小数点以下16桁まで与える数表を使って、必要に応じて補間を行うことで、関数の精度の良い近似値を得ることができた。この分野での典型的な業績の例として、アブラモビッツとステガンの編集したNISTの書籍などが挙げられる（通称“Abramowitz and Stegun”。これは1000ページを超えるもので、典型的な公式、計算式、近似式や関数の数表やグラフなどを多数集めている。コンピュータが利用可能になった後には数表そのものは（関数値のルーチンを作る作業者が計算値の検証に使う場合を除けば）役に立つ機会はほとんどなくなったといえるが、数表のほかに多くの公式、計算式、近似式が集められており、今日でも数値計算の分野にとって有用である）。
機械式計算機やリレー式のデジタル計算機も計算のツールとして開発された。そのような計算機が1940年代に電子式のコンピュータへと進化した。デジタル式のコンピュータは数値の計算以外にも使える機材であるが、例えばENIACの開発目標は、高速な数値計算を行うための機械の実現であった。その後はさらに複雑な計算がより高速に行えるようになっている。（計算機械にはデジタル式以外にもアナログ方式のものがある。例えば計算尺は一種のアナログ式の計算デバイスであるし、機械式や電気式、電子的のアナログ方式のコンピュータもデジタル方式のコンピュータが低価格となりごく当たり前になる以前には良く用いられていた。アナログ方式の弱点は、素子の物理的な特性から決まる誤差やノイズによりある程度以上の高精度な計算を行うことが困難であることや、動作を決めるためのプログラミングは機構や回路そのもので実現するので、ストアドプログラミング方式が実現容易なデジタル方式と違って変更が素早くできないので、用途が専用機械になりがちなことである。）
|
直接解法と反復解法 次の式を x について解くことを考える。
反復解法では、f(x) = 3x3 + 4 に二分法を適用する。初期値として a = 0 と b = 3 を使うと、f(a) = 4、f(b) = 85 である。
ここまでで、解は 1.875 と 2.0625 の間にあるとわかる。このアルゴリズムでは、誤差 0.2 未満でこの範囲にある任意の値を返す。 離散化と数値積分_in_practice_at_USGP_2005.jpg) 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分解、線形計画問題のシンプレックス法などがある。実際は有限精度の浮動小数点数を用いて計算を行うので，得られるものは解の近似値である。
これに対して反復解法は有限の演算回数で完了するとは限らない。ある初期予測値から開始して、計算を反復的に行うことで近似解を真の解に徐々に収束させていく。仮に計算を無限の精度で行ったとしても、収束する反復を有限回までで打ち切って得られる結果は、一般には正確な解にはならない。例として、ニュートン法、二分法、ヤコビ法などがある。一般に大規模な数値線形代数の問題では反復法による解法が要求される[5][6][7][8][9][10]。
数値解析では、多くの計算法は直接解法ではなくて反復法である。GMRES法 や共役勾配法などのようないくつかの手法は，本来は有限回の繰り返しで真の解に到達できる直接解法であるが，それを反復法のように扱って計算を繰り返しの途中で打ち切ることで近似解を得るために使われるものがある。これらの手法を大規模問題に対してもしも直接法として適用すると必要な繰り返しの回数が極めて多くなるが、それを反復解法とみなして途中で計算の繰り返しを打ち切ることにより繰り返しの回数に応じた精度の近似解が得られるという性質がある。
さらに、連続問題を近似的に離散問題に置き換えて解くことが必要になる。この置き換え操作を「離散化（discretization）」という。たとえば、微分方程式を解く場合が挙げられる。数値的に微分方程式を解くためには、データの数が有限でなければ現実には扱うことができない。そこでたとえば微分方程式の定義領域が連続なものであっても、そのなかから有限個の点を適切に代表点として選び、元の微分方程式をそれらの点での値についてだけの関係に置き換えて扱う。
誤差の研究は、数値解析の重要な一分野である。解に誤差が入り込む原因はいくつかある。
アルゴリズムや計算プログラムに与える入力データ自身が持つ誤差。たとえば入力するデータがそれ自身が既に丸められた値である場合。 あるいは入力する数値を指定された有限桁の浮動小数点数に丸めることでも発生する（たとえば10進数で0.1を入力してもそれをプログラムの内部で2進数にして扱うとすると、0.1は2進数で表現すれば循環小数になるから有限桁数では正確には表せず、それを内部で扱う桁数に丸めて扱うとその段階で丸め誤差が入る。2の平方根や3の自然対数、円周率などの無理数の厳密な値は10進でも2進でも無限に続く小数になるがそれらをプログラム中で有限桁数の小数として近似して扱うならその段階で既に丸め誤差が入る）。あるいは入力が測定や観測から得られるものの場合には、一般的には真の値は未知であり、データ自身が確率的な振る舞いを持った観測誤差を伴う。
有限な素子から構成されているデジタルコンピューターは内部状態の数も有限であるので、無限の情報（無限の桁数）を持ちうる実数はただ1つですら一般には値を正確に表現することができない。また、数値をある決まった桁数で表す場合に、それらの数値に四則演算を行った結果は一般には同じ桁数のままでは正確に表わせない。そこで演算結果の数値を一定の桁数になるように丸めると、端数処理にともなう誤差が発生する。この誤差を丸め誤差という。丸め誤差の影響はより表現精度の高い倍精度を用いて計算を行うなどのように、計算に用いる数値の表現とそれらに対する演算の精度を上げることで小さくできる。
打ち切り誤差とは、数学的には繰り返しを無限に続けた極限では真の解を与える計算法を、無限回の操作を行うことは現実にはできないので、繰り返しをある有限回までで打ち切って得られた近似解の真の解との差である。たとえば右の欄にある を解く問題で、10回程度の反復では、解は約 1.99 となる。このとき打ち切り誤差は 0.01 である。一般には（丸め誤差の影響を無視すれば）反復回数を十分に増やせばこの誤差は減少する。またたとえば収束する無限級数の和を、最初のある項数までの有限部分和に置き換えた場合の誤差も、打ち切り誤差である。
コンピュータは有限個の素子からできていて一般には無限の自由度は扱えないので、本来は連続無限の自由度を持つ問題に対して何らかの近似を導入することにより有限の自由度の問題として定式化する作業のことを問題の離散化という。 たとえば微分方程式は独立変数も従属変数も連続量であるが、それに対して計算点として有限個の分点を代表として選び、微分方程式中の微分を差分で近似して置き換える「差分近似」を行うと、それにより元の微分方程式とは異なる有限個の自由度に対する差分方程式が得られる。差分方程式はテイラー展開の剰余項を微小であると仮定して無視する近似から得られるものであるから、通常その解は元の微分方程式の解には一致しない。このように離散化近似によって得られる近似解の持つ元の方程式の真の解に対する誤差のことを離散化誤差という。この種類の誤差を減らすためには、より高次の離散化近似方法をとる、近似に用いる自由度（計算点の個数）をより多くするなどの方法がある。（なお微分方程式の離散化の方法は差分法だけではなくて、問題の性質や近似手法に応じてさまざまなものが開発・研究されている。）
上述までの誤差は、与えられたモデルを「正しく」解いているか、という観点からの誤差であるが、その対立概念として、元の基礎方程式に関して、「正しい」式を解いているか、という問題がある。例えば非線形現象を線形近似することなどがこれに相当する。これは数値解析というより、元の問題が属する科学分野の問題ではあるが、基礎方程式が誤っている（実現象のモデルとして不適切である）場合には上述の誤差を減らしても解が実現象を正しく表すとは限らないため、解の誤差評価をする際には必ず検討しなければならないことである。この検証過程では定式化や仮説における誤り、モデルの適用限界などに対する考察が必要になる[11]。
入力や計算の途中に発生した誤差は計算の過程で後に伝播していく。実際、電卓やコンピュータでの（浮動小数点数の）加算は正確ではなく、反復計算をすると計算はさらに不正確になっていく。このような誤差の研究から数値的安定性の概念が生まれた[12]。あるアルゴリズムが数値的に安定であるとは、誤差が発生・伝播したときに計算が進むにつれてその誤差があまり拡大しないことを意味する[12]。これは問題が良条件の場合にのみ可能である。良条件とは、データが少しだけ変化したとき、解も少しだけ変化するような性質を持つことを意味する[12]。逆に問題が悪条件であれば、データに含まれる誤差は大きく成長する。
しかし、良条件の問題であってもそれを解くアルゴリズムが数値的に安定であるとは限らない。数値解析の技術は、良条件の問題を解く安定なアルゴリズムを見つけるためにある。例えば、2の平方根（約 1.41421）の計算は良条件問題である[要出典]。この問題を解く多くのアルゴリズムは、初期近似値 x1 から開始して になるべく近い値を求めようとする。つまり、x1=1.4 として、よりよい近似値を x2、x3、…と計算していく。有名なアルゴリズムとしてバビロニアの平方根があり、この場合の式は xk+1 = xk/2 + 1/xk である。別の方法として、例えば、xk + 1 = (xk2−2)2 + xk という式を使うとする(仮に Method X とよんでおく)[注釈 1]。この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 は数値的に不安定である。
近似値の計算を行うのと同時に計算に含まれる丸め誤差、打切り誤差、離散化誤差をすべて数学的な意味で厳密に扱って精密な評価を得る技術を精度保証付き数値計算という。
区間演算やアフィン演算のような手法では、近似値の代わりに真値を含む区間を与える。
さまざまな数値計算法について計算された結果の精度保証が得られるものにする動きが進みつつある。例えば微分方程式の分野では解析的な方法では解の存在の証明が困難な問題に対する数値的なアプローチが確立されつつある[13][14]。 力学系の研究にも応用されており、有力な道具として注目されている[15][16][17][18]。
数値解析は、解こうとしている問題によっていくつかの分野に分かれる。
|
補間: 気温の観測値が1:00には20℃、3:00には14℃だったとする。このデータを線型補間すると、2:00の気温は17℃、1:30の気温は18.5℃となる。 補外: ある国の国内総生産が毎年平均5%伸びていて、昨年の値が1000億ドルだったとする。ここで補外すると、今年は1050億ドルとなる。  回帰: 線型回帰では、n 個の点が与えられたとき、それら n 個の点のなるべく近くを通る直線を求める。  最適化: レモネード売りがレモネードを売っている。1杯1ドルでは、1日に197杯売れる。1杯あたり1セント値段を上げると、1日に売れるレモネードは1杯減る。1杯を1.485ドルにすると売り上げが最大となるが、1セント未満を使った値段は付けられないので、1.49ドルにすると一日の最大売り上げ 220.52 ドルが得られる。 微分方程式: ある部屋で一方からもう一方へ空気が流れるように100個の扇風機を配置し、羽根をそこに落としてみる。何が起きるだろうか? 羽根は空気の流れに従って漂うが、非常に複雑な動きになるかもしれない。その近似としては、羽根が漂っている付近の空気の速度を1秒おきに測定し、シミュレートされた羽根が1秒間は測定された方向にその速度で進むと仮定する。このような手法をオイラー法と呼び、常微分方程式を解くのに使われる。 |
最も単純な問題は、関数のある点での値を求めることである[注釈 2]。単純に数式に値を代入する直接的な手法は、効率的でないこともある。多項式の場合、ホーナー法を使うことで乗算と加算の回数を減らすことができる。一般に、浮動小数点演算を使うことで生じる丸め誤差を予測して制御することが重要となる。
補間が役立つのは、ある未知の関数のいくつかの点の値があるとき、それら以外の中間点でのその関数の値を求める場合である。単純な手法としては線型補間があり、既知の点の間で関数が線型に変化するとみなすものである。これを一般化した多項式補間はもっと正確となることが多いが、ルンゲ現象に悩まされることもある。その他の補間手法としてはスプラインやウェーブレットといった局所化関数を使うものがある。
補外は補間とよく似ているが、未知の関数の値が判っている点の外側の点について値を求めることをいう[20]。
回帰も類似した手法だが、既存のデータが不正確であることを考慮する。いくつかの点とその値があり、それらデータが誤差を含みつつ何らかの関数に従っているとして、その未知の関数を決定する。このための手法として、最小二乗法がよく知られている。
基本的な問題のひとつとして、与えられた方程式の解を計算する問題がある。その方程式が線型か否かによって手法が分類される。例えば、 は線型だが、 は線型ではない。
線型方程式系を解く手法については研究が進んでいる。標準的な直接解法としては何らかの行列分解を使うものがあり、ガウスの消去法、LU分解、対称行列やエルミート行列に関するコレスキー分解、非正方行列に関するQR分解がある。反復解法としては、ヤコビ法、ガウス＝ザイデル法、SOR法、共役勾配法[21]があり、大規模な方程式系でよく使われる。
非線型方程式には求根アルゴリズムが用いられる（根とは、関数の値がゼロとなる変数の値を意味する）。関数が可微分で導関数を導き出せる場合には、適切な初期値から開始してニュートン法が利用されることが多い[22][23][24]。他にも線型化などの手法がある。
固有値分解や特異値分解も重要な問題である。例えば、Spectral Image Compression[25] は特異値分解に基づいたアルゴリズムである。これに対応した統計学のツールを主成分分析という。例えば、World Wide Web上での話題トップ100を自動的に抽出し、各Webページをどの話題に属するか分類するといった作業で使われる。
最適化問題は、与えられた関数が最大（または最小）となる点を求める問題である。解には条件として何らかの制約（等式による関係あるいは不等式による関係）を課すことがよくある。
最適化問題はさらに、関数や制約の形式によっていくつかに分類される。例えば、線形計画問題は関数と制約条件の式が共に線型である場合を扱う。線形計画問題の解法としては、シンプレックス法や内点法などが挙げられる。
制約条件付きの最適化問題を制約条件のない問題の形に変換するためにラグランジュの未定乗数法が用いられる。
数値積分（数値的求積法）では、与えられた領域に於ける定積分の値を求める[26]。一般的な手法としては、ニュートン・コーツ系の公式（中点法やシンプソンの公式）やガウスの求積法[27]、二重指数関数型数値積分公式[28][29]などがある。これらは分割統治戦略に基づいて、大きな領域についての積分を小さな領域の積分に分割して値を求める。これらの手法は領域が高次元であると計算の手間が膨大となり適用が困難になるので、高次元の場合には計算量が領域の空間次元にあまり依存しないモンテカルロ法や準モンテカルロ法などのサンプリング平均により定積分の値を推定する手法がよく用いられる[30][31]。
数値解析では、微分方程式（常微分方程式や偏微分方程式）を（近似的に）解く問題も扱う[32][33][34]。
偏微分方程式を解くには、まずなんらかの方法に基づいて方程式の離散化近似を行い、有限次元の部分空間で計算を行う[32][34]。そのような手法として、有限要素法[35][36][37][38]、差分法、特に工学分野で使われる有限体積法[39]などを挙げることができる。これらの手法は関数解析学の定理などに基づいている。これら各種の離散化近似手法により生じた有限自由度の連立代数関係式を何らかの手段で正確にあるいは近似して解くことにより、求めたい微分方程式の近似解を得るようにする。
20世紀後半以降、多くの数値計算アルゴリズムはコンピュータ上に向けて実装され、実行されてきた[4]。Netlib には数値解析用の各種ルーチンのソースコードがあり、その多くはFORTRANとC言語により書かれている。各種の数値解析アルゴリズムを実装した商用ライブラリ製品としては IMSL や NAG などがある。オープンな（ソースコードが開示されていて、利用や改変の際の自由度が高い）ものの例としては GNU Scientific Library を挙げることができる。
MATLABは行列計算を中心とする数値計算用の商用プログラミング言語として有名だが[40][41][42]、他にも商用ではSAS(統計解析用)[43] 、SPSS(統計解析用)[44][45][46][47][48]、S-PLUS、IDL[49] などがある。
フリーソフトとして、「MATLAB」と互換性の高い Scilab[50][51][52][53]・GNU Octave[54]・FreeMat、「S言語」や「S-PLUS」の言語仕様に準じるR言語[55]、SPSS の代替を目指す PSPP[56] や gretl、そのほかIT++（C++ライブラリ）、Pythonのライブラリ・パッケージである (SciPy[57][58][59]、NumPy) など、様々な数値解析ソフトウェアが使われている。
性能も様々で、ベクトルや行列の演算は一般に高速だが、スカラーのループは10倍以上の差があるものもある[60]。
Mathematica や Maple のような数式処理システム（記号処理システム）は多くの場合に浮動小数点数値の計算機能も含むので数値計算用途にも（性能や効率を問わなければ）一応は使える[61][62][63][64][65][66][67][68][69][70]。SageMath は数値計算と数式処理計算の両方を備えた統合システムである[71]。また、簡単な問題であればMicrosoft Excelなどの表計算ソフトを用いてでも扱える場合がある[72][73]。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
