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

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

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

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

Определение

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

${\ displaystyle b _ {\ nu, n} (x) = {\ binom {n} {\ nu}} x ^ {\ nu} \ left (1-x \ right) ^ {n- \ nu}, \ quad \nu =0,\ldots,n,}$

где – биномиальный коэффициент . ${\ Displaystyle {\ tbinom {п} {\ ню}}}$

Так, например,${\ displaystyle b_ {2,5} (x) = {\ tbinom {5} {2}} x ^ {2} (1-x) ^ {3} = 10x ^ {2} (1-x) ^ { 3}.}$

Первые несколько базисных полиномов Бернштейна для смешивания 1, 2, 3 или 4 значений вместе:

${\ displaystyle {\ begin {align} b_ {0,0} (x) & = 1, \\ b_ {0,1} (x) & = 1-x, & b_ {1,1} (x) & = х\\b_{0,2}(х)&=(1-х)^{2},&b_{1,2}(х)&=2х(1-х),&b_{2,2}(х )&=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{выровнено}}}$

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

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

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

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

${\ displaystyle {\ 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}-x^{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{выровнено}}}$

Характеристики

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

• ${\ Displaystyle б _ {\ ню, п} (х) = 0}$, если или${\ Displaystyle \ ню <0}$${\ Displaystyle \ ню > п.}$
• ${\ Displaystyle б _ {\ ню, п} (х) \ geq 0}$за${\ Displaystyle х \ в [0, \ 1].}$
• ${\ displaystyle b _ {\ nu, n} \ left (1-x \ right) = b_ {n- \ nu, n} (x).}$
• ${\ displaystyle b _ {\ nu, n} (0) = \ delta _ {\ nu, 0}}$и где дельта -функция Кронекера :${\ displaystyle b _ {\ nu, n} (1) = \ delta _ {\ nu, n}}$${\ Displaystyle \ дельта}$${\ displaystyle \ delta _ {ij} = {\ begin {case} 0 & {\ text {if}} i \ neq j, \\ 1 & {\ text {if}} i = j. \ end {case}}}$
• ${\ Displaystyle б _ {\ ню, п} (х)}$имеет корень с кратностью в точке (примечание: если , то нет корня в 0).${\ Displaystyle \ ню}$${\ Displaystyle х = 0}$${\ Displaystyle \ ню = 0}$
• ${\ Displaystyle б _ {\ ню, п} (х)}$имеет корень с кратностью в точке (примечание: если , то нет корня в 1).${\ Displaystyle \ влево (п- \ ню \ вправо)}$${\ Displaystyle х = 1}$${\ Displaystyle \ ню = п}$
• Производную можно записать в виде комбинации двух многочленов более низкой степени :
  $${\ displaystyle b'_ {\ nu, n} (x) = n \ left (b _ {\ nu -1, n-1} (x) -b _ {\ nu, n-1} (x) \ right) .}$$

  
• k -я производная в 0 :
  $${\ displaystyle b _ {\ nu, n} ^ {(k)} (0) = {\ frac {n!} {(nk)!}} {\ binom {k} {\ nu}} (-1) ^ {\ ню + к}.}$$

  
• 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},}$$

  
  и обратным биномиальным преобразованием обратное преобразование
  $${\ displaystyle x ^ {k} = \ sum _ {i = 0} ^ {nk} {\ binom {nk} {i}} {\ frac {1} {\ binom {n} {i}}} b_ { ni, n} (x) = {\ frac {1} {\ binom {n} {k}}} \ sum _ {j = k} ^ {n} {\ binom {j} {k}} b_ {j ,п}(х).}$$

  
• Неопределенный интеграл определяется выражением
  $${\ displaystyle \ int b _ {\ nu, n} (x) \, dx = {\ frac {1} {n + 1}} \ sum _ {j = \ nu + 1} ^ {n + 1} b_ { j,n+1}(x).}$$

  
• Определенный интеграл постоянен для данного n :
  $${\ displaystyle \ int _ {0} ^ {1} b _ {\ nu, n} (x) \, dx = {\ frac {1} {n + 1}} \ quad \ \, {\ text {для всех }}\nu =0,1,\dots ,n.}$$

  
• Если , то имеет единственный локальный максимум на интервале при . Этот максимум принимает значение${\ Displaystyle п \ neq 0}$${\ Displaystyle б _ {\ ню, п} (х)}$${\ Displaystyle [0, \, 1]}$${\ Displaystyle х = {\ гидроразрыва {\ ню} {п}}}$
  $${\ Displaystyle \ ню ^ {\ ню} п ^ {- п} \ влево (п- \ ню \ вправо) ^ {п- \ ню} {п \ выбрать \ ню}.}$$

  
• Базисные полиномы Бернштейна степени образуют разбиение единицы :${\ Displaystyle п}$
  $${\ displaystyle \ sum _ {\ nu = 0} ^ {n} b _ {\ nu, n} (x) = \ sum _ {\ nu = 0} ^ {n} {n \ выберите \ nu} x ^ { \nu}\left(1-x\right)^{n-\nu}=\left(x+\left(1-x\right)\right)^{n}=1.}$$

  
• Взяв первую производную от , рассматривая ее как константу, а затем подставив значение , можно показать, что${\ Displaystyle х}$${\ Displaystyle (х + у) ^ {п}}$${\ Displaystyle у}$${\ Displaystyle у = 1-х}$
  $${\ displaystyle \ sum _ {\ nu = 0} ^ {n} \ nu b _ {\ nu, n} (x) = nx.}$$

  
• Точно так же вторая производная от , снова затем замещенная , показывает, что${\ Displaystyle х}$${\ Displaystyle (х + у) ^ {п}}$${\ Displaystyle у}$${\ Displaystyle у = 1-х}$
  $${\ displaystyle \ sum _ {\ nu = 1} ^ {n} \ nu (\ nu -1) b _ {\ nu, n} (x) = n (n-1) x ^ {2}.}$$

  
• Многочлен Бернштейна всегда можно записать в виде линейной комбинации многочленов более высокой степени:
  $${\ displaystyle b _ {\ nu, n-1} (x) = {\ frac {n- \ nu} {n}} b _ {\ nu, n} (x) + {\ frac {\ nu +1} { n}}b_{\nu +1,n}(x).}$$

  
• Разложение полиномов Чебышева первого рода по базису Бернштейна
  $${\ displaystyle T_ {n} (u) = (2n-1) !! \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {nk}} {(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, п}(х).}$

Можно показать, что

${\ Displaystyle \ lim _ {п \ к \ infty} {B_ {п} (е)} = е}$

равномерно на отрезке [0, 1].

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

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

${\ Displaystyle {\ влево \ | B_ {п} (е) ^ {(к)} \ вправо \ |} _ {\ infty} \ leq {\ гидроразрыва {(п) _ {к}} {п ^ {к} }}}\left\|f^{(k)}\right\|_{\infty}\quad \ {\text{and}}\quad \\left\|f^{(k)}-B_{ n} (f) ^ {(k)} \ right \ | _ {\ infty} \ to 0,}$

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

${\ Displaystyle {\ гидроразрыва {(п) _ {к}} {п ^ {к}}} = \ влево (1 - {\ гидроразрыва {0} {п}} \ вправо) \ влево (1 - {\ гидроразрыва {1} {n}} \ справа) \ cdots \ слева (1 - {\ гидроразрыва {k-1} {n}} \ справа)}$

является собственным значением B _n ; соответствующая собственная функция является полиномом степени  k .

Вероятностное доказательство

Это доказательство следует первоначальному доказательству Бернштейна 1912 года. См. также Феллер (1966) или Коралов и Синай (2007).

Предположим , что K — случайная величина , распределенная как количество успехов в n независимых испытаниях Бернулли с вероятностью x успеха в каждом испытании; другими словами, K имеет биномиальное распределение с параметрами n и  x . Тогда у нас есть ожидаемое значение и ${\ displaystyle \ operatorname {\ mathcal {E}} \ left [{\ frac {K} {n}} \ right] = x \}$

${\ displaystyle p (K) = {n \ выберите K} x ^ {K} \ left (1-x \ right) ^ {nK} = 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 , равная 1 ⁄ n  x (1 − x ), ограничен сверху 1 ⁄ (4 n ) независимо от x .

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

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

равномерно по х . Учитывая, что ƒ ограничено (на заданном интервале), получаем для математического ожидания

${\ Displaystyle \ lim _ {п \ к \ infty} {\ operatorname {\ mathcal {E}} \ влево (\ влево | е \ влево ({\ гидроразрыва {K} {п}} \ вправо) -f \ влево (х\право)\право|\право)}=0}$

равномерно по х . Для этого разбивают сумму ожидания на две части. На одной части разница не превышает ε ; эта часть не может дать вклад больше, чем ε . С другой стороны, разница превышает ε , но не превышает 2 M , где M — верхняя граница | ƒ (х)|; эта часть не может вносить более чем в 2M раза малую вероятность того, что разность превысит ε .

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

${\ displaystyle \ operatorname {\ mathcal {E}} \ left [f \ left ({\ frac {K} {n}} \ right) \ right] = \ sum _ {K = 0} ^ {n} f \ влево ({\ гидроразрыва {K} {п}} \ вправо) р (К) = \ сумма _ {К = 0} ^ {п} е \ влево ({\ гидроразрыва {K} {п}} \ вправо) b_ {К, п} (х) = B_ {п} (е) (х)}$

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

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

Могут быть проверены следующие тождества:

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

В самом деле, по биномиальной теореме

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

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

${\ displaystyle b_ {k, n} (x) = {n \ выберите k} x ^ {k} (1-x) ^ {nk},}$

и разреши

${\ 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 \ дельта > 0}$${\ Displaystyle | е (а) -е (б) | <\ varepsilon}$${\ Displaystyle | аб | <\ дельта}$${\ Displaystyle М = \ суп | е | <\ 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, п}(х).}$

Первая сумма меньше ε. С другой стороны, в силу тождества (3) выше и поскольку вторая сумма ограничена в 2 M раз ${\ Displaystyle | хк / п | \ geq \ дельта}$

${\ displaystyle \ sum _ {| xk / 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}<\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 ) может быть равномерно аппроксимировано формулой

${\ displaystyle \ sum _ {i_ {1}} \ sum _ {i_ {2}} \ cdots \ sum _ {i_ {k}} {n_ {1} \ выберите i_ {1}} {n_ {2} \ выберите i_{2}}\cdots {n_{k} \выберите 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), «Демонстрация фонда теории Вейерштрасса по исчислению вероятностей (Доказательство теоремы Вейерштрасса, основанное на исчислении вероятностей)» (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). "Une remarque sur les polynomes de MS Bernstein" . Студия Математика . 7 : 49–51. doi : 10.4064/см-7-1-49-51 .
• Келиски, Ричард Пол; Ривлин, Теодор Джозеф (1967). «Итерации многочленов Бернштейна» . Тихоокеанский математический журнал . 21 (3): 511. doi : 10.2140/pjm.1967.21.511 .
• Старк, Э. Л. (1981). «Полином Бернштейна, 1912-1955». В Батцере, PL (ред.). ИСНМ60 . стр. 443–461. doi : 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. doi : 10.1017/S0013091500020332 .
• Джой, Кеннет И. (2000). «Полиномы Бернштейна» (PDF) . Архивировано из оригинала (PDF) 20 февраля 2012 г .. Проверено 28 февраля 2009 г. .из Калифорнийского университета в Дэвисе . Обратите внимание на ошибку в пределах суммирования в первой формуле на стр. 9.
• Идрис Бхатти, М.; Брэкен, П. (2007). «Решения дифференциальных уравнений в полиномиальном базисе Бернштейна» . Дж. Вычисл. заявл. Математика . 205 (1): 272–280. Бибкод : 2007JCoAM.205..272I . doi : 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. doi : 10.1016/j.aml.2010.11.013 .
• Фаруки, Рида Т. (2012). «Полиномиальный базис Бернштейна: столетняя ретроспектива». Комп. Помогать. геом. Дес . 29 (6): 379–419. doi : 10.1016/j.cagd.2012.03.001 .
• Чен, Сяоянь; Тан, Цзецин; Лю, Чжи; Се, Джин (2017). «Приближение функций новым семейством обобщенных операторов Бернштейна» . Дж. Матем. Анна. приложение . 450 : 244–261. doi : 10.1016/j.jmaa.2016.12.075 .
• Вайсштейн, Эрик В. «Полином Бернштейна» . Мир Математики .
• Эта статья включает в себя материал из свойств многочлена Бернштейна на PlanetMath , который находится под лицензией Creative Commons Attribution/Share-Alike License .