פולינומי ברנשטיין לקירוב עקומה
בתחום האנליזה הנומרית , פולינום ברנשטיין , הקרוי על שם ממציאו, סרגיי ברנשטיין , הוא פולינום בתצורת ברנשטיין, כלומר הוא מהווה צירוף ליניארי של פולינומי הבסיס של ברנשטיין.
דרך יציבה מבחינה נומרית להעריך פולינומים בתצורת ברנשטיין היא בעזרת אלגוריתם דה-קסטלז'ו .
פולינומים בתצורת ברנשטיין היו בשימוש לראשונה על ידי ברנשטיין, בהוכחה קונסטרוקטיבית למשפט הקירוב של סטון–ויירשטראס . עם כניסת הגרפיקה הממוחשבת , הפכו פולינומי ברנשטיין (על הקטע החסום
[
1
,
0
]
{\displaystyle [1,0]}
) לשימושיים וחשובים ביצירת עקומות בזייה .
n + 1 פולינומי הבסיס של ברנשטיין מדרגה n מוגדרים כך:
b
ν
,
n
(
x
)
=
(
n
ν
)
x
ν
(
1
−
x
)
n
−
ν
,
ν
=
0
,
…
,
n
.
{\displaystyle b_{\nu ,n}(x)={n \choose \nu }x^{\nu }\left(1-x\right)^{n-\nu },\quad \nu =0,\ldots ,n.}
כאשר
(
n
ν
)
{\displaystyle {n \choose \nu }}
הוא המקדם הבינומי .
פולינומי הבסיס של ברנשטיין מדרגה n יוצרים בסיס למרחב הווקטורי
Π
n
{\displaystyle \Pi _{n}}
של פולינומים בדרגה של לכל היותר n .
צירוף ליניארי של פולינומי הבסיס של ברנשטיין,
B
n
(
x
)
=
∑
ν
=
0
n
β
ν
b
ν
,
n
(
x
)
{\displaystyle B_{n}(x)=\sum _{\nu =0}^{n}\beta _{\nu }b_{\nu ,n}(x)}
נקרא פולינום ברנשטיין או פולינום בתצורת ברנשטיין מדרגה n . מקדמי
β
ν
{\displaystyle \beta _{\nu }}
נקראים מקדמי ברנשטיין או מקדמי בזייר .
מספר פולינומי הבסיס הראשונים של ברנשטיין הם:
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
)
=
2
x
(
1
−
x
)
,
b
2
,
2
(
x
)
=
x
2
b
0
,
3
(
x
)
=
(
1
−
x
)
3
,
b
1
,
3
(
x
)
=
3
x
(
1
−
x
)
2
,
b
2
,
3
(
x
)
=
3
x
2
(
1
−
x
)
,
b
3
,
3
(
x
)
=
x
3
b
0
,
4
(
x
)
=
(
1
−
x
)
4
,
b
1
,
4
(
x
)
=
4
x
(
1
−
x
)
3
,
b
2
,
4
(
x
)
=
6
x
2
(
1
−
x
)
2
,
b
3
,
4
(
x
)
=
4
x
3
(
1
−
x
)
,
b
4
,
4
(
x
)
=
x
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}\\b_{0,4}(x)&=(1-x)^{4},&b_{1,4}(x)&=4x(1-x)^{3},&b_{2,4}(x)&=6x^{2}(1-x)^{2},&b_{3,4}(x)&=4x^{3}(1-x),&b_{4,4}(x)&=x^{4}\end{aligned}}}
לפולינומי הבסיס של ברנשטיין התכונות הבאות:
b
ν
,
n
(
x
)
=
0
{\displaystyle b_{\nu ,n}(x)=0}
, אם
ν
<
0
{\displaystyle \nu <0}
או
ν
>
n
{\displaystyle \nu >n}
.
b
ν
,
n
(
0
)
=
δ
ν
,
0
{\displaystyle b_{\nu ,n}(0)=\delta _{\nu ,0}}
ו
b
ν
,
n
(
1
)
=
δ
ν
,
n
{\displaystyle b_{\nu ,n}(1)=\delta _{\nu ,n}}
כאשר
δ
{\displaystyle \delta }
היא הדלתא של קרונקר .
b
ν
,
n
(
x
)
{\displaystyle b_{\nu ,n}(x)}
יש שורש עם כפילות
ν
{\displaystyle \nu }
בנקודה
x
=
0
{\displaystyle x=0}
(הערה: אם
ν
=
0
{\displaystyle \nu =0}
, אין שורש ב-0).
b
ν
,
n
(
x
)
{\displaystyle b_{\nu ,n}(x)}
יש שורש עם כפילות
(
n
−
ν
)
{\displaystyle \left(n-\nu \right)}
בנקודה
x
=
1
{\displaystyle x=1}
(הערה: אם
ν
=
n
{\displaystyle \nu =n}
, אין שורש ב-1).
b
ν
,
n
(
x
)
≥
0
{\displaystyle b_{\nu ,n}(x)\geq 0}
עבור
x
∈
[
0
,
1
]
{\displaystyle x\in [0,\ 1]}
.
b
ν
,
n
(
1
−
x
)
=
b
n
−
ν
,
n
(
x
)
{\displaystyle b_{\nu ,n}\left(1-x\right)=b_{n-\nu ,n}(x)}
.
הנגזרת יכולה להיכתב כצירוף של שני פולינומים מדרגה נמוכה יותר:
b
ν
,
n
′
(
x
)
=
n
(
b
ν
−
1
,
n
−
1
(
x
)
−
b
ν
,
n
−
1
(
x
)
)
.
{\displaystyle b'_{\nu ,n}(x)=n\left(b_{\nu -1,n-1}(x)-b_{\nu ,n-1}(x)\right).}
האינטגרל קבוע עבור
n
{\displaystyle n}
נתון:
∫
0
1
b
ν
,
n
(
x
)
d
x
=
1
n
+
1
;
∀
ν
=
0
,
1
…
n
{\displaystyle \int _{0}^{1}b_{\nu ,n}(x)dx={\frac {1}{n+1}};\forall \nu =0,1\dots n}
אם
n
≠
0
{\displaystyle n\neq 0}
, אז
b
ν
,
n
(
x
)
{\displaystyle b_{\nu ,n}(x)}
בעל מקסימום ייחודי מקומי באינטרוול
[
0
,
1
]
{\displaystyle [0,\ 1]}
ב
x
=
ν
n
{\displaystyle x={\frac {\nu }{n}}}
. המקסימום הנ"ל בעל הערך:
ν
ν
n
−
n
(
n
−
ν
)
n
−
ν
(
n
ν
)
.
{\displaystyle \nu ^{\nu }n^{-n}\left(n-\nu \right)^{n-\nu }{n \choose \nu }.}
פולינומי הבסיס של ברנשטיין מדרגה
n
{\displaystyle n}
יוצרים חלוקת יחידה :
∑
ν
=
0
n
b
ν
,
n
(
x
)
=
∑
ν
=
0
n
(
n
ν
)
x
ν
(
1
−
x
)
n
−
ν
=
(
x
+
(
1
−
x
)
)
n
=
1.
{\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.}
אם לוקחים את האיבר הראשון של
(
x
+
y
)
n
{\displaystyle (x+y)^{n}}
כאשר
y
=
1
−
x
{\displaystyle y=1-x}
, ניתן להראות כי
∑
ν
=
0
n
ν
b
ν
,
n
(
x
)
=
n
x
{\displaystyle \sum _{\nu =0}^{n}\nu b_{\nu ,n}(x)=nx}
האיבר השני
(
x
+
y
)
n
{\displaystyle (x+y)^{n}}
כאשר
y
=
1
−
x
{\displaystyle y=1-x}
משמש להראות כי
∑
ν
=
1
n
ν
(
ν
−
1
)
b
ν
,
n
(
x
)
=
n
(
n
−
1
)
x
2
{\displaystyle \sum _{\nu =1}^{n}\nu (\nu -1)b_{\nu ,n}(x)=n(n-1)x^{2}}
A פולינום ברנשטיין ניתן להיכתב כקומבינציה ליניארית של פולינומים מדרגה גבוהה יותר:
b
ν
,
n
−
1
(
x
)
=
n
−
ν
n
b
ν
,
n
(
x
)
+
ν
+
1
n
b
ν
+
1
,
n
(
x
)
.
{\displaystyle b_{\nu ,n-1}(x)={\frac {n-\nu }{n}}b_{\nu ,n}(x)+{\frac {\nu +1}{n}}b_{\nu +1,n}(x).}
נניח ש-ƒ פונקציה רציפה בקטע [0,1]. נבחן את פולינום ברנשטיין להלן:
B
n
(
f
)
(
x
)
=
∑
ν
=
0
n
f
(
ν
n
)
b
ν
,
n
(
x
)
.
{\displaystyle B_{n}(f)(x)=\sum _{\nu =0}^{n}f\left({\frac {\nu }{n}}\right)b_{\nu ,n}(x).}
ניתן להראות כי:
lim
n
→
∞
B
n
(
f
)
(
x
)
=
f
(
x
)
{\displaystyle \lim _{n\to \infty }{B_{n}(f)(x)}=f(x)\,}
מתכנס במידה שווה בקטע [0,1].[ 1] זו הצהרה חזקה יותר מאשר ההנחה שהגבול קיים בנפרד בכל ערך של x ; זו תהיה התכנסות נקודתית במקום התכנסות במידה שווה. באופן ספציפי, המילים "במידה שווה" מציינות:
lim
n
→
∞
sup
{
|
f
(
x
)
−
B
n
(
f
)
(
x
)
|
:
0
≤
x
≤
1
}
=
0.
{\displaystyle \lim _{n\to \infty }\sup \left\{\,\left|f(x)-B_{n}(f)(x)\right|\,:\,0\leq x\leq 1\,\right\}=0.}
פולינומי ברנשטיין לכן מאפשרים דרך אחת להוכיח את משפט הקירוב של ויירשטראס שכל פונקציה רציפה ממשית על הקטע הממשי [a ,b ] ניתנת להערכה במידה שווה על ידי פונקציות פולינום מעל R .[ 2]
טענה כללית יותר על פונקציה שגזירה ברציפות k פעמים היא:
‖
B
n
(
f
)
(
k
)
‖
∞
≤
(
n
)
k
n
k
‖
f
(
k
)
‖
∞
and
‖
f
(
k
)
−
B
n
(
f
)
(
k
)
‖
∞
→
0
{\displaystyle {\left\|B_{n}(f)^{(k)}\right\|}_{\infty }\leq {\frac {(n)_{k}}{n^{k}}}\left\|f^{(k)}\right\|_{\infty }{\text{ and }}\left\|f^{(k)}-B_{n}(f)^{(k)}\right\|_{\infty }\to 0}
כאשר בנוסף
(
n
)
k
n
k
=
(
1
−
0
n
)
(
1
−
1
n
)
⋯
(
1
−
k
−
1
n
)
{\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 .
נניח ש-K משתנה מקרי המפוזר כמספר ההצלחות מתוך n ניסויי ברנולי בלתי תלויים, עם הסתברות x של הצלחה בכל ניסוי; במילים אחרות, k מתפלג בינומית עם פרמטרים n ו-x . מכאן שערך התוחלת
E
[
K
/
n
]
=
x
{\displaystyle E\left[K/n\right]=x}
.
בעזרת הגרסה החלשה של חוק המספרים הגדולים מתורת ההסתברות ,
lim
n
→
∞
P
(
|
K
n
−
x
|
>
δ
)
=
0
{\displaystyle \lim _{n\to \infty }{P\left(\left|{\frac {K}{n}}-x\right|>\delta \right)}=0}
לכל
δ
>
0
{\displaystyle \delta >0}
. יתרה מכך, הקשר מתקיים במידה שווה ב-x , כפי שניתן להראות מההוכחה בעזרת אי-שוויון צ'בישב , אם לוקחים בחשבון שהשונות של
K
/
n
{\displaystyle K/n}
, השווה ל-
x
(
1
−
x
)
/
n
{\displaystyle x(1-x)/n}
, חסומה מלמעלה על ידי
1
/
4
n
{\displaystyle 1/4n}
ללא תלות ב-x .
מכיוון ש-ƒ, הרציפה על תחום סגור וחסום, חייבת להיות רציפה במידה שווה על התחום, ניתן לנסח את הטענה כי
lim
n
→
∞
P
(
|
f
(
K
n
)
−
f
(
x
)
|
>
ε
)
=
0
{\displaystyle \lim _{n\to \infty }{P\left(\left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|>\varepsilon \right)}=0}
במידה שווה ב-x . אם לוקחים בחשבון ƒ חסום (בקטע נתון), ניתן לצפות ל:
lim
n
→
∞
E
(
|
f
(
K
n
)
−
f
(
x
)
|
)
=
0
{\displaystyle \lim _{n\to \infty }{E\left(\left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|\right)}=0}
במידה שווה ב-x . כאן אפשר לראות כי התוחלת מתחלקת לשני חלקים. בחלק אחד ההפרש אינו עולה על ε; חלק זה יכול לתרום יותר מאשר ε. בעל החלק השני ההפרש עולה על ε, אך אינו עולה על 2M , כאשר M מהווה חסם עליון ל-|(ƒ (x)|; חלק זה אינו יכול לתרום יותר מ-2M פעמים את ההסתברות הקטנה כי ההפרש גדול מ-ε.
לסיכום, ראינו כי הערך המוחלט של ההפרש בין התוחלות לא עולה אף פעם על התוחלת של הערך המוחלט של ההפרש, וכן כי
E
[
f
(
K
/
n
)
]
{\displaystyle E\left[f\left(K/n\right)\right]}
הוא בדיוק פולינום ברנשטיין
B
n
(
f
)
(
x
)
{\displaystyle B_{n}(f)(x)}
.
ראו לדוגמה.[ 3]