The best generally meaning the polynomial which minimizes the error (absolute or relative) with the input function. This error is often $L-\infty$ (the maximum of the absolute difference between the function and the approximating polynomial).
Remez:
The Remez algorithm find solution to linear system of $n+2$ equations $\sum_i{a_i.x_j^i} + (-\epsilon)^i = f(x_j) $ for j in $[0, n+1]$. It starts by setting $x_j$ values to the extrema of the degree $n$ Chebyshev polynomial (mapped to the input interval through affine scaling). Then solve the linear systems which provides a first set of $a_i$ coefficients. Then the extrema of $| P - f $ are found and used as a new set of $x_j$ and the processus is iterated. Theoretically, the process stops when the approximation errors are all equal and of alternating sign, the returned P is the minmax approximation polynomial.
During the iteration the reachable lower bound for the approximation error is the minimum of the absolute value of the extrema the difference $P - f$ (therorem de la Vallée Poussin)
Using Euclidean Lattices
Using Euclidean Lattices
Educational example of polynomial approximation: https://github.com/nibrunie/YourOwnPersonnalRemez
No comments:
Post a Comment