Hacker News Reader

Comment by prvc | Hacker News Reader

>The reason why the Apollo team chose these terms instead of the Taylor ones was because these were actually optimized for minimum error in the interval −π/2<y<π/2

How would these coefficients be derived in the first place?

View on HN

They used the Remez exchange algorithm to find the polynomial with minimax relative error. https://en.wikipedia.org/wiki/Remez_algorithm

If you want to play with this sort of thing and you have access to a copy of Matlab, check out Chebfun, https://www.chebfun.org/examples/approx/

There is a blogpost linked in the annotations: http://jeanmariechauvet.com/papers/curttrig.html

Here are the graphs [0] for both functions from the article:

+ 1/2 * sin(x * pi / 2)

+ 0.785313 * x - 0.321615 x^3 + 0.0363551 x^5

[0] https://www.desmos.com/calculator/x7tm7i2qtj

Also here is the same graph with the classic taylor expansion of sin with 3 terms (x + (x^3)/(3!) + (x^5)/(5!)):

https://www.desmos.com/calculator/emfz64hjhv

Showing relative error: https://www.desmos.com/calculator/a3whptxkqu

We did this in my quantum mechanics class, 8.05x on edX. Consider the functions f_n(x) = x^n to be basis vectors in a vector space. Define the dot product of two vectors (aka functions) to be the integral of their product between -pi/2 and +pi/2. You'll see that your basis vectors aren't orthogonal. So, use Graham Schmidt to make them orthogonal, and normalize them while you're at it.

Now you just take the dot product of these new basis vectors with your target function.

Worth noting that this minimizes expected error. IMO, it's much more common to want to minimize maximum (worst-case) error, which requires an algorithm like Remez exchange. You can modify this algorithm to work with relative error (as suggested in the article) instead of absolute error.

Nitpick: Gram-Schmidt.

If one understands linear algebra (and has Haskell output of matrices with nice eigenvalues), then reviewing this spelling is the only preparation needed to teach a semester course.

Also, something doesn't add up here because they were calculating sin(pi*y/2). I suspect it's optimized for -1 < y < 1, so the argument to sin is in [-pi/2, pi/2].

Reply on news.ycombinator.com