4 ms·
Yes! The workhorse numerical technique is Chebyshev approximation. Remez exchange usually starts with it, for fine-tuning with respect to a "maximum error" norm
by raphlinus 2y ago
Yes! The workhorse numerical technique is Chebyshev approximation. Remez exchange usually starts with it, for fine-tuning with respect to a "maximum error" norm, but it also works quite well by itself, and can be computed efficiently (even with a high degree) even from a function you can only evaluate numerically.
A really good place to read up on it is the documentation for Chebfun.
https://www.chebfun.org/docs/guide/guide04.html https://www.chebfun.org/docs/guide/guide04.html
Also: be on the lookout for a blog post on using Chebyshev polynomials to efficiently compute error metrics for curves.
- bee_rider 2y agoChebyshev’s polynomials seem to have eclipsed his semi-iterative method for solving linear systems, which is too bad IMO.
- sfpotter 2y agoWhy is that bad? Are there any cases where Chebyshev iteration is the best option? It seems like acquiring the necessary information about the spectrum would be prohibitive in practice, although I have never tried it out.
- bee_rider 2y agoI’ve only really played with it on a single-node machine, which isn’t where it ought to shine. IMO it sits at a really interesting spot as a sort of “more robust” (hand-waves) iterative solver that doesn’t require inner products. You need to know something about the spectrum sure, but sneakily figuring out things about the spectrum is somewhere where people can show off their expertise I think.
- sfpotter 2y agoThat seems plausible. I actually spent a little time digging into this, and I'm not sure if this method is actually due to Chebyshev! This link has the most extensive references I found: https://encyclopediaofmath.org/wiki/Chebyshev_iteration_method and from what I can tell it's actually due to Richardson.