# Roots of a finite Fourier series?

In general, are there any clever tricks to help find the roots of a finite Fourier series? Presumably there aren't analytic methods, but can we use the fact that our function is a finite Fourier series to facilitate numerical methods?

The hardest part of numerical root finding is bracketing the root, so is there a way we can do that easily? I know for a general function it's a hard problem.

• There are methods that depend on calculating eigenvalues of a special matrix that depends on the Fourier series coefficients. I'm googling around a bit, but I know the Chebfun package for MATLAB does something similar, but for a Chebyshev polynomial instead of a Fourier series. Commented Apr 24, 2013 at 1:09
• To go further, it seems the latest review article on the topic is called "Computing the zeros, maxima and inﬂection points of Chebyshev, Legendre and Fourier series: solving transcendental equations by spectral interpolation and polynomial rootﬁnding" Commented Apr 24, 2013 at 1:17
• And finally, I was wrong about that being a review article. It is (according to the authors) the first work to publish the result. They give the formulation of how to construct the aforementioned matrix, which is in terms of the Fourier series coefficients. You calculate the eigenvalues of that matrix, and calculate some simple functions on those eigenvalues to give you the roots of your Fourier series. Commented Apr 24, 2013 at 1:33
• @rajb245 That looks really interesting. Unfortunately I don't have access to Springer Journals, and I don't see a free PDF online anywhere. :/ Commented Apr 24, 2013 at 3:33
• By writing the sines and cosines in terms of exponentials you can analytically approximate the large zeros of your sum with exponentially decreasing absolute error. I treat a simple example in my answer to this question and give a reference to a paper which addresses the general case. Commented Apr 26, 2013 at 0:16

## 1 Answer

The short answer to your question is "yes", you can exploit the structure of the Fourier-series to reduce your rootfinding problem to a matrix eigenvalue problem, which can then be solved efficiently using QR decomposition. None of this is my own, but I'm paraphrasing a paper by John P. Boyd at University of Michigan from 2006, entitled "Computing the zeros, maxima and inﬂection points of Chebyshev, Legendre and Fourier series: solving transcendental equations by spectral interpolation and polynomial rootﬁnding". Let a finite Fourier-series with $$2N+1$$ terms be given by

$$f_N(t) = \sum_{j=0}^N a_j\cos(jt) + \sum_{j=1}^N b_j\sin(jt)$$

Define the following $$2N+1$$ coefficients:

$$h_k = \left\{\begin{array}{ll} a_{N-k}+i b_{N-k}, & k=0,1,\ldots,(N-1)\\ 2 a_0 & k=N \\ a_{k-N} - i b_{k-N} & k=N+1,N+2,\ldots, 2N \end{array}\right.$$

And define the following $$2N\times2N$$ matrix $$\bf B$$ with entries $$B_{jk}$$ at indicies $$j,k$$ as $$B_{jk} = \left\{ \begin{array}{ll} \delta_{j,k-1}, & j=1,2,\ldots,(2N-1)\\ - \frac{h_{k-1}}{a_N - i b_{N}} & j=2N \end{array}\right.$$

The delta above is the Kronecker delta that is one when its two arguments are the same, zero otherwise. Let the matrix $$\bf B$$ have eigenvalues given by $$z_k$$, then the roots of $$f_N(t)$$ are given by

$$t_k = -i \log(z_k)$$

In general $$z_k$$ will be complex or negative, so we mean the complex logarithm (this nicely gives that each root is also periodic, the expected behavior of a periodic function)

$$\log(z) = \log(|z|) + i (\arg(z)+2\pi m) \;\;\text{for integer }m$$

For a final formula for the periodic roots

$$t_k = \arg(z_k)+2\pi m-i \log(|z_k|),\;\;k=1,2,\ldots,2N,\;\;m\text{ an integer}$$

So the numerical task of Fourier series rootfinding is reduced to basically solving for eigenvalues of the matrix $$\bf B$$.

• Thanks, that's what I was looking for :) Commented Apr 26, 2013 at 0:22
• The pdf of this paper is here Commented Nov 17, 2021 at 12:49