数値解析の話2

前回の続きです。数値解析は、対象とする数学的問題によって分類されます。
・関数の計算
・補間、補外、回帰
・方程式の計算（線型、非線形方程式）
・行列計算（固有値と特異値）
・微分方程式（常微分、偏微分方程式）

関数の計算

関数の解を求めることです。最も単純な方法は数式に繰り返し値を代入していくことですが非効率的です。多項式の場合は、ホーナー法を使うことで乗算と加算の回数を減らすことができます。通常n次の多項式を直接計算するには、まず第1項AnX^n を計算し、次に第2項An−1X^n−1を計算し、・・・と順番に計算し最後に足し合わせるという方法があり、n(n+1)/2 回の乗算が必要です。このときn次の多項式を式変形することで乗算を n 回で済ませることができます。

これは組立除法を使って効率的に近似解を求めるアルゴリズムです。組立除法とは多項式f(x)を(x－α)で割った時の商と余りを計算する方法です。この余りはf(α)と等しくなる（剰余の定理）ため、高次多項式f(x)に対して少ない計算回数でx=αの値f(α)を計算することができます。これを繰り返し行うと、f(x)のx=αでのテーラー展開の係数が得られます。その係数は、f(x)=0という方程式に対して、その根がすべてαだけ小さくなるように変換された方程式の係数となりますので、真の値を求めるために根を少しずつ近似してゆく方法として使うことができます。

補間、補外、回帰

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

■補外
なお補間と補外の違いですが、内挿と外挿の違いと同じで、未知の関数の値が判っている点の外側の点について値を求めることを補外（外挿）と呼びます。

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

方程式の計算

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

■線型方程式
線型方程式系を解く手法については研究が進んでいます。標準的な直接解法としては何らかの行列分解を使うものがあり、以下のものがあります。
・ガウスの消去法
・LU分解
・対称行列やエルミート行列に関するコレスキー分解
・非正方行列に関するQR分解

反復解法としては
・ヤコビ法
・ガウス＝ザイデル法
・SOR法
・共役勾配法があり、大規模な方程式系でよく使われます。

■非線形方程式
非線型方程式には求根アルゴリズムが用いられます（根とは、関数の値がゼロとなる変数の値）。関数が可微分で導関数を導き出せる場合には、適切な初期値から開始してニュートン法が利用されることが多いです。他にも線型化などの手法があります。

固有値分解と特異値分解

■固有値分解
固有値分解とは、行列を固有値と固有ベクトルに分解することです。ある行列 A を、固有ベクトルを列ベクトルとした行列 V と、固有値 λ を対角線分とした対角行列 Λ としてA=VΛV−1と分解します。

行列の演算は、計算量が非常に大きくなるためコンピューターで行うにしても高くつきます。特に機械学習では、何千、何万もの次元を持つデータを扱うことになるので尚更です。何百万もの次元を持つ行列で線形変換を行うとしたら、たとえ世界最高のコンピュータだとしても、すぐに限界を超えてしまいます。しかし対角行列の場合は、演算は非常にシンプルになります。そのためコストがかかる行列の演算を行う前に、その行列を対角行列に変換してしまえば、コンピュータの計算も遥かに軽くなります。

■特異値分解
特異値分解とはm×n 行列 A を A=UΣVと分解することです。U は m×m の直交行列、Vはn×n の直交行列、Σは非対角成分は0、対角成分は非負で大きさの順に並んだ行列です。任意の行列はこのように分解できます。Σ の対角成分で0 でないもの（0 を含めることもある）を特異値と言います。固有値分解は正方行列に対してのみ定義されますが、特異値分解は正方行列でなくてもできます。

■次元削減の意味
det(B) = |B| = 𝑎𝑐 − 𝑏^2
これは点 (a, c) と原点を対角にもつ長方形と、(b, b) と原点を対角にもつ正方形の面積の差になります。これが0になるとき点 (a, b) と点 (b, c) を結ぶ直線は原点を通ります。あるいは、これらの２点と原点でつくる三角形の面積がゼロになります。

もう1つ次元を挙げて考えてみます。3×3行列のときdet(B)の意味は各点(
a, b, c)、(b, d, e)、(c, e, f ) へと原点からひいた３本の線分を３辺にもつ平行６面体の体積です。det(B − λI) = 0となるためには各点(a - λ, b, c)、(b, d-λ, e)、(c, e, f- λ) が指定する平面が、原点を含むようになるλを求めればいいことになります。これはλの三次式になるので値が３つ存在します。

以上、平面のとき直線になって面積がなくなり、立体のときに平面になって体積がなくなります。このとき、その直線なり平面の上で、データの原点からの距離が、最も効率良く表されることになります（=次元削減）。

最適化問題

最適化問題は、与えられた関数が最大（または最小）となる点を求める問題です。最適化問題は関数や制約の形式によっていくつかに分類されます。例えば、線形計画問題では関数と制約条件の式が共に線型である場合です。線形計画問題の解法としては、シンプレックス法や内点法などが挙げられます。制約条件付きの最適化問題を制約条件のない問題の形に変換するためにラグランジュの未定乗数法が用いられます。

■線型計画問題
目的関数が１次式として表され、制約条件の集合が一次方程式・一次不等式によって定義されている場合
■整数計画問題
線型計画問題のうち、各変数のとる値が整数に制限されている場合
■2次計画問題
目的関数が2次式で定義され、制約条件の集合が一次方程式・一次不等式によって定義されている場合
■凸計画問題
目的関数が凸関数で、制約条件の集合も凸集合である場合
■半正定値計画問題
半正定値行列を変数とする凸計画問題
■非線型計画問題
目的関数や制約条件に非線性が含まれる場合

積分

数値積分（数値的求積法）では、与えられた領域における定積分の値を求めます。一般的な手法としては、ニュートン・コーツ系の公式（中点法やシンプソンの公式）やガウスの求積法、二重指数関数型数値積分公式などがあります。これらは分割統治戦略に基づいて、大きな領域についての積分を小さな領域の積分に分割して値を求めます。これらの手法は領域が高次元であると計算の手間が膨大となり適用が困難になるため、高次元の場合には計算量が領域の空間次元にあまり依存しないモンテカルロ法や準モンテカルロ法などのサンプリング平均により定積分の値を推定する手法がよく用いられます。

微分方程式

数値解析では、微分方程式（常微分方程式や偏微分方程式）を解く問題も扱います。偏微分方程式を解くには、まず何らかの方法に基づき方程式の離散化近似を行い、有限次元の部分空間で計算を行います。そのような手法として、有限要素法、差分法、特に工学分野で使われる有限体積法などがあります。これら各種の離散化近似手法により生じた有限自由度の連立代数関係式を、何らかの手段で正確にあるいは近似して解くことにより、求めたい微分方程式の近似解を得ます。

例）微分方程式: ある部屋の中で一方向に十分強い空気の流れがあるとする。その気流中に羽根を落とした場合の挙動について、羽根は空気の流れに従って漂うが、非常に複雑な動きになるかもしれない。その近似として、羽根が漂っている付近の空気の速度を1秒おきに測定し、シミュレートされた羽根が1秒間は測定された方向にその速度で進むと仮定する。このような手法をオイラー法と呼び、常微分方程式を解くのに使われる。

■有限要素法（Finite Element Method, FEM）
解析的に解くことが難しい微分方程式の近似解を数値的に得る方法の一つです。 方程式が定義された領域を小領域（要素）に分割し、各小領域における方程式を比較的単純で共通な補間関数で近似します。対象領域を細分化することで複雑な形状を正確に表現できます。

■有限差分法（finite-difference methods; FDM）
微分方程式を解くために微分を有限差分近似（差分商）に置き換え差分方程式で近似する離散化手法です。テイラー級数を用いて微分方程式を代数方程式に変換しますが、変換時、次数の高い項は無視されます。

■有限体積法（finite volume method、FVM）
対象領域を有限個のコントロールボリュームに分割し、各ボリュームに対して積分形の物理量の保存方程式を適用するものです。1960年代に非構造格子に基づく流体解析手法として開発され、現在では、多くの商用の流体解析コードに標準的な離散化解析手法として採用されています。有限差分法と有限要素法の両方の特徴を合わせ持つ手法と言えます。

直接解法と反復解法

■直接解法
未知変数を順次消去していくことによって解く方法です。マトリクスが非正定でない限り必ず解くことができます。例えば、連立1次方程式を行列の形式で書くとAu＝bのように記述できます。Aは係数行列で、uは未知ベクトル、bは定数ベクトルです。直接解法ではuの中にある未知変数を順に消去していくという操作で解uを求めます。代表的な手法としてガウスの消去法やQR分解、線形計画問題のシンプレックス法などがあります。

■反復解法
これに対し反復解法では初期推定値を計算し、収束するまで反復する処理によって解を得る方法です。一旦uを仮定し、その仮定したuを使ってAuを計算します。その結果とbの違いからuを仮定し直し、再びAuを計算するという繰り返し計算から真のuに収束させます。この場合、たとえ無限の精度で計算したとしても有限回の反復では正確な解にたどり着くことはありません。ただし、直接法よりもメモリ使用量、計算量が少ないというメリットがあります。代表的な手法にはニュートン法、二分法、ヤコビ法などがあります。数値線形代数の大規模な問題には反復解法が一般に必要とされます。

数値解析の誤差

■入力誤差
アルゴリズムや計算プログラムに与える入力データ自身が持つ誤差です。例えば入力するデータがそれ自身が既に丸められた値である場合です。他にも、例えば入力が測定や観測から得られたデータの場合には、一般的には真の値は未知であり、データ自身が確率的な振る舞いを持った観測誤差を伴います。

■丸め誤差
長い桁や無限桁の小数を扱う際に、これを有限桁で表すためにある桁以降の値を捨ててしまうことにより生じる誤差です。10進数で0.1を入力してもそれをプログラムの内部で2進数にして扱うとすると、0.1は2進数で表現すれば循環小数になるため有限桁数では正確には表せず、それを内部で扱う桁数に丸めて扱うとその段階で丸め誤差が入ります。2の平方根や3の自然対数、円周率などの無理数の厳密な値も無限に続く小数となるため、プログラム内で有限桁数の小数として近似して扱います。丸め誤差自身は計算を倍精度で行うなど、計算に用いる数値の表現とそれらに対する演算の精度を上げることにより減らすことができます。

■打ち切り誤差
数学的には繰り返し計算を無限に続けることで求められる場合でも、現実上、無限回の操作を行うことは不可能なため、繰り返しをある有限回までで打ち切って得られた近似解の真の解との差です。例えば 3x^3+4=28を解く場合、10回程度の反復では解は約 1.99 となります。このとき打ち切り誤差は 0.01 です。一般には反復回数を十分に増やせばこの誤差は減少します。

■離散化誤差
コンピュータは有限個の素子から構成され、一般には無限の自由度は扱えないため、本来は連続無限の自由度を持つ問題に対して何らかの近似を導入することにより有限の自由度の問題として定式化する作業のことを問題の離散化と呼びます。 例えば微分方程式は、独立変数も従属変数も連続量ですが、それに対して計算点として有限個の分点を代表として選び、微分方程式中の微分を差分で近似して置き換える「差分近似」を行うと、それにより元の微分方程式とは異なる有限個の自由度に対する差分方程式が得られます。

差分方程式はテイラー展開の剰余項を微小であると仮定して無視する近似から得られるものであるから、通常その解は元の微分方程式の解には一致しません。このように離散化近似によって得られる近似解の持つ元の方程式の真の解に対する誤差のことを離散化誤差と呼びます。この種類の誤差を減らすためには、より高次の離散化近似方法をとる、近似に用いる自由度（計算点の個数）をより多くするなどの方法があります。

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

https://ja.wikipedia.org/wiki/%E6%95%B0%E5%80%A4%E8%A7%A3%E6%9E%90