다항식 보간법

수치해석학에서 **다항식 보간법**(Polynomial interpolation)은 주어진 자료 집합의 점들을 통과하는 가장 낮은 차수의 다항식으로 보간법을 하는 것이다. 서로 다른 n + 1개의 자료점 (x_0,y_0), \ldots, (x_n,y_n)이 주어졌을 때, 다항 함수 p(x)=a_0+a_1x+\cdots+a_nx^n가 각 j\in\\{0,1,\dotsc,n\\}에 대해 p(x_j)=y_j를 만족하면 자료를 **보간**한다고 말한다. 이러한 다항식은 항상 유일하며, 일반적으로 라그랑주 다항식과 뉴턴 다항식의 두 가지 명시적 공식으로 주어진다.
# 응용
보간 다항식의 원래 용도는 자연로그 및 삼각 함수와 같은 중요한 초월 함수의 값을 근사하는 것이었다. 몇 개의 정확하게 계산된 자료점으로부터, 해당 보간 다항식은 임의의 근처 점에서 함수를 근사할 것이다. 다항식 보간법은 또한 수치 적분 (심프슨 공식) 및 수치 상미분 방정식 (다중 격자법) 알고리즘의 기초를 이룬다. 컴퓨터 그래픽스에서는 다항식을 사용하여 몇 가지 지정된 점(예: 타이포그래피의 글자 모양)이 주어졌을 때 복잡한 평면 곡선을 근사할 수 있다. 이는 일반적으로 베지에 곡선을 사용하여 수행되는데, 이는 보간 다항식의 간단한 일반화이다(지정된 점뿐만 아니라 지정된 접선도 가짐). 수치해석학에서 다항식 보간법은 카라추바 곱셈 및 톰-쿡 알고리즘과 같은 이차 미만의 곱셈 및 제곱을 수행하는 데 필수적이다. 여기서 곱 다항식의 점을 통한 보간은 필요한 특정 곱을 산출한다. 예를 들어, a = f(x) = a0x0 \+ a1x1 \+ ··· 및 b = g(x) = b0x0 \+ b1x1 \+ ···가 주어지면, 곱 ab는 W(x) = f(x)g(x)의 특정 값이다. W(x)의 점은 작은 x 값에서 쉽게 찾을 수 있으며, 이러한 점을 기반으로 한 보간은 W(x)의 항과 특정 곱 ab를 산출한다. 카라추바 곱셈에서 공식화된 바와 같이, 이 기술은 겸손한 크기의 입력에 대해서도, 특히 병렬 하드웨어에서 이차 곱셈보다 상당히 빠르다. 컴퓨터 과학에서 다항식 보간법은 또한 다자간 보안 컴퓨팅 및 비밀 공유 알고리즘으로 이어진다.
# 보간 정리
서로 다른 x_j가 없는 n+1개의 이변량 자료점 (x_0,y_0),\dotsc,(x_n,y_n) \in \R^2에 대해, 이 점들을 보간하는 차수가 최대 n인 유일한 다항식 p(x)가 존재한다. 즉, p(x_0)=y_0, \ldots, p(x_n)=y_n이다.chapter=9.2 - Interpolation 등가적으로, 보간 노드 x_j의 고정된 선택에 대해, 다항식 보간은 실수 값의 (n+1)튜플 (y_0,\ldots,y_n)\in \R^{n+1}과 차수가 최대 n인 실수 다항식의 벡터 공간 P(n) 사이의 선형 전단사 함수 L_n을 정의한다. L_n : \mathbb{R}^{n+1} \stackrel{\sim}{\longrightarrow}\, P(n). 이것은 일종의 유일해성 정리이다. 이 정리는 실수 \R 대신 임의의 무한 체 (예: 유리수 또는 복소수)에 대해서도 유효하다.
## 첫 번째 증명
라그랑주 기저 함수 L_0(x),\ldots,L_n(x)를 다음과 같이 고려한다: 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)}. L_j(x)는 차수 n의 다항식이고, 각 j\neq k에 대해 L_j(x_k)=0이며, L_k(x_k)=1임을 알 수 있다. 따라서 선형 결합: p(x) = \sum_{j=0}^n y_j L_j(x) 는 p(x_k)=\sum_j y_j \,L_j(x_k) = y_k 를 가지므로, p(x)는 차수 n의 보간 다항식이다. 유일성을 증명하기 위해, 차수가 최대 n인 또 다른 보간 다항식 q(x)가 존재하여 모든 k=0,\dotsc,n에 대해 p(x_k)=q(x_k)라고 가정한다. 그러면 p(x)-q(x)는 n+1개의 서로 다른 영점( x_k들)을 갖는 차수가 최대 n인 다항식이다. 그러나 차수가 최대 n인 영이 아닌 다항식은 최대 n개의 영점을 가질 수 없으므로,이는 다항식 나눗셈에 대한 인수 정리에서 비롯된다. p(x)-q(x)는 영 다항식이어야 한다. 즉, p(x)=q(x)이다.location=Hoboken, NJ
## 두 번째 증명
보간 다항식을 다음과 같은 형태로 작성한다: 1 이를 보간 방정식 p(x_j) = y_j에 대입하면, 계수 a_j에 대한 연립 일차 방정식을 얻는다. 이를 행렬-벡터 형식으로 나타내면 다음과 같은 행렬 곱셈이 된다: \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}. 보간 다항식 p(x)는 위 행렬 방정식 X \cdot A = Y의 해 A = (a_n,\ldots,a_0)에 해당한다. 왼쪽의 행렬 X는 방데르몽드 행렬이며, 그 행렬식은 \textstyle \det(X) = \prod_{1 \le i \tilde c_j(t) := c_j(\tfrac{t-b}{a}) = c_j(x),

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

> w(t) := \sum_{j=0}^{k} w_j \tilde c_j(t).

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

> (0,y_0), (1,y_1), (2,y_2).

라그랑주 형식의 보간 다항식은 선형 결합이다. \begin{align} 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)} \\\ &= \tfrac12 y_0 (x-1)(x-2) - y_1 (x-0)(x-2) + \tfrac12 y_2 (x-0)(x-1). \end{align} 예를 들어, y(3) = y_3 = y_0 - 3y_1 + 3y_2 이고 y(1.5) = y_{1.5} = \tfrac18 (-y_0 + 6y_1 + 3y_2)이다. 등간격 점의 경우 유한 차분법으로도 처리할 수 있다. 값의 수열 v=\\{v_j\\}_{j=0}^\infty의 첫 번째 차분은 u_j = v_{j+1}-v_j 로 정의되는 수열 \Delta v = u = \\{u_j\\}_{j=0}^\infty 이다. 이 연산을 반복하면 n차 차분 연산 \Delta^n v = u가 되며, 이는 다음과 같이 명시적으로 정의된다. u_j = \sum_{k=0}^n (-1)^{n-k} {n\choose k} v_{j+k}, 여기서 계수는 부호가 있는 파스칼 삼각형, 즉 이항 변환 계수 삼각형을 형성한다. {| class="wikitable" | colspan="8" | || colspan="2"|1 || colspan="7" | || |행 n = 0 |- | colspan="7" | || colspan="2"|1 || colspan="2"|−1 || colspan="6" | || |행 n = 1 또는 d = 0 |- | colspan="6" | || colspan="2"|1 || colspan="2"|−2 || colspan="2"|1 || colspan="5" | || |행 n = 2 또는 d = 1 |- | colspan="5" | || colspan="2"|1 || colspan="2"|−3 || colspan="2"|3 || colspan="2"|−1 || colspan="4" | || |행 n = 3 또는 d = 2 |- | colspan="4" | || colspan="2"|1 || colspan="2"|−4 || colspan="2"|6 || colspan="2"|−4 || colspan="2"|1 || colspan="3" | || |행 n = 4 또는 d = 3 |- | colspan="3" | || colspan="2"|1 || colspan="2"|−5 || colspan="2"|10 || colspan="2"|−10 || colspan="2"|5 || colspan="2"|−1 || colspan="2" | || |행 n = 5 또는 d = 4 |- | colspan="2" | || colspan="2"|1 || colspan="2"|−6 || colspan="2"|15 || colspan="2"|−20 || colspan="2"|15 || colspan="2"|−6 || colspan="2"|1 || | || |행 n = 6 또는 d = 5 |- | colspan="1" | || colspan="2"|1 || colspan="2"|−7 || colspan="2"|21 || colspan="2"|−35 || colspan="2"|35 || colspan="2"|−21 || colspan="2"|7 || colspan="2"|−1 || |행 n = 7 또는 d = 6 |- | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |} 차수 d의 다항식 y(x)는 양의 정수점에서 값의 수열 y_j = y(j)를 정의하며, 이 수열의 (d+1)^{\text{th 차분은 항상 0이다:

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

따라서 등간격 점에서 y_0,\ldots,y_n 값이 주어지고 n=d+1 이면 다음이 성립한다: (-1)^n y_0 + (-1)^{n-1} \binom{n}{1} y_1 + \cdots - \binom n{n-1} y_{n-1} + y_n= 0. 예를 들어, 이차 다항식 y(x)의 등간격 4개 자료점 y_0,y_1,y_2,y_3 은 0 = -y_0 + 3y_1 - 3y_2 + y_3를 만족하며, y_3에 대해 풀면 위에서 라그랑주 방법을 사용하여 얻은 것과 동일한 보간 방정식을 얻는다.
# 보간 오차: 라그랑주 나머지 공식
주어진 함수 f를 노드 x0,..., xn에서 차수 n의 다항식 p_n으로 보간할 때 다음과 같은 오차를 얻는다. f(x) - p_n(x) = f[x_0,\ldots,x_n,x] \prod_{i=0}^n (x-x_i) 여기서 f[x_0,\ldots,x_n,x]는 자료점

> (x_0,f(x_0)),\ldots,(x_n,f(x_n)),(x,f(x))

의 (n+1)차 나눗셈 차분이다. 더 나아가, 닫힌 구간 I에서 n + 1번 연속 미분 가능하며, n+1개의 서로 다른 점 x_0,\ldots,x_n\in I에서 f를 보간하는 차수가 최대 n인 다항식 p_n(x)에 대해 라그랑주 나머지 형태의 오차가 존재한다. 각 x\in I에 대해 다음을 만족하는 \xi\in I가 존재한다. f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i). 이 오차 한계는 곱 \left | \prod (x - x_i) \right |을 최소화하도록 보간점 xi를 선택할 것을 제안하며, 이는 체비쇼프 노드로 달성된다.
## 라그랑주 나머지 증명
오차 항을 R_n(x) = f(x) - p_n(x) 로 설정하고, 보조 함수를 다음과 같이 정의한다: 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). 따라서: Y^{(n+1)}(t) = R_n^{(n+1)}(t) - \frac{R_n(x)}{W(x)} \ (n+1)! 그러나 p_n(x)는 차수가 최대 n인 다항식이므로 R_n^{(n+1)}(t) = f^{(n+1)}(t) 이고, 다음과 같다: Y^{(n+1)}(t) = f^{(n+1)}(t) - \frac{R_n(x)}{W(x)} \ (n+1)! 이제 xi는 R_n(t)와 W(t)의 근이므로 Y(x)=Y(x_j)=0 이며, 이는 Y가 적어도 n + 2개의 근을 가짐을 의미한다. 롤의 정리에 따라, Y^\prime(t)는 적어도 n + 1개의 근을 가지며, 반복적으로 Y^{(n+1)}(t)는 구간 I에 적어도 하나의 근 ξ를 가진다. 따라서: Y^{(n+1)}(\xi) = f^{(n+1)}(\xi) - \frac{R_n(x)}{W(x)} \ (n+1)! = 0 그리고: R_n(x) = f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i) . 이것은 테일러 정리의 라그랑주 나머지 항 뒤에 있는 추론과 유사하다. 사실, 테일러 나머지는 모든 보간 노드 xi가 동일한 경우 보간 오차의 특별한 경우이다.title=Errors in Polynomial Interpolation x = x_i (모든 i에 대해)일 때 오차가 0이 된다는 점에 유의해야 한다. 따라서 최대 오차는 두 연속 노드 사이의 구간 내 어느 한 점에서 발생한다.
## 등간격 구간
등간격 보간 노드 x_i = a + ih (i=0,1,\ldots,n,) 및 h = (b-a)/n인 경우, 보간 오차 공식의 곱 항은 다음과 같이 제한될 수 있다.title=Notes on Polynomial Interpolation \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}. 따라서 오차 한계는 다음과 같이 주어질 수 있다. \left|R_n(x)\right| \leq \frac{h^{n+1{4(n+1)} \max_{\xi\in[a,b]} \left|f^{(n+1)}(\xi)\right| 그러나 이것은 f^{(n+1)}(\xi)가 h^{n+1}에 의해 지배된다는 것을 가정한다. 즉, f^{(n+1)}(\xi) h^{n+1} \ll 1이다. 여러 경우에 이것은 사실이 아니며 오차는 실제로 n → ∞일 때 증가한다(룽게 현상 참조). 이 문제는 수렴 특성 섹션에서 다룬다.
# 르베그 상수
르베그 상수 보간 노드 x0, ..., xn과 모든 보간 노드를 포함하는 구간 [a, b]를 고정한다. 보간 과정은 함수 f를 다항식 p로 매핑한다. 이것은 [a, b]의 모든 연속 함수 공간 C([a, b])에서 자기 자신으로의 매핑 X를 정의한다. 매핑 X는 선형이며 차수 n 이하의 다항식 부분 공간 P(n) 에 대한 사영작용소이다. 르베그 상수 L은 X의 작용소 노름으로 정의된다. 다음이 성립한다(르베그 보조정리의 특별한 경우): \left\|f-X(f)\right\| \le (L+1) \left\|f-p^*\right\|. 다시 말해, 보간 다항식은 가능한 최상의 근사치보다 최대 (L + 1)배 더 나쁘다. 이는 L을 작게 만드는 보간 노드 집합을 찾는 것이 좋다는 것을 시사한다. 특히, 체비쇼프 노드의 경우 다음이 성립한다. L \le \frac2\pi \log(n+1) + 1. 등간격 노드의 경우 n에 대한 성장이 기하급수적이기 때문에 체비쇼프 노드가 다항식 보간에 매우 좋은 선택이라는 결론을 다시 내린다. 그러나 이 노드들은 최적이 아니다.
# 수렴 특성
어떤 종류의 함수와 어떤 보간 노드에 대해 보간 다항식의 수열이 n → ∞일 때 보간되는 함수로 수렴하는지 묻는 것은 자연스러운 일이다. 수렴은 점별, 균등 또는 특정 적분 노름 등 다양한 방식으로 이해될 수 있다. 등간격 노드의 경우 상황이 다소 좋지 않은데, 무한히 미분 가능한 함수에 대해서도 균등 수렴이 보장되지 않는다. 카를 룽게의 고전적인 예시는 구간 [−5, 5]에서 함수 f(x) = 1 / (1 + x2)이다. 보간 오차 !! f − pn!!∞는 n → ∞일 때 무한히 증가한다. 또 다른 예시는 구간 [−1, 1]에서 함수 f(x) = |x|인데, 이 경우 보간 다항식은 x = ±1, 0 세 점을 제외하고는 점별로도 수렴하지 않는다.p=21은 마지막 예시를 1912에 귀속시킨다. 더 나은 수렴 특성은 다른 보간 노드를 선택하여 얻을 수 있다고 생각할 수 있다. 다음 결과는 다소 고무적인 답변을 제공하는 것처럼 보인다. math_statement = 구간 [a,b]에서 연속인 임의의 함수 f(x)에 대해 보간 다항식의 수열 p_n(x)가 [a,b]에서 f(x)로 균등하게 수렴하는 노드표가 존재한다. n + 1번 교차해야 함을 알고 있다. 교차점을 보간 노드로 선택하면 최적 근사 다항식과 일치하는 보간 다항식을 얻는다. 그러나 이 방법의 단점은 새로운 함수 f(x)마다 보간 노드를 새로 계산해야 한다는 것이고, 이 알고리즘은 수치적으로 구현하기 어렵다는 것이다. 보간 다항식의 수열이 임의의 연속 함수 f(x)로 수렴하는 단일 노드표가 존재할까? 안타깝게도 답은 부정적이다. 1914에 귀속시킨다. 이 증명은 본질적으로 위에 정의된 르베그 상수의 하한 추정치를 사용하며, 르베그 상수는 Xn의 작용소 노름이다(여기서 Xn은 Πn에 대한 사영 연산자이다). 이제 우리는 다음과 같은 노드 표를 찾는다. \lim_{n \to \infty} X_n f = f,\text{ for every }f \in C([a,b]). 바나흐-슈타인하우스 정리에 따르면, 이는 Xn의 노름이 균등하게 유계일 때만 가능하며, 이는 다음을 알고 있으므로 사실일 수 없다. \|X_n\|\geq \tfrac{2}{\pi} \log(n+1)+C. 예를 들어, 등간격 점이 보간 노드로 선택되면 룽게 현상의 함수는 그러한 보간의 발산을 보여준다. 이 함수는 [−1, 1]에서 연속일 뿐만 아니라 무한히 미분 가능함에 유의해야 한다. 그러나 더 나은 체비쇼프 노드의 경우, 다음 결과 때문에 그러한 예시를 찾기가 훨씬 더 어렵다. url=https://books.google.com/books?id=tCMwAAAAMAAJ MR 18-32.
# 관련 개념
룽게 현상은 n의 값이 높을 때 보간 다항식이 자료점 사이에서 심하게 진동할 수 있음을 보여준다. 이 문제는 일반적으로 스플라인 보간을 사용하여 해결된다. 여기서 보간 함수는 다항식이 아니라 스플라인 곡선: 더 낮은 차수의 여러 다항식의 연결이다. 주기함수를 조화 함수로 보간하는 것은 푸리에 변환을 통해 이루어진다. 이것은 조화 기저 함수를 사용한 다항식 보간의 한 형태로 볼 수 있으며, 삼각 보간 및 삼각 다항식을 참조하라. 에르미트 보간법 문제는 노드에서 다항식 p의 값뿐만 아니라 주어진 차수까지의 모든 도함수도 주어지는 경우이다. 이것은 동시 다항식 합동 시스템과 동일하며, 다항식에 대한 중국인의 나머지 정리를 통해 해결될 수 있다. 버크호프 보간법은 0부터 k까지의 모든 차수가 아닌 일부 차수의 도함수만 지정되는 더 일반적인 경우이다. 미분 및 적분 방정식의 해를 위한 콜로케이션 방법은 다항식 보간을 기반으로 한다. 유리 함수 모델링 기술은 다항 함수들의 비를 고려하는 일반화이다. 마지막으로, 고차원 다변수 보간법이 있다.
# 내용주
Notelist
# 더 읽어보기
* isbn=0-471-50023-2 * pages=111-127 * isbn=0-521-29514-9 * isbn=0-19-850279-6 * isbn=0-521-00794-1 * J. L. Walsh: Interpolation and Approximation by Rational Functions in the Complex Domain, AMS (Colloquium Publications, Vol.20), ISBN 0-8218-1020-0 (1960). Chapter VII:'Interpolation by Polynomials'.