임의의 연립일차방정식 Ax = b는 해를 갖는 경우와 해를 갖지 않는 경우로 나누어 진다.
최소제곱문제는 연립방정식이 해를 갖지 않으면 어떤 해를 찾아야 가장 적절한지를 이야기 하는 것이다.
Example) 평면의 세 점 (1,0), (2,1), (3,4)는 일직선상에 있지 않다. 이 세 점에 가장 근접한 직선을 찾아라. (추세선을 찾아라.)
sol)
세 점 (1,0), (2,1), (3,4)을 지나는 직선이 존재한다고 생각하고 계산한다.
즉, \[ y = b + ax \]
를 지난다고 생각하고 각 점을 대입한다.
\[ b + a = 0 \]
\[ b + 2a = 1 \]
\[ b + 3a = 4 \]
를 만족하는데, 당연히 해가 존재하지 않는다.
\[ A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix} \] \[ B = \begin{pmatrix} 0 \\ 1 \\ 4 \end{pmatrix} \] \[ x = \begin{pmatrix} b \\ a \end{pmatrix} \]
이라 놓으면
Ax = B로 표현이 가능하다.
한 직선위의 점이 아니므로 x는 존재하지 않는다.
다만 ||Ax - B|| 를 최소화할 수 있는 직선이 주어진 세 점과 근접한 직선으로 생각할 수 있다.
||Ax - B||를 최소화하면 그 제곱인 ||Ax-B||^2를 최소화하는 x는 B를 A의 열공간 Col(A) = W 로 사영한 projwB 가 B에 가장 가까운 A의 열공간 W의 벡터이다.
\[ Ax = projw B \]
의 해로부터 구할 수 있다.
\[ W = Col(A) = span[v1 = (1,1,1), v2 = (1,2,3)], B = (0,1,4)\]
Gram-Schmidt orthogonalization process 를 이용해 정규 직교기저를 구하면
\[ u1 = (1,1,1)/sqrt(3) , u2 = (-1,0,1)/sqrt(2) \]
B의 사영을 구하면
\[ projw B = (-1/3 , 5/3 , 11/3) \]
즉,
\[ x = \begin{pmatrix} -7/3 \\ 2 \end{pmatrix} \]
따라서 우리가 찾는 직선은
\[ y = -7/3 - 2x \]
최소제곱문제의 정규방정식을 이용하면 조금 더 빠르게 값을 구할 수 있다.