I have the following integral equation $$ \int_0^1 e^{-2\pi i s t} f(t)\, \text{d} t = g(s), \hspace{3em} -1/2 \leq s \leq 1/2$$ where $f$ is to be found, and $g$ is known. I believe this problem is equivalent to finding the inverse Fourier transform of $g$.

This can be viewed as a Fredholm equation of the first kind. The function $g$ is known on $n=129$ points, which are equally spaced and symmetric about $0$. I have used the midpoint quadrature method for $t$ to discretise this problem and obtain a linear system $$ A x = b,$$ where $x$ corresponds to $f$ evaluated at the quadrature points. The problem comes from the fact that the discretisation matrix $A$ in this problem has a huge condition number ($\sim 10^{16}$). My understanding of the Fourier transform is that this problem should be well-posed, or at least stable, and I'm struggling to figure out why the condition number am obtaining seems to be so high.

  • $\begingroup$ If the condition number is 10^16, you will be fine solving this in quad precision (and will run into trouble in double precision). Also, if $f$ is not periodic, then perhaps use Gaussian quadrature nodes/weights instead of the midpoint rule. The other answer suggests that the problem itself is ill-conditioned so I don't know if that's a panacea, but learning to use multiple precisions will be very useful. $\endgroup$ – user14717 Apr 27 at 0:19

The discretization matrix is Vandermonde, in that the ratio of successive columns is constant. Vandermonde matrices are notoriously ill-conditioned, see for example "How Bad Are Vandermonde Matrices?"https://arxiv.org/abs/1504.02118, Pan) and "How (Un)stable Are Vandermonde Systems?" (Gautschi, https://www.cs.purdue.edu/homes/wxg/selected_works/section_01/118.pdf)

In any case, Fredholm equations of the first kind tend to be ill-conditioned in general, so you should expect some numerical unpleasantness.

You may be interested in things like Galerkin methods, such as in "An augmented Galerkin method for first kind Fredholm equations." (Babolian and Delves, https://academic.oup.com/imamat/article/24/2/157/667517)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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