Minimax approximation

Remarks

Example: for $f(x) = x^2$ on $[-1, 1]$ and $n = 1$, the polynomial $p^*(x) = 1/2$ is the minimax approximation, with error $1/2$. Check: $x^2 - 1/2$ takes the values $1/2, -1/2, 1/2$ at $x = -1, 0, 1$. If a line $p$ had $\abs{x^2 - p(x)} < 1/2$ everywhere, then $p(-1) > 1/2$, $p(0) < 1/2$ and $p(1) > 1/2$, which no linear function can do, since $p(0)$ is the mean of $p(-1)$ and $p(1)$.

Non-example: the Taylor polynomial $1 + x$ of $e^x$ at $0$ is not the minimax approximation of degree $1$ on $[-1, 1]$. Its error $e^x - 1 - x$ is never negative, so lowering the line a little makes the largest error smaller.

A minimax approximation exists and is unique for every continuous $f$. It is characterised by equioscillation: the error $f - p^*$ attains its largest absolute value at $n + 2$ points with alternating signs. In terms of norms, $p^*$ minimises $\norm{f - p}_\infty$ over $\mathcal{P}_n$, where $\norm{g}_\infty = \max_{[a, b]} \abs{g}$.