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

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.

-
This might be a good lead: arxiv.org/abs/math/0401382 by Chen and Griffin. In particular, see Figure 3 on page 42. – Paul Tupper Mar 8 2012 at 23:58
Wow, there's a lot more on this topic than I expected - e.g. Peherstorfer, Orthogonal and Extremal Polynomials on Several Intervals (1993, J. Comp. Appl. Math). No results concrete enough to use immediately, but I'm surprised how much people have thought about it. – Paul Mar 9 2012 at 2:26

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.

-
 Sorry, the previous reference is of course available in English as well. The English version of this journal was called Leningrad journal of math. Now StPeterburg journal. – Alexandre Eremenko Aug 6 at 8:33

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.

-
 I should mention that this method works for solving many variations on such problems. Want to add the constraint that $p(5) = 2$? This is affine in the decision variables, so can go right into the SDP. Only interested in globally convex $p$? The coefficients of $p''$ are linear in the decision variables so simply ask for $p''$ to be nonnegative everywhere. And so on... – Noah Stein Mar 8 2012 at 23:33 I really doubt that my question has an analytical answer, so this is probably the closest thing to it. – Paul Mar 8 2012 at 23:36