📂行列代数

QR分解による最小二乗法

アルゴリズム

$A \in \mathbb{C}^{m \times n}$ とベクトル $\mathbf{b} \in \mathbb{C}^{m}$ について、$\text{rank} A = n$ であり、$A \mathbf{x} = \mathbf{b}$ の最小二乗解を $\mathbf{x}_{\ast}$ とする。

ステップ 1. QR 分解

$A = \widehat{Q} \widehat{R}$ を満たす直交行列 $\widehat{Q}$ と上三角行列 $\widehat{R}$ を求める。

---

ステップ 2.

QR 分解で得た $\widehat{Q}$ を使って正射影 $P : = \widehat{Q} \widehat{Q}^{\ast}$ を求める。$A \mathbf{x}_{\ast} = P \mathbf{b}$ なので $\widehat{Q} \widehat{R} \mathbf{x}_{\ast} = \widehat{Q} \widehat{Q}^{\ast} \mathbf{b}$ となり、両辺の左に $\widehat{Q}^{\ast}$ を乗じて $\widehat{R} \mathbf{x}_{\ast} = \widehat{Q}^{\ast} \mathbf{b}$ を得る。

---

ステップ 3.

$\mathbf{y} := \widehat{Q}^{\ast} \mathbf{b}$ を計算して $\widehat{R} \mathbf{x}_{\ast} = \mathbf{y}$ を得る。

---

ステップ 4. 逆代入法

$\widehat{R}$ は上三角行列なので、逆代入法を使って方程式 $\widehat{R} \mathbf{x}_{\ast} = \mathbf{y}$ の解 $\mathbf{x}_{\ast}$ を求める。