Why Does My FFT Integration Method Produce Nonzero Imaginary Parts?

[SchroedingersLion]

TL;DR

I am posting this in the EE forum since electrical engineers are typically skilled with Fourier transforms.

Hi guys,

for a project I had to get involved with discrete Fourier transforms to solve PDEs.
However, the code that I implemented according to a pseudo-code from a paper did not work - it seems like I calculated integrals incorrectly.

To search the error, I tried to integrate the sin(x) function with my method, and it did not work.
I already posted the formula I used for this sine integration, as well as the code, here:
https://scicomp.stackexchange.com/questions/33886/calculate-integrals-using-numpy-fft
Does anyone know what I am doing wrong? The error does not depend on N, and after my inverse FT my signal contains nonzero imaginary parts which should not happen! Is there something wrong with my formula?

I am a bit desperate, since my deadlines are getting closer...
SL

 

[jedishrfu]

I don't think you're going to get much help with Thanksgiving coming up tomorrow.

I saw on Stack you got a couple of responses already.

These are the kinds of problems where you really need to dig in and gain some insight into what is actually going on. Sadly, unless someone has direct experience here its unlikely you'll get the help you need.

As a programmer, I can relate to using a function to do something not really knowing what's going on and trusting that it works as advertised. Most notably are the various integrators that folks like to use like Runge-Kutta RK4 and I have no idea how it does its magic but hey it works so I've use it.

Jedi

 

[SchroedingersLion]

Don't know about Thanksgiving, I am sitting in Europe ^^

I only got two comments, and they imply that something seems to be wrong with the formula.
Isn't this a complete basic problem? I thought that was a trivial question for people who know their way around FTs.

edit: I edited the question, maybe it was not clear that I am talking about integration of sin(x) using fft in this example.

 

[cosmik debris]

I can't help you directly but people use the FFT method for calculating integrals of acceleration to get velocity and position from IMUs (Inertial Measuring Units). The students here seem to find plenty of resources for doing this calculation in the IMU literature. Perhaps looking at some of this stuff may help.

Cheers

 

[DrClaude]

Isn't it just a question of normalization of the FFT?

 

[SchroedingersLion]

I would not know how. The deviation I am seeing is independent of number of data points N. Moreover, my final vector after the inverse transform has nonzero imaginary parts which should be impossible when I take the FFT of a purely real signal. To me, it looks like there is an error in my theoretical formula.

I expand the function in a Fourier series under the integral and truncate it for $|k|>m$. In my code, I only know the function on $2m+1$ discrete data points and I try to calculate the $A_k$, i.e. the coefficients of the Fourier series, via a FFT. Maybe there is something wrong with this approach?

 

[osilmag]

You might have forgotten to multiply by the last $e^{2piky}$ term in your loop.

 

[SchroedingersLion]

But why would I need these? They are simply the usual exponentials of the inverse transform, they do not belong to the amplitudes that are given by ifft.

 

[SchroedingersLion]

I think I found the mistake.
If I know the discrete Fourier transform, i.e. $$ A_k =\sum_{i=-N}^{N} f(x_i)\cdot e^{-i2\pi x_i k}$$ and I write $$ f(x_i)=\sum_{k=-N}^{N} A_k\cdot e^{i2\pi x_i k},$$ then it does not follow that
$$f(x_i+y)=\sum_{k=-N}^{N} A_k\cdot e^{i2\pi (x_i+y) k}.$$

I tested this with a small code:

This would explain why I have not found this kind of integration online :D

What do you think?