Algorithm approximating $g(x)=\sum_{j=1}^n{g_j\cos\left(xy_j\right)}$ I need help in designing an algorithm for approximating $$g(x)=\sum_{j=1}^n{g_j\cos\left(xy_j\right)}$$ at $n$ points $x_i$ with $|x_i|\leq 1$ in $O(n)$ operations, with absolute error bounded by $$10^{-6}\sum_{j=1}^n{|g_j|}$$
 A: Before we begin, I would like to point out that if you have an expression for $g(x)$ as a sum of a finite number of $\cos$ functions, then that is probably a great place to stop. Most mathematical packages have efficient methods for computing $\cos$ and $\sin$, so constructing something yourself can lead to less accurate results if you are careless when implementing a numerical method.
The most common approach to estimating $\cos(x)$ is to use its Taylor expansion: $$\cos(x) = \sum_{n=0}^\infty (-1)^n \frac{x^{2n}}{(2n)!}.$$ This has the convenient remainder formula: $$\left| \cos(x) - \sum_{k=0}^N (-1)^k \frac{x^{2k}}{(2k)!} \right| \le \frac{2^{N+1}}{(N+1)!} \sup_{x\in [-1,1]}\left|\frac{d^{N+1}}{dx^{N+1}} \cos(x)\right| \le \frac{2^{N+1}}{(N+1)!}.$$
For convenience, I will assume that $|y_i| < 1$. The error bound will scale for general $y_i$. In particular, if $M = \max |y_i|$ then you will need to replace $2^{N+1}$ with $(2M)^{N+1}$ for the overall error.
Let $$f_{i,N}(x) = \sum_{k=0}^N (-1)^k \frac{x^{2k}y_i^{2k}}{(2k)!}.$$
Then $$\left| g(x) - \sum_{i=1}^n g_i f_{i,N}(x)\right| = \left| \sum_{i=1}^n g_i ( \cos(xy_i) - f_{i,N}(x)) \right| \le \frac{2^{N+1}}{(N+1)!} \sum_{i=1}^n |g_i|.$$
Note that $2^N/(N+1)!$ is decreasing and tending toward zero. This term will be less than $10^{-6}$ when $N\ge 12$. If $|y_i|$ is not bounded by 1, a little more work will be necessary to determine the precise $N$ for which $(2M)^{N+1}/(N+1)! < 10^{-6}$.
Thus $$\left| g(x) - \sum_{i=1}^n g_i f_{i,12}(x)\right| \le 10^{-6} \sum_{i=1}^n |g_i|$$
for all $x \in [-1,1]$, and your approximating function is $\sum_{i=1}^n g_i f_{i,12}(x)$.
Checking the number of operations, we see that there is a fixed number of calculations to be performed to calculate $f_{i,12}$ for each $i$. Moreover, the number of operations is constant over all the $i$'s. Thus the operations scale with the number of $y_i$'s, namely it scales with $n$. Thus the approximation scheme is $O(n)$ in mathematical operations.
