Возрастающий многочлен на отрезке

[grizzly]

alisa-lebovski в сообщении #1312956 писал(а):

На самом деле мне достаточно грубой оценки, даже на модули всех сразу коэффициентов.

Рост экспоненциальный, на начале натурального ряда примерно с тройкой в основании.

Вы сами можете посмотреть динамику коэффициентов, взяв первообразную от $(2x-1)^{2k}(1-x)$ (это при $n=2(k+1)$; константа нулевая, первообразную нужно нормировать множителем из условия $f(1)=1$). Эта последовательность будет давать не максимально возможные коэффициенты для данных $n$, но относительно весьма близкие. Так что отражение динамики будет вполне адекватным.

[g______d]

На всякий случай (возможно, все это уже знают и так): монотонность полинома с рациональными коэффициентами на данном отрезке с рациональными концами можно достаточно быстро проверить точно, используя последовательность Штурма:

https://en.wikipedia.org/wiki/Sturm%27s ... #Statement

[alisa-lebovski]

grizzly в сообщении #1312993 писал(а):

alisa-lebovski в сообщении #1312956 писал(а):

На самом деле мне достаточно грубой оценки, даже на модули всех сразу коэффициентов.

Рост экспоненциальный, на начале натурального ряда примерно с тройкой в основании.

Вы сами можете посмотреть динамику коэффициентов, взяв первообразную от $(2x-1)^{2k}(1-x)$ (это при $n=2(k+1)$; константа нулевая, первообразную нужно нормировать множителем из условия $f(1)=1$). Эта последовательность будет давать не максимально возможные коэффициенты для данных $n$, но относительно весьма близкие. Так что отражение динамики будет вполне адекватным.

Почему это так, не поняла, но потом еще подумаю. Так сколько вы предлагаете брать, например, для $n=4$ - 20?

[grizzly]

alisa-lebovski в сообщении #1313018 писал(а):

для $n=4$ - 20?

Для $n=4$ если действовать предложенным мной способом, получим многочлен $6x-15x^2+16x^3-6x^4$. Я полагаю, что он максимизирует $a_1$ и что остальные коэффициенты у него тоже должны быть близки к максимуму (да, 20 должно хватить, вероятно). Но для таких малых $n$ лучше всё-таки считать точно (я этому не научился, посмотрел только на асимптотику).

К примеру, для $n=10$ получится такой многочлен:

$$y=-(460.8 x^{10} - 2560 x^9 + 6336 x^8 - 9216 x^7 + 8736 x^6 - 5644.8 x^5 + 2520x^4 - 768 x^3 + 153 x^2 - 18x)$$

Вы можете полагаться на эти примеры только как на общую (конструктивную) оценку снизу для произвольного чётного $n$. Большего я обещать не могу.

-- 18.05.2018, 00:54 --

Вольфрам легко считает первообразные от такого $(4k+2)(2x-1)^{2k}(1-x)$ (я добавил сразу нормирующий множитель $4k+2$). Посмотрите руками несколько разных примеров, это поможет почувствовать оценки снизу.

[Sender]

Хм, вольфрам отыскал старший коэффициент для $n=4$. Если выписать известные на данный момент многочлены, максимизирующие модуль старшего коэффициента, имеем:
$n=2.\;f(x)=2x-x^2.\;f'(x)=2(1-x)$
$n=3.\;f(x)=3x-6x^2+4x^3.\;f'(x)=3(1-2x)^2$
$n=4.\;f(x)=8x^2-16x^3+9x^4.\;f'(x)=4x(2-3x)^2$
В общем, что-то, связанное с $((n-2)-(n-1)x)$

[grizzly]

Sender
Всё интереснее :)

Sender в сообщении #1313150 писал(а):

В общем, что-то, связанное с $((n-2)-(n-1)x)$

А я не смог подобрать по какой-нибудь аналогии следующее $n$.

Но для $n=6$ взял $f'(x)=\frac{30}{47}x(3-4x)^4$ и старший коэффициент получился чуть больше 27 (что, на всякий случай замечу, больше, чем $5^2$). Но я не думаю, что это лучший многочлен: нормирующий множитель странный, и вообще..

[Null]

для $n=5$ есть такой многочлен $9 x - 36 x^2 + 68 x^3 - 60 x^4 + 20 x^5$ и такой( приближенно) $5.93648 t - 33.4919 t^2 + 84.6028 t^3 - 91.4758 t^4 + 35.4285 t^5$
а для $n=4$ есть $-4.73205 x + 15.2942 x^2 - 20.3923 x^3 + 8.83013 x^4$

[grizzly]

Null в сообщении #1313173 писал(а):

для $n=5$ есть такой многочлен $9 x - 36 x^2 + 68 x^3 - 60 x^4 + 20 x^5$

Здорово! Это же не просто многочлен, а золотая жила: лёгким движением руки он превращается в не очень красивый, но ещё лучший в нашем смысле:

$$ \frac{768}{23}x^5-\frac{1920}{23}x^4+\frac{1760}{23}x^3-\frac{720}{23}x^2+\frac{135}{23}x $$

со старшим коэффициентом большим 33.

-- 18.05.2018, 13:44 --

Ага, опоздал :)

[Sender]

Null в сообщении #1313173 писал(а):

а для $n=4$ есть $-4.73205 x + 15.2942 x^2 - 20.3923 x^3 + 8.83013 x^4$

Null, если мы сейчас говорим о максимизации модуля старшего коэффициента при $n=4$, то он, похоже, достигает $9$ (см. моё предыдущее сообщение).

[Null]

Это я максимальный коэффициент из всех ищу, как ТС просил, а это $9 x - 36 x^2 + 68 x^3 - 60 x^4 + 20 x^5$ для младшего члена.

[grizzly]

По поводу старшего коэффициента для $n=5$. У многочлена, производная которого равна $C(x-0.79)^2(x-0.21)^2$, старший коэффициент получается 35,99..., а предстарший -- 89,99... Что намекает.

На этом та жила, которую я разрабатывал, закончилась :)

[Mishka_Barni]

Может быть уже не в тему, но найти оценки сверху можно так (топорный метод, что я предлагал раньше):
Представим $f'(x/2+1/2)$ как $f'(x/2+1/2)=\sum\limits_{k=0}^{n-1}\lambda_k T_k(x)$, $T_k(x):=\cos(n\arccos(x))$. Если $f'(x/2+1/2)\geqslant0$ при $x\in[-1,1]$, то $|\lambda_k|\leqslant 2\lambda_0$ при $k=1,\ldots,n-1$ (стандартное неравенство). Если воспользоваться неравенствам Фейера+ получим

$$ |\lambda_k|\leqslant 2\cos\left(\frac{\pi}{[n/k]+2}\right)\lambda_0,\ k=1,\ldots,n-1.\eqno{(\ast)} $$

Так как $\lambda_k$ как-то линейно выражаются через $a_k$, то $a_k$ лежат в выпуклом многограннике. Тогда максиму $|a_k|$ на этом многограннике (или его крайних точках?) будет искомой оценкой сверху. Оценка вряд ли будет точной и скорее всего при росте $n$ будет становиться хуже.

При $n=4$:
$a_1=1-a_2-a_3-a_4$; $\lambda_3=a_4/8$, $\lambda_2=(3a_3+6a_4)/8$, $\lambda_1=a_2+3a_3/2+15a_4/8$, $\lambda_0=1+a_3/8+a_4/4$.

С помощью Maple получилось как-то так: $|a_1|\leqslant 6.9270$, $|a_2|\leqslant 21.927$, $|a_3|\leqslant 28$, $|a_4|\leqslant 12$.

При $n=5$:
$a_1=1-a_2-a_3-a_4-a_5$; $\lambda_4=5a_5/128$, $\lambda_3=a_4/8+5a_5/16$; $\lambda_2=(3/8)a_3+(3/4)a_4+(35/32)a_5$
$\lambda_1=a_2+(3/2)a_3+(15/8)a_4+(35/16)a_5$, $\lambda_0=(47/128)a_5+a_3/8 +a_4/4+1$ .

Оценки: $|a_1|\leqslant 13.3056$, $|a_2|\leqslant 70.1166$, $|a_3|\leqslant 158.2529$, $|a_4|\leqslant 155.8681$, $|a_5|\leqslant 55.4197$.

[Sender]

grizzly в сообщении #1313183 писал(а):

старший коэффициент получается 35,99..., а предстарший -- 89,99... Что намекает.

$f(x)=36x^5-90x^4+80x^3-30x^2+5x.\;f'(x)=5(1-6x+6x^2)^2$

-- Пт май 18, 2018 23:30:37 --

Идея метода по сути уже была ранее высказана grizzly и заключается в следующем. Предполагается, что производная $f'(x)$ многочлена $f(x)$, максимизирующего модуль старшего коэффициента, имеет вид $p(x)^2$, $xp(x)^2$ или $(1-x)p(x)^2$, где $p(x)$ - некоторый полином с единичным старшим коэффициентом. Потом мы подбираем коэффициенты $p(x)$ так, чтобы минимизировать интеграл $\int\limits_0^1f'(x)dx$, который и укажет нам значение старшего коэффициента.
Вообще, последовательность старших коэффициентов, найденных этим методом($1,4,9,36,100,400,1225$), подозрительно напоминает A018224.

[Sender]

Похожим образом можно найти и последовательность младших коэффициентов. Имеющихся вычислительных мощностей хватило, чтобы найти следующие члены: $2,4,6,9,12,16,20,25,30$, таких последовательностей в OEIS целая куча. Ну и, конечно, никто не обещает, что полученные значения оптимальны в смысле исходной задачи.

[alisa-lebovski]

Спасибо.