خوارزمية دي بور

في فرع التحليل العددي من الرياضيات ، تُعدّ خوارزمية دي بور ^{[ 1 ]} خوارزمية مستقرة عدديًا وذات زمن حسابي متعدد الحدود لتقييم منحنيات السبلاين في صيغة بي-سبلاين . وهي تعميم لخوارزمية دي كاستيلجو لمنحنيات بيزير . وقد ابتكر هذه الخوارزمية عالم الرياضيات الألماني الأمريكي كارل ر. دي بور . وقد طُوّرت صيغ مبسطة وأسرع من خوارزمية دي بور، إلا أنها تعاني من استقرار أقل نسبيًا. ^{[ 2 ] [ 3 ]}

يُقدَّم عرضٌ عامٌّ لـ B-splines في المقالة الرئيسية . هنا نناقش خوارزمية دي بور، وهي طريقة فعّالة ومستقرة عدديًا لتقييم منحنى السبلاين.${\displaystyle \mathbf {S} (x)}$في هذا المنصب${\displaystyle x}$المنحنى مُنشأ من مجموع دوال بي-سبلاين${\displaystyle B_{i,p}(x)}$مضروبًا في ثوابت قد تكون ذات قيم متجهة${\displaystyle \mathbf {c} _{i}}$وتسمى نقاط التحكم، $${\displaystyle \mathbf {S} (x)=\sum _{i}\mathbf {c} _{i}B_{i,p}(x).}$$ منحنيات بي-سبلاين من الرتبة${\displaystyle p+1}$هي دوال متعددة الحدود متصلة على أجزاء من الدرجة${\displaystyle p}$مُعرَّف على شبكة من العُقد${\displaystyle {t_{0},\dots ,t_{i},\dots ,t_{m}}}$(نستخدم دائمًا الفهارس التي تبدأ من الصفر فيما يلي). تستخدم خوارزمية دي بور O (p² ⁾ + O (p) من العمليات لتقييم منحنى السبلاين. ملاحظة: تستخدم المقالة الرئيسية حول B-splines والمنشورات الكلاسيكية ^{[ 1 ]} ترميزًا مختلفًا: يتم فهرسة B-spline على النحو التالي:${\displaystyle B_{i,n}(x)}$مع${\displaystyle n=p+1}$.

تتمتع دوال B-spline بدعم محلي، مما يعني أن كثيرات الحدود تكون موجبة فقط في نطاق مضغوط، وتساوي صفرًا في أي مكان آخر. وتوضح صيغة كوكس-دي بور التكرارية ^{[ 4 ] ذلك.}$${\displaystyle B_{i,0}(x):={\begin{cases}1&{\text{إذا كان }}\quad t_{i}\leq x<t_{i+1}\\0&{\text{فيما عدا ذلك}}\end{cases}}}$$$${\displaystyle B_{i,p}(x):={\frac {x-t_{i}}{t_{i+p}-t_{i}}}B_{i,p-1}(x)+{\frac {t_{i+p+1}-x}{t_{i+p+1}-t_{i+1}}}B_{i+1,p-1}(x).}$$

لنفترض أن المؤشر${\displaystyle k}$حدد فاصل العقدة الذي يحتوي على الموضع،${\displaystyle x\in [t_{k},t_{k+1})}$يمكننا أن نرى في صيغة التكرار أن دوال B-spline فقط هي التي تحتوي على${\displaystyle i=kp,\dots ,k}$تكون هذه القيم غير صفرية في هذه الفترة المحددة. وبالتالي، يختزل المجموع إلى: $${\displaystyle \mathbf {S} (x)=\sum _{i=kp}^{k}\mathbf {c} _{i}B_{i,p}(x).}$$

ويترتب على ذلك${\displaystyle i\geq 0}$الذي - التي${\displaystyle k\geq p}$وبالمثل، نرى في التكرار أن أعلى موقع للعقدة المستعلم عنها هو عند الفهرس${\displaystyle k+1+p}$هذا يعني أن أي فاصل عقدي${\displaystyle [t_{k},t_{k+1})}$والتي يجب أن تحتوي على الأقل على ما يلي، والتي يتم استخدامها فعليًا${\displaystyle p}$عقد إضافية قبل وبعد. في برنامج الحاسوب ، يتم تحقيق ذلك عادةً بتكرار موقع العقدة الأولى والأخيرة المستخدمة.${\displaystyle p}$مرات. على سبيل المثال، لـ${\displaystyle p=3}$ومواقع العقد الحقيقية${\displaystyle (0,1,2)}$، يقوم المرء بتعبئة متجه العقدة إلى${\displaystyle (0,0,0,0,1,2,2,2,2)}$.

باستخدام هذه التعريفات، يمكننا الآن وصف خوارزمية دي بور. لا تحسب الخوارزمية دوال بي-سبلاين.${\displaystyle B_{i,p}(x)}$مباشرة. بدلاً من ذلك، يتم التقييم${\displaystyle \mathbf {S} (x)}$من خلال صيغة تكرارية مكافئة.

يترك${\displaystyle \mathbf {d} _{i,r}}$كن نقاط تحكم جديدة مع${\displaystyle \mathbf {d} _{i,0}:=\mathbf {c} _{i}}$ل${\displaystyle i=kp,\dots ,k}$. ل${\displaystyle r=1,\dots ,p}$يتم تطبيق التكرار التالي: $${\displaystyle \mathbf {d} _{i,r}=(1-\alpha _{i,r})\mathbf {d} _{i-1,r-1}+\alpha _{i,r}\mathbf {d} _{i,r-1};\quad i=k-p+r,\dots ,k}$$$${\displaystyle \alpha _{i,r}={\frac {x-t_{i}}{t_{i+1+pr}-t_{i}}}.}$$

بمجرد اكتمال التكرارات، نكون قد حصلنا${\displaystyle \mathbf {S} (x)=\mathbf {d} _{k,p}}$وهذا يعني أن${\displaystyle \mathbf {d} _{k,p}}$هذه هي النتيجة المرجوة.

تُعد خوارزمية دي بور أكثر كفاءة من الحساب الصريح لـ B-splines${\displaystyle B_{i,p}(x)}$باستخدام صيغة كوكس دي بور التكرارية، لأنها لا تحسب الحدود التي من المضمون ضربها في الصفر.

الخوارزمية المذكورة أعلاه غير مُحسَّنة للتنفيذ على الحاسوب. فهي تتطلب ذاكرة لـ${\displaystyle (p+1)+p+\dots +1=(p+1)(p+2)/2}$نقاط تفتيش مؤقتة${\displaystyle \mathbf {d} _{i,r}}$تُكتب كل نقطة تحكم مؤقتة مرة واحدة بالضبط وتُقرأ مرتين. وذلك بعكس التكرار على${\displaystyle i}$(باستخدام العد التنازلي بدلاً من العد التصاعدي)، يمكننا تشغيل الخوارزمية بذاكرة تكفي فقط${\displaystyle p+1}$نقاط تحكم مؤقتة، عن طريق السماح${\displaystyle \mathbf {d} _{i,r}}$إعادة استخدام الذاكرة لـ${\displaystyle \mathbf {d} _{i,r-1}}$وبالمثل، لا توجد سوى قيمة واحدة لـ${\displaystyle \alpha }$يتم استخدامها في كل خطوة، لذلك يمكننا إعادة استخدام الذاكرة أيضًا.

علاوة على ذلك، من الأنسب استخدام فهرس يبدأ من الصفر${\displaystyle j=0,\dots ,p}$بالنسبة لنقاط التحكم المؤقتة. العلاقة بالمؤشر السابق هي${\displaystyle i=j+kp}$وبذلك نحصل على الخوارزمية المحسّنة:

يترك${\displaystyle \mathbf {d} _{j}:=\mathbf {c} _{j+kp}}$ل${\displaystyle j=0,\dots ,p}$كرر العملية لـ${\displaystyle r=1,\dots ,p}$: $${\displaystyle \mathbf {d} _{j}:=(1-\alpha _{j})\mathbf {d} _{j-1}+\alpha _{j}\mathbf {d} _{j};\quad j=p,\dots ,r\quad }$$$${\displaystyle \alpha _{j}:={\frac {x-t_{j+kp}}{t_{j+1+kr}-t_{j+kp}}}.}$$ لاحظ أنه يجب عدّ قيمة j تنازليًا. بعد اكتمال التكرارات، تكون النتيجة هي${\displaystyle \mathbf {S} (x)=\mathbf {d} _{p}}$.

الكود التالي في لغة برمجة بايثون هو تطبيق بسيط للخوارزمية المُحسَّنة.

دالة deBoor ( k : عدد صحيح , x : عدد صحيح , t , c , p : عدد صحيح ):"""يقيّم S(x). الحجج --------- k: فهرس فاصل العقدة الذي يحتوي على x. س: الموضع. t: مصفوفة من مواضع العقد، يجب حشوها كما هو موضح أعلاه. ج: مصفوفة من نقاط التحكم. p: درجة B-spline. """d = [ c [ j + k - p ] for j in range ( 0 , p + 1 )]for r in range ( 1 , p + 1 ):for j in range ( p , r - 1 , - 1 ):ألفا = ( س - ت [ ي + ك - ف ]) / ( ت [ ي + 1 + ك - ر ] - ت [ ي + ك - ف ])د [ ي ] = ( 1.0 - ألفا ) * د [ ي - 1 ] + ألفا * د [ ي ]إرجاع د [ ص ]

• خوارزمية دي كاستيلجو
• منحنى بيزير
• B-spline غير منتظم وعقلاني

• خوارزمية دي بور
• حساب ديبور-كوكس

• حزمة PPPACK : تحتوي على العديد من خوارزميات التجزئة الخطية بلغة فورتران
• مكتبة جنو العلمية : مكتبة مكتوبة بلغة C، تحتوي على مكتبة فرعية للخطوط المنحنية المنقولة من PPPACK
• SciPy : مكتبة بايثون، تحتوي على مكتبة فرعية scipy.interpolate مع دوال spline مبنية على FITPACK
• TinySpline : مكتبة C لإنشاء الدوال المنحنية مع غلاف C++ وروابط للغات C# و Java و Lua و PHP و Python و Ruby
• Einspline : مكتبة C لإنشاء منحنيات في بُعد واحد، وبُعدين، وثلاثة أبعاد مع أغلفة Fortran

المراجع

• كارل دي بور (2003). دليل عملي للشرائح، طبعة منقحة . سبرينغر-فيرلاغ. ISBN 0-387-95366-3.