에르미트 보간법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 문제 정의 및 해법
3. 오차 분석
4. 응용
- 4.1. 컴퓨터 그래픽스
- 4.2. 기타 응용
참조

1. 개요

에르미트 보간법은 주어진 함수 값과 도함수 값을 모두 일치시키는 다항식을 찾는 보간법이다. 이 방법은 분할 차분 또는 중국인의 나머지 정리를 사용하여 해를 구할 수 있으며, 컴퓨터 그래픽스, 특히 다이렉트X SDK에서 곡선 생성에 활용된다. 에르미트 보간법은 물체의 위치, 속도, 가속도를 기반으로 위치를 보간하는 데도 사용되며, 이후 더 부드러운 곡선을 생성하는 Catmull-Rom 보간법이 개발되어 널리 사용된다.

더 읽어볼만한 페이지

유한차분법 - 포흐하머 기호
포흐하머 기호는 하강 계승과 상승 계승으로 정의되며, 조합론, 초기하함수 이론 등 다양한 분야에서 사용되는 수학 기호이다.
유한차분법 - 음계산법
음계산법은 다항식환에서 특정 조건을 만족하는 다항식열을 연구하는 수학 분야로, 셰퍼 다항식열, 아펠 다항식열, 이항형 다항식열과 같은 특수한 다항식열들을 다루며 다양한 분야에서 응용된다.
보간법 - 선형 보간법
선형 보간법은 두 점 사이의 값을 직선으로 추정하는 방법으로, 다양한 분야에서 활용되지만 비선형 데이터에는 정확도가 낮아 다른 방법으로 대체될 수 있다.
보간법 - 보외법
보외법은 수치 데이터가 없는 범위의 값을 추정하는 방법으로, 다양한 외삽 방법이 존재하며 데이터 생성 프로세스에 대한 사전 지식에 따라 적용 방법을 선택한다.
계승과 이항식 주제 - 이항 정리
이항 정리는 이변수 다항식 (x + y)ⁿ을 전개하는 공식으로, 이항 계수를 사용하며, 조합론적 증명과 수학적 귀납법을 통해 증명할 수 있고, 다양한 분야에 응용되며, 이항 급수, 다항 정리 등 일반화된 형태가 존재한다.
계승과 이항식 주제 - 감마 분포
감마 분포는 형상 모수와 척도 모수로 정의되는 연속 확률 분포로, 확률 밀도 함수가 감마 함수로 표현되며, 베이즈 통계학에서 켤레 사전 분포로 활용되고, 형상 모수가 양의 정수일 때는 얼랑 분포를 나타낸다.

에르미트 보간법
개요
분야	수치해석학
주제	주어진 점에서의 함수 값과 도함수 값을 이용하여 함수를 추정하는 다항식 보간법
관련 항목	선형대수학 수치해석학 다항식 보간법
상세 정보
유형	보간법
방법	선형대수학을 사용한 다항식 구성
응용 분야	수치해석학, 컴퓨터 그래픽스

2. 문제 정의 및 해법

에르미트 보간법은 주어진 각 점에서의 함수값뿐만 아니라 미분값까지 이용하여 함수를 근사하는 방법이다. 뉴턴 보간법이 함수값만을 사용하는 것과 달리, 에르미트 보간법은 미분값을 추가로 사용하여 더 정확한 근사를 가능하게 한다.
문제 정의n개의 자료 점 $(x_0, y_0), (x_1, y_1), \ldots, (x_{n-1}, y_{n-1})$ 과 각 점에서의 1차 미분값 $(x_0, y_0'), (x_1, y_1'), \ldots, (x_{n-1}, y_{n-1}')$ 이 주어졌을 때, 이 모든 조건을 만족하는 다항식을 찾는 것이 에르미트 보간법의 목표이다. 뉴턴 보간법의 다항식의 자유도가 n-1인 반면, 에르미트 보간 다항식은 보통 2n-1의 자유도를 가진다.^[2]

일반적으로, 함수와 그 함수의 m차 도함수까지의 관측값을 모두 일치시키는 최소 차수의 다항식을 찾는 문제로 확장할 수 있다. 이 경우, 총 n(m+1)개의 조건을 만족하는 다항식을 찾게 되며, 그 다항식의 차수는 n(m+1)보다 작다.
일반적인 해의 존재성미정 계수를 갖는 다항식을 이용하여 보간 조건을 만족하는 선형 방정식 시스템을 만들 수 있다. 이 시스템은 일반적으로 유일한 해를 가지며, 샤를 에르미트는 윤곽선 적분을 통해 입력 점들이 서로 다를 때 유일한 해가 존재함을 증명했다.^[1] 에르미트 보간 문제는 합류 반데르몬드 행렬을 사용하는 선형대수학 문제로 볼 수 있다.^[3]

2. 1. 문제 정의

뉴턴 보간법과 달리, 에르미트 보간법은 자료 점들을 값과 1차 미분값을 대응시킨다. 즉 ''n''차 미분값들

(x_0, y_0'),\ldots,(x_{n-1}, y_{n-1}')

이 ''n'' 자료 점들

(x_0, y_0),\ldots,(x_{n-1}, y_{n-1})

에 추가로 주어져야만 한다. 뉴턴 다항식이 최대 자유도 ''n'' − 1을 가지는 반면, 이 보간법의 다항식 결과는 대부분 2''n'' − 1의 자유도를 가지게 된다.^[2]

에르미트 보간법은 알려지지 않은 함수와 관측된 값과 처음 m개의 도함수의 관측된 값을 모두 일치시키는 가능한 한 낮은 차수의 다항식을 계산하는 것으로 구성된다. 이는 n(m + 1)개의 값

\begin{matrix}(x_0, y_0),       & (x_1, y_1),       & \ldots, & (x_{n-1}, y_{n-1}),  \\[1ex](x_0, y_0'),      & (x_1, y_1'),      & \ldots, & (x_{n-1}, y_{n-1}'), \\[1ex]\vdots            & \vdots            &         & \vdots               \\[1ex](x_0, y_0^{(m)}), & (x_1, y_1^{(m)}), & \ldots, & (x_{n-1}, y_{n-1}^{(m)})\end{matrix}

을 알아야 함을 의미한다. 결과 다항식의 차수는 n(m + 1)보다 작다.

차수가 n(m + 1)보다 작은 미정 계수를 갖는 다항식 P(x)를 고려해 보자. 즉, P(x)의 계수는 n(m + 1)개의 새로운 변수이다. 그런 다음 보간 다항식이 만족해야 하는 제약 조건을 작성하여, n(m + 1)개의 미지수를 가진 n(m + 1)개의 선형 방정식 시스템을 얻는다.

일반적으로 이러한 시스템은 정확히 하나의 해를 가진다.^[1] 샤를 에르미트는 윤곽선 적분을 사용하여 x_i가 쌍별로 다를 경우, 이것이 실제로 경우이며 고유한 해를 찾는 것을 증명했다. 에르미트 보간법 문제는 보간 다항식의 계수를 미지수로 하고 합류 반데르몬드 행렬을 행렬로 하는 선형대수학의 문제이다.^[3]

2. 2. 해법 1: 분할 차분 (Divided Differences)

함수 ''f''의 에르미트 다항식을 계산하기 위해 분할 차분(divided difference)을 사용하는 방법은 다음과 같다.

먼저, 보간하려는 함수 ''f''와 ''n'' + 1개의 자료점들

x_0, x_1, x_2, \ldots, x_n

및 그 점들에서의 함수값

f(x_0), f(x_1), \ldots, f(x_n)

과 미분값

f'(x_0), f'(x_1), \ldots, f'(x_n)

이 주어졌다고 가정한다.

1. 각 점들을 복제하여 새로운 자료 집합

z_0, z_1, \ldots, z_{2n+1}

을 만든다. 여기서

z_{2i}=z_{2i+1}=x_i

이다.

2. 점들

z_0, z_1, \ldots, z_{2n+1}

에 대한 분할 차분 표를 만든다. 이때,

z_i = z_{i + 1}

인 경우의 분할 차분은 정의되지 않은 형태(

\frac{0}{0}

)가 되므로, 이 경우 분할 차분을

\frac{f'(z_i)}{1}

로 대체한다. 나머지 분할 차분은 일반적인 방법으로 계산한다.

이러한 과정을 통해 고차 미분값에 대한 에르미트 보간을 일반화할 수 있다. 각 점에 대해 ''k''차 미분값이 주어지면, 각 자료점을 ''k''개 복제하여 자료 집합

z_0, z_1, \ldots, z_{kn-1}

을 만들 수 있다. 이렇게 하면 ''n''개의 자료점에 대해 최대

(k + 1)n - 1

차 다항식을 얻을 수 있다. 동일한 값 ''m''개에 대한 분할 차분은

\frac{f^{(m - 1)}(x_i)}{(m - 1)!}

로 대체한다.

예를 들어,

f[x_i, x_i, x_i, x_i]=\frac{f^{(3)}(x_i)}{6}

,

f[x_i, x_i, x_i]=\frac{f^{(2)}(x_i)}{2}

와 같이 계산한다.
예시:함수

f(x) = x^8 + 1

에 대해,

x \in \{-1, 0, 1\}

에서 함수를 두 번 미분하여 다음 데이터를 얻는다.

x	f(x)	f′(x)	f′′(x)
−1	2	−8	56
0	1	0	0
1	2	8	56

두 미분값들을 가지고 집합 $\{z_i\} = \{-1, -1, -1, 0, 0, 0, 1, 1, 1\}$ 를 구성하고, 분할 차분표를 만들면 다음과 같다.

$\begin{matrix}z_0 = -1 & f[z_0] = 2 & & & & & & & & \\& & \frac{f'(z_0)}{1} = -8 & & & & & & & \\z_1 = -1 & f[z_1] = 2 & & \frac{f''(z_1)}{2} = 28 & & & & & & \\& & \frac{f'(z_1)}{1} = -8 & & f[z_3,z_2,z_1,z_0] = -21 & & & & & \\z_2 = -1 & f[z_2] = 2 & & f[z_3,z_2,z_1] = 7 & & 15 & & & & \\& & f[z_3,z_2] = -1 & & f[z_4,z_3,z_2,z_1] = -6 & & -10 & & & \\z_3 = 0 & f[z_3] = 1 & & f[z_4,z_3,z_2] = 1 & & 5 & & 4 & & \\& & \frac{f'(z_3)}{1} = 0 & & f[z_5,z_4,z_3,z_2] = -1 & & -2 & & -1 & \\z_4 = 0 & f[z_4] = 1 & & \frac{f''(z_4)}{2} = 0 & & 1 & & 2 & & 1 \\& & \frac{f'(z_4)}{1} = 0 & & f[z_6,z_5,z_4,z_3] = 1 & & 2 & & 1 & \\z_5 = 0 & f[z_5] = 1 & & f[z_6,z_5,z_4] = 1 & & 5 & & 4 & & \\& & f[z_6,z_5] = 1 & & f[z_7,z_6,z_5,z_4] = 6 & & 10 & & & \\z_6 = 1 & f[z_6] = 2 & & f[z_7,z_6,z_5] = 7 & & 15 & & & & \\& & \frac{f'(z_6)}{1} = 8 & & f[z_8,z_7,z_6,z_5] = 21 & & & & & \\z_7 = 1 & f[z_7] = 2 & & \frac{f''(z_7)}{2} = 28 & & & & & & \\& & \frac{f'(z_7)}{1} = 8 & & & & & & & \\z_8 = 1 & f[z_8] = 2 & & & & & & & & \\\end{matrix}$

분할 차분표의 대각선 계수들을 가져와서 ''k''번째 계수에 $\prod_{i=0}^{k-1} (x - z_i)$ 를 곱하여 뉴턴 다항식을 생성하면, 다음과 같은 다항식을 얻는다.

: $\begin{align}P(x) &= 2 - 8(x+1) + 28(x+1) ^2 - 21 (x+1)^3 + 15x(x+1)^3 - 10x^2(x+1)^3 \\&\quad + 4x^3(x+1)^3 -1x^3(x+1)^3(x-1)+x^3(x+1)^3(x-1)^2 \\&= x^8 + 1.\end{align}$

2. 3. 해법 2: 중국인의 나머지 정리 (Chinese Remainder Theorem)

Chinese Remainder Theorem^영어인 중국인의 나머지 정리를 사용한 해법은 다음과 같다.

, , 를 실수 또는 체의 표수가 0인 다른 체의 원소라고 가정하고, k를 양의 정수, m_i들을 음이 아닌 정수라고 가정한다. 에르미트 보간법 문제는 다음 조건을 만족하는 다항식 f를 찾는 것이다.

:

f(x_i)=y_{i,0}, f'(x_i)=y_{i,1}, \ldots, f^{m_i}(x_i)=y_{i,m_i}

여기서 이고, 는 와 동일한 체에서 주어진 값이다.

이 조건들은 에서의 차수 인 f의 테일러 다항식이

:

\sum_{j=0}^m\frac{y_{i,j}}{i!}(x-x_i)^j.

임을 의미한다. 즉, 구하고자 하는 다항식 f는

(x-x_i)^{m_i+1}

을 법으로 할 때 이 다항식과 합동이다.

다항식에 대한 중국인의 나머지 정리에 따르면 차수가

n=\sum_{i=0}^k (m_i+1).

보다 작은 해가 정확히 하나 존재한다.

이 해는

O(n^2)

산술 연산으로 계산할 수 있으며, 빠른 다항식 곱셈을 사용하면 더 빠르게 계산할 수 있다.

이 방법은 테일러 다항식 계수의 분모 때문에 양의 표수에서는 작동하지 않는다. 모든 표수에서는 차분 나눗셈을 통한 접근 방식을 사용해야 한다.

3. 오차 분석

계산된 다항식을 ''H'', 원래 함수를 ''f''라고 할 때, 실수 값을 갖는 경우 점 $x \in [x_0, x_n]$ 에서 오차 함수는 다음과 같다.

: $f(x) - H(x) = \frac{f^{(K)}(c)}{K!} \prod_{i}(x - x_i)^{k_i},$

여기서 ''c''는 $[x_0, x_N]$ 범위 안의 알 수 없는 값이고, ''K''는 데이터 점의 총 개수이며, $k_i$ 는 각 $x_i$ 에서 알려진 도함수의 개수이다. 따라서 오른쪽의 다항식 차수는 $H(x)$ 의 차수 상한보다 1 더 높다. 또한, 오차와 $k_i-1$ 차까지의 모든 도함수는 각 노드에서 0이 되는데, 이는 예상된 결과이다.

복소수 값의 경우에는 다음이 성립한다.^[5]

: $f(z) - H(z) = \frac{w(z)}{2\pi i} \oint_C \frac{f(\zeta)}{w(\zeta)(\zeta-z)}d\zeta$

여기서 $C$ 는 $z$ 와 모든 노드 $x_i$ 를 포함하는 경로(contour)이며, 노드 다항식은 $w(z) = \prod_{i}(z - x_i)^{k_i}$ 이다.

4. 응용

에르미트 보간법은 모노레일, 게임, 수로 건설, 철도 건설, 항로 계산 등의 실제적인 업무에 사용된다. 함수( $f$ )와 두 개의 서로 다른 점( $x_0$ 과 $x_1$ )에서의 1차( $f'$ ) 및 2차 도함수( $f''$ )를 기반으로 한 5차 에르미트 보간법은 예를 들어 물체의 위치, 속도 및 가속도를 기반으로 물체의 위치를 보간하는 데 사용할 수 있다.

일반적인 형태는 다음과 같다.

$\begin{align}p(x) & = f(x_0) + f'(x_0) (x - x_0) + \frac{1}{2}f''(x_0) (x - x_0)^2 + \frac{f(x_1) - f(x_0) - f'(x_0) (x_1 - x_0) - \frac{1}{2} f''(x_0) (x_1 - x_0)^2}{(x_1 - x_0)^3} (x - x_0)^3 \\& + \frac{3 f(x_0) - 3 f(x_1) + 2\left( f'(x_0) + \frac{1}{2}f'(x_1) \right) (x_1 - x_0) + \frac{1}{2} f''(x_0) (x_1 - x_0)^2}{(x_1 - x_0)^4} (x - x_0)^3 (x - x_1) \\& + \frac{6 f(x_1) - 6 f(x_0) - 3 \left( f'(x_0) + f'(x_1) \right) (x_1 - x_0) + \frac{1}{2}\left( f''(x_1) - f''(x_0) \right) (x_1 - x_0)^2}{(x_1 - x_0)^5} (x - x_0)^3 (x - x_1)^2.\end{align}$

이후 더 부드러운 곡선을 만들어내는 방법인 Catmull-Rom 보간법이 개발되어 현재는 에르미트 보간법을 대신하여 많이 사용되고 있다. 하지만 이러한 방식을 처음 고안한 사람이 에르미트이기에, 실제로는 Catmull-Rom 보간법을 사용하면서도 에르미트 보간법이라고 통칭하는 경우도 많다.

4. 1. 컴퓨터 그래픽스

마이크로소프트사의 다이렉트X SDK에서는 `D3DXVecHermite`라는 함수로 에르미트 보간법을 이용할 수 있다.

`D3DXVecHermite` 함수의 정의와 각 인수의 의미는 다음과 같다.

```

pV1: 시작점의 좌표 (0,0,0에서 이 점까지의 벡터값)
pT1: 시작점에서 다음 지점까지의 벡터값 (= pV2 - pV1)
pV2: 다음 지점의 좌표 (0,0,0에서 이 점까지의 벡터값)
pT2: 다음 지점에서 그 다음 지점의 벡터값 (= pV3 - pV2)
s: 0.0f ~ 0.1f의 상수

```

아래는 사용 예시이다.

```

D3DXVECTOR3 pOut(0,0,0), pV1(-2.0f,-2.0f,-2.0f), pT1, pV2(1.0f,1.0f,1.0f), pT2, pV3(2.0f,1.5f,3.0f);

FLOAT s;

pT1 *= 0.0f;

pT2 *= 0.0f;

pT1 = pV2 - pV1;

pT2 = pV3 - pV2;

s = 0.5f;

D3DXVecHermite(&pOut, &pV1, &pT1, &pV2, &pT2, s);

```

`pOut.x`, `pOut.y`, `pOut.z`는 에르미트 보간법에 의하여 발생된 곡선의 0.5f 지점(중앙 지점)의 3차원 좌표값을 알려준다.

이는 모노레일, 게임, 수로 건설, 철도 건설, 항로 계산 등의 실제적인 업무에 사용되기도 한다.

이후 더 부드러운 곡선을 만들어 내는 방법인 Catmull-Rom 보간법이 개발되었기에, 현재는 에르미트 보간법을 대신하여 많이 사용되고 있다. 하지만, 이러한 방식을 처음 고안한 사람이 에르미트이기에, 실제로는 Catmull-Rom 보간법을 사용하면서도 에르미트 보간법이라고 통칭하는 경우도 많다.

4. 2. 기타 응용

마이크로소프트사의 다이렉트 X SDK에서는 `D3DXVecHermite`라는 함수로 에르미트 보간법을 이용할 수 있다.

`D3DXVecHermite` 함수의 정의는 다음과 같다.

```c

D3DXVECTOR3* WINAPI D3DXVecHermite( D3DXVECTOR3 *pOut, CONST D3DXVECTOR3 *pV1, CONST D3DXVECTOR3 *pT1,

CONST D3DXVECTOR3 *pV2, CONST D3DXVECTOR3 *pT2, FLOAT s );

```

위에서 각 인수의 의미는 다음과 같다.

pV1: 시작점의 좌표 (0, 0, 0에서 이 점까지의 벡터값)
pT1: 시작점에서 다음 지점까지의 벡터값 (= pV2 - pV1)
pV2: 다음 지점의 좌표 (0, 0, 0에서 이 점까지의 벡터값)
pT2: 다음 지점에서 그 다음 지점의 벡터값 (= pV3 - pV2)
s: 0.0f ~ 0.1f의 상수

아래와 같이 사용할 수 있다.

```c

D3DXVECTOR3 pOut(0,0,0), pV1(-2.0f,-2.0f,-2.0f), pT1, pV2(1.0f,1.0f,1.0f), pT2, pV3(2.0f,1.5f,3.0f);

FLOAT s;

pT1 *= 0.0f;

pT2 *= 0.0f;

pT1 = pV2 - pV1;

pT2 = pV3 - pV2;

s = 0.5f;

D3DXVecHermite(&pOut, &pV1, &pT1, &pV2, &pT2, s);

```

`pOut.x`, `pOut.y`, `pOut.z`는 에르미트 보간법에 의하여 발생된 곡선의 0.5f 지점(중앙 지점)의 3차원 좌표값을 알려준다.

이것은 모노레일, 게임, 수로 건설, 철도 건설, 항로 계산 등의 실제적인 업무에 사용되기도 한다.

이후 더 부드러운 곡선을 만들어 내는 방법인 Catmull-Rom 보간법이 개발되었기에, 현재는 에르미트 보간법을 대신하여 많이 사용되고 있다. 하지만, 이러한 방식을 처음 고안한 사람이 에르미트이기에, 실제로는 Catmull-Rom 보간법을 사용하면서도 에르미트 보간법이라고 통칭하는 경우도 많다.

참조

_[1] 논문 Sur la formule d'interpolation de Lagrange. https://eudml.org/do[...] 1878
_[2] 논문 On Lagrange—Hermite interpolation https://www.jstor.or[...] 1964-12
_[3] 논문 A Generalization of Hermite Interpolation https://www.jstor.or[...] 1960-01
_[4] 논문 Hermite Interpolation: The Barycentric Approach https://link.springe[...] 1991
_[5] 서적 A Graduate Introduction to Numerical Methods Springer 2013

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com