Applied Numerical Linear Algebra
01. Introduction
- $x = Ab$ を解きましょう.
- 直接法は疎でも $O(n^2)$ はかかってしまうので,反復法が良さそう
- $k$ 回目の反復で得られた解を $x^k$,残差を $r^k = b - Ax^k$ とおく
- Jacobi 法,Gauss-Seidel 法
02. Krylov Subspaces and Arnoldi Iteration
- Krylov 部分空間法 = Krylov 部分空間 を用いる手法の総称
- 対称正定値行列なら CG 法,対称なら MINERS, 一般には GMRES
- Krylov 部分空間 $\mathcal{K}^k = \operatorname{span} \, \{ b, Ab, A^2b, \ldots, A^{k-1}b \}$
- $A^{-1}b \in \mathcal{K}^k$ である(が故に求解に使える)
- $A^{-1}$ が $A, A^2, \ldots$ の線形結合で書けるから
Krylov Subspace Iterative Methods
- $Q^k = [q_1, q_2, \ldots, q_k]$ を $\mathcal{K}^k$ の直行基底とする
- $x^k$ = $\mathcal{K}^k$ 内で最良の解として求める
- $w^k = \arg \min || b - A Q^k w^k ||_2, x^k = Q^k w^k$
Arnoldi Iteration
- Arnoldi Iteration とは
- $Q^k$ が陽に必要な理由は,$A^kb$ は冪乗法に他ならず固有ベクトルに収束してしまうから
- なので,Graham-Schmit の直交化を行いながら進める
- これを Arnoldi Iteration と呼ぶらしい
- $Q^0 = [\frac{b}{||b||_2}]$ から開始
- 毎回 $A q_k$ を直行化して $q_{k+1}$ を得る
03. Properties of Arnoldi Iteration
- Arnoldi Iteration は,$Q^k$ を求めるだけでも良い手法だが,それだけではない
- Krylov 部分空間法のため最小二乗問題を解くのも楽になる
- 前イテレーションからの Givens 回転だけで行え,毎回 1 から解く必要がない
Why $v_{k+1} \not= 0$ in Practice
- $A b$ でなく $A q_k$ で良い理由
- $A q_k \in \mathcal{K}^k$ なら $A b \in \mathcal{K}^k$ だから
$Q^k$ Spans $\mathcal{K}^k$
- だいたい同じ
Upper Hessenberg Least Squares
- Graham-Schmit の直交化を移項すると,$A q_k$ は $q_1, \ldots, q_{k+1}$ の線形結合
- なので,$A Q^k = Q^{k+1} H^k$ と書ける
- $H^k$ は Hessenberg 行列
04. Givens QR and GMRES
QR and Least Squares
- QR 分解があるとなぜ最小二乗問題がすぐ解けるか?
- 回転 $Q^T$ を施しても二乗ノルムは変化せず,上三角行列の方程式を解くだけになる
QR with Arnoldi
- QR 分解とは微妙に異なり,上三角行列でなく Hessenberg 行列を使う分解を持ってる
- これを,微妙にいじって QR 分解を保持することにする
Givens QR for $H^{k+1}$
- Givens 回転
- 行列のある場所に 0 を導入するように回転する方法
- $G(i, k, \theta)$ は大体 $E$ だけど $(i, i), (k, k)$ が $c$ で $(i, k), (k, i)$ が $s$
- $H^k$ の QR 分解を持っているのであれば,Givens 回転を使って右下を 0 にするだけで $H^{k+1}$ の QR 分解が手に入る