Volume 6, Issue 4
A Fourier Companion Matrix (Multiplication Matrix) with Real-Valued Elements: Finding the Roots of a Trigonometric Polynomial by Matrix Eigensolving

John P. Boyd

Numer. Math. Theor. Meth. Appl., 6 (2013), pp. 586-599.

Published online: 2013-06

Preview Full PDF 189 1766
Export citation
  • Abstract

We show that the zeros of a trigonometric polynomial of degree $N$ with the usual $(2N +1)$ terms can be calculated by computing the eigenvalues of a matrix of dimension $2N$ with real-valued elements $M_{jk}$. This matrix $\vec{\vec{M}}$ is a multiplication matrix in the sense that, after first defining a vector $\vec{\phi}$ whose elements are the first $2N$ basis functions, $\vec{\vec{M}}\vec{\phi}$ = 2cos($t$)$\vec{\phi}$. This relationship is the eigenproblem; the zeros $t_{k}$ are the arccosine function of $\lambda_{k}/2$ where the $\lambda_{k}$ are the eigenvalues of $\vec{\vec {M}}$. We dub this the "Fourier Division Companion Matrix'', or FDCM for short, because it is derived using trigonometric polynomial division. We show through examples that the algorithm computes both real and complex-valued roots, even double roots, to near machine precision accuracy.

  • Keywords

Fourier series, trigonometric polynomial, root-finding, secular, companion matrix.

  • AMS Subject Headings

65H99, 65T40, 42A85

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-6-586, author = {}, title = {A Fourier Companion Matrix (Multiplication Matrix) with Real-Valued Elements: Finding the Roots of a Trigonometric Polynomial by Matrix Eigensolving}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2013}, volume = {6}, number = {4}, pages = {586--599}, abstract = {

We show that the zeros of a trigonometric polynomial of degree $N$ with the usual $(2N +1)$ terms can be calculated by computing the eigenvalues of a matrix of dimension $2N$ with real-valued elements $M_{jk}$. This matrix $\vec{\vec{M}}$ is a multiplication matrix in the sense that, after first defining a vector $\vec{\phi}$ whose elements are the first $2N$ basis functions, $\vec{\vec{M}}\vec{\phi}$ = 2cos($t$)$\vec{\phi}$. This relationship is the eigenproblem; the zeros $t_{k}$ are the arccosine function of $\lambda_{k}/2$ where the $\lambda_{k}$ are the eigenvalues of $\vec{\vec {M}}$. We dub this the "Fourier Division Companion Matrix'', or FDCM for short, because it is derived using trigonometric polynomial division. We show through examples that the algorithm computes both real and complex-valued roots, even double roots, to near machine precision accuracy.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.2013.1220nm}, url = {http://global-sci.org/intro/article_detail/nmtma/5920.html} }
TY - JOUR T1 - A Fourier Companion Matrix (Multiplication Matrix) with Real-Valued Elements: Finding the Roots of a Trigonometric Polynomial by Matrix Eigensolving JO - Numerical Mathematics: Theory, Methods and Applications VL - 4 SP - 586 EP - 599 PY - 2013 DA - 2013/06 SN - 6 DO - http://doi.org/10.4208/nmtma.2013.1220nm UR - https://global-sci.org/intro/article_detail/nmtma/5920.html KW - Fourier series, trigonometric polynomial, root-finding, secular, companion matrix. AB -

We show that the zeros of a trigonometric polynomial of degree $N$ with the usual $(2N +1)$ terms can be calculated by computing the eigenvalues of a matrix of dimension $2N$ with real-valued elements $M_{jk}$. This matrix $\vec{\vec{M}}$ is a multiplication matrix in the sense that, after first defining a vector $\vec{\phi}$ whose elements are the first $2N$ basis functions, $\vec{\vec{M}}\vec{\phi}$ = 2cos($t$)$\vec{\phi}$. This relationship is the eigenproblem; the zeros $t_{k}$ are the arccosine function of $\lambda_{k}/2$ where the $\lambda_{k}$ are the eigenvalues of $\vec{\vec {M}}$. We dub this the "Fourier Division Companion Matrix'', or FDCM for short, because it is derived using trigonometric polynomial division. We show through examples that the algorithm computes both real and complex-valued roots, even double roots, to near machine precision accuracy.

John P. Boyd. (2020). A Fourier Companion Matrix (Multiplication Matrix) with Real-Valued Elements: Finding the Roots of a Trigonometric Polynomial by Matrix Eigensolving. Numerical Mathematics: Theory, Methods and Applications. 6 (4). 586-599. doi:10.4208/nmtma.2013.1220nm
Copy to clipboard
The citation has been copied to your clipboard