라그랑주 다항식

3. 증명

''L''(''x'')가 데이터를 적절히 보간하기 위해서는, 각 데이터 점 ''j''에 대해 ''k''차 이하의 다항식 ''L''(''x'')가 다음 조건을 만족해야 한다.

:$L(x\_j)\; =\; y\_j\; \backslash qquad\; j=0,\backslash ldots,k$

만약 이 조건이 모든 ''j''에 대해 성립한다면, 그 다항식은 보간 문제의 해답이라고 할 수 있다.

다음은 이 다항식이 유일함을 증명하는 과정이다.

# $\backslash ell\_j(x)$는 곱에서 ''k''개의 항을 포함하고 각 항은 x를 하나씩 포함하고 있으므로, ''L''(''x'')(''k''차 다항식의 합)는 ''k''차 다항식이어야 한다.

# $\backslash ell\_j(x\_i)\; =\; \backslash prod\_\{f=0,\backslash ,\; f\backslash neq\; j\}^\{k\}\; \backslash frac\{x\_i-x\_f\}\{x\_j-x\_f\}$

이 곱셈을 확장하면, 곱이 $f\; =\; j$인 경우를 제외하기 때문에, 만약 $i\; =\; j$라면 모든 항은 $\backslash frac\{x\_j-x\_f\}\{x\_j-x\_f\}\; =\; 1$이 된다. ($x\_j\; =\; x\_f$인 경우는 제외)

만약 주어진 점들을 지나는 차수가 k 이하인 다항식이 L(x)와 M(x) 두 개가 있다고 가정해보자. 그러면 L(x)-M(x)는 k+1개의 서로 다른 근을 가지는 k차 이하의 다항식이 되므로 0이 될 수밖에 없다. 따라서, L(x)=M(x)가 된다. 즉, 주어진 점들을 지나는 k차 이하의 다항식은 유일하다.

4. 주요 아이디어

라그랑주 보간법의 핵심 아이디어는 각 데이터 점에 대해, 해당 점에서는 1이고 다른 모든 점에서는 0이 되는 기저 함수를 구성하는 것이다. 이러한 기저 함수들의 선형 결합을 통해 주어진 모든 점을 지나는 다항식을 만들 수 있다.

서로 다른 $k+1$개의 점 $\backslash \{x\_0,\; x\_1,\; \backslash ldots,\; x\_k\backslash \}$가 주어졌을 때, $j\; \backslash neq\; m$이면 $x\_j\; \backslash neq\; x\_m$이다. 이 점들에 대한 차수가 $k$ 이하인 라그랑주 기저 다항식 집합 $\backslash \{\backslash ell\_0(x),\; \backslash ell\_1(x),\; \backslash ldots,\; \backslash ell\_k(x)\backslash \}$은 다음 조건을 만족한다.

• $m\; \backslash neq\; j$일 때 $\backslash ell\_j(x\_m)\; =\; 0$
• $\backslash ell\_j(x\_j)\; =\; 1$

5. 선형대수학적 관점

보간 문제를 해결하는 것은 행렬의 역행렬을 구하는 선형대수학의 문제로 이어진다. 보간 다항식 $L(x)\; =\; \backslash sum\_\{j=0\}^k\; x^j\; m\_j$에 대한 표준 단항식 기저를 사용하면, 계수 $m\_j$에 대해 $L(x\_i)\; =\; y\_i$를 풀기 위해 반데르몽드 행렬 $(x\_i)^j$의 역행렬을 구해야 한다. 더 나은 기저인 라그랑주 기저 $L(x)\; =\; \backslash sum\_\{j=0\}^k\; l\_j(x)\; y\_j$를 선택하면 항등 행렬, $\backslash delta\_\{ij\}$를 얻게 되는데, 이는 자체 역행렬이다. 즉, 라그랑주 기저는 자동으로 반데르몽드 행렬의 유사 행렬을 ''역전''시킨다.

이 구성은 중국인의 나머지 정리와 유사하다. 정수를 소수로 나눈 나머지를 확인하는 대신, 선형식으로 나눌 때 다항식의 나머지를 확인한다.

또한, 차수가 클 때 고속 푸리에 변환을 사용하여 보간된 다항식의 계수를 구할 수 있다.

6. 중점(Barycentric) 형태

라그랑주 다항식은 중점(barycentric) 형태로 변형하면 계산 효율성을 높일 수 있다. 중점 형태는 크게 두 가지로 나뉜다.

• 첫 번째 중점 형태: 라그랑주 다항식을 각 항의 공통 인수로 묶어 표현하는 방식이다.
• 두 번째 중점 형태 (실제 형태): 첫 번째 형태를 한 번 더 변형하여 계산의 효율성을 더욱 높인 방식이다. 이 형태는 분모와 분자에 공통으로 나타나는 항을 상쇄시켜 계산 정확도를 높이는 장점도 있다.

6. 1. 중점 가중치(Barycentric weight)

6. 2. 첫 번째 중점 형태

6. 3. 두 번째 중점 형태 (실제 형태)

7. 오차항

주어진 함수 ''f''를 노드 $x\_0,...,x\_k$에서 차수 $k$의 다항식으로 보간할 때, 나머지 $R(x)\; =\; f(x)\; -\; L(x)$는 다음과 같이 표현할 수 있다.^[6]

:

여기서 $f[x\_0,\backslash ldots,x\_k,x]$는 나눗셈 차이 표기법이다. 또는, 나머지는 복소 평면에서 다음과 같은 선적분으로 표현할 수 있다.

:$R(x)\; =\; \backslash frac\{\backslash ell(x)\}\{2\backslash pi\; i\}\; \backslash int\_C\; \backslash frac\{f(t)\}\{(t-x)(t-x\_0)\; \backslash cdots\; (t-x\_k)\}\; dt\; =\; \backslash frac\{\backslash ell(x)\}\{2\backslash pi\; i\}\; \backslash int\_C\; \backslash frac\{f(t)\}\{(t-x)\backslash ell(t)\}\; dt.$

나머지는 다음과 같이 제한될 수 있다.

:$|R(x)|\; \backslash leq\; \backslash frac\{(x\_k-x\_0)^\{k+1\}\}\{(k+1)!\}\backslash max\_\{x\_0\; \backslash leq\; \backslash xi\; \backslash leq\; x\_k\}\; |f^\{(k+1)\}(\backslash xi)|.$

$R(x)$는 노드에서 0이다. 점 $x\_p$에서 $R(x)$를 찾기 위해 새로운 함수 $F(x)=R(x)-\backslash tilde\{R\}(x)=f(x)-L(x)-\backslash tilde\{R\}(x)$를 정의하고 $\backslash tilde\{R\}(x)=C\backslash cdot\backslash prod\_\{i=0\}^k(x-x\_i)$을 선택한다. 여기서 $C$는 주어진 $x\_p$에 대해 결정해야 할 상수이다. $F(x)$가 $x\_0$와 $x\_k$ 사이(경계 포함)에 $k+2$개의 0(모든 노드와 $x\_p$에서)을 갖도록 $C$를 선택한다. $f(x)$가 $k+1$번 미분 가능하다고 가정하면, $L(x)$와 $\backslash tilde\{R\}(x)$는 다항식이므로 무한히 미분 가능하며, $F(x)$는 $k+1$번 미분 가능하다. 롤의 정리에 의해, $F^\{(1)\}(x)$는 $k+1$개의 0을 갖고, $F^\{(2)\}(x)$는 $k$개의 0을 갖는다. $F^\{(k+1)\}$은 1개의 0, 즉

:$F^\{(k+1)\}(\backslash xi)=f^\{(k+1)\}(\backslash xi)-L^\{(k+1)\}(\backslash xi)-\backslash tilde\{R\}^\{(k+1)\}(\backslash xi)$

:$L^\{(k+1)\}=0,\backslash tilde\{R\}^\{(k+1)\}=C\backslash cdot(k+1)!$ ($\backslash tilde\{R\}(x)$에서 $x$의 최고 차수가 $k+1$이기 때문)

:$0=f^\{(k+1)\}(\backslash xi)-C\backslash cdot(k+1)!$

이 방정식은 다음과 같이 재배열할 수 있다.^[7]

:$C=\backslash frac\{f^\{(k+1)\}(\backslash xi)\}\{(k+1)!\}$

$F(x\_p)\; =\; 0$이므로 $R(x\_p)=\backslash tilde\{R\}(x\_p)\; =\; \backslash frac\{f^\{k+1\}(\backslash xi)\}\{(k+1)!\}\backslash prod\_\{i=0\}^k(x\_p-x\_i)$이다.

8. 도함수

라그랑주 보간 다항식의 $d$차 도함수는 기저 다항식의 도함수를 이용하여 나타낼 수 있다.

:$L^\{(d)\}(x)\; :=\; \backslash sum\_\{j=0\}^\{k\}\; y\_j\; \backslash ell\_j^\{(d)\}(x).$

각 라그랑주 기저 다항식은 다음과 같다.

:$$\backslash begin\{aligned\}$$

\ell_j(x) &= \prod_{\begin{smallmatrix}m = 0\\ m\neq j\end{smallmatrix}}^k \frac{x-x_m}{x_j-x_m}.

\end{aligned}

첫 번째 도함수는 곱의 규칙을 통해 구한다.

:$\backslash begin\{align\}$

\ell_j'(x) &= \sum_{\begin{smallmatrix}i=0 \\ i\not=j\end{smallmatrix}}^k \Biggl[ \frac{1}{x_j-x_i}\prod_{\begin{smallmatrix}m=0 \\ m\not = (i , j)\end{smallmatrix}}^k \frac{x-x_m}{x_j-x_m} \Biggr]

\\[5mu]

&= \ell_j(x)\sum_{\begin{smallmatrix}i=0 \\i\not=j\end{smallmatrix}}^k \frac{1}{x-x_i}.

\end{align}

두 번째 도함수는 다음과 같다.

:$\backslash begin\{align\}$

\ell_j''(x)

&= \sum_{\begin{smallmatrix}i=0 \\ i\ne j\end{smallmatrix}}^{k} \frac{1}{x_j-x_i} \Biggl[ \sum_{\begin{smallmatrix}m=0 \\ m\ne(i,j)\end{smallmatrix}}^{k} \Biggl( \frac{1}{x_j-x_m}\prod_{\begin{smallmatrix}n=0 \\ n\ne(i,j,m)\end{smallmatrix}}^{k} \frac{x-x_n}{x_j-x_n} \Biggr) \Biggr]

\\[10mu]

&= \ell_j(x)

\sum_{0 \leq i < m \leq k}

\frac{2}{(x-x_i)(x - x_m)}

\\[10mu]

&= \ell_j(x)\Biggl[\Biggl(\sum_{\begin{smallmatrix}i=0 \\i\not=j\end{smallmatrix}}^k \frac{1}{x-x_i}\Biggr)^2-\sum_{\begin{smallmatrix}i=0 \\i\not=j\end{smallmatrix}}^k \frac{1}{(x-x_i)^2}\Biggr].

\end{align}

세 번째 도함수는 다음과 같다.

:$\backslash begin\{align\}$

\ell_j'''(x)

&= \ell_j(x)

\sum_{0 \leq i < m < n \leq k}

\frac{3!}{(x-x_i)(x - x_m)(x - x_n)}

\end{align}

더 높은 차수의 도함수도 이와 유사하게 구할 수 있다.

이러한 공식은 노드나 노드 근처에서는 유효하지 않을 수 있다. 이 경우에는 라그랑주 다항식을 멱 기저(power basis) 형태로 변환하여 도함수를 계산하는 것이 효율적일 수 있다.

9. 유한체(Finite Fields)에서의 응용

라그랑주 다항식은 유한체에서도 계산할 수 있다. 이는 샤미르의 비밀 공유 방식과 같은 암호학에서 응용된다.

10. 예제

다른 예로, $f(x)\; =\; x^2$을 $1\; \backslash leq\; x\; \backslash leq\; 3$의 영역에서 세 개의 노드 $\backslash \{1,\backslash ,\; 2,\backslash ,\; 3\backslash \}$를 사용하여 보간하는 경우를 살펴보자.

각 노드의 바리 중심 가중치는 다음과 같다.

• $w\_0\; =\; (1-2)^\{-1\}(1-3)^\{-1\}\; =\; \backslash tfrac12$
• $w\_1\; =\; (2-1)^\{-1\}(2-3)^\{-1\}\; =\; -1$
• $w\_2\; =\; (3-1)^\{-1\}(3-2)^\{-1\}\; =\; \backslash tfrac12$

• $\backslash ell\_0(x)\; =\; \backslash frac\{x\; -\; 2\}\{1\; -\; 2\}\backslash cdot\backslash frac\{x\; -\; 3\}\{1\; -\; 3\}\; =\; \backslash tfrac12x^2\; -\; \backslash tfrac52x\; +\; 3$
• $\backslash ell\_1(x)\; =\; \backslash frac\{x\; -\; 1\}\{2\; -\; 1\}\backslash cdot\backslash frac\{x\; -\; 3\}\{2\; -\; 3\}\; =\; -x^2\; +\; 4x\; -\; 3$
• $\backslash ell\_2(x)\; =\; \backslash frac\{x\; -\; 1\}\{3\; -\; 1\}\backslash cdot\backslash frac\{x\; -\; 2\}\{3\; -\; 2\}\; =\; \backslash tfrac12x^2\; -\; \backslash tfrac32x\; +\; 1$

11. 주의사항

라그랑주형 보간은 절점 $x_k$를 변경할 때마다 라그랑주 기저 다항식을 모두 다시 계산해야 하는 번거로움이 있다. 따라서 실용적인 목적에서는 중점형 라그랑주 보간 (후술)이나 뉴턴 보간법을 사용하는 것이 좋다.

등간격 절점에 대한 라그랑주 보간은 원래 함수 위아래로 진동하는 다항식을 생성하며, 절점 수가 증가할수록 룬게 현상으로 인해 발산할 수 있다. 이러한 문제는 체비쇼프 노드를 사용하여 보간점을 선택하면 완화할 수 있다.^[9]

참조

_[1] 서적 Leçons Elémentaires sur les Mathématiques
_[1] 서적 Oeuvres de Lagrange Gauthier-Villars
_[1] 서적 Lectures on Elementary Mathematics Open Court
_[2] 논문 Problems concerning interpolations https://archive.org/[...]
_[3] 논문 A chronology of interpolation: from ancient astronomy to modern signal and image processing http://bigwww.epfl.c[...]
_[4] 논문 Barycentric Lagrange Interpolation https://people.maths[...]
_[5] 서적 Scientific Computing with MATLAB https://books.google[...] Springer
_[6] 간행물 AS ref
_[7] 웹사이트 Interpolation https://sam.nitk.ac.[...] 2017-02-15
_[8] 간행물 A chronology of interpolation: from ancient astronomy to modern signal and image processing
_[9] 간행물 Scientific Computing with MATLAB https://books.google[...] Springer
_[10] 논문 Barycentric Lagrange Interpolation
_[11] 문서 Abramowitz and Stegun, "Handbook of Mathematical Functions," p.878