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

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

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

تعريف

لتكن كثيرة الحدود 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)}}$

مثال للتضمين

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

ملاحظات

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

${\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.

المصادر

• Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd.

مقالات ذات صلة

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

موسوعات ذات صلة :

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