베른슈타인 다항식

수학의 수치해석학 분야에서 베른슈타인 다항식(영어: Bernstein polynomial)은 선형 결합으로 표현되는 다항식이다. 이 개념은 수학자 세르게이 나타노비치 베른슈타인의 이름을 따서 명명되었다.

곡선을 근사하는 베른슈타인 다항식

이 형태의 다항식은 베른슈타인이 바이어슈트라스 근사 정리의 구성적 증명에서 처음 사용했다. 컴퓨터 그래픽의 등장과 함께, [0, 1] 구간으로 제한된 베른슈타인 다항식은 베지에 곡선의 형태로 중요해졌다.

베른슈타인 형식(Bernstein form)으로 다항식을 평가하는 수치적으로 안정된 방법은 드 카스텔조 알고리즘이다.

4차 곡선 블렌딩을 위한 베른슈타인 기저 다항식

정의

베른슈타인 기저 다항식

${\displaystyle \ n\ }$차의 ${\displaystyle \ n+1\ }$개의 베른슈타인 기저 다항식은 다음과 같이 정의된다:

${\displaystyle \ b_{\nu ,n}(x)\ \equiv \ {\binom {n}{\nu }}\ x^{\nu }\left(1-x\right)^{n-\nu }\ ,~~}$ (단, ${\displaystyle ~~\nu =0\ ,\ \ldots \ ,n\ }$)

여기서 ${\displaystyle \ {\tbinom {n}{\nu }}\ }$는 이항 계수이다.

예를 들어, ${\displaystyle \ b_{2,5}(x)\ =\ {\tbinom {5}{2}}x^{2}(1-x)^{3}\ =\ 10x^{2}(1-x)^{3}~.}$

1, 2, 3 또는 4 값을 함께 섞기 위한 처음 몇 개의 베른슈타인 기저 다항식은 다음과 같다.

${\displaystyle {\begin{aligned}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{aligned}}}$

${\displaystyle \ n\ }$차 베른슈타인 기저 다항식은 실수 계수를 가진 최대 ${\displaystyle \ n\ }$차 다항식의 벡터 공간 ${\displaystyle \ \Pi _{n}\ }$의 기저를 형성한다.

베른슈타인 다항식

베른슈타인 기저 다항식의 선형 결합

${\displaystyle \ B_{n}(x)\ \equiv \ \sum _{\nu =0}^{n}\beta _{\nu }b_{\nu ,n}(x)\ }$

은 ${\displaystyle \ n\ }$차 베른슈타인 다항식 또는 베른슈타인 형식의 다항식이라고 불린다.^[1] 계수 ${\displaystyle \ \beta _{\nu }\ }$는 베른슈타인 계수 또는 베지에 계수라고 불린다.

위의 처음 몇 개의 베른슈타인 기저 다항식의 단항식 형태는 다음과 같다.

${\displaystyle {\begin{aligned}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{aligned}}}$

성질

베른슈타인 기저 다항식은 다음과 같은 성질을 갖는다.

• ${\displaystyle \ b_{\nu ,n}\!(x)\equiv 0\ ,}$ (만약 ${\displaystyle \ \nu <0\ }$ 또는 ${\displaystyle \ \nu >n~}$이라면)
• ${\displaystyle \ b_{\nu ,n}\!(x)\geq 0\ }$ (만약 ${\displaystyle \ x\in [0,\ 1]~}$이라면)
• ${\displaystyle \ b_{\nu ,n}\!\left(1-x\right)=b_{n-\nu ,n}\!(x)~.}$
• ${\displaystyle \ b_{\nu ,n}\!(0)=\delta _{\nu ,0}\ }$ and ${\displaystyle \ b_{\nu ,n}\!(1)=\delta _{\nu ,n}\ }$ (여기서 ${\displaystyle \ \delta _{i,j}\ }$는 크로네커 델타 함수이다: ${\displaystyle \ \delta _{ij}\equiv {\begin{cases}0&{\text{if }}i\neq j\ ,\\1&{\text{if }}i=j~.\end{cases}}}$)
• ${\displaystyle \ b_{\nu ,n}\!(x)\ }$는 점 ${\displaystyle \ x=0\ }$에서 ${\displaystyle \ \nu \ }$의 중근을 갖는다 (참고: ${\displaystyle \ \nu =0\ }$일 때는 0에서 근이 없다).
• ${\displaystyle \ b_{\nu ,n}\!(x)\ }$는 점 ${\displaystyle \ x=1\ }$에서 ${\displaystyle \ \left(n-\nu \right)\ }$의 중근을 갖는다 (참고: ${\displaystyle \ \nu =n\ }$일 때는 1에서 근이 없다).
• 미분은 더 낮은 차수의 두 다항식의 조합으로 쓸 수 있다. $${\displaystyle \ b_{\nu ,n}'\!(x)=n{\bigl [}\ b_{\nu -1,n-1}\!(x)\ -\ b_{\nu ,n-1}\!(x)\ {\bigr ]}~.}$$
• k차 0에서의 미분: $${\displaystyle \ b_{\nu ,n}^{(k)}\!(0)\ =\ {\frac {n!}{(n-k)!}}{\binom {k}{\nu }}(-1)^{\nu +k}~.}$$
• k차 1에서의 미분: $${\displaystyle \ b_{\nu ,n}^{(k)}(1)\ =\ (-1)^{k}b_{n-\nu ,n}^{(k)}(0)~.}$$
• 베른슈타인 다항식의 단항식으로의 변환은 다음과 같다: $${\displaystyle \ 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 }\ ,}$$ 그리고 역 이항 변환에 의해 역변환은 다음과 같다:^[2] $${\displaystyle \ 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)~.}$$
• 부정 적분은 다음과 같다: $${\displaystyle \ \int b_{\nu ,n}\!(x)\ \operatorname {d} x={\frac {1}{n+1}}\sum _{j=\nu +1}^{n+1}b_{j,n+1}\!(x)~.}$$
• 정적분은 주어진 n에 대해 상수이다. $${\displaystyle \ \int _{0}^{1}b_{\nu ,n}\!(x)\ \operatorname {d} x={\frac {1}{n+1}}~~}$$ (모든 ${\displaystyle ~~\nu =0,1,\ \dots \ ,n~}$에 대해)
• 만약 ${\displaystyle \ n\neq 0\ ,~}$이면 ${\displaystyle ~~b_{\nu ,n}\!(x)\ }$는 구간 ${\displaystyle \ [0,\,1]\ }$에서 ${\displaystyle \ x={\frac {\nu }{n}}~}$에서 유일한 국소 최대값을 가진다. 이 최대값은 다음 값을 갖는다: $${\displaystyle \ \nu ^{\nu }n^{-n}\left(n-\nu \right)^{n-\nu }{n \choose \nu }~.}$$
• ${\displaystyle \ n\ }$차 베른슈타인 기저 다항식은 단위 분할을 형성한다. $${\displaystyle \ \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~.}$$
• ${\displaystyle \ (x+y)^{n}\ }$를 첫 번째 ${\displaystyle x}$-미분하고 ${\displaystyle \ y\ }$를 상수로 취급한 다음 ${\displaystyle \ y=1-x\ }$ 값을 대입하면 다음을 보일 수 있다. $${\displaystyle \ \sum _{\nu =0}^{n}\nu \ b_{\nu ,n}\!(x)=n\ x~.}$$
• 마찬가지로, ${\displaystyle \ (x+y)^{n}\ }$를 두 번째 ${\displaystyle \ x\ }$-미분하고 다시 ${\displaystyle \ y=1-x\ }$를 대입하면 다음을 보인다. $${\displaystyle \ \sum _{\nu =1}^{n}\nu \left(\nu -1\right)\ b_{\nu ,n}\!(x)=n\left(n-1\right)\ x^{2}~.}$$
• 베른슈타인 다항식은 항상 더 높은 차수의 다항식의 선형 조합으로 쓸 수 있다. $${\displaystyle \ 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종 체비쇼프 다항식의 베른슈타인 기저로의 확장은 다음과 같다.^[3] $${\displaystyle \ T_{n}\!(u)\ =\ (2n-1)!!\ \sum _{k=0}^{n}{\frac {~(-1)^{n-k}\ }{\ (2k-1)!!\ (2n-2k-1)!!\ }}\ b_{k,n}\!(u)~.}$$

연속 함수 근사

구간 [0, 1]에서 ƒ가 연속 함수라고 하자. 베른슈타인 다항식을 고려하자.

${\displaystyle B_{n}(f)(x)=\sum _{\nu =0}^{n}f\left({\frac {\nu }{n}}\right)b_{\nu ,n}(x).}$

다음을 보일 수 있다.

${\displaystyle \lim _{n\to \infty }{B_{n}(f)}=f}$

구간 [0, 1]에서 균등하게 수렴한다.^[4][1][5][6]

따라서 베른슈타인 다항식은 바이어슈트라스 근사 정리를 증명하는 한 가지 방법을 제공한다. 이 정리는 실수 구간 [a, b]에서 모든 실수값을 갖는 연속 함수가 ${\displaystyle \mathbb {R} }$상의 다항 함수에 의해 균등하게 근사될 수 있음을 말한다.^[7]

연속 k^차 미분을 갖는 함수에 대한 더 일반적인 진술은 다음과 같다.

${\displaystyle {\left\|B_{n}(f)^{(k)}\right\|}_{\infty }\leq {\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,}$

추가적으로

${\displaystyle {\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)}$

는 B_n의 고유값이며, 해당 고유 함수는 k차 다항식이다.

확률적 증명

이 증명은 베른슈타인의 1912년 원본 증명을 따른다.^[8] 펠러 (1966) 또는 코랄로프 & 시나이 (2007)도 참조하라.^[9][5]

동기

먼저 베른슈타인의 원본 증명에 대한 직관을 제시한다. 콤팩트 구간의 연속 함수는 균등 연속이어야 한다. 따라서 모든 연속 함수의 값은 해당 구간의 유한 점 격자에서 해당 값으로 균등하게 근사될 수 있다. 이 고려 사항은 다항식이 유한한 수의 쌍 ${\displaystyle (x,f(x))}$와 일치(또는 거의 일치)할 만큼 충분히 유연해야 한다는 점을 고려할 때 근사 정리를 직관적으로 만든다. 이를 위해 우리는 (1) 격자에서 ${\displaystyle f}$에 가까운 함수를 구성하고, (2) 격자 외부의 함수를 평활화하여 다항식을 만들 수 있다.

아래의 확률적 증명은 함수를 "평활화"하는 것이 항상 자명하지 않다는 점을 고려할 때, 이러한 점 격자에서 ${\displaystyle f}$와 거의 동일한 다항식을 만드는 구성적 방법을 간단히 제공한다. 간단한 분포를 가진 확률 변수의 기댓값을 취하는 것은 평활화의 일반적인 방법이다. 여기서 우리는 베른슈타인 다항식이 이항 기댓값처럼 보인다는 사실을 이용한다. 우리는 구간을 n개의 이산 값의 격자로 분할한다. 그런 다음 모든 f(x)를 평가하기 위해 x에 가까운 n개의 격자점 중 하나에서 f를 평가하는데, 이 격자점은 이항 분포에 의해 무작위로 선택된다. 이 근사 기법의 기댓값은 이항 확률 변수의 함수 기댓값이므로 다항식이다. 아래 증명은 이것이 f의 균등 근사를 달성한다는 것을 보여준다. 증명의 핵심은 (1) 이항 분포의 집중 속성을 이용하여 임의의 점을 이항적으로 선택된 격자점으로 대체하는 것을 정당화하고, (2) 균등 연속성을 이용하여 ${\displaystyle x\approx X}$에서 ${\displaystyle f(x)\approx f(X)}$로의 추론을 정당화하는 것이다.

베른슈타인의 증명

K가 각 시행에서 성공 확률이 x인 n개의 독립 베르누이 시행에서의 성공 횟수로 분포된 확률 변수라고 가정하자. 즉, K는 매개변수 n과 x를 갖는 이항 분포를 따른다. 그러면 기댓값 ${\displaystyle \operatorname {\mathcal {E}} \left[{\frac {K}{n}}\right]=x\ }$와

${\displaystyle p(K)={n \choose K}x^{K}\left(1-x\right)^{n-K}=b_{K,n}(x)}$를 갖는다.

확률론의 약한 큰 수의 법칙에 의해,

${\displaystyle \lim _{n\to \infty }{P\left(\left|{\frac {K}{n}}-x\right|>\delta \right)}=0}$

모든 δ > 0에 대해 성립한다. 또한, 이 관계는 x에 대해 균등하게 성립하며, 이는 체비쇼프 부등식을 통한 증명에서 볼 수 있다. 1⁄n K의 분산은 x에 관계없이 1⁄(4n)으로 상한이 정해지므로, 이 점을 고려하면 된다.

ƒ는 닫힌 유계 구간에서 연속이므로 해당 구간에서 균등 연속이어야 하므로, 다음과 같은 형태의 진술을 추론할 수 있다.

${\displaystyle \lim _{n\to \infty }{P\left(\left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|>\varepsilon \right)}=0}$

각 ${\displaystyle \epsilon >0}$에 대해 x에 대해 균등하게 성립한다. ƒ가 (주어진 구간에서) 유계라는 점을 고려하면 다음을 알 수 있다.

${\displaystyle \lim _{n\to \infty }{\operatorname {\mathcal {E}} \left(\left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|\right)}=0}$

x에 대해 균등하게 성립한다. 이 진술을 정당화하기 위해 확률론에서 확률 근접성을 기댓값 근접성으로 변환하는 일반적인 방법을 사용한다. ${\displaystyle \left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|}$의 기댓값을 ${\displaystyle \left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|<\epsilon }$인지 여부에 따라 두 부분으로 나눈다. 차이가 ε를 초과하지 않는 구간에서는 기댓값이 ε를 초과할 수 없다. 다른 구간에서는 차이가 여전히 2M을 초과할 수 없으며, 여기서 M은 |ƒ(x)|의 상한이다 (균등 연속 함수는 유계이기 때문). 그러나 '확률 근접성' 진술에 의해 이 구간의 확률은 ε보다 클 수 없다. 따라서 기댓값의 이 부분은 2M 곱하기 ε보다 더 기여하지 않는다. 그러면 총 기댓값은 ${\displaystyle \epsilon +2M\epsilon }$를 초과하지 않으며, 이는 ε을 작게 선택함으로써 임의로 작게 만들 수 있다.

마지막으로, 기댓값 간의 차이의 절대값은 절대값 차이의 기댓값을 절대 초과하지 않는다는 것을 알 수 있다. 이는 헬더 부등식의 결과이다. 따라서 위의 기댓값을 사용하여 (x에 대해 균등하게) 다음을 알 수 있다.

${\displaystyle \lim _{n\to \infty }{\left|\operatorname {\mathcal {E}} f\left({\frac {K}{n}}\right)-\operatorname {\mathcal {E}} f\left(x\right)\right|}\leq \lim _{n\to \infty }{\operatorname {\mathcal {E}} \left(\left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|\right)}=0}$

x가 상수인 동안 K에 대한 무작위성이었음을 주목하면, f(x)의 기댓값은 f(x)와 같다. 그러나 우리는 ${\displaystyle \operatorname {{\mathcal {E}}_{x}} f\left({\frac {K}{n}}\right)}$가 f(x)로 수렴함을 보였다. 그러면 ${\displaystyle \operatorname {{\mathcal {E}}_{x}} f\left({\frac {K}{n}}\right)}$가 x에 대한 다항식이라면 (첨자는 x가 K의 분포를 제어함을 상기시킨다) 우리는 증명을 마친 것이다. 실제로 그렇다:

${\displaystyle \operatorname {{\mathcal {E}}_{x}} \left[f\left({\frac {K}{n}}\right)\right]=\sum _{K=0}^{n}f\left({\frac {K}{n}}\right)p(K)=\sum _{K=0}^{n}f\left({\frac {K}{n}}\right)b_{K,n}(x)=B_{n}(f)(x)}$

함수 간 균등 수렴 속도

위 증명에서, f를 포함하는 각 극한에서의 수렴은 f의 연속률 ${\displaystyle \omega }$에 의존하는 수렴 속도를 암시하는 f의 균등 연속성에 의존한다. 또한 함수의 절대 상한인 'M'에도 의존하지만, ${\displaystyle \omega }$와 구간 크기를 제한하면 이를 우회할 수 있다. 따라서 근사는 고정된 f에 대해 x에 대해 균등하게만 유지되지만, 동등 연속 함수족의 맥락에서 일련의 베른슈타인 다항식으로 일련의 함수를 균등하게 근사하도록 증명을 쉽게 확장할 수 있다.

초등 증명

확률론적 증명은 기초적인 확률론적 아이디어를 사용하면서도 직접적인 검증을 통해 초등적인 방식으로 재구성될 수 있다.^{[10][6][11][12][13]}

다음 항등식들이 검증될 수 있다.

1. ${\displaystyle \sum _{k}{n \choose k}x^{k}(1-x)^{n-k}=1}$ ("확률")
2. ${\displaystyle \sum _{k}{k \over n}{n \choose k}x^{k}(1-x)^{n-k}=x}$ ("평균")
3. ${\displaystyle \sum _{k}\left(x-{k \over n}\right)^{2}{n \choose k}x^{k}(1-x)^{n-k}={x(1-x) \over n}.}$ ("분산")

실제로, 이항 정리에 의해

$${\displaystyle (1+t)^{n}=\sum _{k}{n \choose k}t^{k},}$$

이 방정식은 ${\displaystyle t{\frac {d}{dt}}}$에 두 번 적용될 수 있다. 항등식 (1), (2), (3)은 ${\displaystyle t=x/(1-x)}$를 대입하여 쉽게 유도된다.

이 세 항등식 내에서 위의 기저 다항식 표기법을 사용한다.

${\displaystyle b_{k,n}(x)={n \choose k}x^{k}(1-x)^{n-k},}$

그리고 다음으로 둔다.

${\displaystyle f_{n}(x)=\sum _{k}f(k/n)\,b_{k,n}(x).}$

따라서 항등식 (1)에 의해

${\displaystyle f_{n}(x)-f(x)=\sum _{k}[f(k/n)-f(x)]\,b_{k,n}(x),}$

따라서

${\displaystyle |f_{n}(x)-f(x)|\leq \sum _{k}|f(k/n)-f(x)|\,b_{k,n}(x).}$

f는 균등 연속이므로, ${\displaystyle \varepsilon >0}$이 주어지면, ${\displaystyle |a-b|<\delta }$일 때마다 ${\displaystyle |f(a)-f(b)|<\varepsilon }$인 ${\displaystyle \delta >0}$가 존재한다. 또한 연속성에 의해 ${\displaystyle M=\sup |f|<\infty }$이다. 그러면

${\displaystyle |f_{n}(x)-f(x)|\leq \sum _{|x-{k \over n}|<\delta }|f(k/n)-f(x)|\,b_{k,n}(x)+\sum _{|x-{k \over n}|\geq \delta }|f(k/n)-f(x)|\,b_{k,n}(x).}$

첫 번째 합은 ε보다 작다. 반면에 위의 항등식 (3)과 ${\displaystyle |x-k/n|\geq \delta }$에 의해, 두 번째 합은 ${\displaystyle 2M}$ 곱하기 다음으로 상한이 정해진다.

${\displaystyle \sum _{|x-k/n|\geq \delta }b_{k,n}(x)\leq \sum _{k}\delta ^{-2}\left(x-{k \over n}\right)^{2}b_{k,n}(x)=\delta ^{-2}{x(1-x) \over n}<{1 \over 4}\delta ^{-2}n^{-1}.}$

(체비쇼프 부등식)

따라서 다항식 f_n은 f로 균등하게 수렴한다.

고차원으로의 일반화

베른슈타인 다항식은 k차원으로 일반화될 수 있다 – 결과 다항식은 B_i1(x₁) B_i2(x₂) ... B_ik(x_k) 형태를 갖는다.^[1] 가장 간단한 경우에는 단위 구간 [0,1]의 곱만이 고려되지만, 선의 아핀 변환을 사용하여 베른슈타인 다항식은 [a₁, b₁] × [a₂, b₂] × ... × [a_k, b_k]의 곱에 대해서도 정의될 수 있다. 단위 구간의 k중 곱에서 연속 함수 f에 대해 f(x₁, x₂, ... , x_k)가 다음으로 균등하게 근사될 수 있다는 증명은 다음과 같다.

${\displaystyle \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차원 증명의 간단한 확장이다. ^[14]

같이 보기

• 다항식 보간법
• 뉴턴 형식
• 라그랑주 형식
• 이항 QMF (일명 도베시 웨이블릿)