MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'd like to have an algorithm for a numerical calculation of Fourier transform with a nice error bound. To be precise, if $f$ is a function from $L_1(R)$, $F[f]$ is it's exact Fourier transform and $F_a[f]$ is the "numerical" Fourier transform, I'd like to have the inequality $$ \int_{R} Err(x) dx < \infty, $$ where $Err(x):=|F[f](x) - F_a[f](x)|$, or at least $$ Err(x) < G(x), $$ where $G(x) \to 0$ as $|x| \to \infty$. Do such algorithms exist (at least for functions $f$ from some narrow classes)? Or maybe someone may give concrete examples of algorithms and functions $f$ for which the error $Err(x)$ tends to zero as $|x| \to \infty$?

Thanks in advance.

share|cite|improve this question

This is a subject of a very nice paper by Charlie Epstein (2004)

share|cite|improve this answer

If a numerical algorithm is only allowed to evaluate $f$ at a finite set of points, you're going to have a problem: $f$ might happen to be $0$ at all the points where you evaluate it. Clearly no error bound is possible under such circumstances.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.