Bernstein polynom -Bernstein polynomial

Inom det matematiska området för numerisk analys är ett Bernsteinpolynom ett polynom som är en linjär kombination av Bernsteinbaspolynom . Idén är uppkallad efter Sergei Natanovich Bernstein .

Ett numeriskt stabilt sätt att utvärdera polynom i Bernstein-form är de Casteljaus algoritm .

Polynom i Bernstein form användes först av Bernstein i ett konstruktivt bevis för Weierstrass approximation teorem . Med tillkomsten av datorgrafik blev Bernstein-polynom, begränsade till intervallet [0, 1], viktiga i form av Bézier-kurvor .

Definition

De n  +1 Bernstein-baspolynomen av grad n definieras som

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

var är en binomial koefficient . ${\displaystyle {\tbinom {n}{\nu }}}$

Så t.ex.${\displaystyle b_{2,5}(x)={\tbinom {5}{2}}x^{2}(1-x)^{3}=10x^{2}(1-x)^{ 3}.}$

De första Bernstein-baspolynomen för att blanda 1, 2, 3 eller 4 värden tillsammans är:

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

Bernsteinbaspolynomen av grad n bildar en bas för vektorrummet för polynom med högst grad  n med reella koefficienter. En linjär kombination av Bernstein-baspolynom ${\displaystyle \Pi _{n}}$

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

kallas ett Bernstein-polynom eller polynom i Bernstein-form av grad  n . Koefficienterna kallas för Bernstein-koefficienter eller Bézier-koefficienter . ${\displaystyle \beta _{\nu }}$

De första Bernstein-baspolynomen ovanifrån i monomform är:

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

Egenskaper

Bernstein-baspolynomen har följande egenskaper:

• ${\displaystyle b_{\nu ,n}(x)=0}$, om eller${\displaystyle \nu <0}$${\displaystyle \nu >n.}$
• ${\displaystyle b_{\nu ,n}(x)\geq 0}$för${\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}}$och var är Kronecker delta- funktionen:${\displaystyle b_{\nu ,n}(1)=\delta _{\nu ,n}}$${\displaystyle \delta }$${\displaystyle \delta _{ij}={\begin{cases}0&{\text{if }}i\neq j,\\1&{\text{if }}i=j.\end{cases}}}$
• ${\displaystyle b_{\nu ,n}(x)}$har en rot med multiplicitet vid punkt (obs: om , det finns ingen rot vid 0).${\displaystyle \nu }$${\displaystyle x=0}$${\displaystyle \nu =0}$
• ${\displaystyle b_{\nu ,n}(x)}$har en rot med multiplicitet vid punkt (obs: om , det finns ingen rot vid 1).${\displaystyle \left(n-\nu \right)}$${\displaystyle x=1}$${\displaystyle \nu =n}$
• Derivatan kan skrivas som en kombination av två polynom av lägre grad :
  $${\displaystyle b'_{\nu,n}(x)=n\left(b_{\nu -1,n-1}(x)-b_{\nu,n-1}(x)\höger) .}$$

  
• Den k -te derivatan vid 0:
  $${\displaystyle b_{\nu ,n}^{(k)}(0)={\frac {n!}{(nk)!}}{\binom {k}{\nu }}(-1)^ {\nu +k}.}$$

  
• Den k -te derivatan vid 1:
  $${\displaystyle b_{\nu ,n}^{(k)}(1)=(-1)^{k}b_{n-\nu ,n}^{(k)}(0).}$$

  
• Omvandlingen av Bernsteinpolynomet till monomial är
  $${\displaystyle b_{\nu ,n}(x)={\binom {n}{\nu }}\sum _{k=0}^{n-\nu }{\binom {n-\nu }{ k}}(-1)^{n-\nu -k}x^{\nu +k}=\summa _{\ell =\nu }^{n}{\binom {n}{\ell }} {\binom {\ell }{\nu }}(-1)^{\ell -\nu }x^{\ell },}$$

  
  och genom den inversa binomialtransformationen är den omvända transformationen
  $${\displaystyle x^{k}=\summa _{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 ,n}(x).}$$

  
• Den obestämda integralen ges av
  $${\displaystyle \int b_{\nu ,n}(x)\,dx={\frac {1}{n+1}}\sum _{j=\nu +1}^{n+1}b_{ j,n+1}(x).}$$

  
• Den bestämda integralen är konstant för ett givet n :
  $${\displaystyle \int _{0}^{1}b_{\nu,n}(x)\,dx={\frac {1}{n+1}}\quad \ \,{\text{för alla }}\nu =0,1,\dots ,n.}$$

  
• If , har då ett unikt lokalt maximum på intervallet vid . Detta maximum tar värdet${\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 \välj \nu }.}$$

  
• Bernsteins basispolynom av grad bildar en partition av enhet :${\displaystyle n}$
  $${\displaystyle \sum _{\nu =0}^{n}b_{\nu ,n}(x)=\summa _{\nu =0}^{n}{n \choose \nu }x^{ \nu }\left(1-x\right)^{n-\nu }=\left(x+\left(1-x\right)\right)^{n}=1.}$$

  
• Genom att ta förstaderivatan av , behandla som konstant och sedan ersätta värdet , kan det visas att${\displaystyle x}$${\displaystyle (x+y)^{n}}$${\displaystyle y}$${\displaystyle y=1-x}$
  $${\displaystyle \sum _{\nu =0}^{n}\nu b_{\nu,n}(x)=nx.}$$

  
• På liknande sätt visar andraderivatan av , med igen sedan ersatt , att${\displaystyle x}$${\displaystyle (x+y)^{n}}$${\displaystyle y}$${\displaystyle y=1-x}$
  $${\displaystyle \sum _{\nu =1}^{n}\nu (\nu -1)b_{\nu ,n}(x)=n(n-1)x^{2}.}$$

  
• Ett Bernstein-polynom kan alltid skrivas som en linjär kombination av polynom av högre grad:
  $${\displaystyle b_{\nu ,n-1}(x)={\frac {n-\nu}{n}}b_{\nu,n}(x)+{\frac {\nu +1}{ n}}b_{\nu +1,n}(x).}$$

  
• Utvidgningen av Chebyshev-polynomen av det första slaget till Bernstein-basen är
  $${\displaystyle T_{n}(u)=(2n-1)!!\sum _{k=0}^{n}{\frac {(-1)^{nk}}{(2k-1)! !(2n-2k-1)!!}}b_{k,n}(u).}$$

  

Ungefärlig kontinuerliga funktioner

Låt ƒ vara en kontinuerlig funktion på intervallet [0, 1]. Tänk på Bernstein-polynomet

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

Det kan man visa

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

likformigt på intervallet [0, 1].

Bernstein polynom ger alltså ett sätt att bevisa Weierstrass approximationssats att varje reellt värderad kontinuerlig funktion på ett reellt intervall [ a ,  b ] kan likformigt approximeras av polynomfunktioner över  . ${\displaystyle \mathbb {R} }$

Ett mer allmänt uttalande för en funktion med kontinuerlig k ^:te derivata är

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

där dessutom

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

är ett egenvärde för B _n ; motsvarande egenfunktion är ett polynom med graden  k .

Probabilistiskt bevis

Detta bevis följer Bernsteins ursprungliga bevis från 1912. Se även Feller (1966) eller Koralov & Sinai (2007).

Antag att K är en slumpvariabel fördelad som antalet framgångar i n oberoende Bernoulli-försök med sannolikhet x för framgång för varje försök; K har med andra ord en binomialfördelning med parametrarna n och  x . Då har vi förväntat värde och ${\displaystyle \operatörsnamn {\mathcal {E}} \left[{\frac {K}{n}}\right]=x\ }$

${\displaystyle p(K)={n \choose K}x^{K}\left(1-x\right)^{nK}=b_{K,n}(x)}$

Genom den svaga lagen om ett stort antal sannolikhetsteori ,

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

för varje δ  > 0. Dessutom gäller detta förhållande enhetligt i x , vilket kan ses av dess bevis via Chebyshevs olikhet , med hänsyn till att variansen av 1 ⁄ n  K , lika med 1 ⁄ n  x (1− x ), begränsas uppifrån av 1 ⁄ (4 n ) oavsett x .

Eftersom ƒ , som är kontinuerlig på ett slutet avgränsat intervall, måste vara likformigt kontinuerlig på det intervallet, drar man slutsatsen ett uttalande av formen

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

jämnt i x . Med hänsyn till att ƒ är avgränsad (på det givna intervallet) får man för förväntan

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

jämnt i x . För detta ändamål delar man summan för förväntan i två delar. På en del överstiger inte skillnaden ε ; denna del kan inte bidra med mer än ε . Å andra sidan överstiger skillnaden ε , men inte 2 M , där M är en övre gräns för | ƒ (x)|; denna del kan inte bidra med mer än 2 M gånger den lilla sannolikheten att skillnaden överstiger ε .

Slutligen observerar man att det absoluta värdet av skillnaden mellan förväntningar aldrig överstiger förväntan på det absoluta värdet av skillnaden, och

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

Elementärt bevis

Det sannolikhetsbeviset kan också omformuleras på ett elementärt sätt, med hjälp av de underliggande sannolikhetsidéerna men genom att fortsätta genom direkt verifiering:

Följande identiteter kan verifieras:

1. ${\displaystyle \sum _{k}{n \choose k}x^{k}(1-x)^{nk}=1}$("sannolikhet")
2. ${\displaystyle \sum _{k}{k \over n}{n \choose k}x^{k}(1-x)^{nk}=x}$("betyda")
3. ${\displaystyle \sum _{k}\left(x-{k \over n}\right)^{2}{n \choose k}x^{k}(1-x)^{nk}={x (1-x) \över n}.}$("variation")

I själva verket genom binomialsatsen

och denna ekvation kan tillämpas två gånger på . Identiteterna (1), (2) och (3) följer lätt med hjälp av substitutionen . ${\displaystyle t{\frac {d}{dt}}}$${\displaystyle t=x/(1-x)}$

Inom dessa tre identiteter, använd ovanstående baspolynomnotation

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

och låt

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

Således, genom identitet (1)

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

så att

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

Eftersom f är enhetligt kontinuerlig, givet , Det finns en sådan att närhelst . Dessutom, genom kontinuitet, . Men då ${\displaystyle \varepsilon >0}$${\displaystyle \delta >0}$${\displaystyle |f(a)-f(b)|<\varepsilon }$${\displaystyle |ab|<\delta }$${\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)+\summa _{|x-{k \över n}|\geq \delta }|f(k/n)-f(x)|\,b_{k, n}(x).}$

Den första summan är mindre än ε. Å andra sidan, av identitet (3) ovan, och sedan , begränsas den andra summan av 2 M gånger ${\displaystyle |xk/n|\geq \delta }$

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

( Chebyshevs ojämlikhet )

Därav följer att polynomen f _n tenderar att f likformigt.

Generaliseringar till högre dimension

Bernsteinpolynom kan generaliseras till k dimensioner – de resulterande polynomen har formen B _{i 1} ( x ₁ ) B _{i 2} ( x ₂ ) ... B _{i k} ( x _k ) . I det enklaste fallet beaktas endast produkter av enhetsintervallet [0,1] ; men med användning av affina transformationer av linjen kan Bernstein-polynom också definieras för produkter [ a ₁ , b ₁ ] × [ a ₂ , b ₂ ] × ... × [ a _k , b _k ] . För en kontinuerlig funktion f på den k -faldiga produkten av enhetsintervallet kan beviset på att f ( x ₁ , x ₂ , ... , x _k ) likformigt approximeras med

${\displaystyle \sum _{i_{1}}\sum _{i_{2}}\cdots \sum _{i_{k}}{n_{1} \choose i_{1}}{n_{2} \ välj i_{2}}\cdots {n_{k} \choose i_{k}}f\left({i_{1} \over n_{1}},{i_{2} \over n_{2}}, \dots ,{i_{k} \över 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}}}$

är en rak förlängning av Bernsteins bevis i en dimension.

Se även

• Polynominterpolation
• Newton form
• Lagrange form
• Binomial QMF (även känd som Daubechies wavelet )

Anteckningar

Referenser

• Bernstein, S. (1912), "Démonstration du théorème de Weierstrass fondée sur le calcul des probabilités (Bevis för Weierstrass teorem baserat på sannolikhetskalkylen)" (PDF) , Comm. Kharkov matte. Soc. , 13 : 1–2, Engelsk översättning
• Lorentz, GG (1953), Bernstein Polynomials , University of Toronto Press
• Akhiezer, NI (1956), Theory of approximation (på ryska), översatt av Charles J. Hyman, Frederick Ungar, s. 30–31, rysk upplaga publicerad första gången 1940
• Burkill, JC (1959), Lectures On Approximation By Polynomials (PDF) , Bombay: Tata Institute of Fundamental Research , s. 7–8
• Goldberg, Richard R. (1964), Metoder för verklig analys , John Wiley & Sons, s. 263–265
• Caglar, Håkan; Akansu, Ali N. (juli 1993). "En generaliserad parametrisk PR-QMF designteknik baserad på Bernstein polynom approximation". IEEE-transaktioner på signalbehandling . 41 (7): 2314–2321. Bibcode : 1993ITSP...41.2314C . doi : 10.1109/78.224242 . Zbl  0825.93863 .
• Korovkin, PP (2001) [1994], "Bernstein polynomials" , Encyclopedia of Mathematics , EMS Press
• Natanson, IP (1964). Konstruktiv funktionsteori. Volym I: Uniform approximation . Översatt av Alexis N. Obolensky. New York: Frederick Ungar. MR  0196340 . Zbl  0133.31101 .
• Feller, William (1966), An introduction to probability theory and its applications, Vol, II , John Wiley & Sons, s. 149–150, 218–222
• Beals, Richard (2004), Analys. An introduction , Cambridge University Press , s. 95–98, ISBN 0521600472

externa länkar

• Kac, Mark (1938). "Une remarque sur les polynomes de MS Bernstein" . Studia Mathematica . 7 : 49–51. doi : 10.4064/sm-7-1-49-51 .
• Kelisky, Richard Paul; Rivlin, Theodore Joseph (1967). "Iterativ av Bernstein-polynomer" . Pacific Journal of Mathematics . 21 (3): 511. doi : 10.2140/pjm.1967.21.511 .
• Stark, EL (1981). "Bernstein polynom, 1912-1955". I Butzer, PL (red.). ISNM60 . s. 443–461. doi : 10.1007/978-3-0348-9369-5_40 . ISBN 978-3-0348-9369-5.
• Petrone, Sonia (1999). "Slumpmässiga Bernstein-polynom". Scand. J. Stat . 26 (3): 373–393. doi : 10.1111/1467-9469.00155 . S2CID  122387975 .
• Oruc, Halil; Phillips, Geoerge M. (1999). "En generalisering av Bernstein-polynomen" . Proceedings of the Edinburgh Mathematical Society . 42 (2): 403–413. doi : 10.1017/S0013091500020332 .
• Joy, Kenneth I. (2000). "Bernstein Polynomials" (PDF) . Arkiverad från originalet (PDF) 2012-02-20 . Hämtad 2009-02-28 .från University of California, Davis . Notera felet i summeringsgränserna i den första formeln på sidan 9.
• Idrees Bhatti, M.; Bracken, P. (2007). "Lösningar av differentialekvationer i Bernstein-polynombas" . J. Comput. Appl. Matematik . 205 (1): 272–280. Bibcode : 2007JCoAM.205..272I . doi : 10.1016/j.cam.2006.05.002 .
• Casselman, Bill (2008). "Från Bézier till Bernstein" .Feature Column från American Mathematical Society
• Acikgoz, Mehmet; Araci, Serkan (2010). "Om genereringsfunktionen för Bernstein-polynom". AIP Conf. Proc . AIP Conference Proceedings. 1281 (1): 1141. Bibcode : 2010AIPC.1281.1141A . doi : 10.1063/1.3497855 .
• Doha, EH; Bhrawy, AH; Saker, MA (2011). "Integraler av Bernstein-polynom: En applikation för lösning av differentialekvationer med hög jämn ordning" . Appl. Matematik. Lett . 24 (4): 559–565. doi : 10.1016/j.aml.2010.11.013 .
• Farouki, Rida T. (2012). "The Bernstein polynomial base: a centennial retrospective". Comp. Hjälpa. Geom. Des . 29 (6): 379–419. doi : 10.1016/j.cagd.2012.03.001 .
• Chen, Xiaoyan; Tan, Jieqing; Liu, Zhi; Xie, Jin (2017). "Approximationer av funktioner av en ny familj av generaliserade Bernstein-operatörer" . J. Math. Ann. Applicera . 450 : 244–261. doi : 10.1016/j.jmaa.2016.12.075 .
• Weisstein, Eric W. "Bernstein Polynomial" . MathWorld .
• Den här artikeln innehåller material från egenskaperna hos Bernstein-polynomet på PlanetMath , som är licensierad under Creative Commons Attribution/Share-Alike-licensen .