최소제곱해

최소제곱해

\(m\times n\)행렬 \(A\)에 대해 선형방정식 \(A\mathbf{x}=\mathbf{b}\)가 적어도 하나의 해를 가질 필요충분조건은 \(\mathbf{b}\)가 \(A\)의 열공간 \(\mathcal{C}(A)\)의 원소가 되는 것이다. 이 경우, 해가 유일할 필요충분조건은 \(A\)의 영공간 \(\mathcal{N}(A)\)가 자명한 것이다. 

만약 \(\mathbf{b}\notin\mathcal{C}(A)\subset\mathbb{R}^{m}\)이면, \(A\mathbf{x}=\mathbf{b}\)는 해를 갖지 않는다. 이때 모든 \(\mathbf{x}\in\mathbb{R}^{n}\)에 대하여 \(A\mathbf{x}\in\mathcal{C}(A)\)이므로 \(A\mathbf{x}_{0}\)가 \(\mathbf{b}\)에 가장 가깝게(closest)하는 벡터 \(\mathbf{x}_{0}\in\mathbb{R}^{n}\)를 찾는 것이 최선이다. 즉, \(\|A\mathbf{x}_{0}-\mathbf{b}\|\)(최소제곱오차)가 최소가 되게 하는 \(\mathbf{x}_{0}\)를 찾는 것이 최선이다. 이러한 벡터 \(\mathbf{x}_{0}\)는 \(A\mathbf{x}_{0}\)를 \(\mathbf{b}\)에 가장 가깝게 하는 벡터이고, 이것을 선형방정식 \(A\mathbf{x}=\mathbf{b}\)의 최소제곱해(least square solution)라고 한다.

\(\mathbb{R}^{m}=\mathcal{C}(A)\oplus\mathcal{N}(A^{T})\)이므로 임의의 \(b\in\mathbb{R}^{m}\)에 대하여 \(\text{Proj}_{\mathcal{C}(A)}(\mathbf{b})=\mathbf{b}_{c}\in\mathcal{C}(A)\)는 \(\mathcal{C}(A)\)에 속하는 벡터들 중에서 \(\mathbf{b}\)에 가장 가까운 벡터이다. 그러므로 최소제곱해 \(\mathbf{x}_{0}\in\mathbb{R}^{n}\)은 임의의 \(\mathbf{x}\in\mathbb{R}^{n}\)에 대하여 다음의 조건들을 만족시킨다.$$\begin{align*}A\mathbf{x}_{0}=b_{c}&=\text{Proj}_{\mathcal{C}(A)}(b)\\ \|A\mathbf{x}_{0}-\mathbf{b}\|&\leq\|A\mathbf{x}-\mathbf{b}\|\end{align*}$$\(\mathbf{b}_{c}\in\mathcal{C}(A)\)이므로 방정식 \(A\mathbf{x}_{0}=\mathbf{b}_{c}\)를 만족하는 최소제곱해 \(\mathbf{x}_{0}\in\mathbb{R}^{n}\)는 항상 존재한다. 다른 최소제곱해들은 \(\mathbf{x}_{0}+\mathcal{N}(A)\)의 원소이다. 

정리하자면 방정식 \(A\mathbf{x}=\mathbf{b}\,(\mathbf{b}\notin\mathcal{C}(A))\)의 최소제곱해는 \(A\mathbf{x}=\mathbf{b}_{c}\)의 해이고, 여기서 \(\mathbf{b}_{c}=\text{Proj}_{\mathcal{C}(A)}(\mathbf{b})\in\mathcal{C}(A)\)는 \(\mathbf{b}\)의 유일한 직교분해 중 하나이다.$$\mathbf{b}=\mathbf{b}_{c}+\mathbf{b}_{n}\in\mathcal{C}(A)\oplus\mathcal{N}(A^{T})=\mathbb{R}^{m}\,(\mathbf{b}_{n}=\mathbf{b}-\mathbf{b}_{c}\in\mathcal{N}(A^{T}))$$이것은 최소제곱해를 찾기 위해서는 먼저 \(\mathbf{b}_{c}\)를 찾아야 하고, 그 다음으로 방정식 \(A\mathbf{x}_{0}=\mathbf{b}_{c}\)를 풀면 됨을 뜻한다.

\(\mathbf{b}\)의 \(\mathcal{C}(A)\)로의 직교사영 \(\mathbf{b}_{c}\)를 구하는 것은 어렵기 때문에 그람-슈미츠 과정(실제로 해보면 복잡하다)을 이용하여 \(\mathcal{C}(A)\)의 정규직교기저를 구한 다음, \(\mathbf{b}\)에 대한 정규직교기저를 이용하여 \(\mathbf{b}_{c}\)를 나타낸다. 

가장 쉬운 방법: \(\mathbf{x}_{0}\in\mathbb{R}^{n}\)이 \(A\mathbf{x}=\mathbf{b}\)의 최소제곱해이면, 즉 \(A\mathbf{x}_{0}=\mathbf{b}_{c}\)의 해이면, 다음이 성립한다.$$A\mathbf{x}_{0}-\mathbf{b}=A\mathbf{x}_{0}-(\mathbf{b}_{c}+\mathbf{b}_{n})=-\mathbf{b}_{n}\in\mathcal{N}(A^{T})$$따라서 방정식 \(A\mathbf{x}_{0}=\mathbf{b}\)의 양변에 \(A^{T}\)를 곱해주면 \(A^{T}A\mathbf{x}_{0}=A^{T}\mathbf{b}\)이고, 이것은 \(\mathbf{x}_{0}\)가 다음의 방정식의 해가 됨을 뜻한다.$$A^{T}A\mathbf{x}=A^{T}\mathbf{b}$$이 방정식을 \(A\mathbf{x}=\mathbf{b}\)의 정규방정식(normal equation)이라고 한다. 이 결과를 다음과 같이 정리할 수 있다.

\(A\)를 \(m\times n\)행렬, \(\mathbf{b}\in\mathbb{R}^{m}\)를 임의의 벡터라고 하자. 그러면 벡터 \(\mathbf{x}_{0}\in\mathbb{R}^{n}\)가 \(A\mathbf{x}=\mathbf{b}\)의 최소제곱해가 될 필요충분조건은 \(\mathbf{x}_{0}\)가 정규방정식 \(A^{T}A\mathbf{x}=A^{T}\mathbf{b}\)의 해가 되는 것이다.     

증명: 필요조건만 증명하면 된다. \(\mathbf{x}_{0}\)가 정규방정식 \(A^{T}A\mathbf{x}=A^{T}\mathbf{b}\)의 해이면, \(A^{T}(A\mathbf{x}_{0}-\mathbf{b})=\mathbf{0}\)이므로 다음이 성립한다.$$A\mathbf{x}_{0}-\mathbf{b}=A\mathbf{x}_{0}-(\mathbf{b}_{c}+\mathbf{b}_{n})\in\mathcal{N}(A^{T})$$이것은 다음을 뜻하고$$A\mathbf{x}_{0}-\mathbf{b}_{c}\in\mathcal{N}(A^{T})\cap\mathcal{C}(A)=\{\mathbf{0}\}$$따라서 \(A\mathbf{x}_{0}=\mathbf{b}_{c}=\text{Proj}_{\mathcal{C}(A)}(\mathbf{b})\) 즉 \(\mathbf{x}_{0}\)는 \(A\mathbf{x}=\mathbf{b}\)의 최소제곱해이다. 

예: 행렬 \(A\)와 벡터 \(\mathbf{b}\)과 다음과 같을 때 \(A\mathbf{x}=\mathbf{b}\)의 최소제곱해와 \(\mathbf{b}_{c}=\text{Proj}_{\mathcal{C}(A)}(\mathbf{b})\)를 구하시오.$$A=\begin{pmatrix}1&-2&1\\2&-3&-1\\-1&1&2\\3&-5&0\end{pmatrix},\,\mathbf{b}=\begin{pmatrix}1\\0\\1\\0\end{pmatrix}$$풀이: \(A^{T}A\)를 구하면 다음과 같고$$A^{T}A=\begin{pmatrix}1&2&-1&3\\-2&-3&1&-5\\1&-1&2&0\end{pmatrix}\begin{pmatrix}1&-2&1\\2&-3&-1\\-1&1&2\\3&-5&0\end{pmatrix}=\begin{pmatrix}15&-24&-3\\-24&39&3\\-3&3&6\end{pmatrix}$$\(A^{T}\mathbf{b}\)는 다음과 같다.$$A^{T}\mathbf{b}=\begin{pmatrix}1&2&-1&3\\-2&-3&1&-5\\1&-1&2&0\end{pmatrix}\begin{pmatrix}1\\0\\1\\0\end{pmatrix}=\begin{pmatrix}0\\-1\\3\end{pmatrix}$$정규방정식으로부터 \(A\mathbf{x}=\mathbf{b}\)의 최소제곱해는 \(A^{T}A\mathbf{x}=A^{T}\mathbf{b}\)의 해이다. 즉 다음의 방정식의 해이다.$$\begin{pmatrix}15&-24&-3\\-24&39&3\\-3&3&6\end{pmatrix}\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}=\begin{pmatrix}0\\-1\\3\end{pmatrix}$$이 방정식의 해는 다음과 같고$$\mathbf{x}=\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}=\frac{1}{3}\begin{pmatrix}-8\\-5\\0\end{pmatrix}+t\begin{pmatrix}5\\3\\1\end{pmatrix}\,(t\in\mathbb{R})$$\(\mathbf{b}_{c}\)는 다음과 같이 구할 수 있다.$$\mathbf{b}_{c}=A\mathbf{x}=\frac{1}{3}\begin{pmatrix}2\\-1\\3\\1\end{pmatrix}\in\mathcal{C}(A)$$여기서 다음에 주의한다.$$\mathbf{x}=\frac{1}{3}\begin{pmatrix}-8\\-5\\0\end{pmatrix}\notin\mathcal{R}(A)$$이 예는 정규방정식의 해가 \(A^{T}A\)에 의존함을 보여준다. 

\(A^{T}:\mathbb{R}^{m}\,\rightarrow\,\mathbb{R}^{n}\)이고 \(\mathcal{R}(A)=\mathcal{C}(A^{T})\)이다. 따라서 임의의 \(\mathbf{x}_{r}\in\mathcal{C}(A^{T})=\mathcal{R}(A)\)에 대하여 벡터 \(\mathbf{b}\in\mathbb{R}^{m}\)가 존재해서 \(A^{T}\mathbf{b}=\mathbf{x}_{r}\)이다. \(\mathbf{b}=\mathbf{b}_{c}+\mathbf{b}_{n}\)(\(\mathbf{b}_{c}\in\mathcal{C}(A)\), \(\mathbf{b}_{n}\in\mathcal{N}(A^{T})\))로 나타내면, \(\mathbf{x}_{r}=A^{T}\mathbf{b}=A^{T}\mathbf{b}_{c}\)이다. 그러므로 다음의 제한사상$$\begin{align*}\overline{A}=A|_{\mathcal{R}(A)}:\mathcal{R}(A)\,\rightarrow\,\mathcal{C}(A)\\ \overline{A^{T}}=A^{T}|_{\mathcal{C}(A)}:\mathcal{C}(A)\,\rightarrow\,\mathcal{R}(A)\end{align*}$$은 일대일이고 전사이므로 가역이다. 하지만 이러한 경우에도 \(\overline{A}\overline{A^{T}}=I_{r}\)도 \(\overline{A^{T}}\overline{A}=I_{r}\)도 성립하지 않을 수 있다. 

다음의 정리는 \(A^{T}A\)가 역행렬을 가질 조건을 제공한다.

임의의 \(m\times n\)행렬 \(A\)에 대하여 \(A^{T}A\)는 \(n\times n\)대칭행렬이고, \(\text{rank}(A^{T}A)=\text{rank}A\)이다.   

증명: \((A^{T}A)^{T}=A^{T}(A^{T})^{T}=A^{T}A\)이므로 \(A^{T}A\)는 대칭행렬이다. \(A\)와 \(A^{T}A\)의 열의 개수가 각각 \(n\)이므로 다음이 성립한다.$$\text{rank}A+\text{dim}\mathcal{N}(A)=n=\text{rank}(A^{T}A)+\text{dim}\mathcal{N}(A^{T}A)$$남은 것은 \(\mathcal{N}(A)=\mathcal{N}(A^{T}A)\)임을 보이면 된다. \(\mathbf{x}\in\mathcal{N}(A)\)이면, \(A\mathbf{x}=\mathbf{0}\)이고 \(A^{T}A\mathbf{x}=A^{T}\mathbf{0}=\mathbf{0}\)이므로 \(\mathbf{x}\in\mathcal{N}(A^{T}A)\)이다. 역으로 \(A^{T}A\mathbf{x}=\mathbf{0}\)이라고 하면$$A\mathbf{x}\cdot A\mathbf{x}=(A\mathbf{x})^{T}(A\mathbf{x})=\mathbf{x}^{T}(A^{T}A\mathbf{x})=\mathbf{x}\cdot A^{T}A\mathbf{x}=\mathbf{x}\cdot\mathbf{0}=0$$이므로 \(A\mathbf{x}=\mathbf{0}\), 즉 \(\mathbf{x}\in\mathcal{N}(A)\)이다.   

\(A\)의 열들이 선형독립이면, 즉 \(\text{rank}A=n\)이면, \(\mathcal{N}(A)=\{\mathbf{0}\}\)이거나 \(A\)는 일대일이므로 \(A\mathbf{x}=\mathbf{b}_{c}\)는 유일한 해 \(\mathbf{x}\in\mathcal{R}(A)=\mathbb{R}^{n}\)를 갖고, \(\text{rank}(A^{T}A)=\text{rank}(A)=n\)이므로 \(A^{T}A\)는 역행렬을 갖고 최소제곱해는 다음과 같다.$$\mathbf{x}=(A^{T}A)^{-1}A^{T}\mathbf{b}$$예: 다음의 방정식에서$$A\mathbf{x}=\begin{pmatrix}1&2\\1&5\\0&0\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}4\\3\\9\end{pmatrix}=\mathbf{b}$$\(A\)의 두 열은 선형독립이고 \(\text{dim}\mathcal{C}(A)=2\)이므로 \(\mathbf{b}\notin\mathcal{C}(A)\)이다.$$A^{T}A=\begin{pmatrix}1&1&0\\2&5&0\end{pmatrix}\begin{pmatrix}1&2\\1&5\\0&0\end{pmatrix}=\begin{pmatrix}2&7\\7&29\end{pmatrix}$$는 역행렬이 존재하고 그 역행렬은$$(A^{T}A)^{-1}=\frac{1}{9}\begin{pmatrix}29&-7\\-7&2\end{pmatrix}$$이므로 이 방정식의 최소제곱해는 다음과 같다.$$\begin{align*}\mathbf{x}&=(A^{T}A)^{-1}A^{T}\mathbf{b}\\&=\frac{1}{9}\begin{pmatrix}29&-7\\-7&2\end{pmatrix}\begin{pmatrix}7\\23\end{pmatrix}=\begin{pmatrix}\frac{14}{3}\\-\frac{1}{3}\end{pmatrix}\end{align*}$$이때 \(\mathbf{b}\)의 \(\mathcal{C}(A)\)로의 직교사영은 다음과 같다.$$\mathbf{b}_{c}=A\mathbf{x}=\begin{pmatrix}1&2\\1&5\\0&0\end{pmatrix}\begin{pmatrix}\frac{14}{3}\\-\frac{1}{3}\end{pmatrix}=\begin{pmatrix}4\\3\\0\end{pmatrix}$$

최소제곱해를 이용하여 실험을 통해 관측한 값으로부터 두 변수 간의 수학적 관계를 결정할 수 있다.

곡선 \(y=f(x)\)를 데이터들에 대한 수학적 모델이라 하고 데이터가 다음과 같을 때$$(x_{1},\,y_{1}),\,(x_{2},\,y_{2}),\,...,\,(x_{n},\,y_{n})$$두 변수 \(x\)와 \(y\)의 관계가 \(y=a+bx\)라고 하자. 이 데이터들이 모두 직선 상에 있다면 식 \(y=a+bx\)를 만족하므로 계수 \(a\)와 \(b\)는 다음의 연립방정식$$\begin{align*}y_{1}&=a+bx_{1}\\y_{2}&=a+bx_{2}\\&\vdots\\y_{n}&=a+bx_{n}\end{align*}$$의 해이다. 이 연립방정식을 다음과 같이 행렬로 나타낼 수 있고,$$A\mathbf{x}=\begin{pmatrix}1&x_{1}\\1&x_{2}\\ \vdots&\vdots\\1&x_{n}\end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}=\begin{pmatrix}y_{1}\\y_{2}\\ \vdots\\y_{n}\end{pmatrix}=\mathbf{b}$$이 방정식에 대한 최소제곱해는 \(\mathbf{x}=(A^{T}A)^{-1}A^{T}\mathbf{b}\)이다. 이 결과로 얻은 직선 \(y=a+bx\)를 주어진 데이터에 대한 최소제곱직선(least squares line of best fit) 또는 회귀직선(regression line)이라고 한다.

훅의 법칙(Hooke's law)에 따르면 고정된 용수철에 연결된 물체가 받는 힘은 늘어나는 길이에 비례한다고 한다. 즉, 용수철에 연결된 물체를 잡아당겨 용수철의 길이를 \(x\)만큼 늘렸을 때 받는 힘 \(F\)는 다음과 같다.$$F=a+kx$$여기서 \(k\)는 용수철 상수라고 불리는 비례상수이다. 6.1인치 길이의 용수철을 가지고 물체를 7.6인치 늘렸을 때의 힘은 7.6N, 8.7인치 늘렸을 때의 힘은 4N, 10.4인치 늘렸을 때의 힘은 6N이라고 한다. 이 실험결과들을 다음과 같이 나타낼 수 있고$$\begin{align*}F_{1}&=a+6.1k=0\\F_{2}&=a+7.6k=2\\F_{3}&=a+8.7k=4\\F_{4}&=a+10.4k=6\end{align*}$$다음과 같이 행렬을 이용하여 나타낼 수 있다.$$A\mathbf{x}=\begin{pmatrix}F_{1}\\F_{2}\\F_{3}\\F_{4}\end{pmatrix}=\begin{pmatrix}1&6.1\\1&7.6\\1&8.7\\1&10.4\end{pmatrix}\begin{pmatrix}a\\k\end{pmatrix}=\begin{pmatrix}0\\2\\4\\6\end{pmatrix}=\mathbf{b}$$그러면$$\begin{pmatrix}a\\k\end{pmatrix}=\mathbf{x}=(A^{T}A)^{-1}A^{T}\mathbf{b}=\begin{pmatrix}-8.6\\1.4\end{pmatrix}$$이고 따라서 이 실험결과를 \(F=-8.6+1.4x\,(\text{N})\)(\(x\)의 단위는 인치)으로 나타낼 수 있다.

곡선 \(y=f(x)\)를 데이터들에 대한 수학적 모델이라 하고 데이터가 다음과 같을 때$$(x_{1},\,y_{1}),\,(x_{2},\,y_{2}),\,...,\,(x_{n},\,y_{n})$$두 변수 \(x\)와 \(y\)의 관계가 \(y=a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{k}x^{k}\)라고 하자. 이 데이터들이 곡선 \(y=f(x)\)상에 있다고 하면 다항식의 계수 \(a_{0}\), \(a_{1}\), ..., \(a_{k}\)는 다음의 연립방정식$$\begin{align*}f(x_{1})&=a_{0}+a_{1}x_{1}+a_{2}x_{1}^{2}+\cdots+a_{k}x_{1}^{k}\\f(x_{2})&=a_{0}+a_{1}x_{2}+a_{2}x_{2}^{2}+\cdots+a_{k}x_{2}^{k}\\&\vdots\\f(x_{n})&=a_{0}+a_{1}x_{n}+a_{2}x_{n}^{2}+\cdots+a_{k}x_{n}^{k}\end{align*}$$의 해이다. 이 연립방정식을 다음과 같이 행렬로 나타낼 수 있고,$$A\mathbf{x}=\begin{pmatrix}1&x_{1}&x_{1}^{2}&\cdots&x_{1}^{k}\\1&x_{2}&x_{2}^{2}&\cdots&x_{2}^{k}\\ \vdots&&&\ddots&\vdots\\1&x_{n}&x_{n}^{2}&\cdots&x_{n}^{k}\end{pmatrix}\begin{pmatrix}a_{0}\\a_{1}\\ \vdots\\a_{k}\end{pmatrix}=\begin{pmatrix}y_{1}\\y_{2}\\ \vdots\\ y_{n}\end{pmatrix}=\mathbf{b}$$이 방정식에 대한 최소제곱해는 \(\mathbf{x}=(A^{T}A)^{-1}A^{T}\mathbf{b}\)이다. 

뉴턴의 제2법칙으로부터 지구상의 물체가 지상으로 낙하할 때 다음의 방정식을 만족하며 낙하한다고 한다.$$y=y_{0}+v_{0}t+\frac{1}{2}gt^{2}$$여기서 \(y_{0}\)는 물체의 초기높이, \(v_{0}\)는 물체의 초기속도(떨어지기 시작할 때의 속도), \(g\)는 중력가속도이다. 이때 낙하실험을 해서 높이가 -0.18, 0.31, 1.03, 2.48, 3.73피트인 위치에서 낙하시켰을 때 걸린 시간이 0.1, 0.2, 0.3, 0.4, 0.5초였다.$$A=\begin{pmatrix}1&t_{1}&t_{1}^{2}\\1&t_{2}&t_{2}^{2}\\1&t_{3}&t_{3}^{2}\\1&t_{4}&t_{4}^{2}\\1&t_{5}&t_{5}^{2}\end{pmatrix}=\begin{pmatrix}1&0.10&0.01\\1&0.20&0.04\\1&0.30&0.09\\1&0.40&0.16\\1&0.50&0.25\end{pmatrix},\,\mathbf{x}=\begin{pmatrix}y_{0}\\v_{0}\\ \frac{1}{2}g\end{pmatrix},\,\mathbf{b}=\begin{pmatrix}y_{1}\\y_{2}\\y_{3}\\y_{4}\\y_{5}\end{pmatrix}=\begin{pmatrix}-0.18\\0.31\\1.03\\2.48\\3.73\end{pmatrix}$$라고 하면$$\mathbf{x}=(A^{T}A)^{-1}A^{T}\mathbf{b}=\begin{pmatrix}7.37\\3.21\\16.07\end{pmatrix}$$이므로 \(y_{0}=-0.40\), \(v_{0}=0.35\), \(g=32.14\)이고 방정식은 다음과 같다.$$y=-0.40+0.35t+16.07t^{2}$$

참고자료:

Linear Algebra, jinho Kwak, sungpyo Hong, Birkhauser

현대 선형대수학, 이상구, 경문사