2014 dxdy logo

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

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




 
 Максимум полинома
Сообщение24.04.2007, 16:05 
Sorry for English, but I've been asked from a UK mathematical faculty student about this problem and so I've decided to refer him here.
There is a polynom: $$\omega \left( x \right) = \prod\limits_{i = 0}^n {\left( {x - {i \over n}} \right)} $$. We need to find it's maximum on $$x \in \left[ {0,1} \right]$$.

 
 
 
 Вопрос
Сообщение24.04.2007, 21:11 
Ну неужели никто не знает, как подступиться к решению вопроса??? :(

 
 
 
 Re: Максимум полинома
Сообщение24.04.2007, 22:12 
Аватара пользователя
А чем это рассуждение не подходит?
Excoder писал(а):
Поведение этого полинома таково, что к концам отрезка погрешность все больше нарастает, и достигает наибольшего значения в крайних локальных максимумах.

 
 
 
 
Сообщение24.04.2007, 22:43 
Проблемка в том, что этот характер поведения, вообще говоря, наблюдаем графически, но доказать это строгим рассуждением пока не удается.

 
 
 
 
Сообщение24.04.2007, 23:02 
Аватара пользователя
А константа Лебега к Вашему вопросу отношения не имеет? Это, правда, не то же самое, что Вы спрашиваете, но тоже используется для оценки погрешности интерполяции.

К.И.Бабенко. Основы численного анализа. Москва, "Наука", 1986. Глава 3, § 3.

 
 
 
 
Сообщение25.04.2007, 00:02 
Уважаемый Someone, спасибо за интересную книгу! Действительно, часто применение методов функционального анализа дает в довольно простых вещах весьма нетривиальные и точные результаты. На ВМК таким тонким и красивым вещам, которые я обнаружил в этой книге, к сожалению, не учат...

Однако, я думаю, мне удалось построить верхнюю оценку нужной точности элементарным способом. На самом деле, все оказалось довольно просто :) Когда я найду время, то опишу это простое построение. Здесь же пока скажу, что справедлива такая оценка:

$$
\mathop {\max }\limits_{x \in \left[ {0,1} \right]} \left| {\omega \left( x \right)} \right| \le {{n!} \over {n^{n + 1} }}
$$

По результатам численного эксперимента, она завышает реальные значения максимума в два-три раза, и улучшается с ростом n, но и такой точности достаточно для моих целей :) Спасибо всем за внимание :)

 
 
 
 
Сообщение25.04.2007, 01:22 
Аватара пользователя
Можно выразить через гамма-функцию:
$$\omega(x) = \left(\frac{-1}{n}\right)^{n+1} \frac{\Gamma(-xn+n+1)}{\Gamma(-xn)}$$
и воспользоваться оценками для гамма-функции...

 
 
 
 
Сообщение25.04.2007, 04:02 
Аватара пользователя
Легко написать асимптотику для точки максимума и для самого максимума. Простейшие асимптотики выглядят так:
$$x_0=\frac1{n\ln n}\left(1+O(1/{\ln n})\right);$$
$$|\omega(x_0)|=\sqrt{\frac{2\pi}n}\cdot\frac{e^{-n-1}}{\ln n}\left(1+O(1/{\ln n})\right).$$


Получается это так. Всё происходит на отрезке $[0;\frac12]$. Если $x>1/n$, то $|\omega(x-1/n)|\geqslant|\omega(x)|$, поэтому максимум, действительно, достигается на отрезке $[0;1/n]$. Чтобы оценить $x_0$, достаточно заметить, что это есть корень производной, т.е.
$$\frac1{nx_0}=\sum_{k=1}^n\frac1{k-nx_0}=\frac1{1-nx_0}+\frac1{2-nx_0}+\ldots+\frac1{n-nx_0},$$
откуда можно получить асимптотику для $x_0$.
По формуле Стирлинга получаем
$$|\omega(x_0)|=\frac{x_0\Gamma(n+1-nx_0)}{n^n\Gamma(1-nx_0)}=\frac{x_0\cdot\sqrt{2\pi}n^{1/2-nx_0}e^{-n}}{\Gamma(1-nx_0)}(1+O(1/n)).$$
Учитывая, что $x_0=\frac1{n\ln n}(1+O(1/{\ln n}))$, получаем оценку для $|\omega(x_0)|$.

 
 
 
 
Сообщение27.04.2007, 02:01 
Уважаемый RIP, пожалуйста, немного поподробнее распишите :) Видимо, я не совсем корректно действую. Вот что получается после аккуратного расписывания функции и ее асимптотики:
$$
$\omega \left( x \right) = \left( { - {1 \over n}} \right)^{n + 1} {{\Gamma \left( {n + 1 - nx} \right)} \over {\Gamma \left( { - nx} \right)}} \sim \left( { - {1 \over {\mathop{\rm e}\nolimits} }} \right)^n 2x^{nx + {\textstyle{1 \over 2}}} \left( {1 - x} \right)^{n\left( {1 - x} \right) + {\textstyle{1 \over 2}}} \sin \pi nx$
$$
Получается асимптотика, несколько занижающая значения функции. Но в этом и преимущество, т.к. можно показать, какой величины эта функция заведомо больше. Если в асимпотике избавиться от синуса, то максимум асимпотики, грубо говоря, сильно съедет от максимума функции.

Далее я пытаюсь оценить максимум асимптотики на отрезке, содержащем экстремум. Для этого отыскиваются нули производной, которые являются решениями уравнения:
$$
n\ln {x \over {1 - x}} + {1 \over {2x}} - {1 \over {2\left( {1 - x} \right)}} + \pi n{\mathop{\rm ctg}\nolimits} \pi nx = 0
$$
В общем, этот путь ни к чему хорошему не приводит... Я в тупике :( Дело в том, что Ваш результат очень хорошо согласуется с данными численного эксперимента по нахождению максимума исходной функции, и для корня данные тоже весьма точны. Но я не могу получить этот результат. Видимо, я делаю что-то принципиально неверное :oops: Особенно мне интересно, как же в оценке для корня появляется логарифм.

 
 
 
 
Сообщение27.04.2007, 03:22 
Аватара пользователя
Сначала об оценке для точки максимума.
Поскольку $\omega(x)=\prod\limits_{k=0}^n(x-k/n)$, то $\frac{\omega'(x)}{\omega(x)}=\sum\limits_{k=0}^{n}\frac1{x-k/n}$. Поскольку $\omega'(x_0)=0$, для $x_0$ получаем уравнение, приведённое в моём посте. Как же из него извлекается асимптотика для $x_0$? Обозначим для удобства $nx_0=t\in(0;1)$. Тогда
$$1/t=\sum_{k=1}^n\frac1{k-t}>\sum_{k=1}^n1/k>\ln n,$$
значит, $t=O(1/\ln n)$. Поэтому
$$1/t=\sum_{k=1}^n\frac1{k-t}=\sum_{k=1}^n\frac1k(1-t/k)^{-1}=\sum_{k=1}^n\frac1k(1+t/k+O(t^2/k^2))=$$
$$\begin{equation}=\ln n+\gamma+O(1/n)+\left(\frac{\pi^2}6+O(1/n)\right)t+O(t^2)=\ln n+\gamma+\frac{\pi^2}6t+O(1/\ln^2n),\end{equation}$$
где $\gamma=0.57721566490153286060651209008240243104215933593992...~-$ постоянная Эйлера. В частности, $1/t=\ln n+O(1)$, откуда $t=1/(\ln n+O(1))=1/\ln n+O(1/\ln^2n)$. Подставляя это значение в (1), получаем
$$1/t=\ln n+\gamma+\frac{\pi^2}{6\ln n}+O(1/\ln^2n),$$
откуда можно поиметь более точную оценку
$$t=\frac1{\ln n}\left(1+\frac\gamma{\ln n}+\frac{\pi^2}{6\ln^2n}+O(1/\ln^3n)\right)^{-1}=$$
$$=\frac1{\ln n}\left(1-\frac\gamma{\ln n}+\frac{6\gamma^2-\pi^2}{6\ln^2n}+O(1/\ln^3n)\right).$$
Т.е. более точная асимптотика для $x_0$ выглядит так:
$$x_0=\frac1{n\ln n}\left(1-\frac\gamma{\ln n}+\frac{6\gamma^2-\pi^2}{6\ln^2n}+O\left(\frac1{\ln^3 n}\right)\right).$$


Теперь об оценке самого максимума. Формула Стирлинга имеет вид
$$\ln\Gamma(s)=(s-1/2)\ln s-s+\ln\sqrt{2\pi}+O(1/s).$$
Подставляем $s=n+1-nx_0=n+t$, где $t=1-nx_0\in(0;1)$ (т.к. $x_0\in(0;1/n)$):
$$\ln\Gamma(n+t)=(n+t-1/2)\ln(n+t)-n-t+\ln\sqrt{2\pi}+O(1/n)=$$
$$=(n+t-1/2)(\ln n+t/n+O(1/n^2))-n-t+\ln\sqrt{2\pi}+O(1/n)=(n+t-1/2)\ln n-n+\ln\sqrt{2\pi}+O(1/n),$$
значит,
$$\Gamma(n+1-nx_0)=\sqrt{2\pi}\,n^{n+1/2-nx_0}e^{-n}(1+O(1/n)).$$
Для начала,
$$x_0n^{-nx_0}=x_0\exp(-nx_0\ln n)=\frac1{n\ln n}(1-\gamma/\ln n+O(1/\ln^2n))\exp(-1+\gamma/\ln n+O(1/\ln^2 n))=$$
$$=\frac{e^{-1}}{n\ln n}(1+O(1/\ln^2n)).$$
Далее,
$$\Gamma(1-nx_0)=\Gamma(1)-\Gamma'(1)nx_0+O((nx_0)^2)=1+\frac\gamma{\ln n}+O(1/\ln^2n).$$
Суммируя всё это, получаем
$$|\omega(x_0)|=x_0\frac{\Gamma(n+1-nx_0)}{n^n\Gamma(1-nx_0)}=$$
$$=\sqrt{\frac{2\pi}n}\frac{e^{-n-1}}{\ln n}(1-\gamma/{\ln n}+O(1/\ln^2n)).$$
Надеюсь, нигде не наврал. :)

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group