베른슈타인 다항식

date=2016년 6월곡선을 근사하는 베른슈타인 다항식 수학의 수치해석학 분야에서 **베른슈타인 다항식**(Bernstein polynomial)은 선형 결합으로 표현되는 다항식이다. 이 개념은 수학자 세르게이 나타노비치 베른슈타인의 이름을 따서 명명되었다. 이 형태의 다항식은 베른슈타인이 바이어슈트라스 근사 정리의 구성적 증명에서 처음 사용했다. 컴퓨터 그래픽의 등장과 함께, [0, 1] 구간으로 제한된 베른슈타인 다항식은 베지에 곡선의 형태로 중요해졌다. **베른슈타인 형식**(Bernstein form)으로 다항식을 평가하는 수치적으로 안정된 방법은 드 카스텔조 알고리즘이다. 4차 곡선 블렌딩을 위한 베른슈타인 기저 다항식
# 정의

## 베른슈타인 기저 다항식
\ n\ 차의 \ n + 1\ 개의 **베른슈타인 기저 다항식**은 다음과 같이 정의된다: : \ b_{\nu,n}(x)\ \equiv\ \binom{n}{\nu}\ x^{\nu} \left( 1 - x \right)^{n - \nu}\ , ~~ (단, ~~ \nu = 0\ ,\ \ldots\ , n\ ) 여기서 \ \tbinom{n}{\nu}\ 는 이항 계수이다. 예를 들어, \ b_{2,5}(x)\ =\ \tbinom{5}{2}x^2(1-x)^3\ =\ 10x^2(1-x)^3 ~. 1, 2, 3 또는 4 값을 함께 섞기 위한 처음 몇 개의 베른슈타인 기저 다항식은 다음과 같다. : \begin{align} b_{0,0}(x) & = 1\ , \\\ b_{0,1}(x) & = 1 - x\ , & b_{1,1}(x) & = x \\\ b_{0,2}(x) & = (1 - x)^2\ , & b_{1,2}(x) & = 2x(1 - x)\ , & b_{2,2}(x) & = x^2 \\\ b_{0,3}(x) & = (1 - x)^3\ , & b_{1,3}(x) & = 3x(1 - x)^2\ , & b_{2,3}(x) & = 3x^2(1 - x)\ , & b_{3,3}(x) & = x^3 ~. \end{align} : \ n\ 차 베른슈타인 기저 다항식은 실수 계수를 가진 최대 \ n\ 차 다항식의 벡터 공간 \ \Pi_n\ 의 기저를 형성한다.
## 베른슈타인 다항식
베른슈타인 기저 다항식의 선형 결합 :\ B_n(x)\ \equiv\ \sum_{\nu=0}^{n} \beta_{\nu} b_{\nu,n}(x)\ 은 \ n\ 차 **베른슈타인 다항식** 또는 **베른슈타인 형식의 다항식**이라고 불린다.1953 계수 \ \beta_\nu\ 는 **베른슈타인 계수** 또는 **베지에 계수**라고 불린다. 위의 처음 몇 개의 베른슈타인 기저 다항식의 단항식 형태는 다음과 같다. : \begin{align} b_{0,0}(x) & = 1\ , \\\ b_{0,1}(x) & = 1 - 1x\ , & b_{1,1}(x) & = 0 + 1x \\\ b_{0,2}(x) & = 1 - 2x + 1x^2, & b_{1,2}(x) & = 0 + 2x - 2x^2\ , & b_{2,2}(x) & = 0 + 0x + 1x^2 \\\ b_{0,3}(x) & = 1 - 3x + 3x^2 - 1x^3\ , & b_{1,3}(x) & = 0 + 3x - 6x^2 + 3x^3\ , & b_{2,3}(x) & = 0 + 0x + 3x^2 - 3x^3, & b_{3,3}(x) & = 0 + 0x + 0x^2 + 1x^3 ~. \end{align} :
# 성질
베른슈타인 기저 다항식은 다음과 같은 성질을 갖는다. * \ b_{\nu, n}\\!(x) \equiv 0\ , (만약 \ \nu n ~이라면) * \ b_{\nu, n}\\!(x) \ge 0\ (만약 \ x \in [0,\ 1] ~이라면) * \ b_{\nu, n}\\!\left( 1 - x \right) = b_{n - \nu, n}\\!(x) ~. * \ b_{\nu, n}\\!(0) = \delta_{\nu, 0}\ and \ b_{\nu, n}\\!(1) = \delta_{\nu, n}\ (여기서 \ \delta_{i,j}\ 는 크로네커 델타 함수이다: \ \delta_{ij} \equiv \begin{cases} 0 &\text{if } i \neq j\ , \\\ 1 &\text{if } i=j ~. \end{cases}) * \ b_{\nu, n}\\!(x)\ 는 점 \ x = 0\ 에서 \ \nu\ 의 중근을 갖는다 (참고: \ \nu = 0\ 일 때는 0에서 근이 없다). * \ b_{\nu, n}\\!(x)\ 는 점 \ x = 1\ 에서 \ \left( n - \nu \right)\ 의 중근을 갖는다 (참고: \ \nu = n\ 일 때는 1에서 근이 없다). * 미분은 더 낮은 차수의 두 다항식의 조합으로 쓸 수 있다. \ b_{\nu, n}'\\!(x) = n \bigl[\ b_{\nu - 1, n - 1}\\!(x)\ -\ b_{\nu, n - 1}\\!(x)\ \bigr] ~. * k차 0에서의 미분: \ b_{\nu, n}^{(k)}\\!(0)\ =\ \frac{n!}{(n - k)!} \binom{k}{\nu} (-1)^{\nu + k} ~. * k차 1에서의 미분: \ b_{\nu, n}^{(k)}(1)\ =\ (-1)^k b_{n - \nu, n}^{(k)}(0) ~. * 베른슈타인 다항식의 단항식으로의 변환은 다음과 같다: \ b_{\nu,n}\\!(x)\ =\ \binom{n}{\nu}\sum_{k=0}^{n-\nu} \binom{n-\nu}{k}(-1)^{n-\nu-k} x^{\nu+k}\ =\ \sum_{\ell=\nu}^n \binom{n}{\ell}\binom{\ell}{\nu}(-1)^{\ell-\nu}x^\ell\ , 그리고 역 이항 변환에 의해 역변환은 다음과 같다:class=math.NA \ x^k\ =\ \sum_{i=0}^{n-k} \frac{ \binom{n-k}{i} }{ \binom{n}{i} } b_{n-i,n}\\!(x)\ =\ \frac{1}{\binom{n}{k \sum_{j=k}^n \binom{j}{k}b_{j,n}\\!(x) ~. * 부정 적분은 다음과 같다: \ \int b_{\nu, n}\\!(x)\ \operatorname{d} x = \frac{1}{n+1} \sum_{j=\nu+1}^{n+1} b_{j, n+1}\\!(x) ~. * 정적분은 주어진 n에 대해 상수이다. \ \int_0^1 b_{\nu, n}\\!(x)\ \operatorname{d} x = \frac{1}{n+1} ~~ (모든 ~~ \nu = 0, 1,\ \dots\ , n ~에 대해) * 만약 \ n \ne 0\ , ~이면 ~~ b_{\nu, n}\\!(x)\ 는 구간 \ [0,\, 1]\ 에서 \ x = \frac{\nu}{n} ~에서 유일한 국소 최대값을 가진다. 이 최대값은 다음 값을 갖는다: \ \nu^\nu n^{-n} \left( n - \nu \right)^{n - \nu} {n \choose \nu} ~. * \ n\ 차 베른슈타인 기저 다항식은 단위 분할을 형성한다. \ \sum_{\nu = 0}^n b_{\nu, n}(x)\ =\ \sum_{\nu = 0}^n {n \choose \nu} x^\nu \left(1 - x\right)^{n - \nu}\ =\ \left(x + \left( 1 - x \right) \right)^n = 1 ~. * \ (x + y)^n\ 를 첫 번째 x-미분하고 \ y\ 를 상수로 취급한 다음 \ y = 1-x\ 값을 대입하면 다음을 보일 수 있다. \ \sum_{\nu=0}^{n} \nu\ b_{\nu, n}\\!(x) = n\ x ~. * 마찬가지로, \ (x+y)^n\ 를 두 번째 \ x\ -미분하고 다시 \ y = 1-x\ 를 대입하면 다음을 보인다. \ \sum_{\nu=1}^{n} \nu \left( \nu-1 \right)\ b_{\nu, n}\\!(x) = n\left( n-1 \right)\ x^2 ~. * 베른슈타인 다항식은 항상 더 높은 차수의 다항식의 선형 조합으로 쓸 수 있다. \ b_{\nu, n - 1}\\!(x)\ =\ \left( \frac{n - \nu}{n}\right)\ b_{\nu, n}\\!(x)\ +\ \left( \frac{\nu + 1}{n}\right)\ b_{\nu + 1, n}\\!(x) ~. * 제1종 체비쇼프 다항식의 베른슈타인 기저로의 확장은 다음과 같다.doi-access=free \ T_n\\!(u)\ =\ (2n-1)!!\ \sum_{k=0}^n \frac{~ (-1)^{n-k}\ }{\ (2k-1)!!\ (2n-2k-1)!!\ }\ b_{k,n}\\!(u) ~.
# 연속 함수 근사
구간 [0, 1]에서 ƒ가 연속 함수라고 하자. 베른슈타인 다항식을 고려하자. :B_n(f)(x) = \sum_{\nu = 0}^n f\left( \frac{\nu}{n} \right) b_{\nu,n}(x). 다음을 보일 수 있다. :\lim_{n \to \infty}{ B_n(f) } = f 구간 [0, 1]에서 균등하게 수렴한다.Natanson (1964) p. 619662004 따라서 베른슈타인 다항식은 바이어슈트라스 근사 정리를 증명하는 한 가지 방법을 제공한다. 이 정리는 실수 구간 [a, b]에서 모든 실수값을 갖는 연속 함수가 \mathbb R상의 다항 함수에 의해 균등하게 근사될 수 있음을 말한다.Natanson (1964) p. 3 연속 k차 미분을 갖는 함수에 대한 더 일반적인 진술은 다음과 같다. :{\left\| B_n(f)^{(k)} \right\|}_\infty \le \frac{ (n)_k }{ n^k } \left\| f^{(k)} \right\|_\infty \quad\ \text{and} \quad\ \left\| f^{(k)}- B_n(f)^{(k)} \right\|_\infty \to 0, 추가적으로 :\frac{ (n)_k }{ n^k } = \left( 1 - \frac{0}{n} \right) \left( 1 - \frac{1}{n} \right) \cdots \left( 1 - \frac{k - 1}{n} \right) 는 Bn의 고유값이며, 해당 고유 함수는 k차 다항식이다.
## 확률적 증명
이 증명은 베른슈타인의 1912년 원본 증명을 따른다.1912 펠러 (1966) 또는 코랄로프 & 시나이 (2007)도 참조하라.chapter="Probabilistic proof of the Weierstrass theorem"
### 동기
먼저 베른슈타인의 원본 증명에 대한 직관을 제시한다. 콤팩트 구간의 연속 함수는 균등 연속이어야 한다. 따라서 모든 연속 함수의 값은 해당 구간의 유한 점 격자에서 해당 값으로 균등하게 근사될 수 있다. 이 고려 사항은 다항식이 유한한 수의 쌍 (x, f(x))와 일치(또는 거의 일치)할 만큼 충분히 유연해야 한다는 점을 고려할 때 근사 정리를 직관적으로 만든다. 이를 위해 우리는 (1) 격자에서 f에 가까운 함수를 구성하고, (2) 격자 외부의 함수를 평활화하여 다항식을 만들 수 있다. 아래의 확률적 증명은 함수를 "평활화"하는 것이 항상 자명하지 않다는 점을 고려할 때, 이러한 점 격자에서 f와 거의 동일한 다항식을 만드는 구성적 방법을 간단히 제공한다. 간단한 분포를 가진 확률 변수의 기댓값을 취하는 것은 평활화의 일반적인 방법이다. 여기서 우리는 베른슈타인 다항식이 이항 기댓값처럼 보인다는 사실을 이용한다. 우리는 구간을 n개의 이산 값의 격자로 분할한다. 그런 다음 모든 f(x)를 평가하기 위해 x에 가까운 n개의 격자점 중 하나에서 f를 평가하는데, 이 격자점은 이항 분포에 의해 무작위로 선택된다. 이 근사 기법의 기댓값은 이항 확률 변수의 함수 기댓값이므로 다항식이다. 아래 증명은 이것이 f의 균등 근사를 달성한다는 것을 보여준다. 증명의 핵심은 (1) 이항 분포의 집중 속성을 이용하여 임의의 점을 이항적으로 선택된 격자점으로 대체하는 것을 정당화하고, (2) 균등 연속성을 이용하여 x \approx X에서 f(x) \approx f(X)로의 추론을 정당화하는 것이다.
### 베른슈타인의 증명
K가 각 시행에서 성공 확률이 x인 n개의 독립 베르누이 시행에서의 성공 횟수로 분포된 확률 변수라고 가정하자. 즉, K는 매개변수 n과 x를 갖는 이항 분포를 따른다. 그러면 기댓값 \operatorname{\mathcal E}\left[\frac{K}{n}\right] = x\ 와 :p(K) = {n \choose K} x^{K} \left( 1 - x \right)^{n - K} = b_{K,n}(x)를 갖는다. 확률론의 약한 큰 수의 법칙에 의해, :\lim_{n \to \infty}{ P\left( \left| \frac{K}{n} - x \right|>\delta \right) } = 0 모든 δ > 0에 대해 성립한다. 또한, 이 관계는 x에 대해 균등하게 성립하며, 이는 체비쇼프 부등식을 통한 증명에서 볼 수 있다. n K의 분산은 x에 관계없이 (4n)으로 상한이 정해지므로, 이 점을 고려하면 된다. ƒ는 닫힌 유계 구간에서 연속이므로 해당 구간에서 균등 연속이어야 하므로, 다음과 같은 형태의 진술을 추론할 수 있다. :\lim_{n \to \infty}{ P\left( \left| f\left( \frac{K}{n} \right) - f\left( x \right) \right| > \varepsilon \right) } = 0 각 \epsilon > 0에 대해 x에 대해 균등하게 성립한다. ƒ가 (주어진 구간에서) 유계라는 점을 고려하면 다음을 알 수 있다. : \lim_{n \to \infty}{ \operatorname{\mathcal E}\left( \left| f\left( \frac{K}{n} \right) - f\left( x \right) \right| \right) } = 0 x에 대해 균등하게 성립한다. 이 진술을 정당화하기 위해 확률론에서 확률 근접성을 기댓값 근접성으로 변환하는 일반적인 방법을 사용한다. \left| f\left( \frac{K}{n} \right) - f\left( x \right) \right|의 기댓값을 \left| f\left( \frac{K}{n} \right) - f\left( x \right) \right| 0이 주어지면, |a-b| 0가 존재한다. 또한 연속성에 의해 M= \sup |f| < \infty이다. 그러면 : |f_n(x) - f(x)| \le \sum_{|x -{k\over n}|< \delta} |f(k/n) - f(x)|\, b_{k,n}(x) + \sum_{|x -{k\over n}|\ge \delta} |f(k/n) - f(x)|\, b_{k,n}(x) . 첫 번째 합은 ε보다 작다. 반면에 위의 항등식 (3)과 |x - k/n| \ge \delta에 의해, 두 번째 합은 2M 곱하기 다음으로 상한이 정해진다. :\sum_{|x - k/n|\ge \delta} b_{k,n}(x) \le \sum_k \delta^{-2} \left(x -{k\over n}\right)^2 b_{k,n}(x) = \delta^{-2} {x(1-x)\over n} < {1\over4} \delta^{-2} n^{-1}. :(체비쇼프 부등식) 따라서 다항식 fn은 f로 균등하게 수렴한다.
# 고차원으로의 일반화
베른슈타인 다항식은 k차원으로 일반화될 수 있다 – 결과 다항식은 Bi1(x1) Bi2(x2) ... Bik(xk) 형태를 갖는다. 가장 간단한 경우에는 단위 구간 [0,1]의 곱만이 고려되지만, 선의 아핀 변환을 사용하여 베른슈타인 다항식은 [a1, b1] × [a2, b2] × ... × [ak, bk]의 곱에 대해서도 정의될 수 있다. 단위 구간의 k중 곱에서 연속 함수 f에 대해 f(x1, x2, ... , xk)가 다음으로 균등하게 근사될 수 있다는 증명은 다음과 같다. :\sum_{i_1} \sum_{i_2} \cdots \sum_{i_k} {n_1\choose i_1} {n_2\choose i_2} \cdots {n_k\choose i_k} f\left({i_1\over n_1}, {i_2\over n_2}, \dots, {i_k\over n_k}\right) x_1^{i_1} (1-x_1)^{n_1-i_1} x_2^{i_2} (1-x_2)^{n_2-i_2} \cdots x_k^{i_k} (1-x_k)^{n_k - i_k} 이는 베른슈타인의 1차원 증명의 간단한 확장이다.
# 내용주