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

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

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

## הגדרה
עקומת בזייר *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*0 ניתנת להערכה בעזרת נוסחת נסיגה
: \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*0 כדי להעריך את פולינום ברנשטיין אנחנו יכולים להשתמש בשני האלכסונים של המשולש כדי לבנות חלוקה של פולינום
: 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*0

אנחנו מתחילים את הרקורסיה עם
: \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{align}
\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{align}

אשר הוא הפולינום ברנשטיין הצפוי מדרגה&#x20;*2*.

## עקומת בזייר
בעת הערכת עקומת בזייר מדרגה *n* במרחב 3-ממדי עם *n*+1 נקודות בקרה, **P**i
: \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.
התמונה הבאה מראה את התהליך הזה עבור עקומת בזייר מעוקבת:

קובץ:DeCasteljau1.svg

יש לשים לב כי נקודות הביניים שנבנו הן למעשה נקודות בקרה עבור שתי עקומות בזייר החדשות שנוצרו, שתיהן בדיוק מתואמות עם הקודמת. אלגוריתם זה לא רק מעריך את העקומה ב- \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_ix_i, w_iy_i, w_iz_i, w_i)\}. האלגוריתם ממשיך כרגיל, מבצע אינטרפולציה ב \scriptstyle \mathbf{R}^4. התוצאה של נקודות ארבעה-ממדיות עשויות להיות מוטלות בחזרה לתוך מרחב תלת־ממדי עם מטריצת מעבר כלשהי.

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

## ראו גם
* עקומות בזייר
* פולינומי צ'בישב
## קישורים חיצוניים

קטגוריה:אנליזה נומרית