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

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

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

== הגדרה ==
עקומת בזייר ''B'' (בדרגה ''n'', עם נקודות הבקרה <math>\beta_0, \ldots, \beta_n</math>) יכולה להיות כתובים בעזרת פולינומי ברנשטיין כדלקמן
: <math>B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t) </math>,
כאשר ''b'' הוא פולינום בסיס מתצורת [[פולינום ברנשטיין|ברנשטיין]]
: <math> b_{i,n}(t) = {n \choose i}(1-t)^{n-i}t^i</math>.
העקומה בנקודה ''t''<sub>0</sub> ניתנת להערכה בעזרת [[נוסחת נסיגה]]
: <math>\beta_i^{(0)} := \beta_i \mbox{ , } i=0,\ldots,n</math>
: <math>\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</math>
אז, <math>B</math> בנקודה <math>t_0</math> יכול להיות מוערך ב <math>n</math> השלבים של האלגוריתם. התוצאה <math>B(t_0)</math> נתונה על ידי:
: <math>B(t_0)=\beta_0^{(n)}.</math>
יתר על כן, עקומת בזייר <math>B</math> יכולה להתפצל בנקודה <math>t_0</math> לשתי עקומות עם נקודות בקרה, בהתאמה:
: <math>\beta_0^{(0)},\beta_0^{(1)},\ldots,\beta_0^{(n)}</math>
: <math>\beta_0^{(n)},\beta_1^{(n-1)},\ldots,\beta_n^{(0)}</math>

== הערות ==
כאשר עושים את החישוב באופן ידני, שימושי לכתוב את המקדמים במשולש כ:
: <math>
\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}
</math>
בעת בחירת נקודה ''t''<sub>0</sub> כדי להעריך את פולינום ברנשטיין אנחנו יכולים להשתמש בשני האלכסונים של המשולש כדי לבנות חלוקה של פולינום
: <math>B(t) = \sum_{i=0}^n \beta_i^{(0)} b_{i,n}(t) \mbox{ , } \qquad t \in [0,1]</math>
ל:
: <math>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]</math>
ו
: <math>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]</math>

== דוגמה ==
אנחנו רוצים להעריך את פולינום ברנשטיין מדרגה 2 עם מקדמי ברנשטיין
: <math>\beta_0^{(0)} = \beta_0</math>
: <math>\beta_1^{(0)} = \beta_1</math>
: <math>\beta_2^{(0)} = \beta_2</math>
בנקודה ''t''<sub>0</sub>

אנחנו מתחילים את הרקורסיה עם
: <math>\beta_0^{(1)} = \beta_0^{(0)} (1-t_0) + \beta_1^{(0)}t_0 = \beta_0(1-t_0) + \beta_1 t_0</math>
: <math>\beta_1^{(1)} = \beta_1^{(0)} (1-t_0) + \beta_2^{(0)}t_0 = \beta_1(1-t_0) + \beta_2 t_0</math>
עם איטרציה שנייה הרקורסיה מפסיקה עם
: <math> 
\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}
</math>
אשר הוא הפולינום ברנשטיין הצפוי מדרגה&#x20;''2''.

== עקומת בזייר ==
בעת הערכת עקומת בזייר מדרגה ''n'' במרחב 3-ממדי עם ''n''+1 נקודות בקרה, '''P'''i
: <math>\mathbf{B}(t) = \sum_{i=0}^{n} \mathbf{P}_i b_{i,n}(t) \mbox{ , } t \in [0,1]</math>
עם
: <math>\mathbf{P}_i := 
\begin{pmatrix} 
x_i \\ 
y_i \\
z_i 
\end{pmatrix}
</math>.
אנחנו מחלקים את עקומת בזייר לשלוש משוואות נפרדות.
: <math>B_1(t) = \sum_{i=0}^{n} x_i b_{i,n}(t) \mbox{ , } t \in [0,1]</math>
: <math>B_2(t) = \sum_{i=0}^{n} y_i b_{i,n}(t) \mbox{ , } t \in [0,1]</math>
: <math>B_3(t) = \sum_{i=0}^{n} z_i b_{i,n}(t) \mbox{ , } t \in [0,1]</math>
אשר אנו מעריכים בנפרד באמצעות האלגוריתם של דה-קסטלז'ו.

== פרשנות גאומטרית ==
האינטרפולציה הגאומטרית של דה-קסטלז'ו הוא ברור וישיר.
* נניח עקומת בזייר עם נקודות בקרה <math>\scriptstyle P_0,...,P_n</math>. אם נחבר נקודות ברצף אנחנו יוצרים את פוליגון הבקרה של העקומה.
* מחלקים עכשיו כל מקטע של הפוליגון עם יחס <math>\scriptstyle t : (1-t)</math> ומחברים את הנקודות המתקבלות. בדרך זו, מגיעים לפוליגון חדש עם מקטע אחד פחות.
* חוזרים על התהליך עד שמגיעים לנקודה אחת - זו הנקודה של העקומה המתאימה לפרמטר <math>\scriptstyle t</math>.
התמונה הבאה מראה את התהליך הזה עבור עקומת בזייר מעוקבת:

[[קובץ:DeCasteljau1.svg]]

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

הפרשנות שניתנה לעיל תקפה לעקומת בזייר אי-אציונאליות. כדי להעריך עקומת בזייר רציונלית ב <math>\scriptstyle \mathbf{R}^n</math>, אנו יכולים להטיל את הנקודה לתוך <math>\scriptstyle \mathbf{R}^{n+1}</math>; למשל, עקומה בשלושה ממדים עשויה לקבל את נקודות הבקרה <math>\scriptstyle \{(x_i, y_i, z_i)\}</math> ומשקולות <math>\scriptstyle \{w_i\}</math> מוטלת לנקודות הבקרה המשוקללות <math>\scriptstyle \{(w_ix_i, w_iy_i, w_iz_i, w_i)\}</math>. האלגוריתם ממשיך כרגיל, מבצע [[אינטרפולציה]] ב <math>\scriptstyle \mathbf{R}^4</math>. התוצאה של נקודות ארבעה-ממדיות עשויות להיות מוטלות בחזרה לתוך מרחב תלת־ממדי עם [[מטריצת מעבר]] כלשהי.

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

== ראו גם ==
* [[עקום בזייה|עקומות בזייר]]
* [[פולינומי צ'בישב]]
==קישורים חיצוניים==
{{ויקישיתוף בשורה}}

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