Discrete Chebyshev transform

In applied mathematics, a discrete Chebyshev transform (DCT) is an analog of the discrete Fourier transform for a function of a real interval, converting in either direction between function values at a set of Chebyshev nodes and coefficients of a function in Chebyshev polynomial basis. Like the Chebyshev polynomials, it is named after Pafnuty Chebyshev. The two most common types of discrete Chebyshev transforms use the grid of Chebyshev zeros, the zeros of the Chebyshev polynomials of the first kind Tn(x) and the grid of Chebyshev extrema, the extrema of the Chebyshev polynomials of the first kind, which are also the zeros of the Chebyshev polynomials of the second kind Un(x). Both of these transforms result in coefficients of Chebyshev polynomials of the first kind.

Other discrete Chebyshev transforms involve related grids and coefficients of Chebyshev polynomials of the second, third, or fourth kinds.

## Contents

* 1 Discrete Chebyshev transform on the roots grid
* 2 Discrete Chebyshev transform on the extrema grid
* 3 Usage and implementations
* 4 See also
* 5 References

## Discrete Chebyshev transform on the roots grid

The discrete chebyshev transform of u(x) at the points xn is given by:

am=pmN∑n=0N−1u(xn)Tm(xn)

where:

xn=−cos⁡(πN(n+12))

am=pmN∑n=0N−1u(xn)cos⁡(mcos−1(xn))

where pm=1⇔m=0 and pm=2 otherwise.

Using the definition of xn,

am=pmN∑n=0N−1u(xn)cos⁡(mπN(N+n+12))

am=pmN∑n=0N−1u(xn)(−1)mcos⁡(mπN(n+12))

and its inverse transform:

un=∑m=0N−1amTm(xn)

(This so happens to the standard Chebyshev series evaluated on the roots grid.)

un=∑m=0N−1amcos⁡(mπN(N+n+12))

∴un=∑m=0N−1am(−1)mcos⁡(mπN(n+12))

This can readily be obtained by manipulating the input arguments to a discrete cosine transform.

This can be demonstrated using the following MATLAB code:

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

The discrete cosine transform (dct) is in fact computed using a fast Fourier transform algorithm in MATLAB.

And the inverse transform is given by the MATLAB code:

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

## Discrete Chebyshev transform on the extrema grid

This transform uses the grid:

xn=−cos⁡(nπN)

Tn(xm)=cos⁡(πmnN+nπ)=(−1)ncos⁡(πmnN)

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.

There is a discrete (and in fact fast because it performs the dct by using a fast Fourier transform) algorithm available at the MATLAB file exchange that was created by Greg von Winckel. So it is omitted here.

In this case the transform and its inverse are

u(xn)=un=∑m=0NamTm(xn)

am=pmN[12(u0(−1)m+uN)+∑n=1N−1unTm(xn)]

where pm=1⇔m=0,N and pm=2 otherwise.

## Usage and implementations

The primary uses of the discrete Chebyshev transform are numerical integration, interpolation, and stable numerical differentiation.[1] An implementation which provides these features is given in the C++ library Boost.[2]

## See also

* Chebyshev polynomials
* Discrete cosine transform
* Discrete Fourier transform
* List of Fourier-related transforms

## References

1. ↑ Trefethen, Lloyd (2013). Approximation Theory and Approximation Practice.
2. ↑ Thompson, Nick; Maddock, John. "Chebyshev Polynomials". http://www.boost.org/doc/libs/release/libs/math/doc/html/math_toolkit/sf_poly/chebyshev.html.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Discrete Chebyshev transform. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Discrete_Chebyshev_transform&oldid=205898"