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

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

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

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

حيث b هي متعددة الحدود لبيرنشتاين أساسية، تكون كثيرة الحدود عن نقطة t₀ قابلة للتقييم بفضل علاقة التكرار.

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

${\displaystyle \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}$

حينئذ، يكون تقييم ${\displaystyle B}$ عند نقطة ${\displaystyle t_{0))$ ممكناً في ${\displaystyle n}$ خطوة من الخوارزم. وتعطى النتيجة ${\displaystyle B(t_{0})}$ بالعلاقة:

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

بالإضافة لذلك، يمكن فصل منحنى بيزيه ${\displaystyle B}$عن نقطة ${\displaystyle t_{0))$ إلى منحنيين بنقطتي تحكم متتاليتين:

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

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

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

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)

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

${\displaystyle {\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₀ لتقييم كثيرة حدود بيرنستين، بإمكاننا استعمال قطري المخطط المثلثي لإنشاء قسمة كثيرة الحدود.

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

إلى

${\displaystyle 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}]}$

و

${\displaystyle 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 بمعاملات بيرنستين

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

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

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

عند النقطة t₀.

نستهل المعاودة بـ

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

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

وبالتكرار الثاني يتوقف الاستدعاء الذاتي مع

${\displaystyle {\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))}$

وهي كثيرة الحدود المتوقعة من الدرجة  n.

• منحنى بيزير
• مخطط هورنر
• خوارزم كلنشو

في كومنز صور وملفات عن: خوارزم دوكاستلجو

• بوابة خوارزميات
• بوابة رياضيات
• بوابة علم الحاسوب