기초 개념

• 보간: 모든 점을 다 지나가야 함
• 곡선근사: 모든 점을 제일 효과적으로 근사해야 함

좀 더 수학적으로 쓰면 주어진 자료 $(x_i, f_i)$가 있을 때,
미리 선택한 기저함수 $\phi_i$들의 선형결합으로($\sum w_i\phi_i$) 주어진 자료를 표현하는 것

• 보간: $\sum w_i\phi_i$가 $(x_i, f_i)$를 다 지남
• 곡선근사 $\sum w_i\phi_i$가 $(x_i, f_i)$랑 제일 가까움

여기서 $\phi_i$를 $1, x, x^2, \ldots$를 선택하면 다항식 보간/근사가 됨

참고) $ax^2 + bx + c$ 같은 식으로 다항식을 쓰면 $x^n$ 오차가 너무 커져서 안 됨!!
수치해석에서는 $(ax + b)x + c$ 같은 식으로 다항식을 씀

라그랑주 보간

실제로 쓸일 없음 왜냐? 너무 오래 걸림

간단하게 두 점 $(x_0, f_0), (x_1, f_1)$으로 시작하면 아래와 같이 라그랑주 정규다항식을 정의할 수 있음.

$$L_0(x) = \frac{x - x_1}{x_0 - x_1}, L_1(x) = \frac{x - x_0}{x_1 - x_0}$$

위 다항식은 $L_i(x_j)$가 $i = j$면 1, $i \neq j$면 0이기 때문에 아래와 같이 간단하게 보간할 수 있음.

$$f(x) = f_0L_0(x) + f_1L_1(x)$$

일반적으로 점 n+1개 $(x_0, f_0), \ldots, (x_n, f_n)$이 주어질 때 라그랑주 정규다항식은

$$L_i(x) = \frac{(x - x_0)\cdots(x - x_{i-1})(x - x_{i+1})\cdots(x - x_n)}{(x_i - x_0)\cdots(x_i - x_{i-1})(x_i - x_{i+1})\cdots(x_i - x_n)}$$

으로 주어지고, 라그랑주 보간은

$$P_n(x) = f_0L_0(x) + \cdots + f_nL_n(x)$$

로 주어짐.

또한 라그랑주 보간의 오차도 알려져 있는데, 어떤 $x_0 \leq \xi \leq x_n$에 대해 오차 $e(x) = f(x) - P_n(x)$는

$$e(x) = \frac{(x - x_0)\cdots(x - x_n)}{(n+1)!}f^{(n+1)}(\xi)$$

이다. 따라서 $f(x)$가 n차 미만 다항식인 경우 (n+1)계도함수가 0이라 오차가 0이 된다. (즉, 모든 점을 정확하게 지난다.)

뉴턴 전진/후진 보간

전진보간법

$\Delta^1 f_1 = \frac{f_2 - f_1}{x_2 - x_1}$을 전진분할차분, 또는 간단히 전진차분이라고 한다.
마찬가지로 2계미분의 전진차분은 $\Delta^2 f_1 = \frac{\Delta^1 f_2 - \Delta^1 f_1}{x_3 - x_1}$으로 정의된다.

이걸 주어진 n+1개의 점 $(x_0, f_0), \ldots, (x_n, f_n)$으로부터 1계미분, 2계미분, ..., n계미분을 구한 것을 전진분할차분표, 또는 전진차분표라고 한다.

이제 보건다항식을 $P_n(x) = a_0 + a_1(x - x_0) + \cdots + a_n(x - x_0) \cdots (x - x_{n-1})$이라고 하자.

$x = x_0$을 대입하면 $a_0 = f_0 = \Delta^0 f_0$
$x = x_1$을 대입하면 $f_1 = f_0 + a_1(x - x_0), \therefore a_1 = \Delta^1 f_0$
마찬가지로 $x = x_i$를 대입하면 $a_i = \Delta^i f_0$이 된다.

이를 뉴턴의 전진보간법이라고 하는데, 임의의 $x_i, \ldots, x_j$ 구간에 대해서 보간하거나 새로운 점 $(x_{n+1}, f_{n+1})$을 추가할 때 기존 전진차분표를 재활용할 수 있어 유용하다.

차항규칙

앞에서 오차는

$$e(x) = \frac{(x - x_0)\cdots(x - x_n)}{(n+1)!}f^{(n+1)}(\xi)$$

라고 했었는데, 사실 여기서 근사적으로 $\Delta^{n+1} f_0 \approx \frac{f^{(n+1)}(\xi)}{(n+1)!}$으로 볼 수 있다.
즉, 차분표를 한 번 더 계산하여

$$|e(x)| \approx |(x - x_0)\cdots(x - x_n)\Delta^{n+1} f_0|$$

으로 근사할 수 있고, 다음 항을 사용해서 차항규칙이라고 한다.

후진보간법

$$\nabla^1 f_2 = \frac{f_2 - f_1}{x_2 - x_1}$$

하지만 $\nabla^n f_i = \Delta^n f_{i-n}$$이므로 사실 차이가 없다.

$$\begin{align*} P_n(x) &= \Delta^0 f_0 + \Delta^1 f_0(x - x_0) + \cdots + \Delta^n f_0(x - x_0) \cdots (x - x_{n-1}) \\ &= \nabla^0 f_n + \nabla^1 f_n(x - x_n) + \cdots + \nabla^n f_n(x - x_n) \cdots (x - x_1) \\ |e(x)| &\approx |(x - x_0)\cdots(x - x_n)\nabla^{n+1} f_n| \end{align*}$$

여담) 미분과 차분

미적분에서 $x^n$은 차분에서 $x(x+1) \cdots (x+n-1)$과 같음

$$\int \frac{1}{n!}x^ndx = \frac{1}{(n+1)!}x^{n+1}, \sum \frac{1}{n!}x(x+1) \cdots (x+n-1) = \frac{1}{(n+1)!}x(x+1) \cdots (x+n)$$

반대로 $\frac{1}{n}x^n$의 미분은 $x^{n-1}$, $\frac{1}{n}x(x+1) \cdots (x+n-1)$의 차분은 $x(x+1) \cdots (x+n-2)$

실제로 뉴턴다항식의 점 개수를 무한대로 보내면 테일러급수가 된다!

등간격 뉴턴보간

$x_{i+1} = x_i + h$인 경우 전진차분을 훨씬 간단한 형태로 나타낼 수 있음.

$$\Delta^1 f_1 = \frac{f_2 - f_1}{h}, \Delta^2 f_1 = \frac{f_1 - 2f_2 + f_3}{2! h^2}$$

일반적으로 $f_i$들의 계수는 파스칼의 삼각형과 같고, 부호는 교대로 바뀐다.

$$\Delta^5 f_i = \frac{f_{i+5} - 5f_{i+4} + 10f_{i+3} - 10f_{i+2} + 5f_{i+1} - f_i}{5!h^5}$$

$\Delta^k f_i$에서 $f_i$들로 연산한 부분을 $\triangle^k f_i$라고 하자. (즉, $\Delta^k f_i = \frac{\triangle^k f_i}{k! h^k})$

한편 $x = x_0 + sh$라고 놓으면 $s = \frac{x - x_0}{h}$이므로

$$\begin{align*} (x - x_0) &= hs \\ (x - x_0)(x - x_1) &= h^2 s(s-1) \\ &\vdots \\ (x - x_0)(x - x_1) \cdots (x-x_{k-1}) &= h^k s(s-1) \cdots (s - k + 1) \end{align*}$$

등의 관계가 성립된다.

따라서 아래 보건다항식을 이렇게 단순화시킬 수 있다.

$$\begin{align*} P_n(x) &= \Delta^0 f_0 + \Delta^1 f_0(x - x_0) + \cdots + \Delta^n f_0(x - x_0) \cdots (x - x_{n-1}) \\ &= \sum_{k=0}^n \triangle^kf_0 \frac{s(s-1) \cdots (s-k+1)}{k!} \\ &= \sum_{k=0}^n \triangle^kf_0 \binom{s}{k} \end{align*}$$

후진차분의 경우 $\nabla^k f_i = \frac{\triangledown^k f_i}{k! h^k})$로 정의하면

$$P_n(x) = \sum_{k=0}^n \triangledown^k f_n \binom{s+k-1}{k}$$

최소제곱 회귀

n개의 데이터 $(x_1, f_1), \cdots, (x_n, f_n)$이 주어져있을 때, r개의 기저함수 $u_1(x), \cdots, u_r(x)$의 선형결합 $u(x) = \sum a_iu_i$로 주어진 데이터의 최적근사를 구한다.

최소제곱회귀는 주어진 데이터와의 절대오차 $e_i = |f_i - u(x_i)|$의 제곱의 합을 최소로 한다.
$S = \sum_{i=1}^n e_i^2$이라고 하면 이를 최소로 하는 계수는 $\frac{\partial S}{\partial a_j} = 0$이여야 하므로

$$\frac{\partial S}{\partial a_j} = -2 \sum_{i=1}^n u_j(x_i)(f_i - a_1u_1(x_i) - a_2u_2(x_i) - \cdots - a_ru_r(x_i)) = 0$$

$$\therefore \sum_{i=1}^n u_j(x_i)(a_1u_1(x_i) + a_2u_2(x_i) + \cdots + a_ru_r(x_i)) = \sum_{i=1}^n u_j(x_i)f_i$$

를 만족해야 한다.

이때 상관계수를 아래와 같이 정의한다.

$$f_{ave} = \frac{1}{n}\sum_{i=1}^n f_i, S_0 = \sum_{i=1}^n(f_i - f_{ave})^2, r^2 = \frac{S_0 - S}{S_0}$$

만약 오차가 없어 $S = 0$이라면 $r = 1$이 된다.

행렬표현

$$\sum_{i=1}^n u_j(x_i)(a_1u_1(x_i) + a_2u_2(x_i) + \cdots + a_ru_r(x_i)) = \sum_{i=1}^n u_j(x_i)f_i$$

를 행렬로 나타낼 수 있다.

$$U = \begin{bmatrix} u_1(x_1) & u_1(x_2) & \cdots & u_1(x_n)\\ u_2(x_1) & u_2(x_2) & \cdots & u_2(x_n)\\ \vdots & \vdots & \ddots & \vdots\\ u_r(x_1) & u_r(x_2) & \cdots & u_r(x_n) \end{bmatrix}, a = \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_r \end{bmatrix}, f = \begin{bmatrix} f_1 \\ f_2 \\ \vdots \\ f_n \end{bmatrix}$$

으로 정의하면 위 식은 간단하게 $UU^Ta = Uf$가 된다.

다항식 회귀

$u_i(x) = x^i$로 놓으면 (i는 0부터 r까지 있다고 가정) 위의 행렬은 아래처럼 나타낼 수 있다.

$$U = \begin{bmatrix} 1 & 1 & \cdots & 1\\ x_1 & x_2 & \cdots & x_n\\ \vdots & \vdots & \ddots & \vdots\\ x_1^r & x_2^r & \cdots & x_n^r \end{bmatrix}$$

비선형 회귀

비선형 회귀는 다항식 회귀로 식을 변형시키는 경우가 많다.

$$\begin{align*} y = ae^{bx} &\rightarrow \ln y = \ln a + bx \\ y = ax^b &\rightarrow \ln y = \ln a + b \ln x \\ y = \frac{a}{x+b} &\rightarrow y = \frac{a}{b} - \frac{1}{b}(xy) \end{align*}$$

스플라인 보간

매우 중요!! 제일 현실적인 보간!! 시험에 나옴!!

n개의 데이터를 단순히 n차방정식으로 보간해버리면 차수가 너무 높아 오차가 심해지는 문제가 있다.
이 경우 각 소구간 $x_{i-1} \leq x \leq x_i$를 보간한 뒤, 보간한 각 함수가 잘 이어지는 spline이 되도록 만든다.

각 점마다 $f_i, f_i''$가 주어졌다고 하고, 양쪽 스플라인의 기울기가 (즉, 1차미분이) 연속인 조건을 추가하자. (사실 spline의 양 끝점에서 $f, f', f''$가 같아야 한다는 말임)
3차함수로 n개의 spline을 만들 경우,

• 미지수는 4n개다.
• 각 3차함수의 양 끝점 $f_i$가 같아야 하므로 방정식 2n개가 나온다.
• 이웃한 3차함수의 미분값 $f_i'$가 같아야 하므로 방정식 (n-1)개가 나온다.
• 이웃한 3차함수의 2계도함수 $f_i''$가 같아야 하므로 방정식 (n-1)개가 나온다.

아니면 싹다 $f_i''$로 만들어버렸을 때 $f_i''$의 관계식은 (n-1)개인데 미지수는 $f_0''$부터 $f_n''$까지 (n+1)개 있다고 봐도 된다.
따라서 2개의 조건을 추가로 정의해줘야 하고, $f_0''$과 $f_n''$을 보통 정의해준다.

• 자연 3차 스플라인: $f_0'' = f_n'' = 0$
• $f_0'' = f_1'', f_{n-1}'' = f_n''$
• 선형보외: $\frac{f_1'' - f_0''}{x_1 - x_0} = \frac{f_2'' - f_1''}{x_2 - x_1}, \frac{f_n'' - f_{n-1}''}{x_n - x_{n-1}} = \frac{f_{n-1}'' - f_{n-2}''}{x_{n-1} - x_{n-2}}$

위의 모든 방법은 어떻게든 $a_if_i'' + b_if_{i-1}'' + c_if_{i+1}'' = d_i$ 꼴의 방정식을 만든 다음 TDMA(3대각행렬 푸는거)를 사용하여 구한다.
여담으로 각 구간의 spline은 $f_i, f_{i+1}, f_i'', f_{i+1}''$만 주어지면 변수 4개가 주어졌기 때문에 3차방정식을 확정지을 수 있다.
이 내용이 싹다 계산되어있으니 나중에 궁금하면 교재를 찾아보자.....

체비셰프 보간

시험에 안 나옴

지금까지 배운 보간은 $(x_i, f_i)$가 미리 주어진 경우로, 수동적(passive) 보간이라고 함.
반면에 구간이 주어져있을때 $x_i$를 능동적으로 선택하는 경우를 능동적(active) 보간이라고 함.

구간 $-1 \leq x \leq 1$에서 체비셰프 다항식은 두가지 방법으로 표현된다. (둘 다 같은 식이다)

$$\begin{gather} T_n(x) = \cos(n - \cos^{-1} x) \\ T_0(x) = 1, T_1(x) = x, T_i(x) = 2xT_{i-1}(x) - T_{i-2}(x) \end{gather}$$

항상 $|T_n(x)| \leq 1$이며, 체비셰프 다항식의 근은 $n\cos^{-1}x = (n - 0.5 - k)\pi$에서

$$x_k = \cos \left( n - \frac{1}{2} - k \right)\frac{\pi}{n}, 0 \leq k < n$$

대체 이게 뭐임??
우선 일원다항식을 정의해야 하는데, 그냥 $x^n$ 계수가 1인 n차다항식을 일원다항식이라고 한다.
이때 놀랍게도 $-1 \leq x \leq 1$에서 가장 작은 최대값을 가지는 n차 일원다항식은 $\frac{T_n(x)}{2^{n-1}}$임이 알려져있다. (최대값은 $\frac{1}{2^{n-1}}$)

우리의 오차식 $e(x) = \frac{(x - x_0)\cdots(x - x_n)}{(n+1)!}f^{(n+1)}(\xi)$를 되살펴보면 $|(x - x_0)\cdots(x - x_n)|$를 줄이면 오차를 줄일 수 있다는 사실을 알 수 있다.
근데 이게 뭐다? (n+1)차 일원다항식이다!
따라서 $(x - x_0) \cdots (x - x_n)$이 체비셰프 다항식이면 오차를 줄일 수 있고, 반대로 $x_0, \cdots, x_n$을 체비셰프 다항식 $T_{n+1}(x)$의 근으로 선택하면 오차를 줄일 수 있다.

만약 구간이 $a \leq x \leq b$라면, $x = a + \frac{b-a}{2}(z+1)$으로 간단하게 $-1 \leq z \leq 1$로 구간을 바꿀 수 있다.

$$z_k = \cos \left( n - \frac{1}{2} - k \right)\frac{\pi}{n}, x_k = a + \frac{b-a}{2}(z_k + 1)$$

참고로 이 모든 과정은 점을 구하는데 사용한거고, 이제 구한 점으로 차분법이든 뭐든 아무 수동적 보간을 하면 된다...

에르미트 보간

역시 시험에 안 나옴

왜 함수값만 보간하냐? 기울기도 보간하면 안 됨? 하는게 에르미트 보간이다.
이제 데이터가 $(x_i, f_i, f_i')$로 주어진다.
참고) 스플라인 보간은 $f_i''$를 사용, 얘는 $f_i'$를 사용

우선 너무 어지러우므로 등간격을 가정하고 구간 $x_{i-1} \leq x \leq x_i$를 $s = \frac{x - x_{i-1}}{x_i - x_{i-1}} = \frac{x - x_{i-1}}{h}$을 사용해 구간을 $0 \leq s \leq 1$으로 바꾸자.

이때 $f(s) = f_{i-1} + (f_i - f_{i-1})s + As(s-1) + Bs^2(s-1)$은 $f(0) = f_{i-1}, f(1) = f_i$를 만족한다.
미분하고 방정식을 열심히 풀고 대입하면 3차 방정식이 나온다....