From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) Newsgroups: sci.math Subject: Re: Taylor Series for Arctan Date: 23 Jun 1998 18:35:22 -0400 In article , Christian Bau wrote: >In article <6mgp9t$3rs@nnrp3.farm.idt.net>, robjohn9@idt.net (Rob Johnson) >wrote: > >> The Chebyshev polynomials are a set of orthogonal polynomials that are >> solutions to the Chebyshev differential equations: >> >> 2 >> ( (1-x^2) D - x D + m ) P = 0 >> >> Because they are orthogonal polynomials, their usage is similar to that >> of sin(nx) and cos(nx). They are used more for theoretical purposes than >> computational. Perhaps I am missing something, but I don't see how these >> polynomials are going to speed up the computation of arctan. > >That should be obvious: With orthogonal polynomials, you can easily >construct a polynomial that is the "best approximation" to arctan x for >certain definitions of "best approximation", and this polynomial is quite >likely to give a smaller error than the taylor polynomial. For example, >using orthogonal polynomials you can find the polynomial p that minimises >Integral (x = -1 to +1) (arctan x - p(x)) ^ 2. > Correction: It is different weight: integral (x=-1 to 1) (arctan(x) - p(x))^2 * (1-x^2)^(-1/2) dx or by a change of variable, integral (t=0 to pi) (arctan(cos(t)) - p(cos(t)))^2 dt The expression (I quote) >Integral (x = -1 to +1) (arctan x - p(x)) ^ 2 dx is minimized (given an upper bound on degree(p)) by an expansion into Legendre polynomials. It would be rather messy. The Chebyshev expansions of a scaled arctangent are neater, namely: Given k>0, define q = k / (1 + (1 + k^2)^(1/2)), and then arctan(k*x) = 2 * sum(n=0 to inf.) ((-1)^n * q^(2*n+1)/(2*n+1)) * T_(2*n+1)(x) In particular, for k=1 and x=1, the series converges (note q=1/(1+sqrt(2))) but the effect is not very spectacular. A similar improvement can be achieved by a half-angle formula: arctan(x) = 2 * arctan (x/(1+sqrt(1+x^2))) where we substitute z=x/(1+sqrt(1+x^2)) and apply Maclaurin's formula to z. Similarly, we can halve the angle several times until we obtain an argument small enough to be handled by a very short segment of the power series. The details of the design can be left to the user who is more familiar with the arithmetical device. >Also, could it be there are quite a lot of polynomials that are called >Chebyshev polynomials? I remember Chebyshev's theorem: > >Let f(x) be a function that is continuous on [a, b]. Then there is exactly >one polynomial p of degree n that minimises max (|p(x)-f(x)|) for x in [a, >b], and this polynomial has the property that there are n+2 consecutive >points where the error is maximal, but with alternating sign (and I >remember this polynomial being called a Chebyshev polynomial). Looks like two theorems and two terms compressed into one approximate reminiscence: The polynomial claimed to exist is expected to have degree n _or less_ (what if f is already a polynomial of degree 1, and n is set to be equal to 2?). The "equiripple" property is quoted correctly, but the resulting polynomial is perhaps called the "best uniform approximation of f" with some more specifications. The term "Chebyshev polynomials" is attached to something else. The (original) Chebyshev polynomials of the first kind are best defined in [-1,1] by the notorious T_n(x) = cos(n*arccos(x)). They are best generated and implemented by T_0(x)=1, T_1(x)=x, T_(n+1)(x) = 2 * x * T_n(x) - T_(n-1)(x) for n = 1, 2, ... They are orthogonal on [-1,1] with the weight 1/sqrt(1-x^2) , and for n>=1, T_n(x)/2^(n-1) is the unique polynomial among those with leading term x^n which has the smallest maximum norm on [-1,1]. This means that when we use m+1 terms of a Chebyshev expansion of a function f on [-1,1], and then drop the (m+1)st term c_(m+1)*T_(m+1)(x) then we commit an extra (uniformly bounded) error of size exactly abs(c_(m+1)). Contrary to claims in other posts, it is not necessary (and it may lead to serious loss of accuracy) to convert Chebyshev expansion into a polynomial in power form to make it useful. Chebyshev expansions (and other expansions into polynomials satisfying recursive relations) can be evaluated using a "Clenshaw scheme" (see reference). Also, contrary to what has been seen in other posts, there extra errors do _not_ add up exactly (they only "sub-add", according to triangle inequality). ***In particular, the m-term orthogonal Chebyshev approximation of f is _not always_ the best uniform approximation of f (of degree less than m) on [-1,1]*** (examples exist but the interesting ones are messy). It is "near-best" in that the error of the m-term orthogonal expansion can be greater than the m-term best uniform approximation only by a factor const.*log(m) (recall log(1000) is about 7, and who wants to use expansions with 1000 terms?) For bounded intervals [a,b] other than [-1,1], we simply change the variable: the n-th modified Chebyshev polynomial is T_n((2*x-a-b)/(b-a)) There are also Chebyshev polynomials of second kind: for x in [-1,1], U_n(x) = sin((n+1)*arccos(x))/sin(arccos(x)) (make up your own recursive formula). They, when normalized to become monic (with leading coefficient 1) have the smallest L^1 distance from 0 among monic polynomials of the same degree. They have a similar "extra error" property for L^1 approximations. (L^1[-1,1] distance from f to g: integral(x=-1 to 1) abs(f(x)-g(x)) dx ) Reference: Cheney's Approximation Theory, or other books on this subject. Cheers, ZVK (Slavek).