다항식 보간법

수치해석학에서 다항식 보간법(Polynomial interpolation)은 주어진 자료 집합의 점들을 통과하는 가장 낮은 차수의 다항식으로 보간법을 하는 것이다.

서로 다른 n + 1개의 자료점 ${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$이 주어졌을 때, 다항 함수 ${\displaystyle p(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}}$가 각 ${\displaystyle j\in \{0,1,\dotsc ,n\}}$에 대해 ${\displaystyle p(x_{j})=y_{j}}$를 만족하면 자료를 보간한다고 말한다.

이러한 다항식은 항상 유일하며, 일반적으로 라그랑주 다항식과 뉴턴 다항식의 두 가지 명시적 공식으로 주어진다.

응용

보간 다항식의 원래 용도는 자연로그 및 삼각 함수와 같은 중요한 초월 함수의 값을 근사하는 것이었다. 몇 개의 정확하게 계산된 자료점으로부터, 해당 보간 다항식은 임의의 근처 점에서 함수를 근사할 것이다. 다항식 보간법은 또한 수치 적분 (심프슨 공식) 및 수치 상미분 방정식 (다중 격자법) 알고리즘의 기초를 이룬다.

컴퓨터 그래픽스에서는 다항식을 사용하여 몇 가지 지정된 점(예: 타이포그래피의 글자 모양)이 주어졌을 때 복잡한 평면 곡선을 근사할 수 있다. 이는 일반적으로 베지에 곡선을 사용하여 수행되는데, 이는 보간 다항식의 간단한 일반화이다(지정된 점뿐만 아니라 지정된 접선도 가짐).

수치해석학에서 다항식 보간법은 카라추바 곱셈 및 톰-쿡 알고리즘과 같은 이차 미만의 곱셈 및 제곱을 수행하는 데 필수적이다. 여기서 곱 다항식의 점을 통한 보간은 필요한 특정 곱을 산출한다. 예를 들어, a = f(x) = a₀x⁰ + a₁x¹ + ··· 및 b = g(x) = b₀x⁰ + b₁x¹ + ···가 주어지면, 곱 ab는 W(x) = f(x)g(x)의 특정 값이다. W(x)의 점은 작은 x 값에서 쉽게 찾을 수 있으며, 이러한 점을 기반으로 한 보간은 W(x)의 항과 특정 곱 ab를 산출한다. 카라추바 곱셈에서 공식화된 바와 같이, 이 기술은 겸손한 크기의 입력에 대해서도, 특히 병렬 하드웨어에서 이차 곱셈보다 상당히 빠르다.

컴퓨터 과학에서 다항식 보간법은 또한 다자간 보안 컴퓨팅 및 비밀 공유 알고리즘으로 이어진다.

보간 정리

서로 다른 ${\displaystyle x_{j}}$가 없는 ${\displaystyle n+1}$개의 이변량 자료점 ${\displaystyle (x_{0},y_{0}),\dotsc ,(x_{n},y_{n})\in \mathbb {R} ^{2}}$에 대해, 이 점들을 보간하는 차수가 최대 ${\displaystyle n}$인 유일한 다항식 ${\displaystyle p(x)}$가 존재한다. 즉, ${\displaystyle p(x_{0})=y_{0},\ldots ,p(x_{n})=y_{n}}$이다.^[1]

등가적으로, 보간 노드 ${\displaystyle x_{j}}$의 고정된 선택에 대해, 다항식 보간은 실수 값의 (n+1)튜플 ${\displaystyle (y_{0},\ldots ,y_{n})\in \mathbb {R} ^{n+1}}$과 차수가 최대 n인 실수 다항식의 벡터 공간 ${\displaystyle P(n)}$ 사이의 선형 전단사 함수 ${\displaystyle L_{n}}$을 정의한다. $${\displaystyle L_{n}:\mathbb {R} ^{n+1}{\stackrel {\sim }{\longrightarrow }}\,P(n).}$$

이것은 일종의 유일해성 정리이다. 이 정리는 실수 ${\displaystyle \mathbb {R} }$ 대신 임의의 무한 체 (예: 유리수 또는 복소수)에 대해서도 유효하다.

첫 번째 증명

라그랑주 기저 함수 ${\displaystyle L_{0}(x),\ldots ,L_{n}(x)}$를 다음과 같이 고려한다: $${\displaystyle L_{j}(x)=\prod _{i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{0})\cdots (x-x_{j-1})(x-x_{j+1})\cdots (x-x_{n})}{(x_{j}-x_{0})\cdots (x_{j}-x_{j-1})(x_{j}-x_{j+1})\cdots (x_{j}-x_{n})}}.}$$

${\displaystyle L_{j}(x)}$는 차수 ${\displaystyle n}$의 다항식이고, 각 ${\displaystyle j\neq k}$에 대해 ${\displaystyle L_{j}(x_{k})=0}$이며, ${\displaystyle L_{k}(x_{k})=1}$임을 알 수 있다. 따라서 선형 결합: $${\displaystyle p(x)=\sum _{j=0}^{n}y_{j}L_{j}(x)}$$ 는 ${\displaystyle p(x_{k})=\sum _{j}y_{j}\,L_{j}(x_{k})=y_{k}}$를 가지므로, ${\displaystyle p(x)}$는 차수 ${\displaystyle n}$의 보간 다항식이다.

유일성을 증명하기 위해, 차수가 최대 ${\displaystyle n}$인 또 다른 보간 다항식 ${\displaystyle q(x)}$가 존재하여 모든 ${\displaystyle k=0,\dotsc ,n}$에 대해 ${\displaystyle p(x_{k})=q(x_{k})}$라고 가정한다. 그러면 ${\displaystyle p(x)-q(x)}$는 ${\displaystyle n+1}$개의 서로 다른 영점( ${\displaystyle x_{k}}$들)을 갖는 차수가 최대 ${\displaystyle n}$인 다항식이다. 그러나 차수가 최대 ${\displaystyle n}$인 영이 아닌 다항식은 최대 ${\displaystyle n}$개의 영점을 가질 수 없으므로,^[a] ${\displaystyle p(x)-q(x)}$는 영 다항식이어야 한다. 즉, ${\displaystyle p(x)=q(x)}$이다.^[2]

두 번째 증명

보간 다항식을 다음과 같은 형태로 작성한다:

$${\displaystyle p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}.}$$

(1)

이를 보간 방정식 ${\displaystyle p(x_{j})=y_{j}}$에 대입하면, 계수 ${\displaystyle a_{j}}$에 대한 연립 일차 방정식을 얻는다. 이를 행렬-벡터 형식으로 나타내면 다음과 같은 행렬 곱셈이 된다: $${\displaystyle {\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&\ldots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&\ldots &x_{1}&1\\\vdots &\vdots &\vdots &&\vdots &\vdots \\x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&\ldots &x_{n}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.}$$

보간 다항식 ${\displaystyle p(x)}$는 위 행렬 방정식 ${\displaystyle X\cdot A=Y}$의 해 ${\displaystyle A=(a_{n},\ldots ,a_{0})}$에 해당한다. 왼쪽의 행렬 X는 방데르몽드 행렬이며, 그 행렬식은 ${\displaystyle \textstyle \det(X)=\prod _{1\leq i<j\leq n}(x_{j}-x_{i})}$로 알려져 있다. 노드 ${\displaystyle x_{j}}$가 모두 다르므로 행렬식은 0이 아니다. 이는 행렬이 가역이며 방정식이 유일한 해 ${\displaystyle A=X^{-1}\cdot Y}$를 가진다는 것을 보장한다. 즉, ${\displaystyle p(x)}$는 존재하며 유일하다.

귀결

${\displaystyle f(x)}$가 차수가 최대 ${\displaystyle n}$인 다항식이라면, ${\displaystyle n+1}$개의 서로 다른 점에서 ${\displaystyle f(x)}$를 보간하는 다항식은 ${\displaystyle f(x)}$ 자체이다.

보간 다항식 구성

붉은 점들은 자료점 (x_k, y_k)를 나타내고, 파란 곡선은 보간 다항식을 나타낸다.

라그랑주 보간법

 이 부분의 본문은 라그랑주 다항식입니다.

라그랑주 다항식을 이용하여 즉시 다항식을 다음과 같이 작성할 수 있다: $${\displaystyle {\begin{aligned}p(x)&={\frac {(x-x_{1})(x-x_{2})\cdots (x-x_{n})}{(x_{0}-x_{1})(x_{0}-x_{2})\cdots (x_{0}-x_{n})}}y_{0}\\[4pt]&+{\frac {(x-x_{0})(x-x_{2})\cdots (x-x_{n})}{(x_{1}-x_{0})(x_{1}-x_{2})\cdots (x_{1}-x_{n})}}y_{1}\\[4pt]&+\cdots \\[4pt]&+{\frac {(x-x_{0})(x-x_{1})\cdots (x-x_{n-1})}{(x_{n}-x_{0})(x_{n}-x_{1})\cdots (x_{n}-x_{n-1})}}y_{n}\\[7pt]&=\sum _{i=0}^{n}{\Biggl (}\prod _{\stackrel {\!0\,\leq \,j\,\leq \,n}{j\,\neq \,i}}{\frac {x-x_{j}}{x_{i}-x_{j}}}{\Biggr )}y_{i}=\sum _{i=0}^{n}{\frac {p(x)}{p'(x_{i})(x-x_{i})}}\,y_{i}\end{aligned}}}$$행렬 인수의 경우, 이 공식은 실베스터 공식이라고 불리며, 행렬 값 라그랑주 다항식은 프로베니우스 공변량이다.

뉴턴 보간법

 뉴턴 다항식 및 나눗셈 차분 문서를 참고하십시오.

정리

노드 ${\displaystyle x_{i}}$ (${\displaystyle i=0,1,2,3,\cdots ,n}$)에서 ${\displaystyle f}$를 보간하는 차수가 ${\displaystyle n}$ 이하인 다항식을 ${\displaystyle p_{n}}$이라 하자. 노드 ${\displaystyle x_{i}}$ (${\displaystyle i=0,1,2,3,\cdots ,n,n+1}$)에서 ${\displaystyle f}$를 보간하는 차수가 ${\displaystyle n+1}$ 이하인 다항식을 ${\displaystyle p_{n+1}}$이라 하자. 그러면 ${\displaystyle p_{n+1}}$은 다음과 같이 주어진다: $${\displaystyle p_{n+1}(x)=p_{n}(x)+a_{n+1}w_{n}(x)}$$ 여기서 ${\textstyle w_{n}(x):=\prod _{i=0}^{n}(x-x_{i})}$는 뉴턴 기저라고도 하며, ${\textstyle a_{n+1}:={f(x_{n+1})-p_{n}(x_{n+1}) \over w_{n}(x_{n+1})}}$이다.

증명:

이것은 ${\displaystyle i=0,1,2,3,\cdots ,n}$인 경우에 대해 보일 수 있다: $${\displaystyle p_{n+1}(x_{i})=p_{n}(x_{i})+a_{n+1}\prod _{j=0}^{n}(x_{i}-x_{j})=p_{n}(x_{i})}$$ 그리고 ${\displaystyle i=n+1}$일 때: $${\displaystyle p_{n+1}(x_{n+1})=p_{n}(x_{n+1})+{f(x_{n+1})-p_{n}(x_{n+1}) \over w_{n}(x_{n+1})}w_{n}(x_{n+1})=f(x_{n+1})}$$ 차수가 ${\displaystyle n+1}$ 미만인 보간 다항식의 유일성에 따라, ${\textstyle p_{n+1}(x)=p_{n}(x)+a_{n+1}w_{n}(x)}$가 요구되는 다항식 보간이다. 따라서 함수는 다음과 같이 표현될 수 있다:

${\textstyle p_{n}(x)=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+\cdots +a_{n}(x-x_{0})\cdots (x-x_{n-1}).}$

다항식 계수

${\displaystyle a_{i}}$를 찾기 위해, 위 방정식에서 ${\textstyle p_{n}(x_{i})=f(x_{i})=y_{i}}$를 행렬 형태로 배열하여 형성된 하삼각 행렬을 풀어야 한다:

${\displaystyle {\begin{bmatrix}1&&\ldots &&0\\1&x_{1}-x_{0}&&&\\1&x_{2}-x_{0}&(x_{2}-x_{0})(x_{2}-x_{1})&&\vdots \\\vdots &\vdots &&\ddots &\\1&x_{k}-x_{0}&\ldots &\ldots &\prod _{j=0}^{n-1}(x_{n}-x_{j})\end{bmatrix}}{\begin{bmatrix}a_{0}\\\\\vdots \\\\a_{n}\end{bmatrix}}={\begin{bmatrix}y_{0}\\\\\vdots \\\\y_{n}\end{bmatrix}}}$

계수는 다음과 같이 유도된다:

${\displaystyle a_{j}:=[y_{0},\ldots ,y_{j}]}$

여기서

${\displaystyle [y_{0},\ldots ,y_{j}]}$

는 나눗셈 차분에 대한 표기법이다. 따라서 뉴턴 다항식은 n개 점의 다항식 보간 공식을 제공하는 데 사용된다.^[2]

증명

처음 몇 개의 계수는 연립 방정식을 사용하여 계산할 수 있다. n차 계수의 형태는 수학적 귀납법으로 증명하기 위해 가정한다. ${\displaystyle {\begin{aligned}a_{0}&=y_{0}=[y_{0}]\\a_{1}&={y_{1}-y_{0} \over x_{1}-x_{0}}=[y_{0},y_{1}]\\\vdots \\a_{n}&=[y_{0},\cdots ,y_{n}]\quad {\text{(라고 하자)}}\\\end{aligned}}}$ ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ 점들의 다항식 보간을 Q라 하자. 다항식 Q에 ${\displaystyle (x_{0},y_{0})}$를 추가한다: ${\displaystyle Q(x)+a'_{n}(x-x_{1})\cdot \ldots \cdot (x-x_{n})=P_{n}(x),}$ 여기서 ${\textstyle a'_{n}(x_{0}-x_{1})\ldots (x_{0}-x_{n})=y_{0}-Q(x_{0})}$이다. ${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$ 점들의 보간 다항식의 유일성에 따라, ${\displaystyle x^{n-1}}$의 계수를 같다고 놓으면 ${\textstyle a'_{n}=[y_{0},\ldots ,y_{n}]}$을 얻는다. 따라서 다항식은 다음과 같이 표현될 수 있다: ${\displaystyle P_{n}(x)=Q(x)+[y_{0},\ldots ,y_{n}](x-x_{1})\cdot \ldots \cdot (x-x_{n}).}$ 다항식 Q에 ${\displaystyle (x_{n+1},y_{n+1})}$을 추가하면, 다음을 만족해야 한다: ${\textstyle [y_{1},\ldots ,y_{n+1}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})=y_{n+1}-Q(x_{n+1})}$ 여기서 ${\textstyle a_{n}}$에 대한 공식과 보간 다항식이 사용된다. 다항식 ${\textstyle P_{n+1}}$에 대한 ${\textstyle a_{n+1}}$ 항은 다음을 계산하여 찾을 수 있다: $${\displaystyle {\begin{aligned}&[y_{0},\ldots ,y_{n+1}](x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&={\frac {[y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]}{x_{n+1}-x_{0}}}(x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=\left([y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]\right)(x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=[y_{1},\ldots ,y_{n+1}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=(y_{n+1}-Q(x_{n+1}))-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=y_{n+1}-(Q(x_{n+1})+[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n}))\\&=y_{n+1}-P(x_{n+1}).\end{aligned}}}$$ 이는 ${\displaystyle a_{n+1}={y_{n+1}-P_{n}(x_{n+1}) \over w_{n}(x_{n+1})}=[y_{0},\ldots ,y_{n+1}]}$를 의미한다. 따라서 수학적 귀납법의 원리에 의해 증명된다.

뉴턴 전진 공식

${\displaystyle x_{0},x_{1},\dots ,x_{k}}$가 등간격으로 연속적으로 배열되어 있을 때, 뉴턴 다항식은 단순화된 형태로 표현될 수 있다.

만약 ${\displaystyle x_{0},x_{1},\dots ,x_{k}}$가 연속적으로 배열되어 있고, ${\displaystyle {x}_{i}={x}_{0}+ih}$ (i = 0, 1, ..., k)와 같이 등간격이며, 어떤 변수 x가 ${\displaystyle {x}={x}_{0}+sh}$로 표현된다면, 차이 ${\displaystyle x-x_{i}}$는 ${\displaystyle (s-i)h}$로 작성될 수 있다. 따라서 뉴턴 다항식은 다음과 같이 된다.

${\displaystyle {\begin{aligned}N(x)&=[y_{0}]+[y_{0},y_{1}]sh+\cdots +[y_{0},\ldots ,y_{k}]s(s-1)\cdots (s-k+1){h}^{k}\\&=\sum _{i=0}^{k}s(s-1)\cdots (s-i+1){h}^{i}[y_{0},\ldots ,y_{i}]\\&=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}].\end{aligned}}}$

나눗셈 차분과 전진 차분 사이의 관계는 다음과 같이 주어진다.^[3] $${\displaystyle [y_{j},y_{j+1},\ldots ,y_{j+n}]={\frac {1}{n!h^{n}}}\Delta ^{(n)}y_{j},}$$ ${\displaystyle y_{i}=f(x_{i})}$라고 할 때, 이전 절에서 x의 표현이 대신 ${\displaystyle x=x_{j}+sh}$로 간주되었다면, 뉴턴 전진 보간 공식은 다음과 같이 표현된다. $${\displaystyle f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{s \choose i}\Delta ^{(i)}f(x_{j})}$$ 이는 ${\displaystyle x_{j}}$ 이후의 모든 점의 보간이다. 다음과 같이 전개된다. $${\displaystyle f(x_{j}+sh)=f(x_{j})+{\frac {s}{1!}}\Delta f(x_{j})+{\frac {s(s-1)}{2!}}\Delta ^{2}f(x_{j})+{\frac {s(s-1)(s-2)}{3!}}\Delta ^{3}f(x_{j})+{\frac {s(s-1)(s-2)(s-3)}{4!}}\Delta ^{4}f(x_{j})+\cdots }$$

뉴턴 후진 공식

노드가 ${\displaystyle {x}_{k},{x}_{k-1},\dots ,{x}_{0}}$으로 재정렬되면 뉴턴 다항식은 다음과 같다.

${\displaystyle N(x)=[y_{k}]+[{y}_{k},{y}_{k-1}](x-{x}_{k})+\cdots +[{y}_{k},\ldots ,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots (x-{x}_{1}).}$

만약 ${\displaystyle {x}_{k},\;{x}_{k-1},\;\dots ,\;{x}_{0}}$가 ${\displaystyle {x}_{i}={x}_{k}-(k-i)h}$ (i = 0, 1, ..., k)와 같이 등간격으로 떨어져 있고, ${\displaystyle {x}={x}_{k}+sh}$라면,

${\displaystyle {\begin{aligned}N(x)&=[{y}_{k}]+[{y}_{k},{y}_{k-1}]sh+\cdots +[{y}_{k},\ldots ,{y}_{0}]s(s+1)\cdots (s+k-1){h}^{k}\\&=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}].\end{aligned}}}$

나눗셈 차분과 후진 차분 사이의 관계는 다음과 같이 주어진다. $${\displaystyle [{y}_{j},y_{j-1},\ldots ,{y}_{j-n}]={\frac {1}{n!h^{n}}}\nabla ^{(n)}y_{j},}$$ ${\displaystyle y_{i}=f(x_{i})}$라고 할 때, 이전 절에서 x의 표현이 대신 ${\displaystyle x=x_{j}+sh}$로 간주되었다면, 뉴턴 후진 보간 공식은 다음과 같이 표현된다. $${\displaystyle f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}\nabla ^{(i)}f(x_{j}).}$$ 이는 ${\displaystyle x_{j}}$ 이전의 모든 점의 보간이다. 다음과 같이 전개된다. $${\displaystyle f(x_{j}+sh)=f(x_{j})+{\frac {s}{1!}}\nabla f(x_{j})+{\frac {s(s+1)}{2!}}\nabla ^{2}f(x_{j})+{\frac {s(s+1)(s+2)}{3!}}\nabla ^{3}f(x_{j})+{\frac {s(s+1)(s+2)(s+3)}{4!}}\nabla ^{4}f(x_{j})+\cdots }$$

다이아몬드 도표

다이아몬드 도표는 주어진 자료 집합에 대해 구성할 수 있는 여러 가지 보간 공식을 설명하는 데 사용되는 도표이다. 왼쪽 가장자리에서 시작하여 도표를 가로질러 오른쪽으로 이동하는 선은 다음 규칙을 따르면 보간 공식을 나타내는 데 사용될 수 있다.^[4]

다이아몬드 도표: 다항식 보간의 기하학적 표현.

1. 왼쪽에서 오른쪽으로 가는 단계는 덧셈을 나타내고, 오른쪽에서 왼쪽으로 가는 단계는 뺄셈을 나타낸다.
2. 단계의 기울기가 양수이면, 사용될 항은 차분과 그 바로 아래 인수의 곱이다. 단계의 기울기가 음수이면, 사용될 항은 차분과 그 바로 위 인수의 곱이다.
3. 단계가 수평이고 인수를 통과하면, 인수와 그 바로 위아래 두 항의 평균 곱을 사용한다. 단계가 수평이고 차분을 통과하면, 차분과 그 바로 위아래 두 항의 평균 곱을 사용한다.

인수는 다음 공식을 사용하여 표현된다: $${\displaystyle C(u+k,n)={\frac {(u+k)(u+k-1)\cdots (u+k-n+1)}{n!}}}$$

등가성 증명

경로가 ${\displaystyle \Delta ^{n-1}y_{s}}$에서 ${\displaystyle \Delta ^{n+1}y_{s-1}}$로 이동할 때, (a) ${\displaystyle \Delta ^{n}y_{s-1}}$를 통해, (b) ${\textstyle C(u-s,n)}$를 통해, 또는 (c) ${\displaystyle \Delta ^{n}y_{s}}$를 통해 세 가지 중간 단계를 거쳐 연결될 수 있다. 이 세 가지 두 단계 경로의 등가성을 증명하면 모든 (n단계) 경로가 시작과 끝이 같으면서 같은 공식을 나타내도록 변형될 수 있음을 증명할 것이다.

경로 (a):

${\displaystyle C(u-s,n)\Delta ^{n}y_{s-1}+C(u-s+1,n+1)\Delta ^{n+1}y_{s-1}}$

경로 (b):

${\displaystyle C(u-s,n)\Delta ^{n}y_{s}+C(u-s,n+1)\Delta ^{n+1}y_{s-1}}$

경로 (c):

${\displaystyle C(u-s,n){\frac {\Delta ^{n}y_{s-1}+\Delta ^{n}y_{s}}{2}}\quad +{\frac {C(u-s+1,n+1)+C(u-s,n+1)}{2}}\Delta ^{n+1}y_{s-1}}$

경로 a와 b의 기여를 뺀다:

${\displaystyle {\begin{aligned}{\text{경로 a - 경로 b}}=&C(u-s,n)(\Delta ^{n}y_{s-1}-\Delta ^{n}y_{s})+(C(u-s+1,n+1)-C(u-s,n-1))\Delta ^{n+1}y_{s-1}\\=&-C(u-s,n)\Delta ^{n+1}y_{s-1}+C(u-s,n){\frac {(u-s+1)-(u-s-n)}{n+1}}\Delta ^{n+1}y_{s-1}\\=&C(u-s,n)(-\Delta ^{n+1}y_{s-1}+\Delta ^{n+1}y_{s-1})=0\\\end{aligned}}}$

따라서 경로 (a)와 경로 (b)의 기여는 동일하다. 경로 (c)는 경로 (a)와 (b)의 평균이므로, 역시 다항식에 동일한 함수를 기여한다. 따라서 시작점과 끝점이 같은 경로의 등가성이 입증되었다. 가장 왼쪽 모서리의 다른 값으로 경로를 이동할 수 있는지 확인하기 위해, 두 단계 경로만으로 충분하다: (a) ${\displaystyle \Delta y_{s}}$를 통해 ${\displaystyle y_{s+1}}$에서 ${\displaystyle y_{s}}$로 또는 (b) ${\displaystyle y_{s+1}}$와 ${\displaystyle y_{s}}$ 사이의 인수를 통해 ${\displaystyle \Delta y_{s}}$를 통해 ${\displaystyle y_{s}}$로 또는 (c) ${\displaystyle y_{s}}$에서 시작한다.

경로 (a)

${\displaystyle y_{s+1}+C(u-s-1,1)\Delta y_{s}-C(u-s,1)\Delta y_{s}}$

경로 (b)

${\displaystyle {\frac {y_{s+1}+y_{s}}{2}}+{\frac {C(u-s-1,1)+C(u-s,1)}{2}}\Delta y_{s}-C(u-s,1)\Delta y_{s}}$

경로 (c)

${\displaystyle y_{s}}$

${\displaystyle \Delta y_{s}=y_{s+1}-y_{s}}$이므로, 위 식에 대입하면 모든 항이 ${\displaystyle y_{s}}$로 줄어들고 따라서 등가임이 보인다. 따라서 이 경로들은 가장 왼쪽 모서리에서 시작하여 공통점으로 끝날 수 있도록 변형될 수 있다.^[4]

뉴턴 공식

${\displaystyle y_{0}}$에서 ${\displaystyle \Delta ^{n}y_{0}}$로 음의 기울기 횡단선을 취하면 모든 ${\displaystyle n+1}$개의 연속적으로 배열된 점들의 보간 공식을 얻게 되며, 이는 뉴턴의 전진 보간 공식과 동등하다.

${\displaystyle {\begin{aligned}y(s)&=y_{0}+C(s,1)\Delta y_{0}+C(s,2)\Delta ^{2}y_{0}+C(s,3)\Delta ^{3}y_{0}+\cdots \\&=y_{0}+s\Delta y_{0}+{\frac {s(s-1)}{2}}\Delta ^{2}y_{0}+{\frac {s(s-1)(s-2)}{3!}}\Delta ^{3}y_{0}+{\frac {s(s-1)(s-2)(s-3)}{4!}}\Delta ^{4}y_{0}+\cdots \end{aligned}}}$

반면, ${\displaystyle y_{n}}$에서 ${\displaystyle \nabla ^{n}y_{n}=\Delta ^{n}y_{0}}$로 양의 기울기 횡단선을 취하면 모든 ${\displaystyle n+1}$개의 연속적으로 배열된 점들의 보간 공식을 얻게 되며, 이는 뉴턴의 후진 보간 공식과 동등하다.

${\displaystyle {\begin{aligned}y(u)&=y_{k}+C(u-k,1)\Delta y_{k-1}+C(u-k+1,2)\Delta ^{2}y_{k-2}+C(u-k+2,3)\Delta ^{3}y_{k-3}+\cdots \\&=y_{k}+(u-k)\Delta y_{k-1}+{\frac {(u-k+1)(u-k)}{2}}\Delta ^{2}y_{k-2}+{\frac {(u-k+2)(u-k+1)(u-k)}{3!}}\Delta ^{3}y_{k-3}+\cdots \\y(k+s)&=y_{k}+(s)\nabla y_{k}+{\frac {(s+1)s}{2}}\nabla ^{2}y_{k}+{\frac {(s+2)(s+1)s}{3!}}\nabla ^{3}y_{k}+{\frac {(s+3)(s+2)(s+1)s}{4!}}\nabla ^{4}y_{k}+\cdots \\\end{aligned}}}$

여기서 ${\displaystyle s=u-k}$는 뉴턴 보간법에서 도입된 해당 숫자이다.

가우스 공식

${\displaystyle y_{0}}$에서 음의 기울기로 오른쪽으로 지그재그 선을 취하면 가우스 전진 공식을 얻는다.

${\displaystyle y(u)=y_{0}+u\Delta y_{0}+{\frac {u(u-1)}{2}}\Delta ^{2}y_{-1}+{\frac {(u+1)u\left(u-1\right)}{3!}}\Delta ^{3}y_{-1}+{\frac {(u+1)u\left(u-1\right)(u-2)}{4!}}\Delta ^{4}y_{-2}+\cdots }$

반면, ${\displaystyle y_{0}}$에서 양의 기울기로 시작하면 가우스 후진 공식을 얻는다.

${\displaystyle y(u)=y_{0}+u\Delta y_{-1}+{\frac {(u+1)u}{2}}\Delta ^{2}y_{-1}+{\frac {(u+1)u\left(u-1\right)}{3!}}\Delta ^{3}y_{-2}+{\frac {(u+2)(u+1)u\left(u-1\right)}{4!}}\Delta ^{4}y_{-2}+\cdots }$

스털링 공식

${\displaystyle y_{0}}$에서 오른쪽으로 수평 경로를 취하면 스털링 공식을 얻는다.

${\displaystyle {\begin{aligned}y(u)&=y_{0}+u{\frac {\Delta y_{0}+\Delta y_{-1}}{2}}+{\frac {C(u+1,2)+C(u,2)}{2}}\Delta ^{2}y_{-1}+C(u+1,3){\frac {\Delta ^{3}y_{-2}+\Delta ^{3}y_{-1}}{2}}+\cdots \\&=y_{0}+u{\frac {\Delta y_{0}+\Delta y_{-1}}{2}}+{\frac {u^{2}}{2}}\Delta ^{2}y_{-1}+{\frac {u(u^{2}-1)}{3!}}{\frac {\Delta ^{3}y_{-2}+\Delta ^{3}y_{-1}}{2}}+{\frac {u^{2}(u^{2}-1)}{4!}}\Delta ^{4}y_{-2}+\cdots \end{aligned}}}$

스털링 공식은 가우스 전진 공식과 가우스 후진 공식의 평균이다.

베셀 공식

${\displaystyle y_{0}}$와 ${\displaystyle y_{1}}$ 사이의 인수에서 시작하여 오른쪽으로 수평 경로를 취하면 베셀 공식을 얻는다.

${\displaystyle {\begin{aligned}y(u)&=1{\frac {y_{0}+y_{1}}{2}}+{\frac {C(u,1)+C(u-1,1)}{2}}\Delta y_{0}+C(u,2){\frac {\Delta ^{2}y_{-1}+\Delta ^{2}y_{0}}{2}}+\cdots \\&={\frac {y_{0}+y_{1}}{2}}+\left(u-{\frac {1}{2}}\right)\Delta y_{0}+{\frac {u(u-1)}{2}}{\frac {\Delta ^{2}y_{-1}+\Delta ^{2}y_{0}}{2}}+{\frac {\left(u-{\frac {1}{2}}\right)u\left(u-1\right)}{3!}}\Delta ^{3}y_{0}+{\frac {(u+1)u(u-1)(u-2)}{4!}}{\frac {\Delta ^{4}y_{-1}+\Delta ^{4}y_{-2}}{2}}+\cdots \\\end{aligned}}}$

방데르몽드 알고리즘

위 두 번째 증명에 나오는 방데르몽드 행렬은 조건수가 클 수 있으며,^[5] 이로 인해 가우스 소거법을 사용하여 연립 방정식을 풀 경우 계수 a_i를 계산하는 데 큰 오차가 발생할 수 있다.

따라서 여러 저자들이 가우스 소거법에 필요한 O(n³) 연산 대신 O(n²) 연산으로 수치적으로 안정적인 해를 계산하기 위해 방데르몽드 행렬의 구조를 활용하는 알고리즘을 제안했다.^[6][7][8] 이 방법들은 먼저 다항식의 뉴턴 보간을 구성한 다음 이를 단항식 형식으로 변환하는 방식에 의존한다.

비방데르몽드 알고리즘

차수 n의 다항식 벡터 공간 P(n)에서 보간 다항식 p(x)를 찾기 위해, P(n)에 대한 일반적인 단항식 기저를 사용하고 가우스 소거법으로 방데르몽드 행렬을 역행렬화하여 계산 비용이 O(n³) 연산이 된다. 이 알고리즘을 개선하려면, P(n)에 대한 더 편리한 기저를 사용하면 계수 계산을 단순화할 수 있으며, 그 후에는 이를 다시 단항식 기저로 변환해야 한다.

한 가지 방법은 보간 다항식을 뉴턴 형식(즉, 뉴턴 기저 사용)으로 작성하고, 네빌 알고리즘과 같이 나눗셈 차분 방법을 사용하여 계수를 구성하는 것이다. 비용은 O(n²) 연산이다. 게다가, 자료 집합에 추가 점이 추가되는 경우 O(n)의 추가 작업만 필요하며, 다른 방법의 경우 전체 계산을 다시 수행해야 한다.

또 다른 방법은 p(x)의 계수를 계산하는 것이 아니라 원래 자료 집합에 없는 점 x = a에서의 단일 값 p(a)만 계산하는 것이 목적일 때 선호된다. 라그랑주 형식은 O(n²)의 복잡도로 p(a) 값을 계산한다.^[9]

베른슈타인의 바이어슈트라스 근사 정리의 구성적 증명에서 베른슈타인 형식이 사용되었으며, 베지에 곡선 형태로 컴퓨터 그래픽스에서 큰 중요성을 얻었다.

값의 선형 결합으로서의 보간

서로 다른 위치 ${\displaystyle x_{j}}$를 가진 (위치, 값) 자료점 집합 ${\displaystyle (x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{n},y_{n})}$이 주어졌을 때, 보간 다항식 ${\displaystyle y(x)}$는 ${\displaystyle x_{j}}$에 따라 ${\displaystyle x}$의 다항식인 계수를 사용하여 값 ${\displaystyle y_{j}}$의 선형 결합으로 간주될 수 있다. 예를 들어, 라그랑주 형식의 보간 다항식은 선형 결합이다. $${\displaystyle y(x):=\sum _{j=0}^{k}y_{j}c_{j}(x)}$$ 각 계수 ${\displaystyle c_{j}(x)}$는 주어진 위치 ${\displaystyle x_{j}}$에 대한 해당 라그랑주 기저 다항식으로 주어진다. $${\displaystyle c_{j}(x)=L_{j}(x_{0},\ldots ,x_{n};x)=\prod _{0\leq i\leq n \atop i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\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_{n})}{(x_{j}-x_{n})}}.}$$

계수는 값 ${\displaystyle y_{j}}$가 아니라 위치 ${\displaystyle x_{j}}$에만 의존하므로, 동일한 위치에서 두 번째 자료점 집합 ${\displaystyle (x_{0},v_{0}),\ldots ,(x_{n},v_{n})}$에 대한 보간 다항식을 찾기 위해 동일한 계수를 사용할 수 있다. $${\displaystyle v(x):=\sum _{j=0}^{k}v_{j}c_{j}(x).}$$

더 나아가, 계수 ${\displaystyle c_{j}(x)}$는 위치 사이의 상대적 간격 ${\displaystyle x_{i}-x_{j}}$에만 의존한다. 따라서, 점들이 새로운 변수 ${\displaystyle t=ax+b}$ (아핀 변환 of ${\displaystyle x}$, ${\displaystyle x={\tfrac {t-b}{a}}}$에 의해 역변환됨)로 주어지는 세 번째 자료 집합이 주어졌을 때: $${\displaystyle (t_{0},w_{0}),\ldots ,(t_{j},w_{j})\ldots ,(t_{n},w_{n})\qquad {\text{단}}\qquad t_{j}=ax_{j}+b,}$$

이전 계수 다항식의 변환된 버전을 사용할 수 있다:

${\displaystyle {\tilde {c}}_{j}(t):=c_{j}({\tfrac {t-b}{a}})=c_{j}(x),}$

그리고 보간 다항식을 다음과 같이 작성할 수 있다:

${\textstyle w(t):=\sum _{j=0}^{k}w_{j}{\tilde {c}}_{j}(t).}$

자료점 ${\displaystyle (x_{j},y_{j})}$는 종종 등간격 위치를 가지며, 이는 아핀 변환에 의해 ${\displaystyle x_{j}=j}$로 정규화될 수 있다. 예를 들어, 자료점

${\displaystyle (0,y_{0}),(1,y_{1}),(2,y_{2})}$.

라그랑주 형식의 보간 다항식은 선형 결합이다. $${\displaystyle {\begin{aligned}y(x):=\sum _{j=0}^{2}y_{j}c_{j}(x)&=y_{0}{\frac {(x-1)(x-2)}{(0-1)(0-2)}}+y_{1}{\frac {(x-0)(x-2)}{(1-0)(1-2)}}+y_{2}{\frac {(x-0)(x-1)}{(2-0)(2-1)}}\\&={\tfrac {1}{2}}y_{0}(x-1)(x-2)-y_{1}(x-0)(x-2)+{\tfrac {1}{2}}y_{2}(x-0)(x-1).\end{aligned}}}$$

예를 들어, ${\displaystyle y(3)=y_{3}=y_{0}-3y_{1}+3y_{2}}$ 이고 ${\displaystyle y(1.5)=y_{1.5}={\tfrac {1}{8}}(-y_{0}+6y_{1}+3y_{2})}$이다.

등간격 점의 경우 유한 차분법으로도 처리할 수 있다. 값의 수열 ${\displaystyle v=\{v_{j}\}_{j=0}^{\infty }}$의 첫 번째 차분은 ${\displaystyle u_{j}=v_{j+1}-v_{j}}$로 정의되는 수열 ${\displaystyle \Delta v=u=\{u_{j}\}_{j=0}^{\infty }}$이다. 이 연산을 반복하면 n차 차분 연산 ${\displaystyle \Delta ^{n}v=u}$가 되며, 이는 다음과 같이 명시적으로 정의된다. $${\displaystyle u_{j}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}v_{j+k},}$$ 여기서 계수는 부호가 있는 파스칼 삼각형, 즉 이항 변환 계수 삼각형을 형성한다.

								1									행 n = 0
							1		−1								행 n = 1 또는 d = 0
						1		−2		1							행 n = 2 또는 d = 1
					1		−3		3		−1						행 n = 3 또는 d = 2
				1		−4		6		−4		1					행 n = 4 또는 d = 3
			1		−5		10		−10		5		−1				행 n = 5 또는 d = 4
		1		−6		15		−20		15		−6		1			행 n = 6 또는 d = 5
	1		−7		21		−35		35		−21		7		−1		행 n = 7 또는 d = 6

차수 d의 다항식 ${\displaystyle y(x)}$는 양의 정수점에서 값의 수열 ${\displaystyle y_{j}=y(j)}$를 정의하며, 이 수열의 ${\displaystyle (d+1)^{\text{th}}}$ 차분은 항상 0이다:

${\displaystyle \Delta ^{d+1}y=0}$.

따라서 등간격 점에서 ${\displaystyle y_{0},\ldots ,y_{n}}$ 값이 주어지고 ${\displaystyle n=d+1}$이면 다음이 성립한다: $${\displaystyle (-1)^{n}y_{0}+(-1)^{n-1}{\binom {n}{1}}y_{1}+\cdots -{\binom {n}{n-1}}y_{n-1}+y_{n}=0.}$$ 예를 들어, 이차 다항식 ${\displaystyle y(x)}$의 등간격 4개 자료점 ${\displaystyle y_{0},y_{1},y_{2},y_{3}}$은 ${\displaystyle 0=-y_{0}+3y_{1}-3y_{2}+y_{3}}$를 만족하며, ${\displaystyle y_{3}}$에 대해 풀면 위에서 라그랑주 방법을 사용하여 얻은 것과 동일한 보간 방정식을 얻는다.

보간 오차: 라그랑주 나머지 공식

주어진 함수 f를 노드 x₀,..., x_n에서 차수 n의 다항식 ${\displaystyle p_{n}}$으로 보간할 때 다음과 같은 오차를 얻는다. $${\displaystyle f(x)-p_{n}(x)=f[x_{0},\ldots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})}$$ 여기서 ${\textstyle f[x_{0},\ldots ,x_{n},x]}$는 자료점

${\displaystyle (x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n})),(x,f(x))}$

의 (n+1)차 나눗셈 차분이다. 더 나아가, 닫힌 구간 ${\displaystyle I}$에서 n + 1번 연속 미분 가능하며, ${\displaystyle n+1}$개의 서로 다른 점 ${\displaystyle x_{0},\ldots ,x_{n}\in I}$에서 f를 보간하는 차수가 최대 n인 다항식 ${\displaystyle p_{n}(x)}$에 대해 라그랑주 나머지 형태의 오차가 존재한다. 각 ${\displaystyle x\in I}$에 대해 다음을 만족하는 ${\displaystyle \xi \in I}$가 존재한다. $${\displaystyle f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}).}$$

이 오차 한계는 곱 ${\textstyle \left|\prod (x-x_{i})\right|}$을 최소화하도록 보간점 x_i를 선택할 것을 제안하며, 이는 체비쇼프 노드로 달성된다.

라그랑주 나머지 증명

오차 항을 ${\textstyle R_{n}(x)=f(x)-p_{n}(x)}$로 설정하고, 보조 함수를 다음과 같이 정의한다: $${\displaystyle Y(t)=R_{n}(t)-{\frac {R_{n}(x)}{W(x)}}W(t)\qquad {\text{여기서}}\qquad W(t)=\prod _{i=0}^{n}(t-x_{i}).}$$ 따라서: $${\displaystyle Y^{(n+1)}(t)=R_{n}^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!}$$

그러나 ${\displaystyle p_{n}(x)}$는 차수가 최대 n인 다항식이므로 ${\textstyle R_{n}^{(n+1)}(t)=f^{(n+1)}(t)}$이고, 다음과 같다: $${\displaystyle Y^{(n+1)}(t)=f^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!}$$

이제 x_i는 ${\displaystyle R_{n}(t)}$와 ${\displaystyle W(t)}$의 근이므로 ${\displaystyle Y(x)=Y(x_{j})=0}$이며, 이는 Y가 적어도 n + 2개의 근을 가짐을 의미한다. 롤의 정리에 따라, ${\displaystyle Y^{\prime }(t)}$는 적어도 n + 1개의 근을 가지며, 반복적으로 ${\displaystyle Y^{(n+1)}(t)}$는 구간 I에 적어도 하나의 근 ξ를 가진다. 따라서: $${\displaystyle Y^{(n+1)}(\xi )=f^{(n+1)}(\xi )-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!=0}$$

그리고: $${\displaystyle R_{n}(x)=f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}).}$$

이것은 테일러 정리의 라그랑주 나머지 항 뒤에 있는 추론과 유사하다. 사실, 테일러 나머지는 모든 보간 노드 x_i가 동일한 경우 보간 오차의 특별한 경우이다.^[10] ${\displaystyle x=x_{i}}$ (모든 i에 대해)일 때 오차가 0이 된다는 점에 유의해야 한다. 따라서 최대 오차는 두 연속 노드 사이의 구간 내 어느 한 점에서 발생한다.

등간격 구간

등간격 보간 노드 ${\displaystyle x_{i}=a+ih}$ (${\displaystyle i=0,1,\ldots ,n,}$) 및 ${\displaystyle h=(b-a)/n}$인 경우, 보간 오차 공식의 곱 항은 다음과 같이 제한될 수 있다.^[11] $${\displaystyle \left|\prod _{i=0}^{n}(x-x_{i})\right|=\prod _{i=0}^{n}\left|x-x_{i}\right|\leq {\frac {n!}{4}}h^{n+1}.}$$

따라서 오차 한계는 다음과 같이 주어질 수 있다. $${\displaystyle \left|R_{n}(x)\right|\leq {\frac {h^{n+1}}{4(n+1)}}\max _{\xi \in [a,b]}\left|f^{(n+1)}(\xi )\right|}$$

그러나 이것은 ${\displaystyle f^{(n+1)}(\xi )}$가 ${\displaystyle h^{n+1}}$에 의해 지배된다는 것을 가정한다. 즉, ${\displaystyle f^{(n+1)}(\xi )h^{n+1}\ll 1}$이다. 여러 경우에 이것은 사실이 아니며 오차는 실제로 n → ∞일 때 증가한다(룽게 현상 참조). 이 문제는 수렴 특성 섹션에서 다룬다.

르베그 상수

 이 부분의 본문은 르베그 상수입니다.

보간 노드 x₀, ..., x_n과 모든 보간 노드를 포함하는 구간 [a, b]를 고정한다. 보간 과정은 함수 f를 다항식 p로 매핑한다. 이것은 [a, b]의 모든 연속 함수 공간 C([a, b])에서 자기 자신으로의 매핑 X를 정의한다. 매핑 X는 선형이며 차수 n 이하의 다항식 부분 공간 ${\displaystyle P(n)}$에 대한 사영작용소이다.

르베그 상수 L은 X의 작용소 노름으로 정의된다. 다음이 성립한다(르베그 보조정리의 특별한 경우): $${\displaystyle \left\|f-X(f)\right\|\leq (L+1)\left\|f-p^{*}\right\|.}$$

다시 말해, 보간 다항식은 가능한 최상의 근사치보다 최대 (L + 1)배 더 나쁘다. 이는 L을 작게 만드는 보간 노드 집합을 찾는 것이 좋다는 것을 시사한다. 특히, 체비쇼프 노드의 경우 다음이 성립한다. $${\displaystyle L\leq {\frac {2}{\pi }}\log(n+1)+1.}$$

등간격 노드의 경우 n에 대한 성장이 기하급수적이기 때문에 체비쇼프 노드가 다항식 보간에 매우 좋은 선택이라는 결론을 다시 내린다. 그러나 이 노드들은 최적이 아니다.

수렴 특성

어떤 종류의 함수와 어떤 보간 노드에 대해 보간 다항식의 수열이 n → ∞일 때 보간되는 함수로 수렴하는지 묻는 것은 자연스러운 일이다. 수렴은 점별, 균등 또는 특정 적분 노름 등 다양한 방식으로 이해될 수 있다.

등간격 노드의 경우 상황이 다소 좋지 않은데, 무한히 미분 가능한 함수에 대해서도 균등 수렴이 보장되지 않는다. 카를 룽게의 고전적인 예시는 구간 [−5, 5]에서 함수 f(x) = 1 / (1 + x²)이다. 보간 오차 || f − p_n||_∞는 n → ∞일 때 무한히 증가한다. 또 다른 예시는 구간 [−1, 1]에서 함수 f(x) = |x|인데, 이 경우 보간 다항식은 x = ±1, 0 세 점을 제외하고는 점별로도 수렴하지 않는다.^[12]

더 나은 수렴 특성은 다른 보간 노드를 선택하여 얻을 수 있다고 생각할 수 있다. 다음 결과는 다소 고무적인 답변을 제공하는 것처럼 보인다.

정리—구간 [a,b]에서 연속인 임의의 함수 f(x)에 대해 보간 다항식의 수열 ${\displaystyle p_{n}(x)}$가 [a,b]에서 f(x)로 균등하게 수렴하는 노드표가 존재한다.

증명

최적 근사 다항식의 수열 ${\displaystyle p_{n}^{*}(x)}$가 f(x)로 균등하게 수렴하는 것은 명백하다(바이어슈트라스 근사 정리 때문). 이제 각 ${\displaystyle p_{n}^{*}(x)}$가 특정 노드에서의 보간을 통해 얻어질 수 있음을 보여야 한다. 그러나 이는 등진동 정리에서 알려진 최적 근사 다항식의 특별한 속성 때문에 사실이다. 특히, 이러한 다항식은 f(x)와 적어도 n + 1번 교차해야 함을 알고 있다. 교차점을 보간 노드로 선택하면 최적 근사 다항식과 일치하는 보간 다항식을 얻는다.

그러나 이 방법의 단점은 새로운 함수 f(x)마다 보간 노드를 새로 계산해야 한다는 것이고, 이 알고리즘은 수치적으로 구현하기 어렵다는 것이다. 보간 다항식의 수열이 임의의 연속 함수 f(x)로 수렴하는 단일 노드표가 존재할까? 안타깝게도 답은 부정적이다.

정리—어떤 노드표에 대해서도 [a, b] 구간에서 보간 다항식의 수열이 발산하는 연속 함수 f(x)가 존재한다.^[13]

이 증명은 본질적으로 위에 정의된 르베그 상수의 하한 추정치를 사용하며, 르베그 상수는 X_n의 작용소 노름이다(여기서 X_n은 Π_n에 대한 사영 연산자이다). 이제 우리는 다음과 같은 노드 표를 찾는다.

$${\displaystyle \lim _{n\to \infty }X_{n}f=f,{\text{ for every }}f\in C([a,b]).}$$

바나흐-슈타인하우스 정리에 따르면, 이는 X_n의 노름이 균등하게 유계일 때만 가능하며, 이는 다음을 알고 있으므로 사실일 수 없다.

$${\displaystyle \|X_{n}\|\geq {\tfrac {2}{\pi }}\log(n+1)+C.}$$

예를 들어, 등간격 점이 보간 노드로 선택되면 룽게 현상의 함수는 그러한 보간의 발산을 보여준다. 이 함수는 [−1, 1]에서 연속일 뿐만 아니라 무한히 미분 가능함에 유의해야 한다. 그러나 더 나은 체비쇼프 노드의 경우, 다음 결과 때문에 그러한 예시를 찾기가 훨씬 더 어렵다.

정리—[−1, 1]에서 모든 절대 연속 함수에 대해 체비쇼프 노드에서 구성된 보간 다항식의 수열은 f(x)로 균등하게 수렴한다.^[14]

관련 개념

룽게 현상은 n의 값이 높을 때 보간 다항식이 자료점 사이에서 심하게 진동할 수 있음을 보여준다. 이 문제는 일반적으로 스플라인 보간을 사용하여 해결된다. 여기서 보간 함수는 다항식이 아니라 스플라인 곡선: 더 낮은 차수의 여러 다항식의 연결이다.

주기함수를 조화 함수로 보간하는 것은 푸리에 변환을 통해 이루어진다. 이것은 조화 기저 함수를 사용한 다항식 보간의 한 형태로 볼 수 있으며, 삼각 보간 및 삼각 다항식을 참조하라.

에르미트 보간법 문제는 노드에서 다항식 p의 값뿐만 아니라 주어진 차수까지의 모든 도함수도 주어지는 경우이다. 이것은 동시 다항식 합동 시스템과 동일하며, 다항식에 대한 중국인의 나머지 정리를 통해 해결될 수 있다. 버크호프 보간법은 0부터 k까지의 모든 차수가 아닌 일부 차수의 도함수만 지정되는 더 일반적인 경우이다.

미분 및 적분 방정식의 해를 위한 콜로케이션 방법은 다항식 보간을 기반으로 한다.

유리 함수 모델링 기술은 다항 함수들의 비를 고려하는 일반화이다.

마지막으로, 고차원 다변수 보간법이 있다.

같이 보기

• 뉴턴 급수
• 다항 회귀
• 스플라인 스무딩

내용주

1. 이는 다항식 나눗셈에 대한 인수 정리에서 비롯된다.