절6.5최소제곱법¶ 고유 링크

목표

최적 적합 문제의 예를 익힙니다.
최적 적합 문제를 최소제곱 문제로 바꾸는 방법을 익힙니다.
계산 절차: 최소제곱해 구하기(두 가지 방법).
그림: 최소제곱해의 기하학적 의미.
용어: 최소제곱해.

이 절에서는 다음의 중요한 질문에 답합니다.

$Ax=b$ 의 해가 존재하지 않는다고 가정합시다. 가장 좋은 근사해는 무엇입니까?

여기서는 가장 좋은 근사해를 최소제곱해라고 부릅니다. 최소제곱해를 구하는 두 가지 방법을 제시하고, 최적 적합 문제에 대한 몇 가지 응용을 소개하겠습니다.

소절6.5.1최소제곱해

먼저 해가 없는 행렬 방정식 $Ax=b$ 의 “가장 좋은 근사해”가 정확히 무엇을 뜻하는지 명확히 하겠습니다.

정의

$A$ 를 $m\times n$ 행렬이라 하고, $b$ 를 $\R^m$ 의 벡터라 합시다. 행렬 방정식 $Ax=b$ 의 최소제곱해는 $\R^n$ 의 다른 모든 벡터 $x$ 에 대하여

$\begin{equation*} \dist(b,\,A\hat x) \leq \dist(b,\,Ax) \end{equation*}$

를 만족하는 $\R^n$ 의 벡터 $\hat x$ 입니다.

$\dist(v,w) = \|v-w\|$ 는 벡터 $v$ 와 $w$ 사이의 거리였음을 상기하십시오. “최소제곱”이라는 용어는 $\dist(b,Ax) = \|b-A\hat x\|$ 가 벡터 $b-A\hat x$ 의 성분들의 제곱의 합의 제곱근이라는 사실에서 유래합니다. 따라서 최소제곱해는 $A\hat x$ 와 $b$ 의 성분 간 차이의 제곱의 합을 최소화합니다. 다시 말해, 최소제곱해는 차 $b-Ax$ 의 제곱의 합이 최소가 된다는 의미에서 방정식 $Ax=b$ 를 가능한 한 가깝게 풉니다.

최소제곱: 그림

방정식 $Ax=b$ 가 해를 갖지 않는다고 가정합시다. 이 참고 in 절 2.3에서 $A$ 의 열공간은 $Ax=c$ 가 해를 갖도록 하는 다른 모든 벡터 $c$ 의 집합이었음을 상기하십시오. 다시 말해, $\Col(A)$ 는 $Ax.$ 꼴의 모든 벡터의 집합입니다. 따라서 $Ax$ 꼴의 벡터 중 $b$ 에 가장 가까운 벡터는 $b$ 를 $\Col(A)$ 위로 정사영한 것입니다. 이 표기법 in 절 6.3에 따라 이를 $b_{\Col(A)}$ 로 표기합니다.

$\begin{tikzpicture}[scale=1.5, myxyz, thin border nodes] \coordinate (u) at (0,1,0); \coordinate (v) at (1.1,0,-.2); \coordinate (uxv) at (.2,0,1.1); \coordinate (x) at ($-1.1*(u)+(v)+1.5*(uxv)$); \begin{scope}[x=(u),y=(v),transformxy] \fill[seq-violet!30] (-2,-2) rectangle (2,2); \draw[seq-violet, help lines] (-2,-2) grid (2,2); \node[seq-violet] at (2.8,1) {$\Col A$}; \point[black!50, "$Ax$" text=black!50] at (1,-1); \point[black!50, "$Ax$" text=black!50] at (-1,0); \point[black!50, "$Ax$" text=black!50] at (1,1); \end{scope} \point[seq-blue, "{$A\hat x = b_{\Col(A)}$}" {below, text=seq-blue}] (y) at ($-1.1*(u)+1*(v)$); \coordinate (yu) at ($(y)+(u)$); \coordinate (yv) at ($(y)+(v)$); \pic[draw, right angle len=3mm] {right angle=(x)--(y)--(yu)}; \pic[draw, right angle len=3mm] {right angle=(x)--(y)--(yv)}; \point[seq-red, "$b$" {above,text=seq-red}] (xx) at (x); \draw[vector] (y) -- node[auto,pos=.6] {$b-A\hat x = b_{\Col(A)^\perp}$} (xx); \point["$0$" above] at (0,0,0); \end{tikzpicture}$

$Ax=b$ 의 최소제곱해는 해를 갖는 방정식 $Ax=b_{\Col(A)}$ 의 해 $\hat x$ 입니다.

노트

$Ax=b$ 가 해를 가지면 $b_{\Col(A)} = b$ 이므로, 최소제곱해는 일반적인 해와 같습니다.

이 그림에서 $\hat x$ 는 어디에 있습니까? $v_1,v_2,\ldots,v_n$ 이 $A$ 의 열이면

$\begin{equation*} A\hat x = A\vec{\hat x_1 \hat x_2 \vdots, \hat x_n} = \hat x_1v_1 + \hat x_2v_2 + \cdots + \hat x_nv_n. \end{equation*}$

입니다. 따라서 $\hat x$ 의 성분은 $\Col(A)$ 의 생성 집합 $\{v_1,v_2,\ldots,v_m\}$ 에 대한 $b_{\Col(A)}$ 의 “좌표”입니다. ( $A$ 의 열들이 일차독립이면 이는 진정한 $\cB$ -좌표입니다.)

$\begin{tikzpicture}[scale=2, myxyz, thin border nodes] \coordinate (u) at (0,1,0); \coordinate (v) at (1.1,0,-.2); \coordinate (uxv) at (.2,0,1.1); \coordinate (x) at ($-1.1*(u)+(v)+1.5*(uxv)$); \coordinate (y) at ($-1.1*(u)+1*(v)$); \begin{scope}[x=(u),y=(v),transformxy] \fill[seq-violet!30] (-2,-1) rectangle (2,2); \draw[seq-violet, help lines] (-2,-1) grid (2,2); \node[seq-violet] at (2.8,1) {$\Col A$}; \draw[vector, seq-orange] (0, 0) to["$v_1$"] (u); \draw[vector, seq-orange] (0, 0) to["$v_2$"] (v); \draw[thick, dashed] (0,0) -| node[pos=.25,above] {$\hat x_1v_1$} node[pos=.7,above left] {$\hat x_2v_2$} (y); \end{scope} \point[seq-blue, "{$A\hat x = b_{\Col(A)}$}" {below, text=seq-blue}] at (y); \coordinate (yu) at ($(y)+(u)$); \coordinate (yv) at ($(y)+(v)$); \pic[draw, right angle len=3mm] {right angle=(x)--(y)--(yu)}; \pic[draw, right angle len=3mm] {right angle=(x)--(y)--(yv)}; \point[seq-red, "$b$" {above,text=seq-red}] (xx) at (x); \draw[vector] (y) -- node[auto,pos=.6] {$b-A\hat x = b_{\Col(A)^\perp}$} (xx); \point["$0$" above] at (0,0,0); \end{tikzpicture}$

그림4보라색 평면은 $\Col(A)$ 입니다. $Ax$ 가 $b$ 에 가장 가까이 갈 수 있는 점은 $\Col(A)$ 위에서 $b$ 에 가장 가까운 벡터이며, 이는 정사영 $b_{\Col(A)}$ (파란색)입니다. 벡터 $v_1,v_2$ 는 $A$ 의 열이고, $\hat x$ 의 계수는 초록색 선분의 길이입니다. $b$ 를 클릭하고 끌어서 움직여 보십시오.

노트

$Ax=b$ 가 해를 가지면 $b_{\Col(A)} = b$ 이므로, 최소제곱해는 일반적인 해와 같습니다.

이런 종류의 정사영 문제를 푸는 방법은 절 6.3에서 배웠습니다.

정리

$A$ 를 $m\times n$ 행렬이라 하고 $b$ 를 $\R^m$ 의 벡터라 합시다. $Ax=b$ 의 최소제곱해는 다음 행렬 방정식의 해입니다.

$\begin{equation*} A^TAx = A^Tb \end{equation*}$

증명

특히, 최소제곱해를 구한다는 것은 해가 있는 연립일차방정식을 푸는 것을 의미합니다. 위의 정리를 다음과 같은 계산 절차로 옮길 수 있습니다.

계산 절차 1: 최소제곱해 구하기

$A$ 를 $m\times n$ 행렬이라 하고 $b$ 를 $\R^n$ 의 벡터라 합시다. $Ax=b$ 의 최소제곱해를 구하는 방법은 다음과 같습니다.

행렬 $A^TA$ 와 벡터 $A^Tb$ 를 계산하십시오.
행렬 방정식 $A^TAx = A^Tb$ 의 첨가행렬을 만들고 행 축약하십시오.
이 방정식은 항상 해가 존재하며, 임의의 해 $\hat x$ 는 최소제곱해입니다.

다시 말하자면, $Ax=b$ 의 최소제곱해 $\hat x$ 를 구하고 나면 $b_{\Col(A)}$ 는 $A\hat x$ 와 같습니다.

예제

독자는 우리가 복수형을 써서 “최소제곱해들”이라고 하거나, 부정관사를 써서 “하나의 최소제곱해”라고 신중하게 표현해 왔다는 것을 눈치챘을 것입니다. 이는 최소제곱해가 유일할 필요가 없기 때문입니다: 실제로 $A$ 의 열이 일차종속이면 $Ax=b_{\Col(A)}$ 는 무수히 많은 해를 가집니다. 유일성에 대한 동치 조건을 제시하는 다음 정리는 이 따름정리 in 절 6.3에 대응하는 결과입니다.

정리

$A$ 를 $m\times n$ 행렬이라 하고, $b$ 를 $\R^m$ 의 벡터라 합시다. 다음은 서로 동치입니다.

$Ax=b$ 는 유일한 최소제곱해를 가집니다.
$A$ 의 열들은 일차독립입니다.
$A^TA$ 는 가역입니다.

이 경우 최소제곱해는 다음과 같습니다.

$\begin{equation*} \hat x = (A^TA)\inv A^Tb. \end{equation*}$

증명

예제(무한히 많은 최소제곱해)

늘 그렇듯이, 직교 집합이 있으면 사영과 관련된 계산이 더 쉬워집니다. 실제로 $A$ 가 직교하는 열 $u_1,u_2,\ldots,u_m$ 을 가지는 $m\times n$ 행렬이면, 사영 공식 in 절 6.4에 따라 다음과 같이 쓸 수 있습니다.

$\begin{equation*} b_{\Col(A)} = \frac{b\cdot u_1}{u_1\cdot u_1}\,u_1 + \frac{b\cdot u_2}{u_2\cdot u_2}\,u_2 + \cdots + \frac{b\cdot u_m}{u_m\cdot u_m}\,u_m = A\vec{(b\cdot u_1)/(u_1\cdot u_1) (b\cdot u_2)/(u_2\cdot u_2) \vdots, (b\cdot u_m)/(u_m\cdot u_m)}. \end{equation*}$

이 경우 직교 집합은 일차독립이므로 최소제곱해가 유일하다는 점에 유의하십시오.

계산 절차 2: 최소제곱해 구하기

$A$ 를 직교하는 열 $u_1,u_2,\ldots,u_m$ 을 가지는 $m\times n$ 행렬이라 하고, $b$ 를 $\R^n$ 의 벡터라 합시다. 그러면 $Ax=b$ 의 최소제곱해는 다음 벡터입니다.

$\begin{equation*} \hat x = \left(\frac{b\cdot u_1}{u_1\cdot u_1},\; \frac{b\cdot u_2}{u_2\cdot u_2},\; \ldots,\; \frac{b\cdot u_m}{u_m\cdot u_m} \right). \end{equation*}$

직교하는 열을 갖는 행렬은 자연에서 자주 나타나므로, 이 공식은 과학 분야에서 특히 유용합니다.

예제

소절6.5.2최적 적합 문제

이 소절에서는 최소제곱법을 데이터 모델링에 응용하는 방법을 소개합니다. 기본적인 예제부터 시작합니다.

예제(가장 잘 맞는 직선)

세 개의 데이터 점

$\begin{equation*} (0,6),\quad (1,0),\quad (2,0), \end{equation*}$

을 측정했고, 이 데이터에 대한 모델에 따르면 이 점들이 한 직선 위에 놓여야 한다고 가정합시다. 물론 이 세 점은 실제로 한 직선 위에 놓여 있지 않지만, 이는 측정 오차 때문일 수 있습니다. 이 점들이 어느 직선 위에 놓여야 하는지 어떻게 예측할 수 있겠습니까?

$\begin{tikzpicture}[thin border nodes] \draw[grid lines] (-2,-2) grid (4,7); \draw[->] (-2,0) -- (4,0); \draw[->] (0,-2) -- (0,7); \point["{$(0,6)$}" above right] at (0,6); \point["{$(1,0)$}" below] at (1,0); \point["{$(2,0)$}" anchor=-130] at (2,0); \end{tikzpicture}$

(수직이 아닌) 직선의 일반 방정식은 다음과 같습니다.

$\begin{equation*} y = Mx + B. \end{equation*}$

세 데이터 점이 이 직선 위에 놓여 있다면 다음 방정식들이 성립할 것입니다:

$\begin{equation*} \begin{split} 6 \amp= M\cdot 0 + B \\ 0 \amp= M\cdot 1 + B \\ 0 \amp= M\cdot 2 + B. \end{split} \end{equation*}$ (6.5.1)

가장 잘 맞는 직선을 구하기 위해, 미지수 $M$ 과 $B$ 에 대하여 위 방정식들을 풀어 봅니다. 세 점이 실제로는 한 직선 위에 놓여 있지 않으므로 실제 해는 존재하지 않습니다. 따라서 대신 최소제곱해를 계산합니다.

이 일차방정식들을 행렬 형태로 나타내면, 다음에 대하여 $Ax=b$ 를 푸는 것이 됩니다.

$\begin{equation*} A = \mat{0 1; 1 1; 2 1} \qquad x = \vec{M B}\qquad b = \vec{6 0 0}. \end{equation*}$

이 최소제곱 문제는 이 예제에서 풀었습니다: $Ax=b$ 의 유일한 최소제곱해는 $\hat x = {M\choose B} = {-3\choose 5}$ 이므로, 가장 잘 맞는 직선은

$\begin{equation*} y = -3x + 5. \end{equation*}$

입니다.

직선 $y= f(x) = -3x+5$ 가 최소화하는 것은 정확히 무엇입니까? 최소제곱해 $\hat x$ 는 벡터 $b-A\hat x$ 의 성분들의 제곱의 합을 최소화합니다. 벡터 $b$ 는 (6.5.1)의 좌변이며,

$\begin{equation*} A\vec{-3 5} = \vec{-3(0)+5 -3(1)+5 -3(2)+5} = \vec{f(0) f(1) f(2)}. \end{equation*}$

다시 말해, $A\hat x$ 는 데이터 점에서 지정한 $x$ 값들에서의 직선 그래프의 $y$ 좌표를 성분으로 갖는 벡터이고, $b$ 는 그 데이터 점들의 $y$ 좌표를 성분으로 갖는 벡터입니다. 차 $b-A\hat x$ 는 데이터 점들로부터 그래프까지의 수직 거리입니다:

$\begin{tikzpicture}[decoration={brace,raise=1mm}, thin border nodes] \draw[grid lines] (-2,-2) grid (4,7); \draw[->] (-2,0) -- (4,0); \draw[->] (0,-2) -- (0,7); \point["{$(0,6)$}" above right] at (0,6); \point["{$(1,0)$}" below] at (1,0); \point["{$(2,0)$}" anchor=-130] at (2,0); \draw[decorate, seq-blue, thick, decoration={mirror}] (0,5) -- node[right=2mm] {$-1$} (0,6); \draw[decorate, seq-blue, thick] (1,0) -- node[left=2mm,yshift=1.5pt] {$2$} (1,2); \draw[decorate, seq-blue, thick] (2,0) -- node[right=2mm] {$-1$} (2,-1); \draw[thick, seq-red] (-2/3,7) -- node[sloped,above=1pt] {$y=-3x+5$} (7/3,-2); \node[text=seq-blue] at (1,-3.2) {$b - A\hat x = \vec{6 0 0} - A\vec{-3 5} = \vec{-1 2 -1}$}; \end{tikzpicture}$

가장 잘 맞는 직선은 이 수직 거리들의 제곱의 합을 최소화합니다.

인터랙티브: 가장 잘 맞는 직선

예제(가장 잘 맞는 포물선)

예제(가장 잘 맞는 일차함수)

위의 예들은 모두 다음과 같은 형태입니다. 몇 개의 데이터 점 $(x,y)$ 가 주어지고, 이 점들을 가장 잘 근사하는 함수

$\begin{equation*} y = B_1g_1(x) + B_2g_2(x) + \cdots + B_mg_m(x) \end{equation*}$

를 구하고자 합니다. 여기서 $g_1,g_2,\ldots,g_m$ 은 $x$ 에 대한 고정된 함수입니다. 실제로 가장 잘 맞는 직선의 예에서는 $g_1(x)=x\text{,}$ $g_2(x)=1$ 이었고, 가장 잘 맞는 포물선의 예에서는 $g_1(x)=x^2\text{,}$ $g_2(x)=x\text{,}$ $g_3(x)=1$ 이었으며, 가장 잘 맞는 일차함수의 예에서는 $g_1(x_1,x_2)=x_1\text{,}$ $g_2(x_1,x_2)=x_2\text{,}$ $g_3(x_1,x_2)=1$ 이었습니다(이 예에서는 $x$ 를 두 성분을 갖는 벡터로 봅니다). 주어진 데이터 점들에서 위 방정식을 계산하여 미지수 $B_1,B_2,\ldots,B_m$ 에 대한 연립일차방정식을 얻고— $g_i$ 를 계산하고 나면 이들은 단지 수가 되므로 어떤 함수인지는 상관이 없습니다—최소제곱해를 구합니다. 그 결과 얻은 가장 잘 맞는 함수는 $y = f(x)$ 의 그래프로부터 원래 데이터 점들까지의 수직 거리들의 제곱의 합을 최소화합니다.