Algorytm Clenshawa

Algorytm Clenshawa

Algorytm Clenshawa to rekurencyjna technika służąca do obliczania liniowej kombinacji wielomianów Czebyszewa. Jest on używany do różnych klas funkcji, które można zdefiniować za pomocą trójtermowego równania rekurencyjnego.

Niech ciąg

{\displaystyle \phi _{k},\;k=0,1,\dots }

spełnia liniową relację rekurencyjną:

{\displaystyle \phi _{k+1}(x)+\alpha _{k}(x)\,\phi _{k}(x)+\beta _{k}(x)\,\phi _{k-1}(x)=0,}

gdzie współczynniki

{\displaystyle \alpha _{k}}

i

{\displaystyle \beta _{k}}

są znane. Dla dowolnego skończonego ciągu

{\displaystyle c_{0},\dots ,c_{n},}

możemy zdefiniować funkcje

{\displaystyle b_{k}}

na podstawie „odwróconego” wzoru rekurencyjnego:

{\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

{\displaystyle \phi _{k}}

spełnia:

{\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

Rozważmy kombinację liniową wielomianów Czebyszewa:

{\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:

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

Korzystając z zależności:

{\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:

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

Zobacz też

Przypisy

Przeczytaj u przyjaciół: