EXPLANATION FILE OF PROGRAM CHEBYSHE ==================================== Cbebyshev Approximation ----------------------- The Chebyshev polynomial of degree n is denoted Tn(x), and is given the explicit formula Tn(x) = cos(n arccos x) (5.6.1) This may look trigonometrie at first glanee (and there is in fact a close relation between the Chebyshev polynomials and the discrete Fourier trans- form); Howeever (5.6.1) can be combined with trigonometrie identities to yield explicit expressions for Tn(x), To(x) = 1 T1(x) = X T2(X) = 2x2 - 1 (5.6.2) T3(x) = 4x3 - 3x T4(x) = 8x4 - 8x2 + 1 The Chebyshev polynomials are orthogonal in the interval [-1,1] over a weight (1 - X2)-1/2. ln particular, 1 Ti(x) Tj(x) |0 i <> j Sum ------------ dx = |pi/2 i=j <> 0 (5.6.3) -1 sqrt(1-x²) |pi i= j = 0 The polynomial Tn(x) has n zeros in the interval [-1,1], and they are located at the points pi(k-1/2) x = cos ----------- k = 1, 2,...,n (5.6.4) n In this same interval there are n + 1 extrema (maxima and minima), located at x = cos ( pi k/n ) k = 0, 1, ... ,n (5.6.5) At all of the maxima Tn(x) = 1, while at all of the minima Tn(x) = -1; it is precisely this property that makes the Chebyshev polynomials so useful in polynomial approximation of functions. The Chebyshev polynomials satisfy a discrete orthogonality relation as well as the continuous one (5.6.3): If Xk (k = 1, ... , m) are the m zeroes of Tm(x) given by (5.6.4), then m |0 i <> j Sum Ti(xk) TJ(Xk) = |m/2 i=j <> 0 (5.6.6) k=1 |m i = j = 0 It is not too difficult to combine equations (5.6.1), (5.6.4), and (5,6.6) to prove the following theorem: If f(x) is an arbitrary function in the in the interval [-1, 1], and if N coefficients Cj, j = 1,..., N, are defined by N c = (2/N) Sum f(xk) Tj-1(xk) j k=1 N pi(K-1/2) pi(j-1)(k-1/2) = (2/N) Sum f [cos (---------)] cos (--------------) (5.6.7) k=1 N N then the approximation formula N f(x) = [Sum c T (x)]- (1/2) c (5.6.8) k=1 k k-1 1 is exact for x equal to all of the N zeros of TN(x). For a fixed N, equation (5.6.8) is a polynomial in x which approximates the function f(x) in the interval [-1,1] (where an the zeros of TN(x) are located). Why is this particular approximating polynomial better than any other one, exact on some other set of N points? The answer is not that (5.6.8) is necessarily more accurate than some other approximating polynomial of the same order N (for some specified definition of "accurate"), but rather that (5.6.8) can be truncated to a polynomial of lower degree m « N in a very graceful way, one which does yield the "most accurate" approximation of degree m (in a sense which can be made precise). Suppose N is so large that (5.6.8) is virtually a perfect approximation of f(x). Now consider the truncated approximation f(x) = [Sum c T (x)] - (1/2) c (5.6.9) k k-1 1 with the same cj's, computed from (5.6.7). Since the Tk(X)'S are an bounded between ±1, the difference between (5.6.9) and (5.6.8) can be no larger than the sum of the neglected Ck's (k = m + 1,...,N). ln fact, if the Ck's are rapidly decreasing (which is the typical case), then the error is dominated by Cm+1Tm(x), an oscillatory function with m + 1 equal extrema distributed smoothly over the interval [-1, 1]. This smooth spreading out of the error is a very important property: The Chebyshev approximation (5.6.9) is very nearly the same polynomial as that holy grail of approximating polynomials the minimax polynomial, which (among an polynomials of the same degree) has the smallest maximum deviation from the true function f(x). The minimax polyno- mial is very difficult to find; the Chebyshev approximating polynomial is almost identical and is very easy to compute! So, given some (perhaps difficult) means of computing the function f(x), we now need algorithms for implementing (5.6.7) and (after inspection of the resulting Ck'S and choice of a truncating value m) evaluating (5.6.9). The latter equation then becomes an easy way of computing f(x) for an subsequent time. The first of these tasks is straightforward. A generalization of equation (5.6.7) that is here implemented is to allow the range of approximation to be between two arbitrary limits a and b, instead of just -1 to 1. This is effected by a change of variable x - (1/2)(b + a) y = ---------------- (5.6.10) (1/2)(b-a) and by the approximation of f(x) by Chebyshev polynomial in y. From [BIBLI 08]. ---------------------------------------------------------------- End of file chebyshe.txt