余弦函数线性组合的最大值求解及阈值判定优化方案问询

给定整数序列 $a_1, a_2, \dots, a_n$，我想知道能不能找到计算以下函数最大值的方法：
$$f(\theta) = \sum_{j=1}^n a_j \cos(j \theta)$$

更具体地说，我需要判断 $f(\theta)$ 是否能超过某个给定值 $N$，而且我估计大部分测试序列应该都能满足这个条件。

我目前的做法是直接在101个点上计算这个函数的值，也就是 $\theta = 0, \frac{\pi}{100}, \dots, \frac{99\pi}{100}, \pi$，把得到的最大值记为 $M$，这个 $M$ 其实是 $f$ 最大值的一个下界，之后我就直接判断 $M > N$ 与否。

这个方法的好处是不会出现假阳性（只要 $M > N$，那 $f$ 肯定在某个点超过了 $N$），但有没有其他计算复杂度差不多的方法，能得到更紧的下界——从而减少假阴性的概率呢？（假阴性就是 $M \leq N$ 但实际上 $f$ 在某个点还是超过了 $N$ 的情况）

补充测试结果：
下面提到的牛顿法确实比我之前的方法有明显改进。我用100,000个长度为20的序列做了测试，这些序列对应的 $f$ 都能在某个点超过 $N$：

• 用100个点采样的方法，能确认超过 $N$ 的比例是99.6%；
• 把采样点减少到25个，耗时只有原来的30%，但能确认的比例降到了92.6%；
• 而用25个采样点加上牛顿法，耗时是原来的50%，但能确认的比例达到了99.7%。

现在我想问问，还有没有其他类似牛顿法或者别的方法能进一步优化？比如有没有针对这类正弦/余弦函数特性的专门方法？

备注：内容来源于stack exchange，提问作者user200783