6 ms·
Folks interested in this topic should look at Chebfun, http://www.chebfun.org http://www.chebfun.org Also at Lloyd Trefethen’s book Approximation Theory and Ap
by jacobolus 11y ago
Folks interested in this topic should look at Chebfun, http://www.chebfun.org http://www.chebfun.org
Also at Lloyd Trefethen’s book Approximation Theory and Approximation Practice, of which the first 6 chapters are available online, http://www.chebfun.org/ATAP/ http://www.chebfun.org/ATAP/
The author of this blog post might as well have used Clenshaw’s algorithm as he mentioned was suggested by Numerical Recipes. It’s like 4–5 lines of code, fast, and has been proven numerically stable.
If bk1, and bk2 are the previous two terms of the recurrence, and c the coefficient array, code to find y = f(x) for x in [-1, 1] looks like:
x2 = 2*x
bk2 = bk1 = 0
for ck in c[:0:-1]:
bk2, bk1 = bk1, ck + x2*bk1 - bk2
y = c[0] + x * bk1 - bk2
(Note: There might be some typos there, I didn’t try running that. Here’s a vectorized Matlab version https://github.com/chebfun/chebfun/blob/development/%40chebtech/clenshaw.m https://github.com/chebfun/chebfun/blob/development/%40chebt... with coefficients in that version ordered from highest to lowest)
Or if he wanted an easy Python tool, just used this (partial) python port of Chebfun (though I guess it dates from around the same time as his post), https://github.com/olivierverdier/pychebfun https://github.com/olivierverdier/pychebfun
I’m not convinced about his measurements on an arbitrary grid -> chebyshev coefficients via weighted least squares method. If his measurement points are reasonably clustered near the endpoints of his interval, he could just use an exactly interpolating polynomial and use the barycentric interpolation formula to get the values at the chebyshev points (see Trefethen’s book). His approach might also be fine, I haven’t thought deeply about it. Also see http://www.chebfun.org/examples/approx/RationalInterp.html http://www.chebfun.org/examples/approx/RationalInterp.html http://www.chebfun.org/examples/approx/EquispacedData.html http://www.chebfun.org/examples/approx/EquispacedData.html http://www.chebfun.org/examples/approx/BestL2Approximation.html http://www.chebfun.org/examples/approx/BestL2Approximation.h...
The neat thing about Chebyshev polynomials is that it’s possible to convert from values at the Chebyshev points (either extrema or roots of the Chebyshev polynomial) to Chebyshev coefficients by using an FFT, which takes O(n log n) time. Along with various other efficient algorithms for differentiation, integration, root finding, solving differential equations, etc., Chebfun makes it practical to deal with polynomials of very high degree, and do lots of neat stuff with them.
This blog post’s statement that “higher degree polynomials can have problems with numerical accuracy” turns out to be a myth: https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf
- irremediable 11y agoThanks for an excellent comment -- IMO more useful than the original article. I skimmed a short Trefethen course at the behest of a physicist friend once, and was really impressed by it. I want to study that stuff in more depth someday.
- nimish 11y agoIt's a damned good course and worth a lot of time.
- jacobolus 11y agoI’m realizing my comment sounds kind of negative. Overall I thought it was a great blog post, full of nice pictures!
- jason_s 11y ago>This blog post’s statement that “higher degree polynomials can have problems with numerical accuracy” turns out to be a myth (author here) I should have qualified or corrected that statement in my article. There are a few reasons I rarely use n>5: - when polynomial approximation is appropriate, high-degree polynomials are usually unnecessary on embedded systems (0.1% accuracy usually sufficient) - it's usually a sign that polynomial approximation is being misapplied and there are better ways (via range reduction, transformation like 1/f(x), etc.) - with least-squares, computation of the coefficients can have problems with numerical accuracy. When I've used least-squares fitting polynomials with n>10, I often get a complaint from my numerical tool (MATLAB or Python) that the matrix in question is ill-conditioned. That may be because I used the Vandermonde matrix rather than Chebyshev polynomials, or because I used a large number of points. Chebyshev approximation doesn't have the same problem, I don't think, and I should not have mapped my experience with least-squares fitting onto Chebyshev approximation. Evaluation of the polynomials themselves should be fine (after all, we can easily compute a 20th-degree Chebyshev polynomial).
- jacobolus 11y agoFor fitting arbitrary spaced data, you might also try using a rational interpolant, e.g. Floater & Hormann’s http://www.inf.usi.ch/hormann/papers/Floater.2007.BRI.pdf http://www.inf.usi.ch/hormann/papers/Floater.2007.BRI.pdf and then afterward approximating that by a Chebyshev polynomial of somewhat higher degree for evaluation or other operations like taking derivatives or finding roots etc. (IIRC Trefethen’s book explains this idea, and the last few links in my comment above are also related).