Given the coefficients $a_0,\ldots,a_N$, $b_1,\ldots,b_N$ of a real trigonometric polynomial:
$ f(x) = a_0 + \sum_{n=1}^N a_n \cos(nx) + \sum_{n=1}^N b_n \sin(nx) $
is there any efficient way to approximately determine $\max_{x \in R} f(x)$? If so, what is the accuracy versus efficiency tradeoff?
It turns out that it is possible to achieve an arbitrarily small additive error using semidefinite programming. This is from the paper:
J.W. McLean, H.J. Woerdeman. Spectral factorizations and sums of squares representations via semidefinite programming. SIAM J. Matrix Anal. Appl., 23(3):646--655, 2001. (link)
The result can be rephrased as follows. Let $f(x)=F(e^{ix})$ where $F(z)= \sum_{n=-N}^N c_n z^n$, with $c_n=\frac{1}{2}(a_n-i\ b_n)$ and $c_{-n}=\bar{c}_n$. Then $\min_x f(x)$ is equal to $c_0$ minus the value of the following semidefinite program: $ min_F\ tr(F) $ such that $F \succeq 0$, and $\sum_{p=k}^N F_{p,p-k} = c_k$ for $k=1,\ldots,N$.
Since semidefinite programming can achieve an arbitrarily small additive error, we can approximate the minimum (and thus, the maximum) of $f$ within the same bound.
This was just asked (modulo a minus sign):
Even in the special case where $f(x) \geq 0$ for all $x$, there can't be any simple answer involving the coefficients $(a_n)$, $(b_n)$. You're basically asking to estimate the $L^\infty$ norm of a trigonometric polynomial in terms of the Fourier coefficients, and it's well known that this can't be done in any good way (more generally, the relation between the $L^p$ norm and the coefficients is horribly intractable, for any $p \ne 2$).
EDIT: I suppose it depends what you mean by a "good" way to approximate; this is a bit subjective, but I think "for any reasonable purpose" (any general-purpose programme you would actually run on a computer) no simple theoretical formula exists (which is guaranteed to have good error bounds).
However, if you want a numerical scheme to approximate a specific polynomial, that's a totally different question! You need a good numerical analyst (which I am not, sorry).
With credits to J.J. Green, I found this paper on finding the maximum modulus of a polynomial on the disk; it might be of help in this case.
I stumbled upon this question and I think I have an interesting answer. I will make use of the FFT, please remark that in this argument I do not deal with the numerical error of the FFT but there are explicit error bounds on the FFT so they may be taken into account (you can find them in Higham, Accuracy and Stability...); moreover I will use the representation of Fourier Series with exponentials because it makes the argument easier.
I suppose we are on $[0,1]$ and I will work with the complex exponential basis. Let $\hat{f}(k)$ be the coefficients of the Fourier series with respect to the exponential basi. Since $f$ is a trigonometric polynomial there exists a $K$ such that $\hat{f}(k)=0$ for $k>K$.
We observe now that $\hat{f'}(k)=2\pi i k \hat{f}(k)$. Therefore,
$$||f'||_{\infty}\leq 2\pi K \sum_{-K}^K |\hat{f}(k)|. $$
We now run the inverse FFT of size M bigger than K on the $\hat{f}(k)$. The inverse Fast Fourier Transform using the Cooley-Tuckey algorithm is fast and numerically well behaved and gives us the value of the trigonometric polynomial at $M$ equispaced points, call them $x_1, \ldots, x_M$.
Then $$ \max_{i=1,\ldots, M} f(x_i)\leq \max f(x)\leq \max_{i=1,\ldots, M} f(x_i)+ 2\pi \frac{K}{M} \sum_{-K}^K |\hat{f}(k)|. $$
There are some normalizations involved in the FFT, but the argument should work.
The basic approach could also be useful, and it should be compared with more advanced ones.
Note that $f$ is $2\pi$-periodic and Lipschitz of constant $L:= \sum_{n=1}^N n\sqrt{a_n^2+b_n^2}$ because for any $x\in\mathbb{R}$ $$|f'(x)|\le \sum_{n=1}^N n\big| a_n \sin(nx) - b_n \cos(nx)\big|\le \sum_{n=1}^N n\sqrt{a_n^2+b_n^2}. $$
Therefore for all positive integer $m$
$$0\le \max_{x\in\mathbb{R}}f(x)- \max_{1\le k\le m} f\big(\frac{2k\pi}m\big)\le \frac{\pi L}m.$$
