[math-fun] Chebyshev points for real interval [-1, 1], pretty picture
This picture https://dl.dropboxusercontent.com/u/3507527/Chebyshev175nrpi.png shows the Chebyshev 175-point set -- whose (unweighted) first 175 moments agree with those of the (uniform distribution on the) real interval [-1,1]. Caveats: Unfortunately the polynomial root solver has numerical difficulties so it is dubious these are very accurate. (If I try for 201 points it totally dies.) Only points with non-positive real part and non-negative imaginary part are shown, i.e. this is one quarter of the full picture. So it appears Chebyshev ultimately is approximating the real interval with an ellipse (or something close to it) plus a few stragglers, perhaps on another curve. Pretty interesting, whatever the hell it is. A natural guess is that the ellipse has foci at +-1. It would be good to produce a more-accurate plot of, say, the 1001-point set. Here is how to tell "maxima" to compute the 51 point set: f(N) := taylor( exp( (N/2)*(log(1-z^2) + (2/z)*atanh(z) - 2) ), z, 0, N); g(N) := subst(1/x, z, trunc(f(N))) * x^N; expand(g(51)); allroots(%); In words: find the Maclaurin series of exp( (N/2)*(log(1-z^2) + (2/z)*atanh(z) - 2) ) in powers of z from z^0 up to and including z^N, this is a polynomial in z. Now replace z by 1/x, then multiply the whole thing by x^N, to get the "reversed" degree-N polynomial, which is monic. Now find its roots. The result is the Chebyshev N-point set. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
This is interesting. Can Gaussian integration be improved by moving the sampling points off the [-1,1] interval into the complex plane, and allowing complex weights? -- Gene
________________________________ From: Warren D Smith <warren.wds@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Wednesday, July 9, 2014 1:53 PM Subject: [math-fun] Chebyshev points for real interval [-1, 1], pretty picture
This picture
https://dl.dropboxusercontent.com/u/3507527/Chebyshev175nrpi.png
shows the Chebyshev 175-point set -- whose (unweighted) first 175 moments agree with those of the (uniform distribution on the) real interval [-1,1].
Caveats: Unfortunately the polynomial root solver has numerical difficulties so it is dubious these are very accurate. (If I try for 201 points it totally dies.) Only points with non-positive real part and non-negative imaginary part are shown, i.e. this is one quarter of the full picture.
So it appears Chebyshev ultimately is approximating the real interval with an ellipse (or something close to it) plus a few stragglers, perhaps on another curve. Pretty interesting, whatever the hell it is. A natural guess is that the ellipse has foci at +-1.
It would be good to produce a more-accurate plot of, say, the 1001-point set. Here is how to tell "maxima" to compute the 51 point set:
f(N) := taylor( exp( (N/2)*(log(1-z^2) + (2/z)*atanh(z) - 2) ), z, 0, N); g(N) := subst(1/x, z, trunc(f(N))) * x^N; expand(g(51)); allroots(%);
In words: find the Maclaurin series of exp( (N/2)*(log(1-z^2) + (2/z)*atanh(z) - 2) ) in powers of z from z^0 up to and including z^N, this is a polynomial in z. Now replace z by 1/x, then multiply the whole thing by x^N, to get the "reversed" degree-N polynomial, which is monic. Now find its roots. The result is the Chebyshev N-point set.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
On 7/9/14, Warren D Smith <warren.wds@gmail.com> wrote:
This picture
https://dl.dropboxusercontent.com/u/3507527/Chebyshev175nrpi.png
shows the Chebyshev 175-point set -- whose (unweighted) first 175 moments agree with those of the (uniform distribution on the) real interval [-1,1].
--it occurs to me that the behavior in this picture (if genuine when N--> infinity points) should prove that the Chebyshev numerical integration method FAILS TO CONVERGE to the correct answer, for trying to integrate integral f(x) dx from x=-1 to +1 if f(x) = 1/(x^2 + 0.01). To explain: the sum Chebyshev uses to approximate the integral, can be regarded as a closed-contour complex integral of f(x)/(N*pi*i) * [1/(x-x1) + 1/(x-x2) +...+ 1/(x-xN)] dx for a contour enclosing everything in the picture. This is because of the Cauchy residue theorem where the x1,x2,...,xN are the N Chebyshev points. This contour integral will get the right answer if f(x) is analytic everywhere inside the contour, for example for polynomials -- but the f(x) that I suggested has poles located at x = +- 0.1*i and hence we should get the wrong answer. Related, is the fact (discovered I think by C.D.T.Runge in 1901?) that the Newton-Cotes integration rules (using equispaced points and weights chosen to maximize degree of exactness) also fail to converge for integrating this f(x). So in conclusion: Newton-Cotes and Chebyshev both suck as max-degree-of-exactness mehtods of numerical integration. Gauss rules (it always converges, it is a Riemann-like sum). So this is a very nice and resounding conclusion... except that it is not presently rigorous, since it depends on proving that picture truly describes the limiting situation. If true, then the functions f(x) for which Chebyshev converges are going to be EXACTLY the functions analytic throughout that ellipse-like region! And essentially the same, I thunk, is also known to be true for Newton-Cotes.
participants (2)
-
Eugene Salamin -
Warren D Smith