Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Discrete Chebyshev transform
open-in-new
<h2 id="discrete-chebyshev-transform-on-the-roots-grid">Discrete Chebyshev transform on the roots grid</h2> <p>The discrete Chebyshev transform of u ( x ) {\displaystyle {u(x)}} at the points x n {\displaystyle {x_{n}}} is given by: </p> a m = p m N ∑ n = 0 N − 1 u ( x n ) T m ( x n ) {\displaystyle a_{m}={\frac {p_{m}}{N}}\sum _{n=0}^{N-1}u(x_{n})T_{m}(x_{n})} <p>where: </p> x n = − cos ( π N ( n + 1 2 ) ) {\displaystyle x_{n}=-\cos \left({\frac {\pi }{N}}(n+{\frac {1}{2}})\right)} a m = p m N ∑ n = 0 N − 1 u ( x n ) cos ( m cos − 1 ( x n ) ) {\displaystyle a_{m}={\frac {p_{m}}{N}}\sum _{n=0}^{N-1}u(x_{n})\cos \left(m\cos ^{-1}(x_{n})\right)} <p>where p m = 1 ⇔ m = 0 {\displaystyle p_{m}=1\Leftrightarrow m=0} and p m = 2 {\displaystyle p_{m}=2} otherwise. </p><p>Using the definition of x n {\displaystyle x_{n}} , </p> a m = p m N ∑ n = 0 N − 1 u ( x n ) cos ( m π N ( N + n + 1 2 ) ) {\displaystyle a_{m}={\frac {p_{m}}{N}}\sum _{n=0}^{N-1}u(x_{n})\cos \left({\frac {m\pi }{N}}(N+n+{\frac {1}{2}})\right)} a m = p m N ∑ n = 0 N − 1 u ( x n ) ( − 1 ) m cos ( m π N ( n + 1 2 ) ) {\displaystyle a_{m}={\frac {p_{m}}{N}}\sum _{n=0}^{N-1}u(x_{n})(-1)^{m}\cos \left({\frac {m\pi }{N}}(n+{\frac {1}{2}})\right)} <p>and its inverse transform: </p> u n = ∑ m = 0 N − 1 a m T m ( x n ) {\displaystyle u_{n}=\sum _{m=0}^{N-1}a_{m}T_{m}(x_{n})} <p>(This so happens to be the standard Chebyshev series evaluated on the roots grid.) </p> u n = ∑ m = 0 N − 1 a m cos ( m π N ( N + n + 1 2 ) ) {\displaystyle u_{n}=\sum _{m=0}^{N-1}a_{m}\cos \left({\frac {m\pi }{N}}(N+n+{\frac {1}{2}})\right)} ∴ u n = ∑ m = 0 N − 1 a m ( − 1 ) m cos ( m π N ( n + 1 2 ) ) {\displaystyle \therefore u_{n}=\sum _{m=0}^{N-1}a_{m}(-1)^{m}\cos \left({\frac {m\pi }{N}}(n+{\frac {1}{2}})\right)} <p>This can readily be obtained by manipulating the input arguments to a discrete cosine transform. </p><p>This can be demonstrated using the following <a href="/facts/MATLAB/qPjLISCk">MATLAB</a> code: </p> function a=fct(f, l) % x =-cos(pi/N*((0:N-1)'+1/2)); f = f(end:-1:1,:); A = size(f); N = A(1); if exist('A(3)', 'var') && A(3)~=1 for i=1:A(3) a(:,:,i) = sqrt(2/N) * dct(f(:,:,i)); a(1,:,i) = a(1,:,i) / sqrt(2); end else a = sqrt(2/N) * dct(f(:,:,i)); a(1,:)=a(1,:) / sqrt(2); end <p>The discrete cosine transform (dct) is in fact computed using a fast Fourier transform algorithm in MATLAB. </p><p>And the inverse transform is given by the MATLAB code: </p> function f=ifct(a, l) % x = -cos(pi/N*((0:N-1)'+1/2)) k = size(a); N=k(1); a = idct(sqrt(N/2) * [a(1,:) * sqrt(2); a(2:end,:)]); end <h2 id="discrete-chebyshev-transform-on-the-extrema-grid">Discrete Chebyshev transform on the extrema grid</h2> <p>This transform uses the grid: </p> x n = − cos ( n π N ) {\displaystyle x_{n}=-\cos \left({\frac {n\pi }{N}}\right)} T n ( x m ) = cos ( π m n N + n π ) = ( − 1 ) n cos ( π m n N ) {\displaystyle T_{n}(x_{m})=\cos \left({\frac {\pi mn}{N}}+n\pi \right)=(-1)^{n}\cos \left({\frac {\pi mn}{N}}\right)} <p>This transform is more difficult to implement by use of a Fast Fourier Transform (FFT). However it is more widely used because it is on the extrema grid which tends to be most useful for boundary value problems. Mostly because it is easier to apply boundary conditions on this grid. </p><p>In this case the transform and its inverse are </p> u ( x n ) = u n = ∑ m = 0 N a m T m ( x n ) {\displaystyle u(x_{n})=u_{n}=\sum _{m=0}^{N}a_{m}T_{m}(x_{n})} a m = p m N [ 1 2 ( u 0 ( − 1 ) m + u N ) + ∑ n = 1 N − 1 u n T m ( x n ) ] {\displaystyle a_{m}={\frac {p_{m}}{N}}\left[{\frac {1}{2}}(u_{0}(-1)^{m}+u_{N})+\sum _{n=1}^{N-1}u_{n}T_{m}(x_{n})\right]} <p>where p m = 1 ⇔ m = 0 , N {\displaystyle p_{m}=1\Leftrightarrow m=0,N} and p m = 2 {\displaystyle p_{m}=2} otherwise. </p> <h2 id="usage-and-implementations">Usage and implementations</h2> <p>The primary uses of the discrete Chebyshev transform are numerical integration, interpolation, and stable numerical differentiation.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> An implementation which provides these features is given in the <a href="/facts/C%2B%2B/Et0F2qn9">C++</a> library Boost.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Chebyshev_polynomials/HoBINqgC">Chebyshev polynomials</a></li> <li><a href="/facts/Discrete_cosine_transform/gPpDhPwP">Discrete cosine transform</a></li> <li><a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">Discrete Fourier transform</a></li> <li><a href="/facts/List_of_Fourier-related_transforms/omM5lS1k">List of Fourier-related transforms</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Trefethen, Lloyd (2013). Approximation Theory and Approximation Practice. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Thompson, Nick; Maddock, John. "Chebyshev Polynomials". boost.org. <a href="http://www.boost.org/doc/libs/release/libs/math/doc/html/math_toolkit/sf_poly/chebyshev.html" target="_blank">http://www.boost.org/doc/libs/release/libs/math/doc/html/math_toolkit/sf_poly/chebyshev.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> </ol>