Generalización de los polinomios de Chebyshev

Question

¿Cuál es el polinomio mónico $p(x)$ de grado $n$ que minimiza $\max_{x \in [-1,1]} |p(x)|$ ? La respuesta es el polinomio de Chebyshev, y su mayor valor en $[-1,1]$ es $1/2^{n-1}$ .

Supongamos ahora la siguiente pregunta: ¿cuál es el polinomio de grado $n$ de la forma $$x^n + a_d x^d + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$ que minimiza $\max_{x \in [-1,1]} |p(x)|$ ? Aquí $d<n$ ; si tomamos $d = n-1$ recuperamos el polinomio de Chebyshev.

Mi principal propósito al preguntar esto es estimar cómo de grande $\max_{x \in [-1,1]} |p(x)|$ en función de $n$ y $d$ para dicho polinomio.

Se puede emular la derivación de los polinomios de Chebyshev: resolveríamos el problema si pudiéramos construir un polinomio de esta forma que nunca exceda de $A$ en valor absoluto y oscila entre $A$ y $-A$ suficientes veces en $[-1,1]$ . Sin embargo, no tengo muy claro cómo hacerlo.

Answer 1

En primer lugar, existe una teoría general (debida a Chebyshev) sobre la mejor aproximación uniforme de CUALQUIER función continua $f$ por polinomios de grado máximo $d$ en un intervalo. Describe el polinomio de la mejor aproximación, que es único.

En polinomios de Chebyshev, $f=x^n$ y $d=n-1$ . Usted pregunta por $f=x^n$ y algunos dados $d<n$ . No recomiendo leer al propio Chebyshev sobre esto sino a Akhiezer, Lectures on approximation theory. Ahora, el caso cuando $d=n-2$ se elaboró explícitamente por Zolotarev, alumno de Chebyshev, en términos de funciones elípticas. Cuando $d$ es menor que eso, sólo se conocen algunos hechos generales sobre los polinomios de mejor aproximación, pero no creo que nadie haya escrito una expresión exacta explícita para el polinomio o para el error.

Answer 2

Un poco de cálculo suele ser una forma útil de entender estas cuestiones. Afortunadamente, los solucionadores de código abierto disponibles pueden resolver aproximadamente una instancia dada de este problema con unas pocas líneas de código y en un segundo o menos.

Código

He aquí un programa en Python que utiliza CVXOPT para encontrar el polinomio de menor desviación para un determinado $n$ y $d$ . Aquí hay una aproximación importante: minimiza $p(x)$ sólo sobre un conjunto discreto de puntos $x$ . Sin embargo, tomando una cuadrícula moderadamente fina del intervalo deseado, se obtienen valores razonablemente precisos.

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)))

Aquí hay un bucle anidado que llama a esto para un rango de $n,d$ valores con el intervalo $[-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

Puede descargar el código aquí .

Una advertencia: para valores suficientemente grandes de $n,d$ este enfoque dará resultados inexactos debido a los efectos de los errores de redondeo.

Resultados

He aquí la tabla de valores resultante (calculada en unos segundos), truncada con 4 decimales:

$$\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}$$

El valor de $n$ es 1 para la columna de la izquierda y aumenta hacia la derecha (hasta 10); el valor de $d$ es 0 en la primera fila y aumenta hacia abajo. Puede ver el $1/2^{n-1}$ correspondientes a los polinomios de Chebyshev, a lo largo de la diagonal principal.

Por supuesto, el código anterior también proporciona los coeficientes del polinomio óptimo.

Conjeturas

Experimentando e investigando estos valores, podrás conjeturar el comportamiento general. Por ejemplo, es obvio que la primera superdiagonal es idéntica a la diagonal principal; la 2ª y 3ª superdiagonales son idénticas, etc., aparentemente porque el polinomio óptimo tiene $a_d=0$ siempre que $n-d$ es impar.

Cabría esperar que las demás diagonales mostraran progresiones geométricas como la de los polinomios de Chebyshev, pero el examen de las demás diagonales muestra que esto es falso. Sin embargo, al calcular una tabla de valores más grande y con mayor precisión, se llega a la conjetura de que asintóticamente la relación de valores consecutivos a lo largo de cualquier diagonal se aproxima a dos.