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

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

الخوارزمية

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

ϕ_{k + 1} (x) + α_{k} (x) ϕ_{k} (x) + β_{k} (x) ϕ_{k - 1} (x) = 0,

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

\begin{array}{r} b_{n + 1} (x) & = b_{n + 2} (x) = 0, \\ [. 5 e m] b_{k} (x) & = c_{k} - α_{k} (x) b_{k + 1} (x) - β_{k + 1} b_{k + 2} (x) . \end{array}

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

\sum_{k = 0}^{n} c_{k} ϕ_{k} (x) = b_{0} (x) ϕ_{0} (x) + b_{1} (x) [ϕ_{1} (x) + α_{0} (x) ϕ_{0} (x)] .

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

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

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

α_{k} (x) = - 2 x, β_{k} = 1 .

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

\begin{array}{r} T_{0} (x) & = 1, T_{1} (x) = x T_{0} (x), \\ [. 5 e m] b_{0} (x) & = a_{0} + 2 x b_{1} (x) - b_{2} (x), \end{array}

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

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

^ C. W. Clenshaw، A note on the summation of Chebyshev series, Math. Tab. Wash. 9 (1955) pp 118--120.
^ L. Fox and I. B. Parker, Chebyshev Polynomials in Numerical Analysis, Oxford University Press (1968).