![[탐구 보고서] 보간법과 최소제곱법 with 선형대수학](/assets/images/posts/[실험실].png)
[탐구 보고서] 보간법과 최소제곱법 with 선형대수학
도입
수학적 데이터 분석에서 가장 중요한 도구 중 하나가 다항식 근사입니다. 주어진 데이터 점들을 정확히 지나는 다항식을 찾는 과정인 보간법과, 주어진 데이터 점들과 가장 가까운 다항식을 찾는 최소제곱법을 선형대수학을 통해 어떻게 구현할 수 있는지 알아보겠습니다.
배경지식
보간법 (Interpolation)
정의
보간법은 주어진 점들을 정확히 지나는 다항식을 찾는 방법입니다. 이를 위해 주어진 점의 개수만큼의 다항식 차수를 설정하여, 모든 점을 지나도록 하는 다항식의 계수를 구합니다.
Vandermonde 행렬
보간법에서 중요한 역할을 하는 것이 Vandermonde 행렬입니다. 이 행렬은 주어진 데이터 점들의 ( x ) 좌표를 사용하여 구성되며, 다음과 같은 형태를 가집니다.
\[A = \begin{pmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^n \\ 1 & x_2 & x_2^2 & \cdots & x_2^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_m & x_m^2 & \cdots & x_m^n \\ \end{pmatrix}\]보간 다항식 계산
보간법에서는 점들 \((x_i, y_i)\)를 정확히 지나는 다항식의 계수를 찾기 위해, 다음과 같은 선형 방정식을 풉니다.
\[A \mathbf{c} = \mathbf{y}\]여기서 \(\mathbf{c} = [c_0, c_1, \ldots, c_n]^T\)는 다항식의 계수, \(\mathbf{y} = [y_1, y_2, \ldots, y_m]^T\)는 주어진 점의 ( y ) 좌표들입니다. 이 선형 방정식을 풀면 보간 다항식의 계수를 얻을 수 있습니다.
보간법의 수학적 원리 및 증명
유일성
보간 다항식은 주어진 ( m )개의 점들을 정확히 지나는 유일한 다항식입니다. 만약 ( n )차 다항식을 사용하여 ( m )개의 점을 보간하려 한다면, ( n+1 = m )이 되어야 합니다. ( m > n+1 )일 경우, 방정식의 해가 없거나 무한히 많아지므로 보간이 불가능합니다.
예시
def bogan(n: int, li: list[tuple[float, float]]) -> NDArray[np.float64]:
"""주어진 점들을 정확히 지나는 다항함수의 계수를 반환함(선형대수학의 보간법 참고).
Args:
n (int): 원하는 함수의 최고차항 차수
li (list of tuples): 점 순서쌍 리스트 [(x1, y1), (x2, y2), ...]
Returns:
NDArray[np.float64]: 다항식 계수를 나타내는 numpy 배열
Usage Example:
try:
result = bogan(3, [(1, 3), (2, -2), (3, -5), (4, 0)])
print("계수: ", result)
except ValueError as e:
print("오류:", e)
Note:
'(최고차항 차수 + 1) == 점의 수' 이어야 작동하며, 그마저도 맞는 함수가 없으면 에러남.
이상.
"""
ndot = len(li)
# 점을 numpy 배열로 변환
x_vals = np.array([pt[0] for pt in li], dtype=np.float64)
y_vals = np.array([pt[1] for pt in li], dtype=np.float64)
# Vandermonde 행렬 생성
A = np.vander(x_vals, n + 1, increasing=True)
if n + 1 == ndot:
# 유일한 해를 계산
try:
coeffs = np.linalg.solve(A, y_vals)
return coeffs
except np.linalg.LinAlgError as e:
raise ValueError("다항식의 계수를 계산할 수 없음. 오류: " + str(e))
else:
raise ValueError("점의 수가 이상함. 함수 설명 참고.")
위 함수에서 np.vander(x_vals, n + 1, increasing=True) 부분이 Vandermonde 행렬을 생성하는 코드입니다. 만약 ( n+1 )이 점의 수와 같다면, ( A ) 행렬은 정방행렬이 되어 유일한 해를 가지게 됩니다. np.linalg.solve는 이 정방행렬을 이용해 다항식의 계수를 계산합니다.
최소제곱법 (Least Squares Method)
정의
최소제곱법은 주어진 점들과 가장 가까운 다항식을 찾는 방법입니다. 보간법과 달리, 모든 점을 정확히 지나는 것이 아니라 점들 사이의 오차를 최소화하는 다항식을 찾습니다.
수학적 모델
최소제곱법의 목표는 주어진 점들 ( (x_i, y_i) )와 다항식 ( f(x) ) 사이의 오차를 최소화하는 것입니다. 오차는 다음과 같이 정의됩니다.
\[E(\mathbf{c}) = \sum_{i=1}^{m} (y_i - f(x_i))^2\]이 오차를 최소화하기 위해서는, 오차 ( E(\mathbf{c}) )에 대해 다항식의 계수들 ( \mathbf{c} )에 대한 편미분을 취해 0으로 만드는 조건을 찾아야 합니다.
최소제곱해 계산
이를 위한 방정식은 다음과 같습니다.
\[A^T A \mathbf{c} = A^T \mathbf{y}\]여기서 ( A^T A )는 정방행렬이 되며, 이 방정식을 풀면 최소제곱해를 구할 수 있습니다.
최소제곱법의 수학적 원리 및 증명
증명
\[\mathbf{Y} = \mathbf{A} \mathbf{X}\] \[\mathbf{r} = \mathbf{Y} - \mathbf{A} \mathbf{X}\] \[\text{목표:} \quad \min_{\mathbf{X}} \|\mathbf{r}\|^2 = \min_{\mathbf{X}} \|\mathbf{Y} - \mathbf{A} \mathbf{X}\|^2\] \[\|\mathbf{r}\|^2 = (\mathbf{Y} - \mathbf{A} \mathbf{X})^T (\mathbf{Y} - \mathbf{A} \mathbf{X})\] \[\|\mathbf{r}\|^2 = \mathbf{Y}^T \mathbf{Y} - 2 \mathbf{X}^T \mathbf{A}^T \mathbf{Y} + \mathbf{X}^T \mathbf{A}^T \mathbf{A} \mathbf{X}\] \[\frac{\partial}{\partial \mathbf{X}} \|\mathbf{r}\|^2 = -2 \mathbf{A}^T \mathbf{Y} + 2 \mathbf{A}^T \mathbf{A} \mathbf{X} = 0\] \[\mathbf{A}^T \mathbf{A} \mathbf{X} = \mathbf{A}^T \mathbf{Y}\]예시
def lsm(n: int, li: list[tuple[float, float]]) -> NDArray[np.float64]:
"""주어진 점들과 오차가 가장 적은 다항함수를 반환함(선형대수학 최소제곱법 참고).
Args:
n (int): 원하는 함수의 최고차항 차수
li (list of tuples): 점 순서쌍 리스트 [(x1, y1), (x2, y2), ...]
Returns:
NDArray[np.float64]: 다항식 계수를 나타내는 numpy 배열
Usage Example:
try:
result = lsm(1, [(0, 1), (1, 3), (2, 4), (3, 4)])
print("계수:", result)
except ValueError as e:
print("오류:", e)
Note:
일차함수를 넣는게 정석. 점의 위치를 보면서 최고차항의 계수를 적당히 입력하는걸 추천함.
이상.
"""
ndot = len(li)
# 점을 numpy 배열로 변환
x_vals = np.array([pt[0] for pt in li], dtype=np.float64)
y_vals = np.array([pt[1] for pt in li], dtype=np.float64)
# Vandermonde 행렬 생성
A = np.vander(x_vals, n + 1, increasing=True)
A1 = np.dot(A.T, A)
y_vals = np.dot(A.T, y_vals)
try:
coeffs = np.linalg.solve(A1, y_vals)
return coeffs
except np.linalg.LinAlgError as e:
raise ValueError("다항식의 계수를 계산할 수 없음. 오류: " + str(e))
위 함수에서 ( A^T A )와 ( A^T \mathbf{y} )를 계산한 후, np.linalg.solve를 사용해 최소제곱해를 구합니다. 이 과정은 주어진 점들과의 오차를 최소화하는 다항식을 찾기 위한 것입니다.
느낀점
보간법과 최소제곱법은 데이터 분석과 수학적 모델링에서 중요한 도구입니다. 이 두 가지 방법을 이해하고 구현하면서, 선형대수학이 실생활의 문제 해결에 얼마나 유용한지 깨닫게 되었습니다. 특히, 데이터를 분석하거나 예측할 때 다항식 근사가 얼마나 효과적인지 실감할 수 있었습니다.
이러한 과정에서 수학적 원리와 실제 코드 구현을 연결하는 것이 중요하다는 것을 배웠으며, 이를 통해 보다 효과적인 알고리즘을 설계하고 문제를 해결할 수 있는 능력을 길렀습니다.
이상.
