Многочлен наилучшего приближения с добавкой

[Gafield]

Пусть $n\in\mathbb N$, $T_n(x)=\cos(n \arccos(x))=2^{n-1}x^n+\ldots$ - многочлены Чебышева на отрезке$ [-1,1]$, а $p_{n-1}(x)$ - многочлен степени не выше $n-1$. Для непрерывной функции $f$ обозначим

$$\|f\|=\max_{x\in[-1,1]}|f(x)|$$

.

Гипотеза: если

$$ \|T_n+p_{n-1}\|=a\ge1$$

, то

$$\|p_{n-1}\|\le 2(a-1)$$

.

Некоторые соображения в пользу такого неравенства имеются, но доказательства у меня нет.
Ее можно рассматривать как количественную оценку устойчивости наилучшего приближения. То, что $ \|T_n\|=1$, и такой многочлен со старшим коэффициентом $2^{n-1}$ один - единственность задачи о н. пр. Если норма немного больше единицы, то и многочлен мало отличается от $T_n$ - устойчивость по норме $C[-1,1]$.
Может, оценка такого сорта вытекает из чего-то известного в теории функций?

[maxal]

Похоже, у вас одно неравенство перепутано.

[Gafield]

Какое?

[maxal]

Gafield писал(а):

Гипотеза: если

$$ \|T_n+p_{n-1}\|=a\ge1$$

, то

$$\|p_{n-1}\|\le 2(a-1)$$

.

Последнее из этих.

Добавлено спустя 3 минуты 41 секунду:

Хотя, может, это именно то, что имелось в виду.
Неравенство такое:

$$\|p_{n-1}\|\le 2( \|T_n+p_{n-1}\|-1)$$

[Gafield]

Да, именно это. А есть еще интересный вариант?

[RIP]

Гипотеза точно неверна при $n\geqslant2$. Действительно, фиксируем $n$ и в качестве добавки рассмотрим $p_{n-1}(x)=-\varepsilon(1/2+T_1(x)+T_2(x)+\ldots+T_{n-1}(x))$, где $\varepsilon>0$ - маленькое. Если $x=\cos\varphi$, то $p_{n-1}(x)=-\frac{\varepsilon\sin(n-1/2)\varphi}{2\sin\frac\varphi2}$. Корни производной многочлена $T_n+p_{n-1}$ равны $x_k=\cos\frac{\pi k}{n}+O(\varepsilon)$, $k=1,2,\ldots,n-1$. Поэтому $p_{n-1}(x_k)=(-1)^k\varepsilon/2+O(\varepsilon^2)$ и $|T_n(x_k)+p_{n-1}(x_k)|=1+\varepsilon/2+O(\varepsilon^2)$. Далее, $|T_n(1)+p_{n-1}(1)|=1-(n-1/2)\varepsilon$, $|T_n(-1)+p_{n-1}(-1)|=1+\varepsilon/2$. Следовательно, $a=\|T_n+p_{n-1}\|=1+\varepsilon/2+O(\varepsilon^2)$. С другой стороны, очевидно, что $\|p_{n-1}\|=(n-1/2)\varepsilon$.

Интересно было бы получить хоть какую-нибудь оценку $\|p_{n-1}\|\leqslant?$, которая стремится к 0 при $a\to1+0$. Наверняка что-то подобное известно, но я не встречал.

[Руст]

Лучше сразу выразить $x=cos y$, тогда

$$T_n(x)=cos(ny), \ p_{n-1}=\sum_{k=0}^{n-1}a_kcos(ky).$$

Если не ошибаюсь максимальное значение

$$f(y)=\sum_{k=0}^nb_kcos(ky)$$

есть

$$\sqrt{\sum_{k=0}^n b_k^2.$$

Тогда получаем неравенство $||p_{n-1}||\le \sqrt{a^2-1}.$

[RIP]

Руст писал(а):

Если не ошибаюсь максимальное значение

$$f(y)=\sum_{k=0}^nb_kcos(ky)$$

есть

$$\sqrt{\sum_{k=0}^n b_k^2}.$$

Ошибаетесь. Если все $b_k>0$, то $\max|f(y)|=f(0)=\sum_{k=0}^nb_k>\sqrt{\sum_{k=0}^n b_k^2}$.

[Gafield]

Хм, интересно, спасибо.

Цитата:

Интересно было бы получить хоть какую-нибудь оценку $\|p_{n-1}\|\leqslant?$, которая стремится к 0 при $a\to1+0$. Наверняка что-то подобное известно, но я не встречал.

Ага. Я надеялся, что константа в ней будет независимой от $n$, но это оказалось слишком оптимистичным

[RIP]

RIP писал(а):

Интересно было бы получить хоть какую-нибудь оценку $\|p_{n-1}\|\leqslant?$, которая стремится к 0 при $a\to1+0$.

Удалось получить оценку вида $c(n)(a-1)$, где $c(n)$ можно вычислить явно, но мне лень. Идею доказательства мне подсказал С. В. Конягин.
Как уже написал Руст, удобнее работать с косинусами, поэтому пусть $p(x)=\sum_{k=0}^{n-1}a_k\cos kx$, $S(x)=\cos nx+p(x)$, $a=\|S\|$. Поскольку $\frac1n\sum_{k=0}^{n-1}S(x+2\pi k/n)=\cos nx+a_0$, то $1+|a_0|=\|\cos nx+a_0\|\leqslant\|S\|=a$, $|a_0|\leqslant a-1$. Далее, $p(2\pi k/n)=S(2\pi k/n)-1\leqslant a-1$ для $k\in\mathbb Z$, поэтому опять же для $k\in\mathbb Z$

$$p(2\pi k/n)=na_0-\sum_{\substack{0\leqslant l\leqslant n-1\\l\ne k}}p(2\pi l/n)\geqslant-(2n-1)(a-1)$$

(именно этот трюк мне подсказал Сергей Владимирович; трюк из разряда "как же я сам не догадался???").
Таким образом, $-(2n-1)(a-1)\leqslant p(2\pi k/n)\leqslant a-1$ для целых $k$. Аналогично, $-(a-1)\leqslant p(\pi(2k+1)/n)\leqslant(2n-1)(a-1)$. Суммируя: $|p(\pi k/n)|\leqslant(2n-1)(a-1)$. Понятно, что отсюда следует требуемое, поскольку коэффициенты $a_k$ определяются из системы линейных уравнений $\sum_{k=0}^{n-1}a_k\cos\frac{\pi kl}n=p(\pi l/n)$, $l=0,\ldots,n-1$, определитель которой считается.

P.S. Я думаю, что можно доказать $\|p\|\leqslant(2n-1)(a-1)$, но не уверен.

[Руст]

RIP писал(а):

P.S. Я думаю, что можно доказать $\|p\|\leqslant(2n-1)(a-1)$, но не уверен.

Вроде получается $|p|\le 2n(a-1)$. (1)
Я пытался получить отклонение типа $\sqrt{a-1}$ экспериментируя добавкой типа $p(x)=\epsilon T_n'(x)$ (приравняв нулю отклонения в средних точках) и понял бесполезность этого. Однако попробовав $p(x)=\epsilon_1 T_n'(x)+\epsilon_2$ получается отклонение порядка $2n(a-1)$.
Поэтому, думаю правильная оценка такая.

[RIP]

Странно, у меня при $n=1,2,3$ вроде получилось доказать $\|p\|\leqslant(2n-1)(a-1)$.
Вот, например, при $n=3$ (обозначим $\delta= a-1$):

$$-5\delta\leqslant p(0)=a_0+a_1+a_2\leqslant\delta;$$

$$-\delta\leqslant p(\pi/3)=a_0+(a_1-a_2)/2\leqslant5\delta;$$

$$-5\delta\leqslant p(2\pi/3)=a_0-(a_1+a_2)/2\leqslant\delta;$$

$$-\delta\leqslant p(\pi)=a_0-(a_1-a_2)\leqslant5\delta.$$

Из первой и третьей строчки получаем $|a_1+a_2|\leqslant 4\delta$, а из второй и четвертой - $|a_1-a_2|\leqslant4\delta$, поэтому $\|p\|\leqslant|a_0|+|a_1|+|a_2|\leqslant\delta+4\delta=5\delta$.

[Gafield]

RIP писал(а):

P.S. Я думаю, что можно доказать $\|p\|\leqslant(2n-1)(a-1)$, но не уверен.

Если это верно, то вместе с предыдущим вашим примером

Цитата:

Следовательно, $a=\|T_n+p_{n-1}\|=1+\varepsilon/2+O(\varepsilon^2)$. С другой стороны, очевидно, что $\|p_{n-1}\|=(n-1/2)\varepsilon$.

получилось бы красивое точное неравенство.

Определитель матрицы $(\cos(kl\pi/n)_{k=0\ldots,n-1,\ l=0\ldots,n-1}$ для нескольких первых $n$ равен $(-1)^{n(n-1)/2}(n/2)^{(n-1)/2}$, так что впрямую из него вряд ли можно получить что-нибудь хорошее, слишком быстро растет.

Мне оценка нужна была с постоянной, не зависящей от $n$, но имхо задача сама по себе интересна. Вероятно, вопрос об устойчивости больше характерен для ДУ, чем для теории приближений. В книжках по ТФДП вроде такого нет, хотя постановка, по-моему, весьма естественна. Но, может, из нее не следует ничего полезного для теории приближений, вот и не рассматривали

[RIP]

Gafield писал(а):

RIP писал(а):

P.S. Я думаю, что можно доказать $\|p\|\leqslant(2n-1)(a-1)$, но не уверен.

Если это верно, то вместе с предыдущим вашим примером

Цитата:

Следовательно, $a=\|T_n+p_{n-1}\|=1+\varepsilon/2+O(\varepsilon^2)$. С другой стороны, очевидно, что $\|p_{n-1}\|=(n-1/2)\varepsilon$.

получилось бы красивое точное неравенство.

Собственно поэтому я и думаю, что можно его доказать. Пример я ведь не с потолка списал, а подбирал из некоторых соображений, исходя из которых он должен быть близким к оптимальному (хотя не факт).

Gafield писал(а):

Определитель матрицы $(\cos(kl\pi/n)_{k=0\ldots,n-1,\ l=0\ldots,n-1}$ для нескольких первых $n$ равен $(-1)^{n(n-1)/2}(n/2)^{(n-1)/2}$, так что впрямую из него вряд ли можно получить что-нибудь хорошее, слишком быстро растет.

Так это же хорошо. Вот если бы он быстро убывал, то было бы очень плохо. Тут вопрос в том, не растёт ли он слишком медленно для хорошего результата.

[Руст]

Пусть
(1) $g(x)=p(x\frac{\pi}{n})=\sum_{k=0}^na_kcos\frac{xk\pi}{n}=S(x)-cos(x\pi)$.
Рассмотрим это в целых точках $x=0,1,...,n-1$ и просуммируем каждое равенство умножив на $cos\frac{mx\pi}{n}$. Учитывая, что

$$\sum_{x=0}^{n-1}cos\frac{xl\pi}{n}=0$$

при $2n\not |l$ получается
(2)

$$a_k=\frac{2}{n}\sum_{x=0}^{n-1}(S(x)-(-1)^x)cos\frac{kx\pi}{n}.$$

Здесь для k=0 коэффициент получается $\frac 1n$ ( в два раза меньше). Подставляя это в (1) получаем максимально возможное значение, когда $S(x)=(-1)^x+(a-1)$ и в этом случае $|p(x)|=(2n-1)(a-1)$.