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

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

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

تعريف

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

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

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

مثال للتضمين

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

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

$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₀.

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

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

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

انظر أيضا

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