数値解析
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/04/05 01:06 UTC 版)
数値解析は自然科学および工学のあらゆる分野に応用がある。計算言語学[1]や社会統計学[2]のように、人文科学や社会科学でも重要である。
現在知られている人類史における最初期の数学的記述の一つとして、バビロニアの粘土板 YBC 7289 を挙げることができる。YBC 7289 は正方形の対角線の長さを近似したものと考えられ、結果として 2時間のレースで、自動車の速度を3回測定した結果が次表のようになっている。
離散化とは、この場合、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法 や共役勾配法などのようないくつかの手法は,本来は有限回の繰り返しで真の解に到達できる直接解法であるが,それを反復法のように扱って計算を繰り返しの途中で打ち切ることで近似解を得るために使われるものがある。これらの手法を大規模問題に対してもしも直接法として適用すると必要な繰り返しの回数が極めて多くなるが、それを反復解法とみなして途中で計算の繰り返しを打ち切ることにより繰り返しの回数に応じた精度の近似解が得られるという性質がある。
時間 0:20 1:00 1:40
km/h 140 150 180
離散化
さらに、連続問題を近似的に離散問題に置き換えて解くことが必要になる。この置き換え操作を「離散化(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]。
注釈
出典
- ^ 長尾真. (1986). 計算言語学: 計算言語学の歴史と展望. 情報処理, 27(8).
- ^ 安田三郎. (1977). 社会統計学. 丸善.
- ^ Photograph, illustration, and description of the root(2) tablet from the Yale Babylonian Collection
- ^ a b c Brezinski, C., & Wuytack, L. (2012). Numerical analysis: Historical developments in the 20th century. Elsevier.
- ^ 藤野清次, 阿部邦美, 杉原正顕, 中嶋徳正, 日本計算工学会『線形方程式の反復解法』丸善出版〈計算力学レクチャーコース〉、2013年。ISBN 9784621087411。
- ^ 藤野清次, 張紹良『反復法の数理』朝倉書店〈応用数値計算ライブラリ〉、1996年。ISBN 4254114044。国立国会図書館書誌ID:000002552625。
- ^ Saad, Y. (2003). "Iterative methods for sparse linear systems". SIAM.
- ^ Hageman, L. A., & Young, D. M. (2012). Applied iterative methods. Courier Corporation.
- ^ Traub, J. F. (1982). Iterative methods for the solution of equations. American Mathematical Society.
- ^ Greenbaum, A. (1997). Iterative methods for solving linear systems. SIAM.
- ^ 峯村吉泰『JAVAによる流体・熱流動の数値シミュレーション』森北出版、2001年、4頁。ISBN 4-627-91751-1。
- ^ a b c Higham, N. J. (2002). "Accuracy and stability of numerical algorithms" (Vol. 80). SIAM.
- ^ Nakao, Mitsuhiro T; Plum, Michael; Watanabe, Yoshitaka (2019). Numerical verification methods and computer-assisted proofs for partial differential equations. Springer. doi:10.1007/978-981-13-7669-6
- ^ Tucker, W. (2011). Validated numerics: a short introduction to rigorous computations. Princeton University Press.
- ^ 中尾充宏、山本野人:「精度保証付き数値計算―コンピュータによる無限への挑戦」、日本評論社、(1998年)
- ^ 大石進一:「精度保証付き数値計算」、コロナ社、(2000年)
- ^ 中尾充宏、渡辺善隆:「実例で学ぶ精度保証付き数値計算」、サイエンス社(2011年)
- ^ 大石進一編著:「精度保証付き数値計算の基礎」、コロナ社、(2018年)
- ^ Gil, A., Segura, J., & Temme, N. (2007). Numerical methods for special functions (Vol. 99). Siam.
- ^ Brezinski, C., & Zaglia, M. R. (2013). Extrapolation methods: theory and practice. Elsevier.
- ^ 戸川隼人. (1977). 共役勾配法. シリーズ新しい応用の数学.
- ^ Ezquerro Fernández, José Antonio; Hernández Verón, Miguel Ángel (2017). Newton's method : an updated approach of Kantorovich's theory. Frontiers in mathematics. Birkhäuser and Springer. doi:10.1007/978-3-319-55976-6
- ^ Peter Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms, Second printed edition. Series Computational Mathematics 35, Springer (2006)
- ^ 小澤一文「導関数を用いない非線形スカラー方程式の高速多倍長数値解法」『日本応用数理学会論文誌』第31巻第2号、日本応用数理学会、2021年、44-62頁、CRID 1390007005094550528、doi:10.11540/jsiamt.31.2_44、ISSN 2424-0982。
- ^ The Singular Value Decomposition and Its Applications in Image Compression Archived 2006年10月4日, at the Wayback Machine.
- ^ Davis, P. J., & Rabinowitz, P. (2007). Methods of numerical integration. Courier Corporation.
- ^ Weisstein, Eric W. "Gaussian Quadrature." From MathWorld--A Wolfram Web Resource. mathworld
.wolfram .com /GaussianQuadrature .html - ^ Takahasi, Hidetosi; Mori, Masatake (1974). “Double exponential formulas for numerical indefinite integration”. Publications of the Research Institute for Mathematical Sciences (京都大学数理解析研究所) 9 (3): 721-741. doi:10.2977/prims/1195192451. ISSN 0034-5318 .
- ^ 森正武「数値解析における二重指数関数型変換の最適性」『数学』第50巻第3号、日本数学会、1998年、248-264頁、CRID 1390001205066239872、doi:10.11429/sugaku1947.50.248、ISSN 0039470X。
- ^ 手塚集「数値多重積分に関する話題(<特集>数値計算)」『応用数理』第8巻第4号、日本応用数理学会、1998年、267-276頁、CRID 1390282680742275200、doi:10.11540/bjsiam.8.4_267、ISSN 09172270。
- ^ Geweke, John (1996). “Monte Carlo simulation and numerical integration”. Handbook of computational economics (Elsevier) 1: 731-800. doi:10.1016/S1574-0021(96)01017-9 .
- ^ a b 田端正久; 偏微分方程式の数値解析, 2010. 岩波書店.
- ^ 三井斌友 et. al. (2004). 微分方程式による計算科学入門. 共立出版.
- ^ a b 登坂宣好, & 大西和榮. (2003). 偏微分方程式の数値シミュレーション. 東京大学出版会.
- ^ 森正武. (1986) 有限要素法とその応用. 岩波書店.
- ^ 菊池文雄. (1999). 有限要素法概説 [新訂版]. サイエンス社.
- ^ 菊池文雄. (1994). 有限要素法の数理. 培風館.
- ^ 大塚厚二, 高石武史, 日本応用数理学会『有限要素法で学ぶ現象と数理 : FreeFem++数理思考プログラミング』共立出版〈シリーズ応用数理〉、2014年。ISBN 9784320019539。国立国会図書館書誌ID:025174389 。
- ^ LeVeque, Randall (2002), Finite Volume Methods for Hyperbolic Problems, Cambridge University Press.
- ^ Quarteroni, A., Saleri, F., & Gervasio, P. (2006). Scientific computing with MATLAB and Octave. Berlin: Springer.
- ^ Gander, W., & Hrebicek, J. (Eds.). (2011). Solving problems in scientific computing using Maple and Matlab®. en:Springer Science & Business Media.
- ^ Barnes, B., & Fulford, G. R. (2011). Mathematical modelling with case studies: a differential equations approach using Maple and MATLAB. Chapman and Hall/CRC.
- ^ Khattree, R., & Naik, D. N. (2018). Applied multivariate statistics with SAS software. SAS Institute Inc..
- ^ Wagner III, W. E. (2019). Using IBM® SPSS® statistics for research methods and social science statistics. Sage Publications.
- ^ Pollock III, P. H., & Edwards, B. C. (2019). An IBM® SPSS® Companion to Political Analysis. Cq Press.
- ^ Babbie, E., Wagner III, W. E., & Zaino, J. (2018). Adventures in social research: Data analysis using IBM SPSS statistics. Sage Publications.
- ^ Aldrich, J. O. (2018). Using IBM® SPSS® Statistics: An interactive hands-on approach. Sage Publications.
- ^ Stehlik-Barry, K., & Babinec, A. J. (2017). Data Analysis with IBM SPSS Statistics. Packt Publishing Ltd.
- ^ Gumley, L. E. (2001). Practical IDL programming. Elsevier.
- ^ Bunks, C., Chancelier, J. P., Delebecque, F., Goursat, M., Nikoukhah, R., & Steer, S. (2012). Engineering and scientific computing with Scilab. en:Springer Science & Business Media.
- ^ 大野修一. (2009). Scilab 入門: フリーソフトで始める数値シミュレーション. CQ出版.
- ^ 上坂吉則. (2010). Scilab プログラミング入門. 牧野書店.
- ^ Thanki, R. M., & Kothari, A. M. (2019). Digital image processing using SCILAB. Springer International Publishing.
- ^ Octaveの精義 - フリーの高機能数値計算ツールを使いこなす, 松田七美男 (2011)
- ^ Ihaka, R., & Gentleman, R. (1996). R: a language for data analysis and graphics. Journal of computational and graphical statistics, 5(3), 299-314.
- ^ Yagnik, J. (2014). PSPP: a free and open source tool for data analysis (No. 2014-03-21).
- ^ Jones, E., Oliphant, T., & Peterson, P. (2001). SciPy: Open source scientific tools for Python.
- ^ Bressert, E. (2012). SciPy and NumPy: an overview for developers. " O'Reilly Media, Inc.".
- ^ Blanco-Silva, F. J. (2013). Learning SciPy for numerical and scientific computing. Packt Publishing Ltd.
- ^ Speed comparison of various number crunching packages Archived 2006年10月5日, at the Wayback Machine.
- ^ Maeder, R. E. (1991). Programming in mathematica. Addison-Wesley Longman Publishing Co., Inc..
- ^ Stephen Wolfram. (1999). The MATHEMATICA® book, version 4. en:Cambridge University Press.
- ^ Shaw, W. T., & Tigg, J. (1993). Applied Mathematica: getting started, getting it done. Addison-Wesley Longman Publishing Co., Inc..
- ^ 中村健蔵. (1998). Mathematica で絵を描こう. 東京電機大学出版局.
- ^ 椎原浩輔. (2000). Mathematica による金融工学. 東京電機大学出版局.
- ^ 吉本堅一, & 松下修己. (2004). Mathematica で学ぶ振動とダイナミクスの理論. 森北出版.
- ^ Beltzer, A. I. (1995). Engineering analysis with Maple/Mathematica. en:Academic Press.
- ^ Mathematicaによる数値計算, R.D.Skeel ・J.B.Keiper 著・玄光男・辻陽一・尾内俊夫 共訳, 共立出版, 1995.
- ^ Mathematica によるテンソル解析, 野村靖一 著, 共立出版, 2019.
- ^ Marasco, A., & Romano, A. (2001). Scientific Computing with Mathematica: Mathematical Problems for Ordinary Differential Equations; with a CD-ROM. en:Springer Science & Business Media.
- ^ Zimmermann, P., Casamayou, A., Cohen, N., Connan, G., Dumont, T., Fousse, L., ... & Bray, E. (2018). Computational Mathematics with SageMath. SIAM.
- ^ 吉村忠与志, 吉村三智頼, 佐々和洋, & 青山義弘. (2009). Excel で数値計算の解法がわかる本. 秀和システム.
- ^ 渋谷道雄, & 渡邊八一. (2001). Excel で学ぶ信号解析と数値シミュレーション. 株式会社 オーム社.
数値解析と同じ種類の言葉
固有名詞の分類
- 数値解析のページへのリンク