All roots spectral methods: Constraints, floating point arithmetic and root exclusion

The nonlinear two-point boundary value problem (TPBVP for short) $$u_{xx}+u^{3}=0,\quad u(0)=u(1)=0,$$ offers several insights into spectral methods.

First, it has been proved a priori that $$\int u(x)dx=\frac p{\sqrt{2}}.$$ By building this constraint into the spectral approximation, the accuracy of $N=1$ degrees of freedom is achieved from the work of solving a system with only N degrees of freedom. When N is small, generic polynomial system solvers, such as those in the computer algebra system Maple, can find all roots of the polynomial system, such as a spectral discretization of the TPBVP.

Our second point is that floating point arithmetic in lieu of exact arithmetic can double the largest practical value of N. (Rational numbers with a huge number of digits are avoided, and eliminating M symbols like $\sqrt{2}$ and p reduces $N+M$-variate polynomials to polynomials in just the N unknowns.) Third, a disadvantage of an “all roots” approach is that the polynomial solver generates many roots $( 3^N-1)$ -for our example – which are genuine solutions to the $N$-term discretization but spurious in the sense that they are not close to the spectral coefficients of a true solution to the TPBVP.

We show here that a good tool for “root-exclusion” is calculating $$\rho=\sqrt{\sum\limits_{n=1}^{N}b_{n}^{2}};$$ spurious roots have $\rho$ larger than that for the physical solution by at least an order of magnitude. The $\rho$-criterion is suggestive rather than infallible, but root exclusion is very hard, and the best approach is to apply multiple tools with complementary failings.

John P. Boyd
(Department of Climate & Space Sciences and Engineering, University of Michigan, United States)

Calin-Ioan Gheorghiu
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)

See the expanding block below.

J.P. Boyd, C.I. Gheorghiu, All roots spectral methods: Constraints, floating point arithmetic and root exclusion, Applied Mathematics Letters 67 (2017) 28–32
DOI: 10.1016/j.aml.2016.11.015

?

Google Scholar Profile

?