数学 › 数値線形代数 › Krylov 部分空間法 I

前処理つき共役勾配法

定理 6.2（「Krylov 部分空間法 I」§6） ・ ✓公理まで証明済み

MM を正定値 Hermite 行列とし、M1/2M^{1/2} をその正定値な平方根とする。前処理つき共役勾配法を、r0=b−Ax0\boldsymbol{r}_0 = \boldsymbol{b} - A\boldsymbol{x}_0、z0=M−1r0\boldsymbol{z}_0 = M^{-1}\boldsymbol{r}_0、p0=z0\boldsymbol{p}_0 = \boldsymbol{z}_0 とし、

αk=rk∗zkpk∗Apk,xk+1=xk+αkpk,rk+1=rk−αkApk,zk+1=M−1rk+1,βk=rk+1∗zk+1rk∗zk,pk+1=zk+1+βkpk\begin{aligned} \alpha_k &= \frac{\boldsymbol{r}_k^{*}\boldsymbol{z}_k}{\boldsymbol{p}_k^{*}A\boldsymbol{p}_k}, & \boldsymbol{x}_{k+1} &= \boldsymbol{x}_k + \alpha_k\boldsymbol{p}_k, & \boldsymbol{r}_{k+1} &= \boldsymbol{r}_k - \alpha_kA\boldsymbol{p}_k,\\ \boldsymbol{z}_{k+1} &= M^{-1}\boldsymbol{r}_{k+1}, & \beta_k &= \frac{\boldsymbol{r}_{k+1}^{*}\boldsymbol{z}_{k+1}}{\boldsymbol{r}_k^{*}\boldsymbol{z}_k}, & \boldsymbol{p}_{k+1} &= \boldsymbol{z}_{k+1} + \beta_k\boldsymbol{p}_k \end{aligned}

で定める。A^=M−1/2AM−1/2\hat{A} = M^{-1/2}AM^{-1/2}、b^=M−1/2b\hat{\boldsymbol{b}} = M^{-1/2}\boldsymbol{b} とおくと、x^k=M1/2xk\hat{\boldsymbol{x}}_k = M^{1/2}\boldsymbol{x}_k は A^x^=b^\hat{A}\hat{\boldsymbol{x}} = \hat{\boldsymbol{b}} に x^0=M1/2x0\hat{\boldsymbol{x}}_0 = M^{1/2}\boldsymbol{x}_0 から共役勾配法を使った反復と一致する。とくに、M−1AM^{-1}A の固有値（正の実数）の最大と最小の比を κ^\hat{\kappa} として

∥xk−x∗∥A≤2(κ^−1κ^+1)k∥x0−x∗∥A.\|\boldsymbol{x}_k - \boldsymbol{x}^{*}\|_A \le 2\left(\frac{\sqrt{\hat{\kappa}} - 1}{\sqrt{\hat{\kappa}} + 1}\right)^k\|\boldsymbol{x}_0 - \boldsymbol{x}^{*}\|_A .

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

閉包の状態

✓ 公理まで証明済み

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

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

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

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

これを使っている定理

証明で明示的に参照している定理は、まだありません。

関連するノック 1 問