라그랑주 다항식

1. 개요

라그랑주 다항식은 주어진 점들을 지나는 차수가 k 이하인 유일한 다항식으로, 라그랑주 기저 다항식들의 선형 결합으로 표현된다. 이 다항식은 수학, 특히 수치 해석에서 함수의 보간에 사용되며, 암호학과 같은 분야에서도 응용된다. 라그랑주 다항식은 각 데이터 점에 대해 해당 점에서는 1이고 다른 모든 점에서는 0이 되는 기저 함수를 구성하는 핵심 아이디어를 기반으로 하며, 중점 형태를 사용하여 계산 효율성을 높일 수 있다. 그러나 절점 변경 시 기저 다항식을 다시 계산해야 하는 단점이 있으며, 등간격 절점 사용 시 룬게 현상과 같은 문제를 야기할 수 있다.

2. 정의

k^영어 + 1개의 데이터 점 $(x\_0,\; y\_0),\; \backslash ldots,\; (x\_k,\; y\_k)$가 주어졌을 때 (단, 모든 $x\_j$는 서로 다르다), 이 점들을 지나는 차수가 k^영어 이하인 유일한 다항식을 라그랑주 보간 다항식이라고 한다. 라그랑주 다항식은 라그랑주 기저 다항식들의 선형 결합으로 표현된다. 보간 다항식은 유일하다는 성질을 가진다.

2.1. 라그랑주 기저 다항식

k + 1개의 데이터 점 (x₀, y₀), ..., (x_j, y_j), ..., (x_k, y_k)가 주어지고, 이때 어떤 두 x_j도 같지 않다고 가정한다. 라그랑주 형식의 보간 다항식은 라그랑주 기저 다항식의 선형 결합으로 표현된다.

각 j에 대해, 라그랑주 기저 다항식 ℓ_j(x)는 다음과 같이 정의된다.

:$\backslash ell\_j(x):\; =\; \backslash prod\_\{f=0,\backslash ,\; f\backslash neq\; j\}^\{k\}\; \backslash frac\{x-x\_f\}\{x\_j-x\_f\}\; =\; \backslash frac\{(x-x\_0)\}\{(x\_j-x\_0)\}\; \backslash cdots\; \backslash frac\{(x-x\_\{j-1\})\}\{(x\_j-x\_\{j-1\})\}\; \backslash frac\{(x-x\_\{j+1\})\}\{(x\_j-x\_\{j+1\})\}\; \backslash cdots\; \backslash frac\{(x-x\_\{k\})\}\{(x\_j-x\_\{k\})\}.$

x_i는 서로 같은 값을 가지지 않으므로, $x\_j\; -\; x\_f\; \backslash neq\; 0$ 이고, 위 표현은 잘 정의된다.

서로 다른 k + 1개의 노드 {x₀, x₁, ..., x_k}가 주어지면, j ≠ m인 인덱스에 대해 x_j ≠ x_m을 만족한다. 이 노드들에 대한 차수가 k 이하인 다항식의 라그랑주 기저는, 각 차수가 k이고 m ≠ j일 때 ℓ_j(x_m) = 0이며 ℓ_j(x_j) = 1의 값을 갖는 다항식 집합 {ℓ₀(x), ℓ₁(x), ..., ℓ_k(x)}이다. 크로네커 델타를 사용하면, 이를 ℓ_j(x_m) = δ_jm으로 쓸 수 있다.

분자 $\backslash prod\_\{m\; \backslash neq\; j\}(x\; -\; x\_m)$은 노드 $\backslash \{x\_m\backslash \}\_\{m\; \backslash neq\; j\}$에서 k개의 근을 갖는다. 반면, 분모 $\backslash prod\_\{m\; \backslash neq\; j\}(x\_j\; -\; x\_m)$은 결과 다항식을 스케일링하여 ℓ_j(x_j) = 1이 되도록 한다.

2.2. 선형 결합

k + 1개의 데이터 점 (x₀, y₀), ..., (x_j, y_j), ..., (x_k, y_k)가 주어졌을 때 (단, x_j는 모두 서로 다른 값), 라그랑주 형식의 보간 다항식은 다음과 같은 라그랑주 기저 다항식들의 선형 결합으로 나타낼 수 있다.

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

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

:$\backslash ell\_j(x):\; =\; \backslash prod\_\{f=0,\backslash ,\; f\backslash neq\; j\}^\{k\}\; \backslash frac\{x-x\_f\}\{x\_j-x\_f\}\; =\; \backslash frac\{(x-x\_0)\}\{(x\_j-x\_0)\}\; \backslash cdots\; \backslash frac\{(x-x\_\{j-1\})\}\{(x\_j-x\_\{j-1\})\}\; \backslash frac\{(x-x\_\{j+1\})\}\{(x\_j-x\_\{j+1\})\}\; \backslash cdots\; \backslash frac\{(x-x\_\{k\})\}\{(x\_j-x\_\{k\})\}.$

이 식은 L(x_i) = y_i (i = 0부터 k까지)를 만족하여, 주어진 모든 점을 지난다. $\backslash ell\_j(x\_i)$
= \prod_{f=0,\, f\neq j}^{k} \frac{x_i-x_f}{x_j-x_f}
에서 i = j 라면 모든 항이 1이 되고, j ≠ m 에 대해 $x\_j\; \backslash neq\; x\_m$ 이고, m ≠ j 일 때, $\backslash ell\_j(x\_m)\; =\; 0$이며 $\backslash ell\_j(x\_j)\; =\; 1$의 값을 갖는다. 크로네커 델타를 사용하면 이를 $\backslash ell\_j(x\_m)\; =\; \backslash delta\_\{jm\}$으로 쓸 수 있다.

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$

크로네커 델타를 사용하면, $\backslash ell\_j(x\_m)\; =\; \backslash delta\_\{jm\}$으로 표현할 수 있다. 각 기저 다항식은 다음과 같이 나타낼 수 있다.

$$\backslash begin\{aligned\}$$
\ell_j(x) &= \frac{(x-x_0)}{(x_j-x_0)} \cdots \frac{(x-x_{j-1})}{(x_j-x_{j - 1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \cdots \frac{(x-x_k)}{(x_j-x_k)} \\[8mu]
&= \prod_{\begin{smallmatrix}0\le m\le k\\ m\neq j\end{smallmatrix}} \frac{x-x_m}{x_j-x_m} \vphantom\Bigg|.
\end{aligned}

여기서 분자 $\backslash prod\_\{m\; \backslash neq\; j\}(x\; -\; x\_m)$은 $\backslash \{x\_m\backslash \}\_\{m\; \backslash neq\; j\}$에서 $k$개의 근을 갖는다. 분모 $\backslash prod\_\{m\; \backslash neq\; j\}(x\_j\; -\; x\_m)$은 $\backslash ell\_j(x\_j)\; =\; 1$이 되도록 다항식을 조정한다.

주어진 점들에서의 값 $\backslash \{y\_0,\; y\_1,\; \backslash ldots,\; y\_k\backslash \}$에 대해, 라그랑주 다항식은 다음과 같은 선형 결합으로 표현된다.

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

각 기저 다항식의 차수가 $k$이므로, 합 $L(x)$의 차수는 $k$ 이하이다. 또한 $L(x\_m)\; =\; \backslash sum\_\{j=0\}^\{k\}\; y\_j\; \backslash ell\_j(x\_m)\; =\; \backslash sum\_\{j=0\}^\{k\}\; y\_j\; \backslash delta\_\{mj\}\; =\; y\_m$이므로, 이 다항식은 주어진 점들을 보간한다.

보간 다항식은 유일하다. 차수가 $k$ 이하인 다항식 $M(x)$가 데이터를 보간한다고 가정하면, $M(x)\; -\; L(x)$는 $k+1$개의 서로 다른 점 $\backslash \{x\_0,\; x\_1,\; \backslash ldots,\; x\_k\backslash \}$에서 0이다. 그러나 $k$개 이상의 근을 갖는 $k$ 차 이하의 다항식은 상수 0 함수뿐이므로, $M(x)\; -\; L(x)\; =\; 0$, 즉 $M(x)\; =\; L(x)$이다.

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)

각 라그랑주 기저 다항식은 세 부분의 곱으로 다시 쓸 수 있다. 모든 기저 다항식에 공통적인 함수 , 노드 특정 상수 (중점 가중치(barycentric weight)라고 함) 및 에서 로의 변위를 나타내는 부분이다.

합에서 를 묶어내면, 이른바 첫 번째 중점(barycentric) 형태로 라그랑주 다항식을 쓸 수 있다.

가중치 가 미리 계산되었다면, 각 라그랑주 기저 다항식 를 개별적으로 평가하는 데 가 필요한 것에 비해 연산만 필요하다.

중점(barycentric) 보간 공식은 또한 각 , 를 로 나누고 새로운 을 위와 같이 구성하여 새로운 노드 을 통합하도록 쉽게 업데이트할 수 있다.

임의의 에 대해, 이다. 왜냐하면 상수 함수 은 데이터 }를 보간하는 차수 의 고유한 다항식이기 때문이다. 따라서 로 중점(barycentric) 공식을 더욱 단순화할 수 있다.

이것은 중점(barycentric) 보간 공식의 두 번째 형태 또는 실제 형태라고 불린다.

이 두 번째 형태는 계산 비용과 정확도 측면에서 장점이 있다. 의 평가를 피한다. 분모 의 각 항을 계산하는 작업은 이미 를 계산하는 데 수행되었으므로, 분모의 합을 계산하는 데 개의 덧셈 연산만 필요하다. 노드 중 하나에 가까운 평가점 의 경우, catastrophic cancelation이 일반적으로 값 에 문제가 되겠지만, 이 양은 분자와 분모 모두에 나타나며 두 개가 상쇄되어 최종 결과에 좋은 상대적 정확도를 남긴다.

이 공식을 사용하여 노드 중 하나에서 를 평가하면 부정형 가 발생한다. 컴퓨터 구현은 이러한 결과를 로 대체해야 한다.

각 라그랑주 기저 다항식은 중점(barycentric) 형태로도 쓸 수 있다.

라그랑주 기저 다항식을 다음과 같이 다시 쓸 수 있다.

이는 중심 가중치(barycentric weight)를 로 정의하면 간단하게

로 쓸 수 있는데, 이를 중심 라그랑주 보간의 "제1형"이라고 부른다.

이 형태의 다항식 보간을 고려하는 것의 이점은 보간 다항식 를 평가할 때, 가중치 가 사전에 알려져 있다면 으로 계산할 수 있다는 것이다(라그랑주 기저 를 개별적으로 계산하는 것은 이 소요된다). 또 다른 중심형 보간의 이점으로, 새로운 절점 의 추가도 각 를 로 나누고, 새로운 를 계산하는 것만으로 쉽게 할 수 있다는 점을 들 수 있다.

더욱이 제1형을 단순화하는 것도 가능하다. 먼저 상수 함수 의 중심 보간 를 계산한 다음, 을 로 나누면, 얻는

은 주어진 절점에서의 보간성을 잃지 않는다. 이 보간 다항식을 중심 보간 다항식의 "제2형" 또는 "진정한 형태"라고 한다. 진정한 중심 보간 다항식은 의 각 절점에서 평가할 때 라그랑주 기저 를 평가할 필요가 없다는 점에서 유리하다.

6.2. 첫 번째 중점 형태

각 라그랑주 기저 다항식 $\backslash ell\_j(x)$는 모든 기저 다항식에 공통적인 함수 $\backslash ell(x)\; =\; \backslash prod\_m\; (x\; -\; x\_m)$, 노드 특정 상수 $w\_j\; =\; \backslash prod\_\{m\backslash neq\; j\}(x\_j\; -\; x\_m)^\{-1\}$(barycentric weight라고 함) 및 $x\_j$에서 $x$로의 변위를 나타내는 부분의 곱으로 다시 쓸 수 있다.

:$\backslash ell\_j(x)\; =\; \backslash ell(x)\; \backslash dfrac\{w\_j\}\{x\; -\; x\_j\}$

합에서 $\backslash ell(x)$를 묶어내면, 라그랑주 다항식을 첫 번째 barycentric 형태로 쓸 수 있다.

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

가중치 $w\_j$가 미리 계산되었다면, 각 라그랑주 기저 다항식 $\backslash ell\_j(x)$을 개별적으로 평가하는 데 $\backslash mathcal\; O(k^2)$가 필요한 것에 비해 $\backslash mathcal\; O(k)$ 연산만 필요하다.

barycentric 보간 공식은 또한 각 $w\_j$, $j=0\; \backslash dots\; k$를 $(x\_j\; -\; x\_\{k+1\})$로 나누고 새로운 $w\_\{k+1\}$을 위와 같이 구성하여 새로운 노드 $x\_\{k+1\}$을 통합하도록 쉽게 업데이트할 수 있다.

라그랑주 기저 다항식을 $$\backslash begin\{align\}$$
\ell(x) &= (x - x_0)(x - x_1) \cdots (x - x_k)\\[5pt]
\ell'(x_j) &= \frac{d\ell(x)}{dx}\Big|_{x=x_j} = \prod_{i=0,i \neq j}^k(x_j-x_i)
\end{align} 를 사용하여 $\backslash ell\_j(x)\; =\; \backslash frac\{\backslash ell(x)\}\{\backslash ell\text{'}(x\_j)(x-x\_j)\}$로 다시 쓸 수 있다. 이는 barycentric weight^영어를 $w\_j\; =\; \backslash frac\{1\}\{\backslash ell\text{'}(x\_j)\}$ 로 정의하면 간단하게 $$\backslash ell\_j(x)\; =\; \backslash ell(x)\backslash frac\{w\_j\}\{x-x\_j\}$$ 로 쓸 수 있는데, 이를 중심(重心) 라그랑주 보간의 "제1형"이라고 부른다.

이 형태의 다항식 보간을 고려하는 것의 이점은 보간 다항식 $L(x)\; =\; \backslash ell(x)\; \backslash sum\backslash limits\_\{j=0\}^k\; \backslash frac\{w\_j\}\{x-x\_j\}y\_j$ 를 평가할 때, 가중치가 사전에 알려져 있다면 $\backslash mathcal\; O(n)$으로 계산할 수 있다는 것이다(라그랑주 기저 $\backslash ell\_j(x)$ 를 개별적으로 계산하는 것은 $\backslash mathcal\; O(n^2)$이 소요된다). 또 다른 중심형 보간의 이점으로, 새로운 절점 $x\_\{k+1\}$ 의 추가도 각 $w\_j$를 $(x\_j\; -\; x\_\{k+1\})$ 로 나누고, 새로운 $w\_\{j+1\}$ 를 계산하는 것만으로 쉽게 할 수 있다는 점을 들 수 있다.

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

각 라그랑주 기저 다항식 $\backslash ell\_j(x)$는 세 부분의 곱으로 다시 쓸 수 있다. 모든 기저 다항식에 공통적인 함수 $\backslash ell(x)\; =\; \backslash prod\_m\; (x\; -\; x\_m)$, 노드 특정 상수 $w\_j\; =\; \backslash prod\_\{m\backslash neq\; j\}(x\_j\; -\; x\_m)^\{-1\}$ (barycentric weight라고 함) 및 $x\_j$에서 $x$로의 변위를 나타내는 부분이다.

:$\backslash ell\_j(x)\; =\; \backslash ell(x)\; \backslash dfrac\{w\_j\}\{x\; -\; x\_j\}$

합에서 $\backslash ell(x)$를 묶어내면, 라그랑주 다항식을 첫 번째 barycentric 형태로 쓸 수 있다.

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

가중치 $w\_j$가 미리 계산되었다면, 각 라그랑주 기저 다항식 $\backslash ell\_j(x)$을 개별적으로 평가하는 데 $\backslash mathcal\; O(k^2)$가 필요한 것에 비해 $\backslash mathcal\; O(k)$ 연산만 필요하다.

barycentric 보간 공식은 새로운 노드 $x\_\{k+1\}$을 통합하도록 쉽게 업데이트할 수 있다. 각 $w\_j$ ($j=0\; \backslash dots\; k$)를 $(x\_j\; -\; x\_\{k+1\})$로 나누고 새로운 $w\_\{k+1\}$을 위와 같이 구성하면 된다.

임의의 $x$에 대해, $\backslash sum\_\{j=0\}^k\; \backslash ell\_j(x)\; =\; 1$이다. 왜냐하면 상수 함수 $g(x)\; =\; 1$은 데이터 $\backslash \{(x\_0,\; 1),\; (x\_1,\; 1),\; \backslash ldots,\; (x\_k,\; 1)\; \backslash \}$를 보간하는 차수 $\backslash leq\; k$의 고유한 다항식이기 때문이다. 따라서 $L(x)\; =\; L(x)\; /\; g(x)$로 barycentric 공식을 더욱 단순화할 수 있다.

:$\backslash begin\{aligned\}$
L(x) &= \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j}y_j \Bigg/ \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j} \\[10mu]
&= \sum_{j=0}^k \frac{w_j}{x-x_j}y_j \Bigg/ \sum_{j=0}^k \frac{w_j}{x-x_j}.
\end{aligned}

이것은 barycentric 보간 공식의 두 번째 형태 또는 실제 형태라고 불린다.

이 두 번째 형태는 계산 비용과 정확도 측면에서 장점이 있다. $\backslash ell(x)$의 평가를 피할 수 있다. 분모 $w\_j/(x-x\_j)$의 각 항을 계산하는 작업은 이미 $\backslash bigl(w\_j/(x-x\_j)\backslash bigr)y\_j$를 계산하는 데 수행되었으므로, 분모의 합을 계산하는 데 $k$ 개의 덧셈 연산만 필요하다. 노드 $x\_j$ 중 하나에 가까운 평가점 $x$의 경우, catastrophic cancelation이 일반적으로 값 $(x-x\_j)$에 문제가 되겠지만, 이 양은 분자와 분모 모두에 나타나며 상쇄되어 최종 결과에 좋은 상대적 정확도를 남긴다.

이 공식을 사용하여 노드 $x\_j$ 중 하나에서 $L(x)$를 평가하면 부정형 $\backslash infty\; y\_j/\backslash infty$가 발생한다. 컴퓨터 구현은 이러한 결과를 $L(x\_j)\; =\; y\_j.$로 대체해야 한다.

각 라그랑주 기저 다항식은 barycentric 형태로도 쓸 수 있다.

:$$
\ell_j(x) = \frac{w_j}{x-x_j} \Bigg/ \sum_{m=0}^k \frac{w_m}{x-x_m}.

7. 오차항

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

:

여기서 $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)!$

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

:$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. 예제

값이 잘 알려진 함수 ƒ(x) = tan(x)를 보간하는 예제를 살펴보자. 다음의 함수값을 이용한다.



주어진 값을 바탕으로 각 기저 다항식을 구하면 다음과 같다.

* $\backslash ell\_0(x)=\{x\; -\; x\_1\; \backslash over\; x\_0\; -\; x\_1\}\backslash cdot\{x\; -\; x\_2\; \backslash over\; x\_0\; -\; x\_2\}\backslash cdot\{x\; -\; x\_3\; \backslash over\; x\_0\; -\; x\_3\}\backslash cdot\{x\; -\; x\_4\; \backslash over\; x\_0\; -\; x\_4\}$
={1\over 243} x (2x-3)(4x-3)(4x+3)

* $\backslash ell\_1(x)\; =\; \{x\; -\; x\_0\; \backslash over\; x\_1\; -\; x\_0\}\backslash cdot\{x\; -\; x\_2\; \backslash over\; x\_1\; -\; x\_2\}\backslash cdot\{x\; -\; x\_3\; \backslash over\; x\_1\; -\; x\_3\}\backslash cdot\{x\; -\; x\_4\; \backslash over\; x\_1\; -\; x\_4\}$
= {} -{8\over 243} x (2x-3)(2x+3)(4x-3)

* $\backslash ell\_2(x)=\{x\; -\; x\_0\; \backslash over\; x\_2\; -\; x\_0\}\backslash cdot\{x\; -\; x\_1\; \backslash over\; x\_2\; -\; x\_1\}\backslash cdot\{x\; -\; x\_3\; \backslash over\; x\_2\; -\; x\_3\}\backslash cdot\{x\; -\; x\_4\; \backslash over\; x\_2\; -\; x\_4\}$
={3\over 243} (2x+3)(4x+3)(4x-3)(2x-3)

* $\backslash ell\_3(x)=\{x\; -\; x\_0\; \backslash over\; x\_3\; -\; x\_0\}\backslash cdot\{x\; -\; x\_1\; \backslash over\; x\_3\; -\; x\_1\}\backslash cdot\{x\; -\; x\_2\; \backslash over\; x\_3\; -\; x\_2\}\backslash cdot\{x\; -\; x\_4\; \backslash over\; x\_3\; -\; x\_4\}$
=-{8\over 243} x (2x-3)(2x+3)(4x+3)

* $\backslash ell\_4(x)=\{x\; -\; x\_0\; \backslash over\; x\_4\; -\; x\_0\}\backslash cdot\{x\; -\; x\_1\; \backslash over\; x\_4\; -\; x\_1\}\backslash cdot\{x\; -\; x\_2\; \backslash over\; x\_4\; -\; x\_2\}\backslash cdot\{x\; -\; x\_3\; \backslash over\; x\_4\; -\; x\_3\}$
={1\over 243} x (2x+3)(4x-3)(4x+3)

이를 통해 보간된 다항식을 구하면 다음과 같다.

:
& {} \qquad {} - 8f(x_1)x (2x-3)(2x+3)(4x-3) \\
& {} \qquad {} + 3f(x_2)(2x+3)(4x+3)(4x-3)(2x-3) \\
& {} \qquad {} - 8f(x_3)x (2x-3)(2x+3)(4x+3) \\
& {} \qquad {} + f(x_4)x (2x+3)(4x-3)(4x+3)\Big)\\
& = 4.834848x^3 - 1.477474x
\end{align}




다른 예로, $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$

따라서 라그랑주 보간 다항식은 다음과 같다.

:$$
L(x) = 1\cdot\frac{x - 2}{1 - 2}\cdot\frac{x - 3}{1 - 3}
+ 4\cdot\frac{x - 1}{2 - 1}\cdot\frac{x - 3}{2 - 3}
+ 9\cdot\frac{x - 1}{3 - 1}\cdot\frac{x - 2}{3 - 2}
= x^2


이는 두 번째 바리 중심 형태를 사용하여 다음과 같이 표현할 수 있다.

:$$
L(x) = \frac
{\displaystyle \sum_{j=0}^2 \frac{w_j}{x-x_j}y_j}
{\displaystyle \sum_{j=0}^2 \frac{w_j}{x-x_j}}
= \frac
{\displaystyle \frac{\tfrac12}{x - 1} + \frac{-4}{x - 2} + \frac{\tfrac92}{x - 3}}
{\displaystyle \frac{\tfrac12}{x - 1} + \frac{-1}{x - 2} + \frac{\tfrac12}{x - 3}}

11. 주의사항

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

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