QR分解による最小二乗法
アルゴリズム
$A \in \mathbb{C}^{m \times n}$ とベクトル $\mathbb{b} \in \mathbb{C}^{m}$ について、$\text{rank} A = n$ であり、$A \mathbb{x} = \mathbb{b}$ の最小二乗解を $\mathbb{x}_{\ast}$ とする。
ステップ 1. QR 分解
$A = \widehat{Q} \widehat{R}$ を満たす直交行列 $\widehat{Q}$ と上三角行列 $\widehat{R}$ を求める。
ステップ 2.
QR 分解で得た $\widehat{Q}$ を使って正射影 $P : = \widehat{Q} \widehat{Q}^{\ast}$ を求める。$A \mathbb{x}_{\ast} = P \mathbb{b}$ なので $\widehat{Q} \widehat{R} \mathbb{x}_{\ast} = \widehat{Q} \widehat{Q}^{\ast} \mathbb{b}$ となり、両辺の左に $\widehat{Q}^{\ast}$ を乗じて $\widehat{R} \mathbb{x}_{\ast} = \widehat{Q}^{\ast} \mathbb{b}$ を得る。
ステップ 3.
$\mathbb{y} := \widehat{Q}^{\ast} \mathbb{b}$ を計算して $\widehat{R} \mathbb{x}_{\ast} = \mathbb{y}$ を得る。
ステップ 4. 逆代入法
$\widehat{R}$ は上三角行列なので、逆代入法を使って方程式 $\widehat{R} \mathbb{x}_{\ast} = \mathbb{y}$ の解 $\mathbb{x}_{\ast}$ を求める。