polynomials with minimal $L_\infty$ norm on multiple disjoint intervals

Question

It is well-known that Chebyshev polynomials are the polynomials of minimal $L_\infty$ norm on [-1,1] with leading coefficient 1. But what if you want the minimal $L_\infty$ polynomial on two disjoint intervals $[-1,1]$ and $[a,b]$?

An upper bound can be obtained by seeking the minimal $L_\infty$ norm polynomial over the "filled-in" interval $I = [\min(-1,a), \max(1,b)]$. This would be a translated and scaled Chebyshev polynomial. My question is, can you do significantly better than this? Intuitively, can you exploit the fact that there is empty space between $[-1,1]$ and $[a,b]$ where the polynomial is not required to have a small value? Or is this empty space essentially useless?

My first instinct was to try a product of scaled Chebyshevs which are small on $[-1,1]$ and $[a,b]$ respectively. However there is no growth control on one Chebyshev in the others' interval, so there is no guarantee that you are doing any better. Because of this I am pessimistic that one can do much better than the upper bound, but I would love to be proven wrong.

I am interested in this question because I am studying the convergence of Krylov subspace methods, where such approximations play an important role. I want to understand the convergence rate of conjugate gradients when there are multiple clusters of eigenvalues contained in different intervals, rather than just a single cluster.

Answer 1

There exists a complete theory for minimal $L^\infty$ norm polynomials on two intervals. It is due to N. I. Akhiezer. You can look at his books: Lectures on Approximation theory or, another book, Elliptic functions. There is also a nice survey paper on this problem for any number of intervals, by Sodin and Yuditskii, Functions that deviate least from zero on closed subsets of the real axis. Algebra i Analiz 4 (1992), no. 2, 1--61.

Answer 2

This problem can be reformulated exactly as an SOS (sum of squares) program and then solved to any degree of accuracy efficiently as an SDP (semidefinite program). For lots of references I'd recommend Pablo Parrilo's course notes (full disclosure: he was my thesis advisor).

The general idea is as follows. If a polynomial is a sum of squares of polynomials (we will say it is SOS), then it is obviously nonnegative everywhere. The converse is true in a few notable cases such as univariate polynomials, which is all we will need. It turns out that the condition that an affine transformation of a vector be the coefficients of an SOS polynomial is expressible in a semidefinite program. A simple refinement of this method allows you to express the condition that a polynomial is nonnegative on a given interval.

To solve the problem you ask you can create a semidefinite program whose decision variables are the coefficients of your polynomial $p$ (here you must fix the degree of $p$) and a scalar $s$. Constrain the leading coefficient of $p$ to be $1$. Constraining $s - p(t)$ and $s+p(t)$ to be nonnegative on $[-1,1]$ and $[a,b]$ are four constraints of the type above -- a polynomial with coefficients affine in the decision variables must be nonnegative on an interval. These constraints say precisely that $s$ is at least the $L^\infty$ norm of $p$ on $[-1,1]\cup[a,b]$. You can then tell the SDP solver to minimize $s$, and the optimum will be the solution you seek.

Software-wise, SeDuMi and SDPT3 are good SDP solvers for MATLAB, and SOSTOOLS and YALMIP are good front-ends for these which allow you to enter SOS programs without having to convert them to SDPs by hand.