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