Алгоритм Кленшоу - Clenshaw algorithm

В численном анализе , то Clenshaw алгоритм , называемый также Clenshaw суммированием , является рекурсивным методом оценки линейной комбинации полиномов Чебышева . Метод был опубликован Чарльзом Уильямом Кленшоу в 1955 году. Это обобщение метода Хорнера для вычисления линейной комбинации мономов .

Он обобщается не только на многочлены Чебышева; он применяется к любому классу функций, который может быть определен трехчленным рекуррентным соотношением .

Алгоритм Кленшоу

В общем, алгоритм Кленшоу вычисляет взвешенную сумму конечного ряда функций : ${\ Displaystyle \ phi _ {к} (х)}$

${\ Displaystyle S (х) = \ сумма _ {к = 0} ^ {n} a_ {k} \ phi _ {k} (x)}$

где - последовательность функций, удовлетворяющих линейному рекуррентному соотношению ${\ displaystyle \ phi _ {k}, \; k = 0,1, \ ldots}$

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

где коэффициенты и известны заранее. ${\ Displaystyle \ альфа _ {к} (х)}$${\ Displaystyle \ бета _ {к} (х)}$

Алгоритм является наиболее полезным , когда функции , которые осложнены непосредственно вычислить, но и являются особенно просто. В наиболее распространенных приложениях не зависит и является константой, которая не зависит ни от, ни . ${\ Displaystyle \ phi _ {к} (х)}$${\ Displaystyle \ альфа _ {к} (х)}$${\ Displaystyle \ бета _ {к} (х)}$${\ Displaystyle \ альфа (х)}$${\ displaystyle k}$${\ displaystyle \ beta}$${\ displaystyle x}$${\ displaystyle k}$

Чтобы произвести суммирование для заданного ряда коэффициентов , вычислите значения по формуле «обратной» рекурсии: ${\ displaystyle a_ {0}, \ ldots, a_ {n}}$${\ displaystyle b_ {k} (x)}$

${\ displaystyle {\ begin {align} b_ {n + 1} (x) & = b_ {n + 2} (x) = 0, \\ b_ {k} (x) & = a_ {k} + \ alpha _ {k} (x) \, b_ {k + 1} (x) + \ beta _ {k + 1} (x) \, b_ {k + 2} (x). \ end {выравнивается}}}$

Обратите внимание, что это вычисление не делает прямой ссылки на функции . После вычисления и желаемую сумму можно выразить через них и простейшие функции и : ${\ Displaystyle \ phi _ {к} (х)}$${\ displaystyle b_ {2} (х)}$${\ displaystyle b_ {1} (х)}$${\ Displaystyle \ phi _ {0} (х)}$${\ Displaystyle \ phi _ {1} (х)}$

${\ displaystyle S (x) = \ phi _ {0} (x) \, a_ {0} + \ phi _ {1} (x) \, b_ {1} (x) + \ beta _ {1} ( x) \, \ phi _ {0} (x) \, b_ {2} (x).}$

См. Fox and Parker для получения дополнительной информации и анализа стабильности.

Примеры

Хорнер как частный случай Кленшоу

Особенно простой случай возникает при вычислении многочлена вида

${\ Displaystyle S (x) = \ сумма _ {k = 0} ^ {n} a_ {k} x ^ {k}}$.

Функции просто

${\ displaystyle {\ begin {align} \ phi _ {0} (x) & = 1, \\\ phi _ {k} (x) & = x ^ {k} = x \ phi _ {k-1} (х) \ конец {выровнено}}}$

и производятся коэффициентами рекуррентности и . ${\ Displaystyle \ альфа (х) = х}$${\ displaystyle \ beta = 0}$

В этом случае рекуррентная формула для вычисления суммы:

${\ displaystyle b_ {k} (x) = a_ {k} + xb_ {k + 1} (x)}$

и в этом случае сумма просто

${\ Displaystyle S (x) = a_ {0} + xb_ {1} (x) = b_ {0} (x)}$,

что является в точности обычным методом Хорнера .

Особый случай для чебышевского сериала

Рассмотрим усеченный ряд Чебышева

${\ displaystyle p_ {n} (x) = a_ {0} + a_ {1} T_ {1} (x) + a_ {2} T_ {2} (x) + \ cdots + a_ {n} T_ {n }(Икс).}$

Коэффициенты в рекурсивном соотношении для полиномов Чебышева равны

${\ Displaystyle \ альфа (х) = 2х, \ квад \ бета = -1,}$

с начальными условиями

${\ displaystyle T_ {0} (x) = 1, \ quad T_ {1} (x) = x.}$

Таким образом, повторяемость

${\ displaystyle b_ {k} (x) = a_ {k} + 2xb_ {k + 1} (x) -b_ {k + 2} (x)}$

и окончательная сумма

${\ displaystyle p_ {n} (x) = a_ {0} + xb_ {1} (x) -b_ {2} (x).}$

Один из способов оценить это - продолжить повторение еще на один шаг и вычислить

${\ displaystyle b_ {0} (x) = 2a_ {0} + 2xb_ {1} (x) -b_ {2} (x),}$

(обратите внимание , что в два раза более ₀ коэффициент) , а затем

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

Длина дуги меридиана на эллипсоиде

Суммирование по Кленшоу широко используется в геодезических приложениях. Простое приложение - суммирование тригонометрических рядов для вычисления расстояния дуги меридиана на поверхности эллипсоида. Они имеют вид

${\ Displaystyle м (\ тета) = C_ {0} \, \ theta + C_ {1} \ sin \ theta + C_ {2} \ sin 2 \ theta + \ cdots + C_ {n} \ sin n \ theta. }$

Оставляя начальный член, остаток представляет собой суммирование соответствующей формы. Нет ведущего термина, потому что . ${\ Displaystyle C_ {0} \, \ theta}$${\ Displaystyle \ phi _ {0} (\ theta) = \ sin 0 \ theta = \ sin 0 = 0}$

Рекуррентное соотношение для${\ Displaystyle \ грех к \ тета}$ IS

${\ Displaystyle \ грех (к + 1) \ тета = 2 \ соз \ тета \ грех к \ тета - \ грех (к-1) \ тета}$,

делая коэффициенты в рекурсивном соотношении

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

и оценка серии дается

${\ displaystyle {\ begin {align} b_ {n + 1} (\ theta) & = b_ {n + 2} (\ theta) = 0, \\ b_ {k} (\ theta) & = C_ {k} +2 \ cos \ theta \, b_ {k + 1} (\ theta) -b_ {k + 2} (\ theta), \ quad \ mathrm {для \} n \ geq k \ geq 1. \ end {выровнено }}}$

Последний шаг сделан особенно простым, потому что , поэтому конец повторения просто ; термин добавляется отдельно: ${\ displaystyle \ phi _ {0} (\ theta) = \ sin 0 = 0}$${\ Displaystyle В_ {1} (\ тета) \ грех (\ тета)}$${\ Displaystyle C_ {0} \, \ theta}$

${\ Displaystyle м (\ theta) = C_ {0} \, \ theta + b_ {1} (\ theta) \ sin \ theta.}$

Обратите внимание, что алгоритм требует только оценки двух тригонометрических величин и . ${\ displaystyle \ cos \ theta}$${\ Displaystyle \ грех \ тета}$

Разница в длине дуги меридиана

Иногда необходимо вычислить разность двух дуг меридиана таким образом, чтобы сохранить высокую относительную точность. Это достигается за счет использования тригонометрических тождеств для записи

${\ Displaystyle м (\ тета _ {1}) - м (\ тета _ {2}) = С_ {0} (\ тета _ {1} - \ тета _ {2}) + \ сумма _ {к = 1 } ^ {n} 2C_ {k} \ sin {\ bigl (} {\ textstyle {\ frac {1} {2}}} k (\ theta _ {1} - \ theta _ {2}) {\ bigr) } \ cos {\ bigl (} {\ textstyle {\ frac {1} {2}}} k (\ theta _ {1} + \ theta _ {2}) {\ bigr)}.}$

В этом случае можно применить суммирование по Кленшоу, если мы одновременно вычисляем и выполняем матричное суммирование, ${\ Displaystyle м (\ тета _ {1}) + м (\ тета _ {2})}$

${\ displaystyle {\ mathsf {M}} (\ theta _ {1}, \ theta _ {2}) = {\ begin {bmatrix} (m (\ theta _ {1}) + m (\ theta _ {2 })) / 2 \\ (m (\ theta _ {1}) - m (\ theta _ {2})) / (\ theta _ {1} - \ theta _ {2}) \ end {bmatrix}} = C_ {0} {\ begin {bmatrix} \ mu \\ 1 \ end {bmatrix}} + \ sum _ {k = 1} ^ {n} C_ {k} {\ mathsf {F}} _ {k} (\ theta _ {1}, \ theta _ {2}),}$

где

${\ displaystyle {\ begin {align} \ delta & = {\ textstyle {\ frac {1} {2}}} (\ theta _ {1} - \ theta _ {2}), \\\ mu & = { \ textstyle {\ frac {1} {2}}} (\ theta _ {1} + \ theta _ {2}), \\ {\ mathsf {F}} _ {k} (\ theta _ {1}, \ theta _ {2}) & = {\ begin {bmatrix} \ cos k \ delta \ sin k \ mu \\\ displaystyle {\ frac {\ sin k \ delta} {\ delta}} \ cos k \ mu \ конец {bmatrix}}. \ end {выравнивается}}}$

Первый элемент - это среднее значение, а второй - средний наклон. удовлетворяет рекуррентному соотношению ${\ Displaystyle {\ mathsf {M}} (\ theta _ {1}, \ theta _ {2})}$${\ displaystyle m}$${\ displaystyle {\ mathsf {F}} _ {k} (\ theta _ {1}, \ theta _ {2})}$

${\ displaystyle {\ mathsf {F}} _ {k + 1} (\ theta _ {1}, \ theta _ {2}) = {\ mathsf {A}} (\ theta _ {1}, \ theta _ {2}) {\ mathsf {F}} _ {k} (\ theta _ {1}, \ theta _ {2}) - {\ mathsf {F}} _ {k-1} (\ theta _ {1 }, \ theta _ {2}),}$

где

${\ displaystyle {\ mathsf {A}} (\ theta _ {1}, \ theta _ {2}) = 2 {\ begin {bmatrix} \ cos \ delta \ cos \ mu & - \ delta \ sin \ delta \ грех \ му \\ - \ displaystyle {\ frac {\ sin \ delta} {\ delta}} \ sin \ mu & \ cos \ delta \ cos \ mu \ end {bmatrix}}}$

занимает место в рекуррентном отношении, и . Стандартный алгоритм Кленшоу теперь может применяться для получения ${\ displaystyle \ alpha}$${\ displaystyle \ beta = -1}$

${\ displaystyle {\ begin {align} {\ mathsf {B}} _ {n + 1} & = {\ mathsf {B}} _ {n + 2} = {\ mathsf {0}}, \\ {\ mathsf {B}} _ {k} & = C_ {k} {\ mathsf {I}} + {\ mathsf {A}} {\ mathsf {B}} _ {k + 1} - {\ mathsf {B} } _ {k + 2}, \ qquad \ mathrm {для \} n \ geq k \ geq 1, \\ {\ mathsf {M}} (\ theta _ {1}, \ theta _ {2}) & = C_ {0} {\ begin {bmatrix} \ mu \\ 1 \ end {bmatrix}} + {\ mathsf {B}} _ {1} {\ mathsf {F}} _ {1} (\ theta _ {1 }, \ theta _ {2}), \ end {align}}}$

где - матрицы 2 × 2. Наконец у нас есть ${\ displaystyle {\ mathsf {B}} _ {k}}$

${\ displaystyle {\ frac {m (\ theta _ {1}) - m (\ theta _ {2})} {\ theta _ {1} - \ theta _ {2}}} = {\ mathsf {M} } _ {2} (\ theta _ {1}, \ theta _ {2}).}$

Этот метод можно использовать в пределе и для одновременного вычисления и производной , при условии, что при вычислении и мы берем . ${\ Displaystyle \ theta _ {2} = \ theta _ {1} = \ mu}$${\ Displaystyle \ delta = 0 \,}$${\ Displaystyle м (\ му)}$ ${\ Displaystyle дм (\ му) / д \ му}$${\ displaystyle {\ mathsf {F}} _ {1}}$${\ displaystyle {\ mathsf {A}}}$${\ Displaystyle \ lim _ {\ дельта \ rightarrow 0} (\ грех \ дельта) / \ дельта = 1}$

Смотрите также

• Схема Хорнера для вычисления многочленов в мономиальной форме
• Алгоритм де Кастельжау для вычисления многочленов в форме Безье

Рекомендации