Discretising the Fourier Integral gives a high condition number

Question

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.

Answer 1

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)