خوارزمية دو كاستلجو

تصغير|200بك|يسار
في التحليل العددي، **خوارزمية دوكاستلجو** (نسبة إلى مبتكره بول دوكاستلجو)، هو طريقة تكرارية لتقييم كثيرات حدود في صورة بيرنستين أو منحنيات بيزير. يمكن استعمالها أيضاً في فصل منحنى بيزير مفرد إلى منحنيات بيزيرية عند قيمة وسيطة اختيارية.

بالرغم من بطء هذا الخوارزم مقارنة بالطريقة المباشرة إلّا أنه أكثر استقراراً عددياً.

## تعريف
لتكن كثيرة الحدود *B* في صورة بيرنستين من الدرجة *n*

:B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t),

حيث *b* هي متعددة الحدود لبيرنشتاين أساسية، تكون كثيرة الحدود عن نقطة *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)}

## مثال للتضمين

المثال التالي يتضمن خوارزم كاستلجو بلغة هاسكل:

```haskell
import Data.Array

deCasteljau::Array Int (Double,Double)->Double->(Double,Double)
deCasteljau controls t0=
 coefs!(0,n)
 where
   (c0,n)=bounds controls
   coefs=listArray ((0,0),(n,n)) $ map deCasteljau' [(i,j) | i<-[0..n], j<-[0..n]]

   deCasteljau' (i,0)
       | i>=c0 = controls!i 
       | otherwise = 0
   deCasteljau' (i,j) =
       let (x0,y0)=coefs!(i,j-1)
           (x1,y1)=coefs!(i+1, j-1)
       in ((1-t0)*x0 + t0*x1, (1-t0)*y0 + t0*y1)
```


## ملاحظات
عند تنفيذ الحسابات يدوياً سيكون من الأجدر تدوين المعاملات في مخطط مثلثي كما يلي

:
\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_{n-i}^{(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}


وهي كثيرة الحدود المتوقعة من الدرجة &nbsp;*n*.
## انظر أيضا
* منحنى بيزير
* مخطط هورنر
* خوارزم كلنشو

تصنيف:تحليل عددي
تصنيف:شريحة