[References]

1. 수치선형대수(Numerical Linear Algebra)

   http://matrix.skku.ac.kr/nla/

2. QR 분해 (QR decomposition)

   http://matrix.skku.ac.kr/sglee/03-Note/QR-Decomp.htm

   [강의] https://youtu.be/crMXPi2lgGs

3. Least Squares 문제에서 QR 분해의 응용

   http://matrix.skku.ac.kr/nla/ch7.htm

최소제곱문제 (Least Squares problems)

다음과 같이 선형연립방정식 $A{\bf x}={\bf b}$를 생각해보자.

다음에서 보듯이 선형연립방정식 $A{\bf x}={\bf b}$는 해가 없다.

이 경우 $A{\bf x}={\bf b}$를 만족하지는 않지만 다음을 만족하는 해를 생각할 수 있다.

    $\min_{{\bf x} \in\mathbb{R}^n} \|A{\bf x}-{\bf b}\|_2$

이를 최소제곱문제(least squares problems)라 하고 해 ${\bf x}$를 최소제곱해(least squares solution)이라고 한다.

QR 분해 (QR decomposition)

정리. 행렬 $A\in\mathbb{R}^{m\times n} (m\ge n)$에 대하여 다음과 같이 QR 분해가 존재한다. $A=Q\begin{bmatrix} R\\ 0\end{bmatrix}$.

여기서 $Q\in\mathbb{R}^{m\times m}$은 직교행렬 (orthogonal matrix, $Q^T=Q^{-1}$)이고

$R\in\mathbb{R}^{n\times n}$은  대각원소가 음이 아닌 상삼각행렬(upper-triangular matrix)이다. 

특히 $m=n$일 때, $A$가 가역이면, QR 분해는 유일하다. 

만일 $A$가 full-column rank (즉 ${\rm rank} (A)=n$)라면, $A$의 QR 분해는 다음과 같이 쓸 수 있다.

    $A=Q\begin{bmatrix} R\\ 0\end{bmatrix}=[Q_1, Q_2]\begin{bmatrix} R\\ 0\end{bmatrix}=Q_1R$

여기서 $Q_1\in\mathbb{R}^{m\times n}$, $Q_2\in\mathbb{R}^{m\times (m-n)}$이다. 이때 orthogonal matrix는 2-norm 길이를 보존하므로 다음이 성립한다. 

    $\|A{\bf x}-{\bf b}\|_2^2=\|Q^T(A{\bf x}-{\bf b})\|_2^2$

    $=\|\begin{bmatrix} R\\ 0\end{bmatrix}{\bf x}-Q^T{\bf b}\|_2^2=\|R{\bf x}-{\bf d_1}\|_2^2+\|{\bf d}_2\|_2^2$

여기서 $Q^T{\bf b}=\begin{bmatrix} {\bf d}_1\\ {\bf d}_2\end{bmatrix}$, ${\bf d}_1\in\mathbb{R}^n$, ${\bf d}_2\in\mathbb{R}^{m-n}$이다.

$\|{\bf d}_2\|_2$는 상수이므로 최소제곱문제는 다음을 이용하여 풀 수 있다.

    $\min_{{\bf x} \in\mathbb{R}^n} \|R{\bf x}-{\bf d}_1\|_2$

$A$가 full-colum rank인지 확인한다.

$A$의 QR 분해를 계산한다.

$A$가 full-column rank일 때는 $R$이 가역행렬이므로 최소제곱문제의 해는 ${\bf x}=R^{-1}{\bf d}_1$이다.

위에서 얻은 해는 아래와 같이 최소제곱문제의 normal equation을 이용하여 계산한 것과 일치한다. 

    $A^TA{\bf x}=A^T{\bf b}$

* $A$가 full-column rank가 아닐 경우에는 다음의 웹사이트를 참조하라.

http://matrix.skku.ac.kr/nla/ch7.htm

(아래 SageMathCell에 실습해보세요)