General Error Bound on the Inverse Midpoint Integral Approximation

The error introduced by the inverse approximation may be quantified by considering the sum as a truncated Taylor series expansion of the integral [1]. In the general case of the integral $\int_a^b f(x) dx$, this leads to an error bound of

$$\left\vert e_m\right\vert \leq \frac{M(b-a)^3}{24p^2}$$ (26)

where $p$ is the number of subintervals between $a$ and $b$ and $\left\vert f''(x)\right\vert\leq M$. Applying this formula to the present case (over the variable $n$), we have

$$\left\vert e_m\right\vert \leq \frac{M(N/2-(-N/2))^3}{24 N^2} = \frac{MN}{24}.$$ (27)

We note that we only consider approximating over $N$ as opposed to $K$, since there is nothing to be gained in approximating the padding zeros. We also choose $K=N$ to simplify the number of potential cases (which does not affect any other pertinent values). We now must calculate $M$ by considering $f''(n)\leq M$:⁶

$$f(n) = \cos(\alpha n^2 - 2\pi k n/N)$$ (28)

$$f'(n) = -\sin(\alpha n^2-2\pi k n/N)(2\alpha n -2 \pi k/N)$$ (29)

$$f''(n) = -\cos(\alpha n^2-2\pi k n/N)(2\alpha n -2 \pi k/N)^2 -\sin(\alpha n^2-2\pi k n/N)(2\alpha).$$ (30)

In the worst case, the sine and cosine factors will be of magnitude 1, giving

$$\vert f''(n)\vert \leq \vert(2\alpha n -2 \pi k/N)^2 + 2\alpha\vert = M.$$ (31)

(We note that in actuality, both functions can never be 1 at the same time, which leads to an overly conservative bound.) The worst case now occurs when $n$ and $k$ are large and opposite in sign. We model the error bound in this situation as:

$$\vert f''(n)\vert \leq (\vert 2\alpha n\vert + \vert 2 \pi k/N\vert)^2 + 2\alpha = M.$$ (32)

Since $n$ is our variable of integration, we maximize over it. (The variable $k$ is best conceptualized as a constant that varies for each ``case'' of each different frequency bin in the FFT.) Since $n$ can be no greater than $N/2$, we have that

$$\vert f''(n)\vert \leq (\alpha N + \vert 2 \pi k/N\vert)^2 + 2\alpha = M.$$ (33)

Substituting into equation 27, we now have that

$$\left\vert e_m(k)\right\vert \leq \frac{N}{24}\left((\alpha N + \vert 2 \pi k/N\vert)^2 + 2\alpha\right)$$ (34)

$$= \frac{N}{24}\left(\alpha^2 N^2 + \vert 4 \pi k \alpha\vert + \ensuremath{\frac{4\pi^2 k^2}{N^2}}+ 2\alpha\right)$$ (35)

$$= \frac{1}{24}\left(2\alpha N + \ensuremath{\frac{4 \pi^2 k^2 \alpha}{N}}+\alpha^2 N^3 + \vert 4\pi k N\alpha\vert \right).$$ (36)

We observe that the error bound used here is overly conservative for two reasons. First, the assumption we made about the sinusoids being 1 was overly conservative as noted above. Second, the given bound implicitly assumes that the integrand varies as rapidly in general as it does in its most rapidly varying portions, namely the edges of the window where $n=\ensuremath{\frac{N}{2}}$. Thus, any term containing $N$ in the numerator is overly conservative. We consider a tighter bound below.