المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)

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

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

تعريف[عدل]

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

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

حينئذ، يكون تقييم عند نقطة ممكناً في خطوة من الخوارزم. وتعطى النتيجة بالعلاقة:

بالإضافة لذلك، يمكن فصل منحنى بيزيه عن نقطة إلى منحنيين بنقطتي تحكم متتاليتين:

مثال للتضمين[عدل]

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

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)

ملاحظات[عدل]

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

عن وقع الاختيار عند نقطة t0 لتقييم كثيرة حدود بيرنستين، بإمكاننا استعمال قطري المخطط المثلثي لإنشاء قسمة كثيرة الحدود.

إلى

و

مثال[عدل]

نرغب بتقييم كثيرة حدود بيرنستين من الدرجة 2 بمعاملات بيرنستين

عند النقطة t0.

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

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

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

المصادر[عدل]

  • Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd. ISBN 1-56881-123-3

انظر أيضا[عدل]