В численном анализе , то Clenshaw алгоритм , называемый также Clenshaw суммированием , является рекурсивным методом оценки линейной комбинации полиномов Чебышева . Метод был опубликован Чарльзом Уильямом Кленшоу в 1955 году. Это обобщение метода Хорнера для вычисления линейной комбинации мономов .
Он обобщается не только на многочлены Чебышева; он применяется к любому классу функций, который может быть определен трехчленным рекуррентным соотношением .
Алгоритм Кленшоу
В общем, алгоритм Кленшоу вычисляет взвешенную сумму конечного ряда функций :
где - последовательность функций, удовлетворяющих линейному рекуррентному соотношению
где коэффициенты и известны заранее.
Алгоритм является наиболее полезным , когда функции , которые осложнены непосредственно вычислить, но и являются особенно просто. В наиболее распространенных приложениях не зависит и является константой, которая не зависит ни от, ни .
Чтобы произвести суммирование для заданного ряда коэффициентов , вычислите значения по формуле «обратной» рекурсии:
Обратите внимание, что это вычисление не делает прямой ссылки на функции . После вычисления и желаемую сумму можно выразить через них и простейшие функции и :
См. Fox and Parker для получения дополнительной информации и анализа стабильности.
Примеры
Хорнер как частный случай Кленшоу
Особенно простой случай возникает при вычислении многочлена вида
-
.
Функции просто
и производятся коэффициентами рекуррентности и .
В этом случае рекуррентная формула для вычисления суммы:
и в этом случае сумма просто
-
,
что является в точности обычным методом Хорнера .
Особый случай для чебышевского сериала
Рассмотрим усеченный ряд Чебышева
Коэффициенты в рекурсивном соотношении для полиномов Чебышева равны
с начальными условиями
Таким образом, повторяемость
и окончательная сумма
Один из способов оценить это - продолжить повторение еще на один шаг и вычислить
(обратите внимание , что в два раза более 0 коэффициент) , а затем
Длина дуги меридиана на эллипсоиде
Суммирование по Кленшоу широко используется в геодезических приложениях. Простое приложение - суммирование тригонометрических рядов для вычисления расстояния дуги меридиана на поверхности эллипсоида. Они имеют вид
Оставляя начальный член, остаток представляет собой суммирование соответствующей формы. Нет ведущего термина, потому что .
Рекуррентное соотношение для IS
-
,
делая коэффициенты в рекурсивном соотношении
и оценка серии дается
Последний шаг сделан особенно простым, потому что , поэтому конец повторения просто ; термин добавляется отдельно:
Обратите внимание, что алгоритм требует только оценки двух тригонометрических величин и .
Разница в длине дуги меридиана
Иногда необходимо вычислить разность двух дуг меридиана таким образом, чтобы сохранить высокую относительную точность. Это достигается за счет использования тригонометрических тождеств для записи
В этом случае можно применить суммирование по Кленшоу, если мы одновременно вычисляем
и выполняем матричное суммирование,
где
Первый элемент - это среднее значение, а второй - средний наклон.
удовлетворяет рекуррентному соотношению
где
занимает место в рекуррентном отношении, и . Стандартный алгоритм Кленшоу теперь может применяться для получения
где - матрицы 2 × 2. Наконец у нас есть
Этот метод можно использовать в пределе
и для одновременного вычисления и производной , при условии, что при вычислении и мы берем .
Смотрите также
Рекомендации