Полином Бернштейна

Чтобы узнать о полиноме Бернштейна в теории D-модулей , см. Полином Бернштейна – Сато .

Полиномы Бернштейна, аппроксимирующие кривую

В математической области численного анализа полином Бернштейна — это полином, выраженный как линейная комбинация Бернштейна базисных полиномов . Идея названа в честь математика Сергея Натановича Бернштейна .

Полиномы в форме Бернштейна были впервые использованы Бернштейном в конструктивном доказательстве аппроксимационной теоремы Вейерштрасса . С появлением компьютерной графики полиномы Бернштейна, ограниченные интервалом [0, 1], стали важными в форме кривых Безье .

способ Численно устойчивый оценки полиномов в форме Бернштейна — алгоритм де Кастельжо .

Базисные полиномы Бернштейна для сглаживания кривых 4-й степени

Определение

полиномы

n +1 степени базисных полиномов Бернштейна n определяются как

$b_{\nu ,n}(x)\mathrel {:} \mathrel {=} {\binom {n}{\nu }}x^{\nu }\left(1-x\right)^{n-\nu },\quad \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{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}}$

Базисные полиномы Бернштейна степени n составляют основу векторного пространства. $\Pi _{n}$ многочленов степени не выше n с действительными коэффициентами.

Полиномы Бернштейна

Линейная комбинация базисных полиномов Бернштейна

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

называется многочленом Бернштейна или многочленом в форме Бернштейна степени n . Коэффициенты $\beta _{\nu }$ называются коэффициентами Бернштейна или коэффициентами Безье .

Первые несколько базисных полиномов Бернштейна сверху в мономиальной форме:

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

Свойства

Базисные полиномы Бернштейна обладают следующими свойствами:

• $b_{\nu ,n}(x)=0$, если $\nu <0$ или $\nu >n.$
• $b_{\nu ,n}(x)\geq 0$ для $x\in [0,\ 1].$
• $b_{\nu ,n}\left(1-x\right)=b_{n-\nu ,n}(x).$
• $b_{\nu ,n}(0)=\delta _{\nu ,0}$ и $b_{\nu ,n}(1)=\delta _{\nu ,n}$ где $\delta$ – дельта - функция Кронекера : $\delta _{ij}={\begin{cases}0&{\text{if }}i\neq j,\\1&{\text{if }}i=j.\end{cases}}$
• $b_{\nu ,n}(x)$ имеет корень кратности $\nu$ в точку $x=0$ (примечание: если $\nu =0$, в 0 нет корня).
• $b_{\nu ,n}(x)$ имеет корень кратности $\left(n-\nu \right)$ в точку $x=1$ (примечание: если $\nu =n$, в точке 1 нет корня).
• Производную можно записать как комбинацию двух многочленов меньшей степени:
  $$b'_{\nu ,n}(x)=n\left(b_{\nu -1,n-1}(x)-b_{\nu ,n-1}(x)\right).$$
• 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 },$$
  и с помощью обратного биномиального преобразования обратное преобразование равно
  $$x^{k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}{\frac {1}{\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)\,dx={\frac {1}{n+1}}\sum _{j=\nu +1}^{n+1}b_{j,n+1}(x).$$
• Определенный интеграл постоянен для данного n :
  $$\int _{0}^{1}b_{\nu ,n}(x)\,dx={\frac {1}{n+1}}\quad \ \,{\text{for all }}\nu =0,1,\dots ,n.$$
• Если $n\neq 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$-производная от $(x+y)^{n}$, лечение $y$ как константу, затем подставив значение $y=1-x$, можно показать, что
  $$\sum _{\nu =0}^{n}\nu b_{\nu ,n}(x)=nx.$$
• Аналогично второй $x$-производная от $(x+y)^{n}$, с $y$ еще раз, затем заменил $y=1-x$, показывает, что
  $$\sum _{\nu =1}^{n}\nu (\nu -1)b_{\nu ,n}(x)=n(n-1)x^{2}.$$
• Полином Бернштейна всегда можно записать как линейную комбинацию полиномов более высокой степени:
  $$b_{\nu ,n-1}(x)={\frac {n-\nu }{n}}b_{\nu ,n}(x)+{\frac {\nu +1}{n}}b_{\nu +1,n}(x).$$
• Разложение полиномов Чебышева первого рода в базис Бернштейна имеет вид
  $$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].

Таким образом, полиномы Бернштейна обеспечивают один из способов доказать аппроксимационную теорему Вейерштрасса о том, что каждая вещественная непрерывная функция на вещественном интервале [ a , b ] может быть равномерно аппроксимирована полиномиальными функциями на протяжении $\mathbb {R}$.

Более общее утверждение для функции с непрерывным k ^й производная

${\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,$

где дополнительно

${\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 года. См. также Феллер (1966) или Коралов и Синай (2007).

Предположим, что K — случайная величина , распределенная как количество успехов в n независимых испытаниях Бернулли с вероятностью x успеха в каждом испытании; другими словами, 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 , что видно из его доказательства с помощью неравенства Чебышева с учетом того, что дисперсия 1 ⁄ n   K , равный 1 ⁄ n   x (1− x ), ограничено сверху 1 ⁄ (4 n ) независимо от x .

Поскольку ƒ , будучи непрерывным на замкнутом ограниченном интервале, должен быть равномерно непрерывным на этом интервале, можно сделать вывод о утверждении вида

$\lim _{n\to \infty }{P\left(\left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|>\varepsilon \right)}=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 . Для этого сумму ожидания разбивают на две части. В одной части разница не превышает ε ; эта часть не может давать больше, чем ε . С другой стороны, разница превышает ε , но не превышает 2 M , где M — верхняя граница | ƒ (х)|; эта часть не может вносить более чем в 2 M раза большую малую вероятность того, что разница превысит ε .

Наконец, можно заметить, что абсолютное значение разницы между ожиданиями никогда не превышает ожидание абсолютного значения разницы, и

$\operatorname {\mathcal {E}} \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)$

Элементарное доказательство

Вероятностное доказательство также можно элементарно перефразировать, используя основные вероятностные идеи, но проводя прямую проверку:

Следующие личности могут быть проверены:

1. $\sum _{k}{n \choose k}x^{k}(1-x)^{n-k}=1$ ("вероятность")
2. $\sum _{k}{k \over n}{n \choose k}x^{k}(1-x)^{n-k}=x$ ("иметь в виду")
3. $\sum _{k}\left(x-{k \over n}\right)^{2}{n \choose k}x^{k}(1-x)^{n-k}={x(1-x) \over n}.$ («дисперсия»)

Действительно, по биномиальной теореме

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

и это уравнение можно применить дважды к $t{\frac {d}{dt}}$. Тождества (1), (2) и (3) легко получаются с помощью замены $t=x/(1-x)$.

В рамках этих трех тождеств используйте приведенное выше обозначение базового полинома.

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

и разреши

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

Таким образом, согласно тождеству (1)

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

так что

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

Поскольку f равномерно непрерывна, учитывая $\varepsilon >0$, Eсть $\delta >0$ такой, что $|f(a)-f(b)|<\varepsilon$ в любое время $|a-b|<\delta$. Более того, в силу преемственности $M=\sup |f|<\infty$. Но потом

$|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), приведенному выше, и поскольку $|x-k/n|\geq \delta$, вторая сумма ограничена $2M$ раз

$\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 _{i 1} ( x ₁ ) B _{i 2} ( x ₂ ) ... B _{i k} ( x _k ) . только произведения единичного интервала [0,1] В простейшем случае рассматриваются ; но, используя аффинные преобразования прямой, полиномы Бернштейна также могут быть определены для произведений [ a ₁ , b ₁ ] × [ a ₂ , b ₂ ] × ... × [ a _k , b _k ] . Для непрерывной функции f на k -кратном произведении единичного интервала доказательство того, что f ( x ₁ , x ₂ , ... , x _k ) может быть равномерно аппроксимировано формулой

$\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}}$

является прямым продолжением доказательства Бернштейна в одном измерении.

См. также

• Полиномиальная интерполяция
• Форма Ньютона
• форма Лагранжа
• Биномиальный QMF (также известный как вейвлет Добеши )

Ссылки

• Бернштейн, С. (1912), «Démonstration du theorème de Weierstrass Fondée Sur le Calcul des Probilités (Доказательство теоремы Вейерштрасса, основанное на исчислении вероятностей)» (PDF) , Comm. Харьковская математика. Соц. , 13 : 1–2 , английский перевод
• Лоренц, Г.Г. (1953), Полиномы Бернштейна , University of Toronto Press
• Ахиезер Н.И. (1956), Теория приближения (на русском языке), перевод Чарльза Дж. Хаймана, Фредерика Унгара, стр. 30–31 , русское издание впервые опубликовано в 1940 году.
• Беркилл, Дж. К. (1959), Лекции по аппроксимации полиномами (PDF) , Бомбей: Институт фундаментальных исследований Таты , стр. 7–8
• Голдберг, Ричард Р. (1964), Методы реального анализа , John Wiley & Sons, стр. 263–265.
• Чаглар, Хакан; Акансу, Али Н. (июль 1993 г.). «Обобщенный параметрический метод проектирования PR-QMF, основанный на аппроксимации полиномом Бернштейна». Транзакции IEEE по обработке сигналов . 41 (7): 2314–2321. Бибкод : 1993ITSP...41.2314C . дои : 10.1109/78.224242 . Збл   0825.93863 .
• Коровкин, П.П. (2001) [1994], «Полиномы Бернштейна» , Энциклопедия Математики , EMS Press
• Натансон, ИП (1964). Конструктивная теория функций. Том I: Равномерное приближение . Перевод Алексея Н. Оболенского. Нью-Йорк: Фредерик Унгар. МР   0196340 . Збл   0133.31101 .
• Феллер, Уильям (1966), Введение в теорию вероятностей и ее приложения, Том II , John Wiley & Sons, стр. 149–150, 218–222.
• Билз, Ричард (2004), Анализ. Введение , Cambridge University Press , стр. 95–98, ISBN.  0521600472

Внешние ссылки

• Кац, Марк (1938). «Замечание о полиномах М. С. Бернштейна» . Студия Математика . 7 :49–51. дои : 10.4064/см-7-1-49-51 .
• Келиски, Ричард Пол; Ривлин, Теодор Джозеф (1967). «Итерации полиномов Бернштейна» . Тихоокеанский математический журнал . 21 (3): 511. doi : 10.2140/pjm.1967.21.511 .
• Старк, Э.Л. (1981). «Полином Бернштейна, 1912-1955». В Батцере, Польша (ред.). ИСНМ60 . стр. 443–461. дои : 10.1007/978-3-0348-9369-5_40 . ISBN  978-3-0348-9369-5 .
• Петроне, Соня (1999). «Случайные полиномы Бернштейна». Скан. Дж. Стат . 26 (3): 373–393. дои : 10.1111/1467-9469.00155 . S2CID   122387975 .
• Орук, Халил; Филлипс, Джордж М. (1999). «Обобщение полиномов Бернштейна» . Труды Эдинбургского математического общества . 42 (2): 403–413. дои : 10.1017/S0013091500020332 .
• Джой, Кеннет И. (2000). «Полиномы Бернштейна» (PDF) . Архивировано из оригинала (PDF) 20 февраля 2012 г. Проверено 28 февраля 2009 г. из Калифорнийского университета в Дэвисе . Обратите внимание на ошибку в пределах суммирования в первой формуле на стр. 9.
• Идрис Бхатти, М.; Бракен, П. (2007). «Решения дифференциальных уравнений в полиномиальном базисе Бернштейна» . Дж. Компьютер. Прил. Математика . 205 (1): 272–280. Бибкод : 2007JCoAM.205..272I . дои : 10.1016/j.cam.2006.05.002 .
• Кассельман, Билл (2008). «От Безье до Бернштейна» . Тематическая колонка Американского математического общества
• Аджикгоз, Мехмет; Арачи, Серкан (2010). «О производящей функции полиномов Бернштейна». Конференция АИП. Проц . Материалы конференции AIP. 1281 (1): 1141. Бибкод : 2010AIPC.1281.1141A . дои : 10.1063/1.3497855 .
• Доха, ЭГ; Бхрави, АХ; Сакер, Массачусетс (2011). «Интегралы от полиномов Бернштейна: приложение для решения дифференциальных уравнений высокого четного порядка» . Прил. Математика. Летт . 24 (4): 559–565. дои : 10.1016/j.aml.2010.11.013 .
• Фаруки, Рида Т. (2012). «Полиномиальный базис Бернштейна: столетняя ретроспектива». Комп. Помогать. Геом. Дес . 29 (6): 379–419. дои : 10.1016/j.cagd.2012.03.001 .
• Чен, Сяоянь; Тан, Цзецин; Лю, Чжи; Се, Цзинь (2017). «Приближение функций новым семейством обобщенных операторов Бернштейна» . Дж. Математика. Анна. Приложение . 450 : 244–261. дои : 10.1016/j.jmaa.2016.12.075 .
• Вайсштейн, Эрик В. «Полином Бернштейна» . Математический мир .
• Эта статья включает в себя материал из свойств полинома Бернштейна из PlanetMath , который доступен по лицензии Creative Commons Attribution/Share-Alike License .