
数値解析は連続数学の問題に対するアルゴリズムの研究です。[ 2 ] これらのアルゴリズムは(離散数学とは対照的に)実変数または複素変数を扱い、通常は記号操作に加えて数値近似を使用します。
数値解析は、工学および物理科学のあらゆる分野に応用されており、21世紀においては、経済学、医学、ビジネス、さらには芸術といった生命科学や社会科学にも応用されています。近年の計算能力の向上により、より複雑な数値解析が可能になり、科学および工学において詳細かつ現実的な数学モデルが提供されています。数値解析の例としては、天体力学(惑星、恒星、銀河の運動を予測する)に見られる常微分方程式、データ分析における数値線形代数[ 3 ] [ 4 ] [ 5 ]、そして医学および生物学における生細胞のシミュレーションに使用される確率微分方程式やマルコフ連鎖などが挙げられます。
現代のコンピュータが登場する以前は、数値計算は大きな印刷された表のデータを用いた手作業による補間式に頼ることが多かった。20世紀半ば以降、必要な関数はコンピュータによって計算されるようになったが、ソフトウェアアルゴリズムでは同じ式の多くが依然として使用されている。[ 6 ]
数値的観点は、最古の数学文献にまで遡ります。イェール大学バビロニアコレクション(YBC 7289)の粘土板には、単位正方形の対角線の長さである2の平方根を60進法で近似した数値が示されています。
数値解析はこの長い伝統を継承しており、実際の測定にのみ適用可能な数字に変換された正確な記号的な答えを与えるのではなく、指定された誤差範囲内の近似解が使用されます。
数値解析分野の全体的な目標は、記号的に解決することが不可能な多くの困難な問題に対して、近似的だが正確な解を与える技術の設計と分析です。
数値解析の分野は、現代のコンピュータの発明より何世紀も前に遡ります。線形補間は2000年以上も前から使われていました。過去の多くの偉大な数学者が数値解析に没頭していたことは、[ 6 ]ニュートン法、ラグランジュ補間多項式、ガウスの消去法、オイラー法といった重要なアルゴリズムの名前からも明らかです。現代の数値解析の起源は、1947年のジョン・フォン・ノイマンとヘルマン・ゴールドスタインの論文と結び付けられることが多いですが、[ 8 ] [ 9 ]現代の数値解析は1912年のE.T.ウィテカー の研究に遡ると考える人もいます。[ 8 ]

手計算を容易にするため、補間点や関数係数などの公式やデータ表を収録した大型書籍が出版されました。これらの表は、関数によっては小数点以下16桁以上まで計算されることも多く、これらの表を用いて、与えられた公式に代入する値を調べることで、一部の関数について非常に正確な数値推定値を得ることができました。この分野の代表的な研究は、アブラモウィッツとステガンが編集したNIST出版物で、1000ページを超える書籍には、非常に多くのよく使われる公式や関数、そして様々な点におけるそれらの値が掲載されています。コンピュータが利用できるようになった現在では、関数の値はもはやそれほど役に立ちませんが、膨大な公式の一覧は依然として非常に便利です。
機械式計算機も手計算用のツールとして開発されました。これらの計算機は1940年代に電子計算機へと進化し、その後、これらの計算機が事務処理にも有用であることが分かりました。しかし、計算機の発明は数値解析の分野にも影響を与えました。[ 6 ]より長く複雑な計算が可能になったからです。
数値解析に関するレスリー・フォックス賞は、数学およびその応用研究所によって 1985 年に創設されました。
直接法は、有限数のステップで問題の解を計算します。これらの方法は、無限精度の演算で実行すれば正確な解が得られます。例としては、ガウス消去法、連立一次方程式を解くためのQR分解法、線形計画法の単体法などが挙げられます。実際には有限精度が使用され、結果は真の解の近似値となります(安定性を仮定)。
直接法とは対照的に、反復法は、たとえ無限精度が可能であったとしても、有限数のステップで終了することは期待されません。初期推定値から始めて、反復法は、極限でのみ正確な解に収束する逐次近似を形成します。十分に正確な解が(うまくいけば)見出されたかどうかを判断するために、多くの場合残差を含む収束テストが指定されます。これらの方法は、無限精度演算を使用しても、(一般に)有限数のステップ内で解に到達しません。例として、ニュートン法、二分法、ヤコビ反復法などがあります。計算行列代数では、大規模な問題には反復法が一般的に必要です。[ 10 ] [ 11 ] [ 12 ] [ 13 ]
数値解析においては、直接法よりも反復法が一般的です。GMRES法や共役勾配法のように、原理的には直接法であるにもかかわらず、通常は直接法ではないかのように用いられる方法もあります。これらの方法では、正確な解を得るために必要なステップ数が非常に多いため、反復法と同様に近似値が受け入れられます。
例として、次の問題を解くことを考えてみましょう。
未知の量xについて。
| 3 × 3+4=28です。 | |
| 4を引く | 3 × 3=24です。 |
| 3で割る | × 3 = 8 です。 |
| 立方根を取る | x = 2 です。 |
反復法では、f ( x )= 3x3−24に二分法を適用します。初期値はa =0、b =3、f ( a )=−24、f ( b )=57です。
| 1つの | b | ミッド | f(ミッド) |
|---|---|---|---|
| 0 | 3 | 1.5 | −13.875 |
| 1.5 | 3 | 2.25 | 10.17... |
| 1.5 | 2.25 | 1.875 | −4.22... |
| 1.875 | 2.25 | 2.0625 | 2.32... |
この表から、解は1.875から2.0625の間であると結論付けられます。アルゴリズムは、その範囲内の任意の数値を0.2未満の誤差で返す可能性があります。
悪条件問題:関数f ( x ) = 1/( x − 1)を考える。f (1.1) = 10 および f (1.001) = 1000 であることに注意する。xが0.1未満変化すると、 f ( x ) はほぼ 1000変化する。x = 1付近で f ( x )を評価することは悪条件問題である。
条件付き問題:対照的に、同じ関数f ( x ) = 1/( x − 1 ) をx = 10付近で評価することは条件付き問題です。例えば、f (10) = 1/9 ≈ 0.111 およびf (11) = 0.1 の場合、 xのわずかな変化はf ( x )のわずかな変化をもたらします。
さらに、連続問題は、解が連続問題の解に近似することが分かっている離散問題に置き換える必要がある場合があります。このプロセスは「離散化」と呼ばれます。例えば、微分方程式の解は関数です。この関数は、その定義域が連続体であっても、有限量のデータ、例えば定義域内の有限個の点における値で表現されなければなりません。
誤差の研究は数値解析の重要な部分を占めています。問題の解法において誤差が生じる原因はいくつかあります。
有限のメモリを持つマシン (すべての実用的なデジタル コンピューターがこれに該当します) ではすべての実数を正確に表現することが不可能であるため、丸め誤差が発生します。
打ち切り誤差は、反復法が終了したり、数学的手順が近似されたりして、近似解が厳密解と異なる場合に発生します。同様に、離散化は離散問題の解が連続問題の解と一致しないため、離散化誤差を引き起こします。上記の の解を計算する例では、10回の反復後、計算された根はおよそ1.99です。したがって、打ち切り誤差はおよそ0.01です。
一度エラーが発生すると、それは計算全体に波及します。例えば、コンピュータにおける演算「+」は不正確です。また、 「 」型の計算はさらに不正確です。
数学的手順を近似すると、打ち切り誤差が生じます。関数を正確に積分するには、無限個の領域和を求める必要がありますが、数値的には有限個の領域和しか求めることができず、したがって厳密解の近似値を求めることはできません。同様に、関数を微分するには、微分要素はゼロに近づきますが、数値的には微分要素の非ゼロ値しか選ぶことができません。
アルゴリズムが数値的に安定であるとは、原因が何であれ、計算中に誤差がそれほど大きくならないことである。[ 14 ]これは問題が適切に条件付けられている場合に起こる。つまり、問題のデータが少し変更されても、解はわずかにしか変わらないということである。[ 14 ]逆に、問題が「悪条件」である場合は、データのどんな小さな誤差も大きな誤差にまで大きくなる。[ 14 ] 元の問題と、その問題を解くために使用されるアルゴリズムは、どちらも適切に条件付けられることも悪条件になることもあり、どのような組み合わせでも可能である。したがって、適切に条件付けられている問題を解くアルゴリズムは、数値的に安定しているか、数値的に不安定であるかのいずれかである。数値解析の技術は、適切に設定された数学の問題を解くための安定したアルゴリズムを見つけることである。
数値解析分野には多くの分野が含まれます。主要なものには以下のようなものがあります。
補間: 気温が午前 1 時の 20 度から午後 3 時の 14 度まで変化するのを観察し、このデータの線形補間により、午後 2 時には 17 度、午後 1 時 30 分には 18.5 度であったと結論付けられます。 外挿:ある国の国内総生産が年間平均 5% 成長し、昨年は 1,000 億ドルだった場合、今年は 1,050 億ドルになると外挿される可能性があります。 回帰: 線形回帰では、n個のポイントが与えられると、それらのn 個のポイントに可能な限り近い線が計算されます。 最適化:レモネードスタンドでレモネードを1杯1.00ドルで販売すると仮定します。1日に197杯のレモネードを販売でき、0.01ドル増加するごとに1杯のレモネードの販売数が減ります。もし1杯あたり1.485ドルを請求できれば利益は最大化されますが、1セント単位で請求しなければならないという制約があるため、1杯あたり1.48ドルまたは1.49ドルを請求すると、どちらも1日あたり220.52ドルという最大の収入が得られます。 ![]() 微分方程式:部屋の端から端まで空気を送るために100台の扇風機を設置し、そこに羽根を落としたらどうなるでしょうか?羽根は、非常に複雑な気流に沿って動きます。近似値を求める一つの方法は、羽根の近くを流れる風速を毎秒測定し、羽根を直線的に同じ速度で1秒間移動させ、その後再び風速を測定することです。これは常微分方程式を解くオイラー法と呼ばれます。 |
最も単純な問題の一つは、与えられた点における関数の評価です。式に数値を代入するだけの最も単純なアプローチは、必ずしも効率的ではありません。多項式の場合、ホーナー法を用いる方がより良いアプローチです。ホーナー法は、必要な乗算と加算の回数を減らすことができるからです。一般的に、浮動小数点演算の使用によって生じる丸め誤差を予測し、制御することが重要です。
補間は、いくつかの点における未知の関数の値が与えられた場合、その関数は、指定された点間の他の点でどのような値を持つかという問題を解決します。
外挿は内挿と非常によく似ていますが、与えられた点の外側にある点における未知の関数の値を見つけなければならない点が異なります。[ 15 ]
回帰も同様ですが、データの不正確さを考慮に入れます。いくつかの点と、それらの点におけるある関数の値(誤差を含む)の測定値が与えられれば、未知の関数を求めることができます。最小二乗法はこれを実現する方法の一つです。
もう一つの基本的な問題は、与えられた方程式の解を求めることです。方程式が線形であるかどうかによって、一般的に2つのケースが区別されます。例えば、方程式は線形ですが、方程式は線形ではありません。
線形方程式系を解く手法の開発には多大な努力が払われてきた。標準的な直接法、すなわち行列分解を用いる手法としては、ガウス消去法、LU分解、対称行列(またはエルミート行列)および正定値行列に対するコレスキー分解、非正方行列に対するQR分解などがある。大規模な系では、ヤコビ法、ガウス・ザイデル法、逐次過緩和法、共役勾配法[ 16 ]などの反復法が一般的に好まれる。一般的な反復法は、行列分割を用いることで開発できる。
根を求めるアルゴリズムは非線形方程式を解くために使用されます(関数の根は、関数がゼロとなる引数であるため、このように呼ばれます)。関数が微分可能で、導関数が既知である場合、ニュートン法がよく使用されます。[ 17 ] [ 18 ]線形化は、非線形方程式を解くためのもう一つの手法です。
いくつかの重要な問題は、固有値分解または特異値分解という用語で表現することができます。例えば、スペクトル画像圧縮アルゴリズム[ 19 ]は特異値分解に基づいています。統計学における対応するツールは主成分分析と呼ばれます。
最適化問題では、与えられた関数が最大化(または最小化)される点を求めます。多くの場合、その点はいくつかの制約条件も満たす必要があります。
最適化の分野は、目的関数と制約条件の形式に応じて、さらにいくつかのサブフィールドに分割されます。例えば、線形計画法は、目的関数と制約条件の両方が線形である場合を扱います。線形計画法の有名な手法として、単体法があります。
ラグランジュ乗数法を使用すると、制約付きの最適化問題を制約のない最適化問題に縮小できます。
数値積分は、場合によっては数値求積法とも呼ばれ、定積分の値を求めます。[ 20 ]一般的な手法では、ニュートン・コーツの公式(中点則やシンプソンの定理など)またはガウス求積法のいずれかを使用します。[ 21 ]これらの手法は、「分割統治」戦略に依存しており、比較的大きな集合の積分をより小さな集合の積分に分割します。高次元では、これらの手法は計算量の点で非常に高価になるため、モンテカルロ法または準モンテカルロ法(モンテカルロ積分[ 22 ]を参照)を使用するか、中程度に大きな次元ではスパースグリッド法を使用します。
数値解析は、常微分方程式と偏微分方程式の両方の解を(近似的に)計算することにも関係しています。[ 23 ]
偏微分方程式は、まず方程式を離散化し、有限次元部分空間に取り込むことによって解かれる。[ 24 ]これは有限要素法、[ 25 ] [ 26 ] [ 27 ]有限差分法、[ 28 ]あるいは(特に工学においては)有限体積法によって行うことができる。[ 29 ]これらの手法の理論的根拠には、しばしば関数解析の定理が用いられる。これにより、問題は代数方程式の解へと帰着する。
20世紀後半以降、ほとんどのアルゴリズムは様々なプログラミング言語で実装されています。Netlibリポジトリには、主にFortranとC言語で書かれた数値問題用の様々なソフトウェアルーチンのコレクションが含まれています。様々な数値アルゴリズムを実装した商用製品には、IMSLライブラリとNAGライブラリがあります。フリーソフトウェアの代替として、GNU Scientific Libraryがあります。
長年にわたり、英国王立統計協会は『応用統計学』(これらの「AS」関数のコードはこちら) において数多くのアルゴリズムを発表してきました。また、ACMも同様に『数学ソフトウェア取引』(「TOMS」コードはこちら)において多数のアルゴリズムを発表しました。海軍水上戦センターは、数学サブルーチンライブラリ(コードはこちら) を複数回にわたって公開しています。
数値計算アプリケーションとしてはMATLAB、[ 30 ] [ 31 ] [ 32 ] TK Solver、S-PLUS、IDL [ 33 ]などが人気があり、またFreeMat、Scilab [ 34 ] [ 35 ] GNU Octave(Matlabに類似)、IT++(C++ライブラリ)などの無料・オープンソースの代替品もあります。プログラミング言語としてはR [ 36 ](S-PLUSに類似)、Julia [ 37 ]、Pythonなどがあり、NumPy 、SciPy [ 38 ] [ 39 ] [ 40 ]、SymPyなどのライブラリがあります。パフォーマンスは大きく異なり、ベクトル演算や行列演算は通常高速ですが、スカラーループでは速度が1桁以上変わることがあります。[ 41 ] [ 42 ]
Mathematicaなどの多くのコンピュータ代数システムも、より正確な結果を提供できる任意精度演算の恩恵を受けています。 [ 43 ] [ 44 ] [ 45 ] [ 46 ]
また、数値解析に関連する簡単な問題は、どのスプレッドシートソフトウェアでも解くことができます。 例えばExcelには、行列関数を含む数百もの関数が用意されており、内蔵の「ソルバー」と組み合わせて使用できます。