Item — HN Reader

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

Also: be on the lookout for a blog post on using Chebyshev polynomials to efficiently compute error metrics for curves.

1 comments

Chebyshev’s polynomials seem to have eclipsed his semi-iterative method for solving linear systems, which is too bad IMO.

Why 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.

I’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.

That 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.