최소제곱법 - Method of Least Squares

최소제곱법 - Method of Least Squares

근사적으로 구하려는 해와 실제 해의 오차의 제곱 합이 최소가 되는 해를 구하는 방법이다.

예를 들어,

$\begin{cases}x+2y=3\\3x+2y=5\\x+y=2.09\end{cases}\Lrarr\begin{cases}x+2y=3\\-4y=-4\\-y=-0.91\end{cases}$

이 연립 방정식은 일관적이지 않은 계로 해가 없다.
이 때 해 $(x_0, y_0)$가 존재하지만 계가 정확하지 않다고 가정해보자.
즉, 오류가 존재할 것이다.

$(x_0, y_0)$의 근사치를 찾는 방법 중 하나가 최소제곱법(Method of Least Squares)이다.

연립 방정식
$\begin{cases}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1\\a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2\\\cdots\\a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n=b_m\end{cases}\Longleftrightarrow A\mathbf{x=b}$

에서 $\mathbf x\in \mathbb R^n$의 잔차(residual)를 다음과 같이 정의한다.

$r(\mathbf x)=\mathbf b-A\mathbf x$

계에 대한 최소제곱해(least squares solution) $\mathbf x$는 $||r(\mathbf x)||$ 또는 $||r(\mathbf x)||^2$를 최소화 하는 $\mathbf x$이다.

$||r(\mathbf x)||^2 = \sum_{i=1}^m(a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n-b_i)^2$

여기서 벡터 $\mathbf{\hat{x}}$가 $A\mathbf{x=b}$의 최소제곱해라면 $\mathbf{\hat{x}}$는 정규 방정식 $A^TA\mathbf{x}=A^T\mathbf{b}$의 해이다(필요충분조건).

따라서 정규 방정식 $A^TA\mathbf x=A^T\mathbf b$는 항상 일관적이다.

예제 풀이

예제 1.

다음 연립 방정식의 최소제곱해를 구하여라.
$\begin{cases}x+2y=3\\3x+2y=5\\x+y=2.09\end{cases}$

풀이.

$\begin{cases}x+2y=3\\3x+2y=5\\x+y=2.09\end{cases}\Longleftrightarrow A\mathbf{x=b}\Longleftrightarrow \begin{pmatrix}1\;\;2\\3\;\;2\\1\;\;1\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}3\\5\\2.09\end{pmatrix}$

$A^TA\mathbf x=A^T\mathbf b$임을 이용한다.

$\begin{pmatrix}1\;\;3\;\;1\\2\;\;2\;\;1\end{pmatrix}\begin{pmatrix}1\;\;2\\3\;\;2\\1\;\;1\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}1\;\;3\;\;1\\2\;\;2\;\;1\end{pmatrix}\begin{pmatrix}3\\5\\2.09\end{pmatrix}$

$\begin{pmatrix}11\;\;9\\\ 9\;\;\;9\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}20.09\\18.09\end{pmatrix}\Longleftrightarrow \begin{cases}x=1\\y=1.01\end{cases}$

예제 2.

다음 데이터에 최소제곱이 맞는
ⅰ) 상수 함수를 구하여라.
ⅱ) 일차 함수를 구하여라.
ⅲ) 이차 함수를 구하여라.

  x  | 0 | 1 | 2 | 3
---------------------
f(x) | 1 | 0 | 1 | 2

풀이 2-1.

$f(x) = c \Rightarrow \begin{cases}c=1\\c=0\\c=1\\c=2\end{cases}\Rightarrow \begin{pmatrix}1\\1\\1\\1\end{pmatrix}(c)=\begin{pmatrix}1\\0\\1\\2\end{pmatrix}$

$A^TA\mathbf x=A^T\mathbf b$임을 이용한다.

$\begin{pmatrix}1\;1\;1\;1\end{pmatrix}\begin{pmatrix}1\\1\\1\\1\end{pmatrix}(c)=\begin{pmatrix}1\;1\;1\;1\end{pmatrix}\begin{pmatrix}1\\0\\1\\2\end{pmatrix} \Lrarr4c=4\Lrarr c=1$

$\therefore f(x)=1$

풀이 2-2.

$f(x) = c_1+c_2x \Rightarrow \begin{cases}c_1=1\\c_1+c_2=0\\c_1+2c_2=1\\c_1+3c_2=2\end{cases}\Rightarrow \begin{pmatrix}1\;\;0\\1\;\;1\\1\;\;2\\1\;\;3\end{pmatrix}\begin{pmatrix}c_1\\c_2\end{pmatrix}=\begin{pmatrix}1\\0\\1\\2\end{pmatrix}$

$\begin{pmatrix}1\;1\;1\;1\\0\;1\;2\;3\end{pmatrix}\begin{pmatrix}1\;\;0\\1\;\;1\\1\;\;2\\1\;\;3\end{pmatrix}\begin{pmatrix}c_1\\c_2\end{pmatrix}=\begin{pmatrix}1\;1\;1\;1\\0\;1\;2\;3\end{pmatrix}\begin{pmatrix}1\\0\\1\\2\end{pmatrix}$

$\begin{pmatrix}4\;\;\;6\\\;6\;\;14\end{pmatrix}\begin{pmatrix}c_1\\c_2\end{pmatrix}=\begin{pmatrix}4\\8\end{pmatrix}\Lrarr \begin{cases}c_1=0.4\\c_2=0.4\end{cases}$

$\therefore f(x)=0.4+0.4x$

풀이 2-3.

$f(x) = c_1+c_2x+c_3x^2 \Rightarrow \begin{cases}c_1=1\\c_1+c_2+c_3=0\\c_1+2c_2+4c_3=1\\c_1+3c_2+9c_3=2\end{cases}\Rightarrow \begin{pmatrix}1\;\;0\;\;0\\1\;\;1\;\;1\\1\;\;2\;\;4\\1\;\;3\;\;9\end{pmatrix}\begin{pmatrix}c_1\\c_2\\c_3\end{pmatrix}=\begin{pmatrix}1\\0\\1\\2\end{pmatrix}$

$\begin{pmatrix}1\;1\;1\;1\\0\;1\;2\;3\\0\;1\;4\;9\end{pmatrix}\begin{pmatrix}1\;\;0\;\;0\\1\;\;1\;\;1\\1\;\;2\;\;4\\1\;\;3\;\;9\end{pmatrix}\begin{pmatrix}c_1\\c_2\end{pmatrix}=\begin{pmatrix}1\;1\;1\;1\\0\;1\;2\;3\\0\;1\;4\;9\end{pmatrix}\begin{pmatrix}1\\0\\1\\2\end{pmatrix}$

$\begin{pmatrix}4\;\;\;6\;\;\;14\\\;6\;\;14\;\;\;36\\14\;\;36\;\;98\end{pmatrix}\begin{pmatrix}c_1\\c_2\\c_3\end{pmatrix}=\begin{pmatrix}4\\8\\22\end{pmatrix}\Lrarr \begin{cases}c_1=0.9\\c_2=-1.1\\c_3=0.5\end{cases}$

$\therefore f(x)=0.9-1.1x+0.5x^2$

---

<참고자료>
Steve J. Leon, Linear Algebra with Application, 10th edition, 2021.