В численном анализе , то Clenshaw алгоритм , называемый также Clenshaw суммированием , является рекурсивным методом оценки линейной комбинации полиномов Чебышева . [1] [2] Хорнера для вычисления линейной комбинации мономов .
Он обобщается не только на многочлены Чебышева; он применяется к любому классу функций, который может быть определен трехчленным рекуррентным соотношением . [3]
Алгоритм Кленшоу [ править ] В общем, алгоритм Кленшоу вычисляет взвешенную сумму конечного ряда функций : ϕ k ( Икс ) {\ Displaystyle \ phi _ {к} (х)}
S ( Икс ) знак равно ∑ k знак равно 0 п а k ϕ k ( Икс ) {\ Displaystyle S (х) = \ сумма _ {к = 0} ^ {n} a_ {k} \ phi _ {k} (x)} где - последовательность функций, удовлетворяющих линейному рекуррентному соотношению ϕ k , k знак равно 0 , 1 , … {\ displaystyle \ phi _ {k}, \; k = 0,1, \ ldots}
ϕ k + 1 ( Икс ) знак равно α k ( Икс ) ϕ k ( Икс ) + β k ( Икс ) ϕ k - 1 ( Икс ) , {\displaystyle \phi _{k+1}(x)=\alpha _{k}(x)\,\phi _{k}(x)+\beta _{k}(x)\,\phi _{k-1}(x),} где коэффициенты и известны заранее. α k ( x ) {\displaystyle \alpha _{k}(x)} β k ( x ) {\displaystyle \beta _{k}(x)}
Алгоритм является наиболее полезным , когда функции , которые осложнены непосредственно вычислить, но и являются особенно просто. В наиболее распространенных приложениях не зависит и является константой, которая не зависит ни от, ни . ϕ k ( x ) {\displaystyle \phi _{k}(x)} α k ( x ) {\displaystyle \alpha _{k}(x)} β k ( x ) {\displaystyle \beta _{k}(x)} α ( x ) {\displaystyle \alpha (x)} k {\displaystyle k} β {\displaystyle \beta } x {\displaystyle x} k {\displaystyle k}
Чтобы произвести суммирование для заданного ряда коэффициентов , вычислите значения по формуле «обратной» рекурсии: a 0 , … , a n {\displaystyle a_{0},\ldots ,a_{n}} b k ( x ) {\displaystyle b_{k}(x)}
b n + 1 ( x ) = b n + 2 ( x ) = 0 , b k ( x ) = a k + α k ( x ) b k + 1 ( x ) + β k + 1 ( x ) b k + 2 ( x ) . {\displaystyle {\begin{aligned}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{aligned}}} Обратите внимание, что это вычисление не имеет прямой ссылки на функции . После вычисления и желаемую сумму можно выразить через них и простейшие функции и : ϕ k ( x ) {\displaystyle \phi _{k}(x)} b 2 ( x ) {\displaystyle b_{2}(x)} b 1 ( x ) {\displaystyle b_{1}(x)} ϕ 0 ( x ) {\displaystyle \phi _{0}(x)} ϕ 1 ( x ) {\displaystyle \phi _{1}(x)}
S ( x ) = ϕ 0 ( x ) a 0 + ϕ 1 ( x ) b 1 ( x ) + β 1 ( x ) ϕ 0 ( x ) b 2 ( x ) . {\displaystyle S(x)=\phi _{0}(x)\,a_{0}+\phi _{1}(x)\,b_{1}(x)+\beta _{1}(x)\,\phi _{0}(x)\,b_{2}(x).} См. Fox и Parker [4]
Хорнер как частный случай Кленшоу [ править ] Особенно простой случай возникает при вычислении многочлена вида
S ( x ) = ∑ k = 0 n a k x k {\displaystyle S(x)=\sum _{k=0}^{n}a_{k}x^{k}} Функции просто
ϕ 0 ( x ) = 1 , ϕ k ( x ) = x k = x ϕ k − 1 ( x ) {\displaystyle {\begin{aligned}\phi _{0}(x)&=1,\\\phi _{k}(x)&=x^{k}=x\phi _{k-1}(x)\end{aligned}}} и производятся коэффициентами рекуррентности и . α ( x ) = x {\displaystyle \alpha (x)=x} β = 0 {\displaystyle \beta =0}
В этом случае рекуррентная формула для вычисления суммы:
b k ( x ) = a k + x b k + 1 ( x ) {\displaystyle b_{k}(x)=a_{k}+xb_{k+1}(x)} и в этом случае сумма просто
S ( x ) = a 0 + x b 1 ( x ) = b 0 ( x ) {\displaystyle S(x)=a_{0}+xb_{1}(x)=b_{0}(x)} что является в точности обычным методом Хорнера .
Частный случай для чебышевского сериала [ править ] Рассмотрим усеченный ряд Чебышева
p n ( x ) = a 0 + a 1 T 1 ( x ) + a 2 T 2 ( x ) + ⋯ + a n T n ( x ) . {\displaystyle p_{n}(x)=a_{0}+a_{1}T_{1}(x)+a_{2}T_{2}(x)+\cdots +a_{n}T_{n}(x).} Коэффициенты в рекурсивном соотношении для полиномов Чебышева равны
α ( x ) = 2 x , β = − 1 , {\displaystyle \alpha (x)=2x,\quad \beta =-1,} с начальными условиями
T 0 ( x ) = 1 , T 1 ( x ) = x . {\displaystyle T_{0}(x)=1,\quad T_{1}(x)=x.} Таким образом, повторяемость
b k ( x ) = a k + 2 x b k + 1 ( x ) − b k + 2 ( x ) {\displaystyle b_{k}(x)=a_{k}+2xb_{k+1}(x)-b_{k+2}(x)} и окончательная сумма
p n ( x ) = a 0 + x b 1 ( x ) − b 2 ( x ) . {\displaystyle p_{n}(x)=a_{0}+xb_{1}(x)-b_{2}(x).} Один из способов оценить это - продолжить повторение еще на один шаг и вычислить
b 0 ( x ) = 2 a 0 + 2 x b 1 ( x ) − b 2 ( x ) , {\displaystyle b_{0}(x)=2a_{0}+2xb_{1}(x)-b_{2}(x),} (обратите внимание , что в два раза более 0 коэффициент) , а затем
p n ( x ) = 1 2 [ b 0 ( x ) − b 2 ( x ) ] . {\displaystyle p_{n}(x)={\frac {1}{2}}\left[b_{0}(x)-b_{2}(x)\right].} Длина дуги меридиана эллипсоида [ править ] Суммирование по Кленшоу широко используется в геодезических приложениях. [2] дуги меридиана на поверхности эллипсоида. Они имеют вид
m ( θ ) = C 0 θ + C 1 sin θ + C 2 sin 2 θ + ⋯ + C n sin n θ . {\displaystyle m(\theta )=C_{0}\,\theta +C_{1}\sin \theta +C_{2}\sin 2\theta +\cdots +C_{n}\sin n\theta .} Оставляя начальный член, остаток представляет собой суммирование соответствующей формы. Ведущего термина нет, потому что . C 0 θ {\displaystyle C_{0}\,\theta } ϕ 0 ( θ ) = sin 0 θ = sin 0 = 0 {\displaystyle \phi _{0}(\theta )=\sin 0\theta =\sin 0=0}
Рекуррентное соотношение для sin k θ {\displaystyle \sin k\theta } IS
sin ( k + 1 ) θ = 2 cos θ sin k θ − sin ( k − 1 ) θ {\displaystyle \sin(k+1)\theta =2\cos \theta \sin k\theta -\sin(k-1)\theta } делая коэффициенты в рекурсивном соотношении
α k ( θ ) = 2 cos θ , β k = − 1. {\displaystyle \alpha _{k}(\theta )=2\cos \theta ,\quad \beta _{k}=-1.} и оценка серии дается
b n + 1 ( θ ) = b n + 2 ( θ ) = 0 , b k ( θ ) = C k + 2 cos θ b k + 1 ( θ ) − b k + 2 ( θ ) , f o r n ≥ k ≥ 1. {\displaystyle {\begin{aligned}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 {for\ } n\geq k\geq 1.\end{aligned}}} Последний шаг сделан особенно простым, потому что , поэтому конец повторения просто ; термин добавляется отдельно: ϕ 0 ( θ ) = sin 0 = 0 {\displaystyle \phi _{0}(\theta )=\sin 0=0} b 1 ( θ ) sin ( θ ) {\displaystyle b_{1}(\theta )\sin(\theta )} C 0 θ {\displaystyle C_{0}\,\theta }
m ( θ ) = C 0 θ + b 1 ( θ ) sin θ . {\displaystyle m(\theta )=C_{0}\,\theta +b_{1}(\theta )\sin \theta .} Обратите внимание, что алгоритм требует только оценки двух тригонометрических величин и . cos θ {\displaystyle \cos \theta } sin θ {\displaystyle \sin \theta }
Разница в длине дуги меридиана [ править ] Иногда необходимо вычислить разность двух дуг меридиана таким образом, чтобы сохранить высокую относительную точность. Это достигается за счет использования тригонометрических тождеств для записи
m ( θ 1 ) − m ( θ 2 ) = C 0 ( θ 1 − θ 2 ) + ∑ k = 1 n 2 C k sin ( 1 2 k ( θ 1 − θ 2 ) ) cos ( 1 2 k ( θ 1 + θ 2 ) ) . {\displaystyle m(\theta _{1})-m(\theta _{2})=C_{0}(\theta _{1}-\theta _{2})+\sum _{k=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 )}.} В этом случае может применяться суммирование по Кленшоу [5] m ( θ 1 ) + m ( θ 2 ) {\displaystyle m(\theta _{1})+m(\theta _{2})}
M ( θ 1 , θ 2 ) = [ ( m ( θ 1 ) + m ( θ 2 ) ) / 2 ( m ( θ 1 ) − m ( θ 2 ) ) / ( θ 1 − θ 2 ) ] = C 0 [ μ 1 ] + ∑ k = 1 n C k F k ( θ 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}),} куда
δ = 1 2 ( θ 1 − θ 2 ) , μ = 1 2 ( θ 1 + θ 2 ) , F k ( θ 1 , θ 2 ) = [ cos k δ sin k μ sin k δ δ cos k μ ] . {\displaystyle {\begin{aligned}\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 \end{bmatrix}}.\end{aligned}}} Первый элемент - это среднее значение, а второй - средний наклон.
удовлетворяет рекуррентному соотношению M ( θ 1 , θ 2 ) {\displaystyle {\mathsf {M}}(\theta _{1},\theta _{2})} m {\displaystyle m} F k ( θ 1 , θ 2 ) {\displaystyle {\mathsf {F}}_{k}(\theta _{1},\theta _{2})}
F k + 1 ( θ 1 , θ 2 ) = A ( θ 1 , θ 2 ) F k ( θ 1 , θ 2 ) − F k − 1 ( θ 1 , θ 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}),} куда
A ( θ 1 , θ 2 ) = 2 [ cos δ cos μ − δ sin δ sin μ − sin δ δ sin μ cos δ cos μ ] {\displaystyle {\mathsf {A}}(\theta _{1},\theta _{2})=2{\begin{bmatrix}\cos \delta \cos \mu &-\delta \sin \delta \sin \mu \\-\displaystyle {\frac {\sin \delta }{\delta }}\sin \mu &\cos \delta \cos \mu \end{bmatrix}}} занимает место в рекуррентном отношении, и . Стандартный алгоритм Кленшоу теперь может применяться для получения α {\displaystyle \alpha } β = − 1 {\displaystyle \beta =-1}
B n + 1 = B n + 2 = 0 , B k = C k I + A B k + 1 − B k + 2 , f o r n ≥ k ≥ 1 , M ( θ 1 , θ 2 ) = C 0 [ μ 1 ] + B 1 F 1 ( θ 1 , θ 2 ) , {\displaystyle {\begin{aligned}{\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 {for\ } 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{aligned}}} где - матрицы 2 × 2. Наконец у нас есть B k {\displaystyle {\mathsf {B}}_{k}}
m ( θ 1 ) − m ( θ 2 ) θ 1 − θ 2 = M 2 ( θ 1 , θ 2 ) . {\displaystyle {\frac {m(\theta _{1})-m(\theta _{2})}{\theta _{1}-\theta _{2}}}={\mathsf {M}}_{2}(\theta _{1},\theta _{2}).} Этот метод может использоваться в пределе
и для одновременного вычисления и производной , при условии, что при вычислении и мы берем . θ 2 = θ 1 = μ {\displaystyle \theta _{2}=\theta _{1}=\mu } δ = 0 {\displaystyle \delta =0\,} m ( μ ) {\displaystyle m(\mu )} d m ( μ ) / d μ {\displaystyle dm(\mu )/d\mu } F 1 {\displaystyle {\mathsf {F}}_{1}} A {\displaystyle {\mathsf {A}}} lim δ → 0 ( sin δ ) / δ = 1 {\displaystyle \lim _{\delta \rightarrow 0}(\sin \delta )/\delta =1}
^ Clenshaw, CW (июль 1955). «Заметка о суммировании рядов Чебышева» . Математические таблицы и другие вспомогательные средства для вычислений . 9 (51): 118. DOI : 10.1090 / S0025-5718-1955-0071856-0 ISSN 0025-5718 . сдвинутых многочленов Чебышева первого рода . T n ∗ ( x ) = T n ( 2 x − 1 ) {\displaystyle T_{n}^{*}(x)=T_{n}(2x-1)} ^ a b Чернинг, CC; Подер, К. (1982), "Некоторые геодезические приложения суммирования Кленшоу" (PDF) , Bolletino di Geodesia e Scienze Affini , 41 (4): 349–375, архивировано из оригинала (PDF) 12 июня 2007 г. , получено 2012-08-02 ^ Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, Б.П. (2007), «Раздел 5.4.2. Формула повторения Кленшоу» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN ^ Фокс, Лесли; Паркер, Ян Б. (1968), Многочлены Чебышева в численном анализе , Oxford University Press, ISBN ^ Karney, CFF (2014), оценка Кленшоу разностных сумм 
![p_ {n} (x) = {\ frac {1} {2}} \ left [b_ {0} (x) -b_ {2} (x) \ right].](https://wikimedia.org/api/rest_v1/media/math/render/svg/75e0954f1b76be0068eae2424bf6a44ef1d03334)
