2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Возрастающий многочлен на отрезке
Сообщение17.05.2018, 22:26 
Заслуженный участник
Аватара пользователя


09/09/14
5556
alisa-lebovski в сообщении #1312956 писал(а):
На самом деле мне достаточно грубой оценки, даже на модули всех сразу коэффициентов.
Рост экспоненциальный, на начале натурального ряда примерно с тройкой в основании.

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

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение17.05.2018, 23:03 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 00:19 
Аватара пользователя


05/12/09
332
grizzly в сообщении #1312993 писал(а):
alisa-lebovski в сообщении #1312956 писал(а):
На самом деле мне достаточно грубой оценки, даже на модули всех сразу коэффициентов.
Рост экспоненциальный, на начале натурального ряда примерно с тройкой в основании.

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


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

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 00:50 
Заслуженный участник
Аватара пользователя


09/09/14
5556
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$). Посмотрите руками несколько разных примеров, это поможет почувствовать оценки снизу.

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 10:09 
Заслуженный участник


14/01/11
1792
Хм, вольфрам отыскал старший коэффициент для $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)$ :-)

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 11:11 
Заслуженный участник
Аватара пользователя


09/09/14
5556
Sender
Всё интереснее :)
Sender в сообщении #1313150 писал(а):
В общем, что-то, связанное с $((n-2)-(n-1)x)$
А я не смог подобрать по какой-нибудь аналогии следующее $n$.

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

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 13:11 
Заслуженный участник


12/08/10
982
для $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$

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 13:43 
Заслуженный участник
Аватара пользователя


09/09/14
5556
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 --

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

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 13:55 
Заслуженный участник


14/01/11
1792
Null в сообщении #1313173 писал(а):
а для $n=4$ есть $-4.73205 x + 15.2942 x^2 - 20.3923 x^3 + 8.83013 x^4$

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

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 13:58 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 14:18 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 15:18 


05/06/17

87
Может быть уже не в тему, но найти оценки сверху можно так (топорный метод, что я предлагал раньше):
Представим $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$.

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение18.05.2018, 22:32 
Заслуженный участник


14/01/11
1792
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.

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение19.05.2018, 00:31 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Возрастающий многочлен на отрезке
Сообщение19.05.2018, 09:22 
Аватара пользователя


05/12/09
332
Спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group