A generalization of Chebyshev polynomials

Question

What is the monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$? The answer is the Chebyshev polynomial, and its largest value on $[-1,1]$ is $1/2^{n-1}$.

Now suppose we ask the following question: what is the polynomial of degree $n$ of the form $$x^n + a_d x^d + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$ which minimizes $\max_{x \in [-1,1]} |p(x)|$? Here $d<n$; if we take $d = n-1$, we recover the Chebyshev polynomial.

My main purpose in asking this is to estimate how big $\max_{x \in [-1,1]} |p(x)|$ is as a function of $n$ and $d$ for such a polynomial.

One can emulate the derivation of Chebyshev polynomials: we would solve the problem if we could construct a polynomial of this form which never exceeds $A$ in absolute value and oscillates between $A$ and $-A$ sufficiently many times in $[-1,1]$. However, its not immediately clear to me how to do this.

Answer 1

First of all, there is a general theory (due to Chebyshev) on the best uniform approximation of ANY continuoius function $f$ by polynomials of degree at most $d$ on an interval. It describes the polynomial of the best approximation, which is unique.

In Chebyshev's polynomials, $f=x^n$ and $d=n-1$. You are asking about $f=x^n$ and some given $d<n$. I do not recommend to read Chebyshev himself on this but Akhiezer, Lectures on approximation theory. Now, the case when $d=n-2$ was worked our explicitly by Zolotarev, Chebyshev's student, in terms of elliptic functions. When $d$ is smaller than that, only some general facts about the polynomials of best approximation are known, but I don't think anyone has written an explicit exact expression for the polynomial or for the error.

Answer 2

A little computation is often a useful way to get insight into such questions. Fortunately, available open-source solvers can approximately solve a given instance of this problem with a few lines of code and in a second or less.

Code

Here is a Python program that makes use of CVXOPT to find the polynomial of least deviation for a given $n$ and $d$. There is one important approximation here: it minimizes $p(x)$ only over a discrete set of points $x$. However, by taking a moderately fine grid of the desired interval, reasonably accurate values are obtained.

import numpy as np

def find_min_poly(x, d, n):
from cvxopt import matrix
from cvxopt.modeling import variable, op, max

X = matrix(x)
y = np.empty( (len(x), d+2) )
y[:,0] = x**n
for i in range(d, -1, -1):
    y[:, d+1-i] = x**i
Y = matrix(y)
c = variable(d+1)

op(max(abs(Y[:,0] + Y[:,1:]*c))).solve()

return c.value, max(abs((Y[:,0] + Y[:,1:]*c.value)))

Here is a nested loop that calls this for a range of $n,d$ values with the interval $[-1,1]$:

x = np.linspace(-1,1,10000)
N = range(1,11)
maxabs = np.zeros( (len(N),len(N)) )

for n in N:
    for d in range(n-1,-1,-1):
        print n, d
        coeffs, M = find_min_poly(x, d, n)
        maxabs[d, n-1] = M
        print M

print maxabs

You can download the code here.

One warning: for large enough values of $n,d$, this approach will give inaccurate results due to effects of roundoff errors.

Results

Here is the resulting table of values (computed in a few seconds), truncated to 4 decimal places:

$$\begin{bmatrix} 1. & 0.5 & 1. & 0.5 & 1. & 0.5 & 1. & 0.5 & 1. & 0.5 \\ - & 0.5 & 0.25 & 0.5 & 0.32645& 0.5 & 0.36491& 0.5 & 0.38843& 0.5 \\ - & - & 0.25 & 0.125 & 0.32645& 0.19245& 0.36491& 0.23624& 0.38843& 0.2675 \\ - & - & - & 0.125 & 0.0625 & 0.19245& 0.11157& 0.23624& 0.14921& 0.2675 \\ - & - & - & - & 0.0625 & 0.03125& 0.11157& 0.06346& 0.14921& 0.09216 \\ - & - & - & - & - & 0.03125& 0.01562& 0.06346& 0.03559& 0.09216 \\ - & - & - & - & - & - & 0.01562& 0.00781& 0.03559& 0.01972 \\ - & - & - & - & - & - & - & 0.00781& 0.00391& 0.01972 \\ - & - & - & - & - & - & - & - & 0.00391& 0.00195 \\ - & - & - & - & - & - & - & - & - & 0.00195 \end{bmatrix}$$

The value of $n$ is 1 for the leftmost column and increases to the right (up to 10); the value of $d$ is 0 in the first row and increases downward. You can see the $1/2^{n-1}$ values, corresponding to the Chebyshev polynomials, along the main diagonal.

The code above also provides the coefficients of the optimal polynomial, of course.

Conjectures

By experimenting and investigating these values, you may be able to conjecture the general behavior. For instance, it is obvious that the first superdiagonal is identical to the main diagonal; the 2nd and 3rd superdiagonals are identical, etc., apparently because the optimal polynomial has $a_d=0$ whenever $n-d$ is odd.

One might hope that the other diagonals exhibit geometric progressions like that of the Chebyshev polynomials, but examining the other diagonals shows this to be false. However, by computing a larger table of values with higher precision, one is led to conjecture that asymptotically, the ratio of consecutive values along any diagonal approaches two.