Математика / Интерполяция

Схема Кленшоу для суммы полиномов Чебышёва

Схема Кленшоу вычисляет конечную сумму S(x)=c₀+ΣcₖTₖ(x) обратной рекурсией. Вместо отдельного построения всех полиномов она хранит два соседних состояния и объединяет вычисление базисных функций с суммированием.

Опубликовано: 31 октября 2026 г.Обновлено: 31 октября 2026 г.

Формула

b_{n+1}=b_{n+2}=0,\quad b_k=c_k+2xb_{k+1}-b_{k+2},\quad S=c_0+xb_1-b_2

Схема Проверочный ряд S=1+2T₁+3T₂

Ряд равен 6x²+2x−2; точка (0,5;0,5) соответствует вычислению рекурсией Кленшоу.

Обозначения

$x$: стандартная координата аргумента, безразмерная
$c_k$: коэффициенты суммы без половинного веса c₀, единица S
$b_k$: вспомогательные состояния обратной рекурсии, единица S
$n$: наибольший индекс полинома, безразмерная

Условия применения

Должны быть известны коэффициенты c₀,…,cₙ и соглашение об их нормировке. В показанной записи постоянное слагаемое равно c₀, без множителя 1/2. Рекурсию выполняют для k=n,n−1,…,1, после чего отдельно вычисляют S=c₀+xb₁−b₂.

Ограничения

Схема оценивает заданный конечный ряд и не доказывает точность самого приближения функции. За пределами [−1;1] полиномы Чебышёва могут быстро расти, поэтому возможны большие промежуточные значения и потеря точности. При n=0 результат равен c₀ и отдельная рекурсия не нужна.

Подробное объяснение

Полиномы первого рода удовлетворяют соотношению Tₖ₊₁(x)=2xTₖ(x)−Tₖ₋₁(x). Если вычислять их слева направо и затем умножать на коэффициенты, приходится явно работать со всеми базисными значениями. Кленшоу использует ту же трёхчленную связь в обратном направлении, собирая вклад старших коэффициентов в два состояния bₖ₊₁ и bₖ₊₂.

Начальные bₙ₊₁=bₙ₊₂=0 означают отсутствие членов за концом конечного ряда. На каждом шаге появляется новый cₖ, а накопленные состояния переносятся по правилу bₖ=cₖ+2xbₖ₊₁−bₖ₊₂. Важно двигаться от n к 1: прямой проход с такими начальными данными вычислял бы другую последовательность.

Последняя строка отличается от внутреннего шага. Поскольку T₀=1 и T₁=x, окончательная сумма равна c₀+xb₁−b₂, а не c₀+2xb₁−b₂. Проверка на ряде из двух членов сразу обнаруживает лишний множитель два. В справочниках встречается ряд c₀/2+ΣcₖTₖ; там постоянная часть в финале тоже делится на два.

Стоимость одного значения линейна по числу коэффициентов, а рабочая память постоянна, если не сохранять промежуточные bₖ. Это алгоритм вычисления уже известного полинома, а не способ получить коэффициенты из наблюдений. Ошибку аппроксимации функции и округление при вычислении суммы следует оценивать отдельно. Для физического аргумента сначала выполняют перенос на стандартную координату x.

Как пользоваться формулой

Уточните, записан ли постоянный член как c₀ или c₀/2, и приведите коэффициенты к одному соглашению.
Перенесите физический аргумент на стандартный отрезок, если коэффициенты были получены для координаты x∈[−1;1].
Задайте два нулевых состояния bₙ₊₁ и bₙ₊₂, затем пройдите индексы от n до 1 включительно.
На каждом шаге сохраните старые состояния и вычислите cₖ+2xbₖ₊₁−bₖ₊₂ без перестановки индексов.
Вычислите финальное c₀+xb₁−b₂ и сравните с прямой суммой для короткого контрольного ряда.

Историческая справка

Чарльз Кленшоу опубликовал работу A note on the summation of Chebyshev series в 1955 году в журнале Mathematical Tables and Other Aids to Computation, том 9, страницы 118–120. Предметом статьи было экономное вычисление чебышёвских разложений. Такая постановка естественна для вычислительной математики: после получения коэффициентов таблица или программа должна многократно возвращать значения функции, не строя полином в обычных степенях заново.

Схема стала стандартным примером использования трёхчленной рекурсии для обратного суммирования. В NIST DLMF раздел о методах приближения отдельно описывает суммирование рядов Чебышёва алгоритмом Кленшоу. Современная запись часто сокращает вычисление до двух изменяемых переменных, но сохраняет исходную идею и требует осторожности с весом постоянного коэффициента. Эта нормировка объясняет различия внешне похожих формул в разных библиотеках.

Историческая линия формулы

Алгоритм обратного суммирования рядов Чебышёва связывают с работой Чарльза Кленшоу 1955 года. Само семейство полиномов и их рекуррентное соотношение появились раньше; авторство схемы вычисления не следует переносить на эти математические объекты.

Пример

Пусть S(x)=1+2T₁(x)+3T₂(x), x=0,5. Коэффициенты: c₀=1, c₁=2, c₂=3, n=2; все величины безразмерны. Начинаем с b₃=b₄=0. При k=2 получаем b₂=3; при k=1 — b₁=2+2·0,5·3−0=5. Финальная строка даёт S=1+0,5·5−3=0,5. Независимая прямая проверка: T₁(0,5)=0,5, T₂(0,5)=2·0,5²−1=−0,5, поэтому 1+2·0,5+3·(−0,5)=0,5. Если ошибочно применить внутреннюю рекурсию и к постоянному члену без поправки, получится другое число. При вычислении этого же ряда в x=1 ответ равен 6, поскольку Tₖ(1)=1 для всех k. Здесь все коэффициенты и результат безразмерны.

Частая ошибка

Не смешивайте коэффициенты рядов с c₀ и c₀/2: разница не исчезает после рекурсии. Не заменяйте xb₁ в финале на 2xb₁. Не начинайте проход с первого коэффициента при нулевых старших состояниях. Не принимайте малую ошибку суммирования за гарантию качества приближения исходной функции.

Практика

Задачи с решением

Проверка знака

Условие. Вычислите S=2−T₁+4T₂ при x=0.

Решение. b₃=b₄=0; b₂=4; b₁=−1. Финал: S=2+0·(−1)−4=−2. Прямо: T₁(0)=0, T₂(0)=−1.

Ответ. S(0)=−2.

Ряд третьей степени

Условие. Найдите T₃(0,5) с помощью схемы, если c₃=1, остальные коэффициенты нулевые.

Решение. b₅=b₄=0; b₃=1; b₂=1; b₁=1−1=0. S=0+0,5·0−1=−1. Проверка: 4·0,5³−3·0,5=−1.

Ответ. T₃(0,5)=−1.

Дополнительные источники

https://dlmf.nist.gov/3.11
https://doi.org/10.1090/S0025-5718-1955-0071856-0
https://dlmf.nist.gov/18.5#E1

Связанные формулы

Математика

Узлы Чебышёва: выбор точек для интерполяции

$x_k=\frac{a+b}{2}+\frac{b-a}{2}\cos\frac{(2k+1)\pi}{2n},\quad k=0,\ldots,n-1$

Узлы Чебышёва — неравномерные точки, сгущённые около концов отрезка. Корни полинома Tₙ дают удобную сетку для интерполяционного полинома степени не выше n−1 и уменьшают наибольший модуль узлового произведения.

Математика

Барицентрическая интерполяция: веса и вычисление полинома

$P(x)=\frac{\sum_{k=0}^{n}\dfrac{w_ky_k}{x-x_k}}{\sum_{k=0}^{n}\dfrac{w_k}{x-x_k}},\qquad w_k=\frac{1}{\prod_{j\ne k}(x_k-x_j)},\quad x\ne x_k$

Барицентрическая форма вычисляет полином Лагранжа через заранее рассчитанные веса узлов. Она удобна для множества запросов по одной таблице; при точном совпадении аргумента с узлом нужно сразу вернуть узловое значение.

Математика

Интерполяция Лагранжа: полином через заданные точки

$P_n(x)=\sum_{k=0}^{n}y_kL_k(x),\qquad L_k(x)=\prod_{\substack{0\leq j\leq n\\j\ne k}}\frac{x-x_j}{x_k-x_j}$

Формула Лагранжа строит полином степени не выше n по n+1 различным узлам. Каждый базисный множитель выбирает значение своего узла и обращает вклады остальных узлов в ноль.