Section 4.4 QR분해와 그람–슈미트
Subsection 4.4.1 최소제곱해 찾기, 정사영 행렬 계산, 정규방정식
연립방정식 \(A\boldsymbol x = \boldsymbol b\)최소제곱해를 어떻게 찾을까? 절 4.4에서는 열이 선형독립인 \(A\)만을 다룰 것이다. 다시 말해 \(\ker(A)=0\)인 경우만 고려하며, 관찰 4.3.2에 따라 최소제곱해는 유일하다.
최소제곱해를 도출한 방식을 따라 계산하는 것이 가능하다. \(P:=A(A^{\operatorname{T}}A)^{-1}A^{\operatorname{T}}\)는 (4.2.8)에서 구한 \(\operatorname C(A)\)로의 정사영을 나타내는 행렬이다. \(P\)를 알면
\begin{equation}
A\boldsymbol x= P\boldsymbol b\tag{4.4.1}
\end{equation}
의 해를 찾는 것으로 귀결된다. 물론, 해를 찾기 위해서는 절 3.3의 방법을 적용할 수 있다.
\(P\)의 표현 (4.2.8)을 따라 역행렬 \((A^{\operatorname{T}}A)^{-1}\)을 구하고, 곱셉 \(A(A^{\operatorname{T}}A)^{-1}A^{\operatorname{T}}\)을 수행하면 된다.
사실 이 방법은 논리적으로 옳지만 실용적인 관점에서 썩 만족스럽지 않다. 대안으로, 정규방정식으로도 불리는
\begin{equation}
A^\operatorname TA \boldsymbol x = A^\operatorname T\boldsymbol b\tag{4.4.2}
\end{equation}
을 푸는 방법이 있다.
증명.
관찰 4.4.2. 증명에 대한 첨언.
위 증명에서는 \(A^{\operatorname{T}}A\)가 가역행렬이라는 점이 중요하게 사용되었다. 이는 \(A\)의 열이 선형독립일 때에 성립하는 사실이다. 정리 4.2.8을 참조하라.
여기까지의 논의를 정리해보자. 최소제곱해를 찾는 문제는 위 정리에 의하여 정규방정식을 푸는 문제로 환원된다. 정규방정식은 연립선형방정식이므로 LU분해 \(A^\operatorname TA=LU\)를 통해 해결할 수 있다.
Subsection 4.4.2 정규직교기저
정규방정식을 이용해 최소제곱해를 찾는 법에 대해 알아보았다. 다른 방식은 없을까? 답하기에 앞서 행렬 \(P\)에 대해 고찰해보자.
\(P\)는 부분공간 \(V:=\operatorname{C}(A)\)로의 정사영을 나타내는 행렬이고, 이때 \(A\)의 열벡터는 \(V\)의 기저이다. 정사영으로 주어지는 대응 \(\boldsymbol x \mapsto P\boldsymbol x\)은 기저와 무관하게 부분공간 \(V\)만으로 결정된다. 부연하건대,
\begin{equation*}
V=\operatorname{C}(B)
\end{equation*}
이면 \(P=B(B^{\operatorname{T}}B)^{-1}B^{\operatorname{T}}\)이어야 한다. 언제 \(B(B^{\operatorname{T}}B)^{-1}B^{\operatorname{T}}\)를 쉽게 구할 수 있을까?
정의 4.4.3. 정규직교.
두 벡터 \(\boldsymbol v\text{,}\) \(\boldsymbol w\)의 정규직교란 \(\boldsymbol v \perp \boldsymbol w\)이고 \(|\!|\boldsymbol v |\!|=|\!|\boldsymbol w|\!|=1\)인 것을 말한다. 둘 이상 벡터의 모임이 있는 경우 둘씩 정규직교하면 모임이 정규직교한다고 말한다.
관찰 4.4.4. 정규직교하면 선형독립.
벡터 \(\boldsymbol v_1,\cdots,\boldsymbol v_r\)이 정규직교하면 이들은 선형독립이다. 왜냐하면 \(a_1\boldsymbol v_1+\cdots+a_r\boldsymbol v_r=0\)에 \(\boldsymbol v_i\)를 내적하면 \(a_i=0\)을 얻기 때문이다.
명제 4.4.5.
\(B\)의 열벡터가 정규직교하면 \(\operatorname{C}(B)\)로의 정사영은 행렬 \(BB^\operatorname{T}\)로 주어진다.
증명.
관찰 4.4.4으로부터 정사영행렬은 \(B(B^\operatorname{T}B)^{-1}B^\operatorname{T}\)임을 안다. \(B^\operatorname{T}B\)의 성분을 내적으로 표현해보면 \(B\)의 열이 정규직교한다는 조건에서 \(B^\operatorname{T}B=I\)를 안다. \(I^{-1}=I\)이므로 원하던 결론을 얻는다.
예시 4.4.6. 정규직교하는 두 벡터.
\(\frac 1 2(1,1,1,1)\)과 \(\frac 1 2 (1,1,-1,-1)\)은 정규직교한다.
예시 4.4.7. 정규직교하는 벡터 모임.
\((1,0,0)\text{,}\) \((0,1,0)\text{,}\) \((0,0,1)\)은 정규직교하는 (세 벡터의) 모임이다.
정의 4.4.8.
정규직교기저란 기저가 정규직교하는 경우를 말한다.
예시 4.4.9. 표준기저는 정규직교기저.
정의 3.2.5의 표준기저는 정규직교기저이다.
예시 4.4.10. \(\mathbf R\)의 정규직교기저.
\(\mathbf R\)의 정규기저는 두 개다. 하나는 \((1)\text{,}\) 다른 하나는 \((-1)\)이다.
예시 4.4.11. 평면의 정규직교기저.
\(V= \{(x,y,z)\in\mathbf R^3 | x+2y=5z\}\)라 하자. 평면 \(V\)의 정규직교기저로는 \(\frac{1}{\sqrt 6}(1,2,1),\frac{1}{\sqrt 5}(2,-1,0)\)이 있다.
Subsection 4.4.3 QR-분해와 최소제곱해
\(A\)의 열벡터로 주어진 \(V\)의 정규직교기저를 찾는 문제는 행렬 분해로 환원할 수 있다.
정의 4.4.12.
\(A\)의 QR분해란
\begin{equation*}
A=QR
\end{equation*}
이 다음 두 조건을 만족하는 것을 말한다.
- \(Q\)의 열벡터는 정규직교한다.
- \(R\)은 가역인 윗삼각행렬이다.
예시 4.4.13. \(2 \times 2\) 행렬의 QR분해 1.
행렬
\begin{equation*}
\begin{bmatrix}
\frac{-\sqrt 3}{2} \amp \frac{1}{2}
\\
\frac{1}{2} \amp \frac{\sqrt 3}{2}
\end{bmatrix}
\end{equation*}
의 열벡터는 정규직교하고, QR분해는
\begin{equation*}
\begin{bmatrix}
\frac{-\sqrt 3}{2} \amp \frac{1}{2}
\\
\frac{1}{2} \amp \frac{\sqrt 3}{2}
\end{bmatrix}
=
\begin{bmatrix}
\frac{-\sqrt 3}{2} \amp \frac{1}{2}
\\
\frac{1}{2} \amp \frac{\sqrt 3}{2}
\end{bmatrix}
\begin{bmatrix}
1 \amp 0
\\
0\amp 1
\end{bmatrix}
\end{equation*}
이다.
예시 4.4.14. \(2 \times 2\) 행렬의 QR분해 2.
행렬
\begin{equation*}
\begin{bmatrix}
0\amp 2
\\
1 \amp 3
\end{bmatrix}
\end{equation*}
의 QR분해는
\begin{equation*}
\begin{bmatrix}
0\amp 2
\\
1 \amp 3
\end{bmatrix}
=
\begin{bmatrix}
0 \amp 1
\\
1 \amp 0
\end{bmatrix}
\begin{bmatrix}
1 \amp 3
\\
0 \amp 2
\end{bmatrix}
\end{equation*}
이다.
예시 4.4.15. \(3 \times 3\) 행렬의 QR분해.
행렬
\begin{equation*}
\begin{bmatrix}
1 \amp 0 \amp 2
\\
0 \amp \frac 3 5 \amp 1
\\
0 \amp - \frac 4 5 \amp 3
\end{bmatrix}
\end{equation*}
의 QR분해는
\begin{equation*}
\begin{bmatrix}
1 \amp 0 \amp 2
\\
0 \amp \frac 3 5 \amp 1
\\
0 \amp - \frac 4 5 \amp 3
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0 \amp 0
\\
0 \amp \frac 3 5 \amp \frac{4}{5}
\\
0 \amp - \frac 4 5 \amp \frac{3}{5}
\end{bmatrix}
\begin{bmatrix}
1 \amp 0 \amp 2
\\
0 \amp 1\amp \frac{-9}{5}
\\
0 \amp 0 \amp \frac{13}{5}
\end{bmatrix}
\end{equation*}
예시 4.4.16. \(3 \times 2\) 행렬의 QR분해.
행렬
\begin{equation*}
\begin{bmatrix}
1 \amp 2
\\
0 \amp 3
\\
0 \amp 4
\end{bmatrix}
\end{equation*}
의 QR분해는
\begin{equation*}
\begin{bmatrix}
1 \amp 2
\\
0 \amp 3
\\
0 \amp 4
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0
\\
0 \amp \frac 3 5
\\
0 \amp \frac 4 5
\end{bmatrix}
\begin{bmatrix}
1 \amp 2
\\
0 \amp 5
\end{bmatrix}
\end{equation*}
이다.
예시 4.4.17. \(4 \times 1\) 행렬의 QR분해.
행렬
\begin{equation*}
\begin{bmatrix}
1 \\ 1 \\ -1 \\ -1
\end{bmatrix}
\end{equation*}
의 QR분해는
\begin{equation*}
\begin{bmatrix}
1 \\ 1 \\ -1 \\ -1
\end{bmatrix}
=
\begin{bmatrix}
\frac 1 2 \\ \frac 1 2 \\ -\frac 1 2 \\ - \frac 1 2
\end{bmatrix}
\begin{bmatrix} 2 \end{bmatrix}
\end{equation*}
이다.
예시 4.4.18. \(4 \times 3\) 행렬의 QR분해.
행렬
\begin{equation*}
\begin{bmatrix}
\frac 1 2 \amp \frac 1 2 \amp 3
\\
\frac 1 2 \amp \frac 1 2 \amp 4
\\
\frac 1 2 \amp - \frac 1 2 \amp 1
\\
\frac 1 2 \amp - \frac 1 2 \amp 0
\end{bmatrix}
\end{equation*}
의 QR분해는
\begin{equation*}
\begin{bmatrix}
\frac 1 2 \amp \frac 1 2 \amp -\frac 1 2
\\
\frac 1 2 \amp \frac 1 2 \amp \frac 1 2
\\
\frac 1 2 \amp - \frac 1 2 \amp \frac 1 2
\\
\frac 1 2 \amp - \frac 1 2 \amp -\frac 1 2
\end{bmatrix}
\begin{bmatrix}
1 \amp 0 \amp 4
\\
0 \amp 1 \amp 3
\\
0 \amp 0 \amp 1
\end{bmatrix}
\end{equation*}
이다.
명제 4.4.19.
QR분해 \(A=QR\)에서 \(Q\)의 열벡터는 \(\operatorname{C}(A)\)의 정규직교기저이다.
증명.
\(QR\)의 열벡터는 \(Q\)의 열공간의 원소이다. 따라서 \(\operatorname{C}(A)\subset\operatorname{C}(Q)\)이다. \(\dim\operatorname{C}(A)=\dim\operatorname{C}(Q)\)이므로 명제 4.1.11에 의해 \(\operatorname{C}(A)=\operatorname{C}(Q)\)를 얻는다.
QR분해를 이용해 최소제곱해를 구해보자. 정규방정식 (4.4.2)은
\begin{equation*}
R^\operatorname T Q^\operatorname T QR\boldsymbol x = R^\operatorname TQ^T\boldsymbol b
\end{equation*}
가 된다. \(Q\)의 열벡터가 정규직교하므로 \(Q^\operatorname TQ=I\)이고 위 식은
\begin{equation*}
R^\operatorname T R\boldsymbol x = R^\operatorname TQ^T\boldsymbol b
\end{equation*}
이 된다. 한편 관찰 4.4.20에 따라 \(\ker(R^\operatorname T)=0\)는 가역이다.
관찰 4.4.20.
\begin{equation}
R\boldsymbol x = Q^T\boldsymbol b\tag{4.4.3}
\end{equation}
이다.
정리 4.4.21.
증명.
먼저 정리 4.4.1에 따라 최소제곱해는 정규방정식으로 표현됨을 상기하자. (4.4.3)의 유도과정을 보면 최소제곱해는 (4.4.3)를 만족한다. 역으로, (4.4.3)를 만족하면 양변에 \(R^{\operatorname T}\)를 곱하고 (4.2.5)을 이용해
\begin{equation*}
R^\operatorname TR\boldsymbol x = A^\operatorname T\boldsymbol b
\end{equation*}
를 얻는다. 비슷하게 \(R^\operatorname TR=R^\operatorname TIR=R^\operatorname TQ^\operatorname T QR= A^\operatorname TA\)를 얻으면 (4.4.2)이 된다.
Subsection 4.4.4 고찰
Subsection 4.4.5 그람–슈미트로 QR분해 구하기
주어진 행렬의 QR분해가 존재함을 보이고 더 나아가 계산법을 알려주는 그람–슈미트 알고리즘을 소개한다. 알고리즘은 재귀적으로 구성되는데, 그 기본 단위는 다음 과제로 구성된다.
- 행렬 \(A_{k+1}\)의 열벡터 \(\boldsymbol v_1,\cdots,\boldsymbol v_k,\boldsymbol v_{k+1}\)이 선형독립이고 \(\boldsymbol v_1,\cdots,\boldsymbol v_k\)이 정규직교할 때 \(A_{k+1}=Q_{k+1}R_{k+1}\)을 구하여라.
기본 단위 과제는 다음과 같이 해결한다. \(V_k :=\operatorname{span}(\boldsymbol v_1,\cdots,\boldsymbol v_k)\)라 하고, (4.2.4)에 따른 분해
\begin{equation*}
\boldsymbol v_{k+1} = \widehat {\boldsymbol v_{k+1}}+\boldsymbol e_{k+1},\hspace{10pt}\text{(단, $\widehat{\boldsymbol v_{k+1}} \in \operatorname{C}(V_k)$, $\boldsymbol e_{k+1} \in \operatorname{C}(V_k)^\perp)$}
\end{equation*}
를 구한다. 이때, \(\widehat {\boldsymbol v_{k+1}}\)은 명제 4.4.5을 이용해 계산하고, 구체적으로는
\begin{equation*}
\widehat {\boldsymbol v_{k+1}} = (\boldsymbol v_{k+1}\bullet \boldsymbol v_{1})\boldsymbol v_{1} + \cdots +(\boldsymbol v_{k+1}\bullet \boldsymbol v_{k})\boldsymbol v_{k}
\end{equation*}
이다. 원하는 분해는
\begin{equation*}
Q_{k+1} = \begin{bmatrix}\boldsymbol v_1 \amp \cdots \amp \boldsymbol v_k \amp \frac{\boldsymbol e_{k+1}}{|\!|\boldsymbol e_{k+1}|\!|}\end{bmatrix}
\end{equation*}
로부터 찾는다. 이 때,
\begin{equation*}
\boldsymbol v_{k+1}=(\boldsymbol v_{k+1}\bullet \boldsymbol v_{1})\boldsymbol v_{1} + \cdots +(\boldsymbol v_{k+1}\bullet \boldsymbol v_{k})\boldsymbol v_{k} + |\!|\boldsymbol e_{k+1}|\!| \frac{\boldsymbol e_{k+1}}{|\!|\boldsymbol e_{k+1}|\!|}
\end{equation*}
이므로, \(A_{k+1}=Q_{k+1}R_{k+1}\) 분해는
\begin{equation*}
A_{k+1}= Q_{k+1} \begin{bmatrix}I\amp \substack{\boldsymbol v_{k+1}\bullet \boldsymbol v_{1}\\\vdots\\\boldsymbol v_{k+1}\bullet \boldsymbol v_{k}}\\0\cdots0\amp |\!|\boldsymbol e_{k+1}|\!|\end{bmatrix}
\end{equation*}
이 된다.
기본 단위로부터 일반적인 QR분해를 얻는 것은 어렵지 않다. 행렬 \(A\)의 열벡터 \(\boldsymbol v_1,\cdots, \boldsymbol v_n\)이 선형독립일 때,
\begin{equation*}
A= \begin{bmatrix}A_{n-1} \amp \boldsymbol v_n\end{bmatrix}
\end{equation*}
으로 나누자. 단, \(A_{n-1}\)의 열벡터는 \(\boldsymbol v_1,\cdots,\boldsymbol v_{n-1}\)이다. \(A_{n-1}\)은 열벡터 수가 줄었으므로 재귀에 의해
\begin{equation*}
A_{n-1}=Q_{n-1}R_{n-1}
\end{equation*}
로 분해한다. 이를 이용해
\begin{equation*}
A =\begin{bmatrix}Q_{n-1}R_{n-1} \amp \boldsymbol v_n\end{bmatrix} =
\begin{bmatrix}Q_{n-1} \amp \boldsymbol v_n\end{bmatrix} \begin{bmatrix}R_{n-1} \amp \substack{0\\\vdots\\0}\\0\cdots0\amp 1\end{bmatrix}
\end{equation*}
를 얻는다. 기본 단위로부터
\begin{equation*}
\begin{bmatrix}Q_{n-1} \amp \boldsymbol v_n\end{bmatrix} = Q_nR_n
\end{equation*}
을 얻는다. 이 때,
\begin{equation*}
R := R_n \begin{bmatrix}R_{n-1} \amp \substack{0\\\vdots\\0}\\0\cdots0\amp 1\end{bmatrix}
\end{equation*}
은 두 윗삼각행렬의 곱이므로 다시 윗삼각행렬이다. \(Q=Q_n\)으로 놓으면 원하던 \(A=QR\)분해를 얻는다.
연습문제 4.4.6 연습문제
1. \(R\)의 대각성분.
\(A\)의 QR분해 \(A=QR\)에서 \(R\)의 대각성분은 항상 양수가 되게 할 수 있다. 왜 그런가?
단서.
그람–슈미트 방법을 적용하면 항상 대각성분이 양수임을 확인하여라. 다음 분해
\begin{equation*}
\begin{bmatrix}
1 \amp 1
\\
0 \amp 2
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0
\\
0 \amp -1
\end{bmatrix}
\begin{bmatrix}
1 \amp 1
\\
0 \amp -2
\end{bmatrix}
\end{equation*}
를 고려해 볼 수도 있다.
