数学 › 計算機援用証明 › 行列計算の認証と最適化の証明書

Cholesky 分解の後ろ向き誤差

定理 4.2（「行列計算の認証と最適化の証明書」§4）・ ✓公理まで証明済み

対称行列 $A\in\mathbb{F}^{n\times n}$ の浮動小数の Cholesky 分解が失敗せずに $\widetilde R$ を返したとする。このとき

\widetilde R^{\mathsf{T}}\widetilde R=A+\Delta A,\qquad|\Delta A|\le\gamma_{n+1}|\widetilde R|^{\mathsf{T}}|\widetilde R|,

さらに各 $j$ について $\sum_k\tilde r_{kj}^2\le a_{jj}/(1-\gamma_{n+1})$ が成り立つ。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 4 件、定義なども含めて 4 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義（直接 1 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

1 ステップの丸め誤差✓補題 4.1・行列計算の認証と最適化の証明書
- 丸めの誤差モデル✓定理 2.4・浮動小数と区間演算
  - 浮動小数の間隔✓補題 2.2・浮動小数と区間演算
- 誤差因子の積✓補題 3.2・浮動小数と区間演算

これを使っている定理証明で参照している 2 件

Rump の正定値性検証✓定理 4.3・行列計算の認証と最適化の証明書
Cholesky 分解の後退安定性✓系 3.1・Cholesky 分解と帯行列・疎行列の直接法

関連するノック 3 問