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}$ 이라고 하자.
Step 1. QR 분해
$A = \widehat{Q} \widehat{R}$ 을 만족하는 직교행렬 $\widehat{Q}$ 과 상삼각행렬 $\widehat{R}$ 을 구한다.
Step 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}$ 를 얻는다.
Step 3.
$\mathbf{y} := \widehat{Q}^{\ast} \mathbf{b}$ 를 계산해 $\widehat{R} \mathbf{x}_{\ast} = \mathbf{y}$ 를 얻는다.
Step 4. 후진대입법
$\widehat{R}$ 는 상삼각행렬이므로 전진대입법을 통해 $\mathbf{x}_{\ast}$ 에 대한 방정식 $\widehat{R} \mathbf{x}_{\ast} = \mathbf{y}$ 의 해를 구한다.