Algorytm Clenshawa [1] rekurencyjna metoda obliczania liniowej kombinacji wielomianów Czebyszewa . Stosuje się go do dowolnej klasy funkcji definiowalnych za pomocą trójtermowego równania rekurencyjnego[2]
Algorytm Clenshawa
edytuj
Niech ciąg
ϕ
k
,
k
=
0
,
1
,
…
{\displaystyle \phi _{k},\;k=0,1,\dots }
ϕ
k
+
1
(
x
)
+
α
k
(
x
)
ϕ
k
(
x
)
+
β
k
(
x
)
ϕ
k
−
1
(
x
)
=
0
,
{\displaystyle \phi _{k+1}(x)+\alpha _{k}(x)\,\phi _{k}(x)+\beta _{k}(x)\,\phi _{k-1}(x)=0,}
gdzie współczynniki
α
k
{\displaystyle \alpha _{k}}
β
k
{\displaystyle \beta _{k}}
c
0
,
…
,
c
n
,
{\displaystyle c_{0},\dots ,c_{n},}
b
k
{\displaystyle b_{k}}
b
n
+
1
(
x
)
=
b
n
+
2
(
x
)
=
0
,
b
k
(
x
)
=
c
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,\\[.5em]b_{k}(x)&=c_{k}-\alpha _{k}(x)\,b_{k+1}(x)-\beta _{k+1}(x)\,b_{k+2}(x).\end{aligned}}}
Kombinacja liniowa
ϕ
k
{\displaystyle \phi _{k}}
∑
k
=
0
n
c
k
ϕ
k
(
x
)
=
b
0
(
x
)
ϕ
0
(
x
)
+
b
1
(
x
)
[
ϕ
1
(
x
)
+
α
0
(
x
)
ϕ
0
(
x
)
]
.
{\displaystyle \sum _{k=0}^{n}c_{k}\phi _{k}(x)=b_{0}(x)\phi _{0}(x)+b_{1}(x)\left[\phi _{1}(x)+\alpha _{0}(x)\phi _{0}(x)\right].}
Specjalny przypadek dla ciągu wielomianów Czebyszewa
edytuj
Rozważmy kombinację liniową wielomianów Czebyszewa
p
n
(
x
)
=
a
0
2
+
a
1
T
1
(
x
)
+
a
2
T
2
(
x
)
+
…
+
a
n
T
n
(
x
)
.
{\displaystyle p_{n}(x)={\frac {a_{0}}{2}}+a_{1}T_{1}(x)+a_{2}T_{2}(x)+\ldots +a_{n}T_{n}(x).}
Współczynniki w postaci rekurencyjnej dla wielomianów Czebyszewa to
α
k
(
x
)
=
−
2
x
,
β
k
=
1.
{\displaystyle \alpha _{k}(x)=-2x,\quad \beta _{k}=1.}
Korzystając z zależności
T
0
(
x
)
=
1
,
T
1
(
x
)
=
x
T
0
(
x
)
,
b
0
(
x
)
=
a
0
+
2
x
b
1
(
x
)
−
b
2
(
x
)
,
{\displaystyle {\begin{aligned}T_{0}(x)&=1,\quad T_{1}(x)=xT_{0}(x),\\[.5em]b_{0}(x)&=a_{0}+2xb_{1}(x)-b_{2}(x),\end{aligned}}}
algorytm Clenshawa redukuje się do:
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].}
↑ C.W. Clenshaw, A note on the summation of Chebyshev series , Math. Tab. Wash. 9 (1955), pp. 118–120.
↑ W.H. W.H. Press W.H. W.H. i inni , Numerical Recipes: The Art of Scientific Computing , Cambridge University Press, 2007 .brak strony (książka) 
![{\displaystyle {\begin{aligned}b_{n+1}(x)&=b_{n+2}(x)=0,\\[.5em]b_{k}(x)&=c_{k}-\alpha _{k}(x)\,b_{k+1}(x)-\beta _{k+1}(x)\,b_{k+2}(x).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afdb983a14297a1ef876f736364e77445eae98ca)
![{\displaystyle \sum _{k=0}^{n}c_{k}\phi _{k}(x)=b_{0}(x)\phi _{0}(x)+b_{1}(x)\left[\phi _{1}(x)+\alpha _{0}(x)\phi _{0}(x)\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e0133a3dbbf2ba212dc0fd05e848fb7fd43baa7)
![{\displaystyle {\begin{aligned}T_{0}(x)&=1,\quad T_{1}(x)=xT_{0}(x),\\[.5em]b_{0}(x)&=a_{0}+2xb_{1}(x)-b_{2}(x),\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f31eb0828a3a95685fc916f0b71b190523235b2f)
![{\displaystyle 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)