אלגוריתם דה-קסטלז'ו

באנליזה נומרית, אלגוריתם דה-קַסְטַלְז'וּ מתאר שיטה רקורסיבית כדי להעריך פולינום ברנשטיין או עקומות בזייר, הקרויה על שם ממציאהּ, פול-דה-קסטלז'ו. אלגוריתם דה-קסטלז'ו יכול לשמש גם כדי לפצל עקומת בזייר יחידה לשתי עקומות בזייר בעזרת פרמטר בעל ערך שרירותי.

למרות שהוא איטי יותר במרבית הארכיטקטורות בהשוואה לגישה הישירה, הוא יציב יותר מבחינה נומרית.

הגדרה

עקומת בזייר B (בדרגה n, עם נקודות הבקרה $\beta _{0},\ldots ,\beta _{n}$) יכולה להיות כתובים בעזרת פולינומי ברנשטיין כדלקמן

$B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t)$,

כאשר b הוא פולינום בסיס מתצורת ברנשטיין

$b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}$.

העקומה בנקודה t₀ ניתנת להערכה בעזרת נוסחת נסיגה

$\beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,n$

$\beta _{i}^{(j)}:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{(j-1)}t_{0}{\mbox{ , }}i=0,\ldots ,n-j{\mbox{ , }}j=1,\ldots ,n$

אז, $B$ בנקודה $t_{0}$ יכול להיות מוערך ב $n$ השלבים של האלגוריתם. התוצאה $B(t_{0})$ נתונה על ידי:

$B(t_{0})=\beta _{0}^{(n)}.$

יתר על כן, עקומת בזייר $B$ יכולה להתפצל בנקודה $t_{0}$ לשתי עקומות עם נקודות בקרה, בהתאמה:

$\beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}$

$\beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}$

הערות

כאשר עושים את החישוב באופן ידני, שימושי לכתוב את המקדמים במשולש כ:

${\begin{matrix}\beta _{0}&=\beta _{0}^{(0)}&&&\\&&\beta _{0}^{(1)}&&\\\beta _{1}&=\beta _{1}^{(0)}&&&\\&&&\ddots &\\\vdots &&\vdots &&\beta _{0}^{(n)}\\&&&&\\\beta _{n-1}&=\beta _{n-1}^{(0)}&&&\\&&\beta _{n-1}^{(1)}&&\\\beta _{n}&=\beta _{n}^{(0)}&&&\\\end{matrix}}$

בעת בחירת נקודה t₀ כדי להעריך את פולינום ברנשטיין אנחנו יכולים להשתמש בשני האלכסונים של המשולש כדי לבנות חלוקה של פולינום

$B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t){\mbox{ , }}\qquad t\in [0,1]$

ל:

$B_{1}(t)=\sum _{i=0}^{n}\beta _{0}^{(i)}b_{i,n}\left({\frac {t}{t_{0}}}\right){\mbox{ , }}\qquad t\in [0,t_{0}]$

ו

$B_{2}(t)=\sum _{i=0}^{n}\beta _{i}^{(n-i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right){\mbox{ , }}\qquad t\in [t_{0},1]$

דוגמה

אנחנו רוצים להעריך את פולינום ברנשטיין מדרגה 2 עם מקדמי ברנשטיין

$\beta _{0}^{(0)}=\beta _{0}$

$\beta _{1}^{(0)}=\beta _{1}$

$\beta _{2}^{(0)}=\beta _{2}$

בנקודה t₀

אנחנו מתחילים את הרקורסיה עם

$\beta _{0}^{(1)}=\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}=\beta _{0}(1-t_{0})+\beta _{1}t_{0}$

$\beta _{1}^{(1)}=\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}=\beta _{1}(1-t_{0})+\beta _{2}t_{0}$

עם איטרציה שנייה הרקורסיה מפסיקה עם

${\begin{aligned}\beta _{0}^{(2)}&=\beta _{0}^{(1)}(1-t_{0})+\beta _{1}^{(1)}t_{0}\\\ &=\beta _{0}(1-t_{0})(1-t_{0})+\beta _{1}t_{0}(1-t_{0})+\beta _{1}(1-t_{0})t_{0}+\beta _{2}t_{0}t_{0}\\\ &=\beta _{0}(1-t_{0})^{2}+\beta _{1}2t_{0}(1-t_{0})+\beta _{2}t_{0}^{2}\end{aligned}}$

אשר הוא הפולינום ברנשטיין הצפוי מדרגה 2.

עקומת בזייר

בעת הערכת עקומת בזייר מדרגה n במרחב 3-ממדי עם n+1 נקודות בקרה, Pi

$\mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]$

עם

$\mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}}$.

אנחנו מחלקים את עקומת בזייר לשלוש משוואות נפרדות.

$B_{1}(t)=\sum _{i=0}^{n}x_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]$

$B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]$

$B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]$

אשר אנו מעריכים בנפרד באמצעות האלגוריתם של דה-קסטלז'ו.

פרשנות גאומטרית

האינטרפולציה הגאומטרית של דה-קסטלז'ו הוא ברור וישיר.

• נניח עקומת בזייר עם נקודות בקרה $\scriptstyle P_{0},...,P_{n}$. אם נחבר נקודות ברצף אנחנו יוצרים את פוליגון הבקרה של העקומה.
• מחלקים עכשיו כל מקטע של הפוליגון עם יחס $\scriptstyle t:(1-t)$ ומחברים את הנקודות המתקבלות. בדרך זו, מגיעים לפוליגון חדש עם מקטע אחד פחות.
• חוזרים על התהליך עד שמגיעים לנקודה אחת - זו הנקודה של העקומה המתאימה לפרמטר $\scriptstyle t$.

התמונה הבאה מראה את התהליך הזה עבור עקומת בזייר מעוקבת:

יש לשים לב כי נקודות הביניים שנבנו הן למעשה נקודות בקרה עבור שתי עקומות בזייר החדשות שנוצרו, שתיהן בדיוק מתואמות עם הקודמת. אלגוריתם זה לא רק מעריך את העקומה ב- $\scriptstyle t$, אלא גם מפצל את העקומה לשתי חתיכות ב-$\scriptstyle t$, ומספק את המשוואות של שתי תת-עקומות בזייר שנוצרו.

הפרשנות שניתנה לעיל תקפה לעקומת בזייר אי-אציונאליות. כדי להעריך עקומת בזייר רציונלית ב $\scriptstyle \mathbf {R} ^{n}$, אנו יכולים להטיל את הנקודה לתוך $\scriptstyle \mathbf {R} ^{n+1}$; למשל, עקומה בשלושה ממדים עשויה לקבל את נקודות הבקרה $\scriptstyle \{(x_{i},y_{i},z_{i})\}$ ומשקולות $\scriptstyle \{w_{i}\}$ מוטלת לנקודות הבקרה המשוקללות $\scriptstyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}$. האלגוריתם ממשיך כרגיל, מבצע אינטרפולציה ב $\scriptstyle \mathbf {R} ^{4}$. התוצאה של נקודות ארבעה-ממדיות עשויות להיות מוטלות בחזרה לתוך מרחב תלת־ממדי עם מטריצת מעבר כלשהי.

באופן כללי, פעולות על עקומה רציונלית (או משטח) שוות ערך ל פעולות על עקומה לא-רציונלית במרחב פרויקטיבי. ייצוג זה כ"נקודות בקרה משוקללות" ומשקולות הוא לעיתים קרובות נוח בעת הערכת עקומות רציונליות.

ראו גם

• עקומות בזייר
• פולינומי צ'בישב

קישורים חיצוניים

מדיה וקבצים בנושא אלגוריתם דה-קסטלז'ו בוויקישיתוף