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 分解が手に入る