خوارزم كلنشو

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

الخوارزم

بفرض أن $ϕ_{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{aligned} b_{n + 1} (x) & = b_{n + 2} (x) = 0, \\ b_{k} (x) & = c_{k} - α_{k} (x) b_{k + 1} (x) - β_{k + 1} b_{k + 2} (x) . \end{aligned}

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

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

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

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

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{aligned} T_{0} (x) & = 1, T_{1} (x) = x T_{0} (x), \\ b_{0} (x) & = a_{0} + 2 x b_{1} (x) - b_{2} (x), \end{aligned}

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

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).