SGCライブラリ - 85

実例で学ぶ精度保証付き数値計算

理論と実装

中尾充宏・渡部善隆　共著

2011年10月25日　初版発行

「精度保証付き数値計算」とは

数値計算の誤差の階層的な分類

レベル０：科学計算のもとになる数学モデルが、現象を正しく記述できていないことによる誤差（モデル化誤差）
レベル１：問題の解法手順が、計算機内で本質的に実現不能なことに起因する誤差（打ち切り誤差）
レベル２：計算機内で扱える数値が、有限桁であるために生じる誤差（丸め誤差）

区間演算と有限次元問題の精度保証

区間演算

${X = [\underline{x},\overline{x}] = \{x \in \mathbb{R}\,|\,\underline{x} \le x \le \overline{x},\,\underline{x},\overline{x} \in \mathbb{R}\}}$

で表現される閉集合 ${X}$ を区間と呼び、区間全体の集合を ${\mathbb{IR}}$ で表記する。

${\underline{x} = \overline{x}}$ となる区間 ${X}$ を点区間と呼ぶ。

区間 ${X = [a,b],\,Y = [c,d] \in \mathbb{IR}}$ と演算 ${\ast \in \{+,-,\cdot,/\}}$ に対し、２項演算 ${\ast}$ を以下で定義する：

${X \ast Y \equiv \{x \ast y\,|\,x \in X,\,y \in Y\}}$

${\mathbb{IR}}$ は演算 ${\ast}$ に関して閉じている。（ ${X \ast Y \in \mathbb{IR}}$ ）

${X + Y = [a + c, b + d]}$
${X - Y = [a - d, b - c]}$
${X \cdot Y = [\min\{ac,ad,bc,bd\}, \max\{ac,ad,bc,bd\}]}$
${X/Y = [a,b] \cdot [1/d,1/c] \quad (0 \notin Y)}$

区間演算の性質

包含関係における単調性
- ${\ast \in \{+,-,\cdot,/\}}$ に対し、 ${A \subset A^{\prime},\,B \subset B^{\prime}}$ ならば、 ${A \ast B \subset A^{\prime} \ast B^{\prime}}$
加法・乗法に関する交換則と結合則は成立
- ${A + B = B + A}$
- ${A \cdot B = B \cdot A}$
- ${A + (B + C) = (A + B) + C}$
- ${A \cdot (B \cdot C) = (A \cdot B) \cdot C}$
加法に関する逆元が存在しない
- ${0 = [0,0] \subset X - X = [\underline{x} - \overline{x},\overline{x} - \underline{x}]}$
乗法に関する逆元が存在しない
- ${1 = [1,1] \subset X/X}$ であり、 ${1}$ を含む区間になる。
半分配則のみ成立
- ${A \cdot (B + C) \subset A \cdot B + A \cdot C}$
- 等号が成立するのは、 ${A}$ が点区間か、 ${\forall b \in B,\,\forall c \in C}$ に対して ${b \cdot c \ge 0}$ となる場合。

Krawczyk 法

${\mathbf{f}}$ を ${\mathbb{R}^n}$ から ${\mathbb{R}^n}$ （ ${n \ge 1}$ ）への連続微分可能な写像とし、 ${\mathbf{f}(\mathbf{x}) = \mathbf{0}}$ を満たす ${\mathbf{x} \in \mathbb{R}^n}$ を求める問題を考える。

${\mathbf{f}}$ の ${\mathbf{x} \in \mathbb{R}^n}$ における微分すなわち Jacobi 行列 ${\mathbf{f}^{\prime}[\mathbf{x}]}$ を、 ${(\mathbf{f}^{\prime}[\mathbf{x}])_{ij} = \partial f_i(\mathbf{x})/\partial x_j}$ （ ${1 \le i,j \le n}$ ）で表す。

${\mathbf{X} \in \mathbb{IR}^n}$ に対して ${\mathbf{f}^{\prime}[\mathbf{X}]}$ を、その値域 ${\{\mathbf{f}^{\prime}[\hat{\mathbf{x}}] \in \mathbb{R}^n\,|\,\hat{\mathbf{x}} \in \mathbf{X}\}}$ を区間行列として拡張したもの（区間包囲）として表す。

${\mathbf{f}(\mathbf{x}) = \mathbf{0}}$ の近似解 ${\tilde{\mathbf{x}} \in \mathbb{R}^n}$ と、近似解 ${\mathbf{x}}$ における Jacobi 行列の逆行列の近似 ${R \approx \mathbf{f}^{\prime}[\tilde{\mathbf{x}}]^{-1}}$ を取る。

Krawczyk–Moore 作用素 ${\mathbf{K}: \mathbb{IR}^n \to \mathbb{IR}^n}$

${\mathbf{K}(\mathbf{X}) := -R \cdot \mathbf{f}(\tilde{\mathbf{x}}) + \{I - R \cdot \mathbf{f}^{\prime}[\tilde{\mathbf{x}} + \mathbf{X}]\}\mathbf{X}}$

${\mathbf{K}}$ は、集合をより小さな集合に移す縮小性を持つことが期待される。

解の存在条件

作用素 ${\mathbf{K}}$ と ${\mathbf{0} \in \mathbf{X} \in \mathbb{IR}^n}$ に対し ${\mathbf{K}(\mathbf{X}) \subset \mathrm{int}(\mathbf{X})}$ が成立するとき、 ${R}$ および ${\mathbf{f}^{\prime}[\tilde{\mathbf{x}} + \mathbf{X}]}$ に含まれるすべての行列は正則であり、 ${\mathbf{f}(\mathbf{x}) = \mathbf{0}}$ の解 ${\mathbf{x} \in \mathbb{R}^n}$ が ${\tilde{\mathbf{x}} + \mathbf{K}(\mathbf{X})}$ の中に局所一意に存在する。

${\mathrm{int}(\mathbf{X})}$ は ${X}$ の内点全体を意味する。

有限次元非線形方程式の解の検証アルゴリズム

${\mathbf{f}(\mathbf{x}) = \mathbf{0}}$ の近似解 ${\tilde{\mathbf{x}}}$ を計算。
${\mathbf{f}^{\prime}[\tilde{\mathbf{x}}]}$ の近似逆行列 ${R}$ を計算。
- ${\mathbf{Z} := -R \cdot \mathbf{f}(\tilde{\mathbf{x}})}$ を精度保証付きで計算。
- 初期区間ベクトル ${\mathbf{X}}$ と反復 ${k := 0}$ をセット。
- ある定数 ${\varepsilon \gt 0}$ に対し区間拡大 ${\hat{\mathbf{X}} := (1 + [-\varepsilon,\varepsilon])\mathbf{X}}$ を行う。
- ${\hat{\mathbf{X}}}$ と ${\mathbf{0}}$ を含む最小の区間ベクトルをあらためて ${\mathbf{X}}$ と置く。
- ${\mathbf{Y} := \mathbf{Z} + \{I - R \cdot \mathbf{f}^{\prime}[\tilde{\mathbf{x}} + \mathbf{X}]\}\mathbf{X}}$ を精度保証付きで計算。
- ${\mathbf{Y} \subset \mathrm{int}(\mathbf{X})}$ ならば検証完了。このとき ${\tilde{\mathbf{x}} + \mathbf{Y}}$ 内に解が一意に存在。
- そうでなければ ${k := k + 1,\,\mathbf{X} = \mathbf{Y}}$ として 4. に戻る。
- ${k}$ が最大反復回数に到達した場合や設定した閾値を超えた場合は反復終了。検証失敗。