VCP Library数値線形代数の精度保証付き数値計算法
記号の準備:\begin{align} {\mathbb R} ~ & \mbox{: 実数全体の集合} \\ | A | ~ & \mbox{: ベクトル/行列}A\mbox{の成分毎の絶対値} \\ \| A \| ~ & \mbox{: ベクトル/行列}A\mbox{の(1/2/最大値)ノルム} \\ \| A \|_{\infty} ~ & \mbox{: ベクトル/行列}A\mbox{の最大値ノルム} \end{align}
連立一次方程式の解の精度保証法
\(A \in {\mathbb R}^{n \times n}, ~ b \in {\mathbb R}^{n}\)をそれぞれ与えられているとします。 そのとき，連立一次方程式 \begin{align} Ax = b \end{align} を満たす真の解\(x^*\)と近似解\(\tilde{x}\)の誤差について考えます。定理[参考: 大石進一: 精度保証付き数値計算, コロナ社, 1992年, p.22 山本の定理]
\(A \in {\mathbb R}^{n \times n}, ~ b \in {\mathbb R}^{n}, ~ R \in {\mathbb R}^{n \times n}\)をそれぞれ与えられているとする。 \(I \in {\mathbb R}^{n \times n}\)を単位行列とし，\(e=(1,1,\cdots,1)^T \in {\mathbb R}^n\)は全成分が\(1\)のベクトルとする。 もし \begin{align} \| I - RA \| < 1 \end{align} を満たすならば，\( A \)は逆行列を持ち \begin{align} | x^* - \tilde{x} | \le |R(b - A \tilde{x})| + \frac{ \| R(b - A \tilde{x}) \| }{ 1 - \| I - RA \| } |I - RA|e \end{align} を満たす．上の定理は行列クラスのポリシーimats< _T, _P >とpidblasのlss関数で利用しています。 ノルムは1ノルム、2ノルム、最大値ノルムのどれをとっても成り立ちますが、VCP Libraryでは最大値ノルムとして計算しています。 与えられる行列\(A\)と\(b\)の成分はimatsではkv::interval< _T >型、pidblasではkv::interval< double >型になっているため、区間行列になっていることに注意が必要です。 \(R\)は\(\mbox{mid}(A)\)に対する近似逆行列とし，\( \tilde{x} \)は\( \mbox{mid}(A)x=\mbox{mid}(b) \)の近似解としているためimatsでは_T型、pidblasではdoubleになります。 具体的にはimatsでは_Pで指定した近似値用のポリシーを、pidblasはimats< double, pdblas >を継承しているため、BLASを用いた近似値用のポリシーpdblasを用いて\(R\)と\(\tilde{x}\)を求めています。 最終的には区間ベクトル \begin{align} \left[ \tilde{x} - \left( |R(b - A \tilde{x})| + \frac{ \| R(b - A \tilde{x}) \| }{ 1 - \| I - RA \| } |I - RA|e \right), \tilde{x} + \left( |R(b - A \tilde{x})| + \frac{ \| R(b - A \tilde{x}) \| }{1 - \| I - RA \| } |I - RA|e \right) \right] \end{align} を包含した結果をlss関数では返します。