خوارزمية كلنشو

في التحليل العددي، خوارزمية كلنشو (بالإنجليزية: Clenshaw algorithm)‏ هي طريقة ذاتية الاستدعاء لتقييم توافقات خطية من كثيرات حدود شيبيشيف. يمكن تطبيقها عموماً على أي نوع من كثيرات الحدود التي يمكن تعريفها بعلاقة تكرارية ثلاثية الحدود.

الخوارزمية

بفرض أن $\phi _{k},\;k=0,1,\ldots$ دوال متعاقبة تحقق العلاقة التكرارية

$\phi _{k+1}(x)+\alpha _{k}(x)\,\phi _{k}(x)+\beta _{k}(x)\,\phi _{k-1}(x)=0,$

حيث إن المعاملات $\alpha _{k}$ و$\beta _{k}$ هي معلومة مسبقاً. لأي تعاقب محدود $c_{0},\ldots ,c_{n}$، تعرف الدوال $b_{k}$ بواسطة صيغة التكرار العكسي:

${\begin{aligned}b_{n+1}(x)&=b_{n+2}(x)=0,\\[.5em]b_{k}(x)&=c_{k}-\alpha _{k}(x)\,b_{k+1}(x)-\beta _{k+1}\,b_{k+2}(x).\end{aligned}}$

التوافق الخطي $\phi _{k}$ يحقق العلاقة:

$\sum _{k=0}^{n}c_{k}\phi _{k}(x)=b_{0}(x)\phi _{0}(x)+b_{1}(x)\left[\phi _{1}(x)+\alpha _{0}(x)\phi _{0}(x)\right].$

طالع فوكس وباركر لمعلومات أوفر عنها وعن تحليل الاستقرارية.

حالة خاصة لمتسلسلة شيبيشيف

لتكن متسلسلة شيبيشيف المختصرة

$p_{n}(x)={\frac {a_{0}}{2}}+a_{1}T_{1}(x)+a_{2}T_{2}(x)+\cdots +a_{n}T_{n}(x).$

تكون المعاملات في الصيغة التكرارية من كثيرات حدود شيبيشيف

$\alpha _{k}(x)=-2x,\quad \beta _{k}=1.$

بالتالي، بالاستعانة بالمطابقات

${\begin{aligned}T_{0}(x)&=1,\quad T_{1}(x)=xT_{0}(x),\\[.5em]b_{0}(x)&=a_{0}+2xb_{1}(x)-b_{2}(x),\end{aligned}}$

يمكن اختصار خوارزم كلنشو إلى:

$p_{n}(x)={\frac {1}{2}}\left[b_{0}(x)-b_{2}(x)\right].$

انظر أيضا

• مخطط هورنر لتقييم متعددات الحدود في
• خوارزم دو كاستلجو لتقييم متعددة حدود في