задачка про функцию (мажорирование выпуклой)

[ewert]

а какое отношение ступеньки имеют к выпуклости?

[Лиля]

ShMaxG писал(а):

А трапеция с высотой

$$ h = \mathop {\max }\limits_{x \in \left[ {0,1} \right]} f\left( x \right) $$

и основанием - отрезком

$$ {\left[ {0,1} \right]} $$

не подходит? С соответствующим выбором наклона боковых сторон?

чуток модифицирую $h = \left| \mathop {\max }\limits_{x \in \left[ {0,1} \right]} f\left( x \right)\right|$ -ваш способ вполне подходит

[ewert]

Лиля писал(а):

ShMaxG писал(а):

А трапеция с высотой

$$ h = \mathop {\max }\limits_{x \in \left[ {0,1} \right]} f\left( x \right) $$

и основанием - отрезком

$$ {\left[ {0,1} \right]} $$

не подходит? С соответствующим выбором наклона боковых сторон?

чуток модифицирую $h = \left| \mathop {\max }\limits_{x \in \left[ {0,1} \right]} f\left( x \right)\right|$ -ваш способ вполне подходит

Естественно, не подходит -- на концах наклоны исходной функции могут быть бесконечными.

[ASA]

vlad239 в сообщении #192615 писал(а):

А говорить про выпуклую оболочку я не хочу - времени нет, а пригождается она на студ.олимпиадах редко.

Выпуклая оболочка используется в курсах линейного программирования, оптимизации, теории игр. Как без нее? Студенты соотв. специальностей должны ее знать. А уж те, кто участвует в олимпиадах, и подавно.

[vlad239]

ASA писал(а):

vlad239 в сообщении #192615 писал(а):

А говорить про выпуклую оболочку я не хочу - времени нет, а пригождается она на студ.олимпиадах редко.

Выпуклая оболочка используется в курсах линейного программирования, оптимизации, теории игр. Как без нее? Студенты соотв. специальностей должны ее знать. А уж те, кто участвует в олимпиадах, и подавно.

В олимпиаде первого курса технических ВУЗов, при одном занятии кружка в неделю в течение трех месяцев? Увы, не лезет.

Влад.

[Лиля]

ewert писал(а):

Таким образом, имеем непрерывную монотонно возрастающую функцию, стремящуюся к нулю в нуле. Она является мажорантой, и притом выпуклой, т.к. $k_n$ монотонно возрастают.

Для правой половины графика -- аналогично.

если $k_n$ монотонно возростает то возможно что

$$\lim_{n\rightarrow \infty}k_{n}= \infty$$

особенно если $f(x)$ не деференцируема
но функция все равно остаеться непрерывной

[Профессор Снэйп]

vlad239 писал(а):

В олимпиаде первого курса технических ВУЗов, при одном занятии кружка в неделю в течение трех месяцев? Увы, не лезет.

Влад.

Ну, если про выпуклую оболочку говорить нельзя, то про что тогда можно? Можно ли, например, пользоваться тем, что кажде ограниченное сверху подмножество прямой имеет супремум? Или вот будет построена какая-то функция в качестве решения: какими методами разрешено пользоваться, чтобы доказать, что она выпукла?

[Dandan]

Ну ок, можете рассказать доказальство ewert, но вот такое выглядит не сложнее по-моему.

$$ g(x) = \mathop {\sup }\limits_{x = \sum_{i=1}^{n} \alpha_i x_i} \Bigg(\sum_{i=1}^{n} \alpha_i f (x_i)\Bigg) $$

Нужно доказать, что всегда выполняется $g(tx+(1-t)y)\geq tg(x)+(1-t)g(y)$.
Так как $g(x)$ и $g(y)$ это супремумы вот того выражения, то есть последовательности, которые к этим супремумам соответственно сходятся. Т.е. $x = \sum_{i=1}^{n^{(k)}} \alpha_i^{(k)} x^{(k)}_i, ~~g(x)\rightarrow g_{(k)}(x)=\sum_{i=1}^{n^{(k)}} \alpha_i^{(k)} f (x_i^{(k)})$ и $y = \sum_{i=1}^{n^{(m)}} \beta_i^{(m)} y^{(m)}_i, ~~g(y)\rightarrow g_{(m)}(y)=\sum_{i=1}^{n^{(m)}} \beta_i^{(m)} f (y_i^{(m)})$. Также из определения $g$ сразу получается, что $g(tx+(1-t)y)\geq tg_{(k)}(x)+(1-t)g_{(m)}(y)$. Ну значит есть и требуемое неравенство. Собсно всё

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

Лиля писал(а):

если $k_n$ монотонно возростает то возможно что

$$\lim_{n\rightarrow \infty}k_{n}= \infty$$

особенно если $f(x)$ не деференцируема

возможно, но для такого построения это ничего не портит

[ewert]

Другой вариант этого построения -- более простой и более корректный.

Пусть $c_0$ -- любое число, большее глобального максимума функции, $x_0=1/2$ и $g_1(x)=k_1(x-x_0)+c_0$ -- касательная к левой части графика (т.е. $k_1$ -- это супремум всех $k$, для которых уравнение $k(x-x_0)+c_0=f(x)$ не имеет решений на участке $[0;x_0]$). Если $g(0)=0$, то построение на отрезке $[0;1/2]$ закончено. В противном случае выбираем $x_1<x_0/2$ так, чтобы было $c_1\equiv g_1(x_1)>\max\limits_{t\in[0;x_1]}f(t)$. Берём в качестве $z_1$ какую-либо точку из интервала $(x_1;x_0)$, в которой $g_1(z_1)=f(z_1)$ (такая всегда найдётся).

Аналогичным образом выбираем $k_2$, $x_2$, $c_2$ и $z_2$ для участка $[0;x_1]$ и т.д. Каждое $x_n$ как минимум вдвое меньше предыдущего и, следовательно, $x_n\to0$ при $n\to\infty$ (если, конечно, процесс не заканчивается за конечное количество шагов).

Функция $g(x)$, равная $g_n(x)$ на каждом из участков $[x_n;x_{n-1}]$ -- выпукла, монотонна и является мажорантой для $f(x)$. Причём $\lim\limits_{x\to0}g(x)=0$, поскольку $c_n<g(z_n)=f(z_n)$ и $z_n<x_{n-1}\to0$.

Для правой половины графика -- аналогично.

[ewert]

Dandan в сообщении #192669 писал(а):

но вот такое выглядит не сложнее по-моему.

Может, и не сложнее, но я лично ничего не понял -- там и в обозначениях путаница, и стрелочки не туда направлены. Надо примерно так:

Цитата:

Для каждого $x\in[0;1]$ определим $g(x)$ как $\sup\left(\sum_{i=1}^{n} \alpha_i f (x_i)\right)$, где супремум берётся по всем наборам $\{x_i\}\subset[0;1]$ и $\{\alpha_i\geqslant 0\}$ таким, что $\sum_{i=1}^{n} \alpha_i=1$ и $\sum_{i=1}^{n} \alpha_ix_i=x$. Этот супремум конечен (он не превосходит максимума модуля функции). Тогда найдётся последовательность наборов $\{\alpha_i^{(m)}\}$ и $\{x_i^{(m)}\}$ такая, что

$$g_x^{(m)}\equiv\sum_{i=1}^{n_x^{(m)}} \alpha_i^{(m)} f (x_i^{(m)})\to g(x)\quad\text{при}\quad m\to\infty.$$

Аналогично, для любой другой точки $y$ найдётся последовательность наборов $\{\beta_i^{(m)}\}$ и $\{y_i^{(m)}\}$ такая, что

$$g_y^{(m)}\equiv\sum_{i=1}^{n_y^{(m)}} \beta_i^{(m)} f (y_i^{(m)})\to g(y)\quad\text{при}\quad m\to\infty.$$

Если теперь $t\in[0;1]$, то наборы $\{t\alpha_i^{(m)},(1-t)\beta_i^{(m)}\}$ и $\{x_i^{(m)},y_i^{(m)}\}$ удовлетворяют указанным требованиям. Поэтому

$$g(tx+(1-t)y)\geqslant\lim\limits_{m\to\infty}\left(\sum_{i=1}^{n_x^{(m)}} t\alpha_i^{(m)} f (x_i^{(m)})+\sum_{i=1}^{n_y^{(m)}}(1-t)\beta_i^{(m)} f (y_i^{(m)})\right)=t\,g(x)+(1-t)g(y).$$

И это, действительно, означает выпуклость. Но, между прочим, следует ещё доказать непрерывность функции $g(x)$ -- просто из выпуклости она не следует. Кроме того, неплохо бы ещё объяснить студентам, откуда у них в боевой обстановке может возникнуть желание рассматривать такие суммы.

[Dandan]

ewert писал(а):

Но, между прочим, следует ещё доказать непрерывность функции $g(x)$ -- просто из выпуклости она не следует.

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

ewert писал(а):

Кроме того, неплохо бы ещё объяснить студентам, откуда у них в боевой обстановке может возникнуть желание рассматривать такие суммы.

Ну дык если знать неравенство Йенсена (которое, кстати, даже на школьных олимпиадах считается известным фактом и которое элементарно выводится из определения выпуклости), то понятно, что для выпуклой g, которая больше f, должно выполняться g(...) >= sup(sum...f...).

[ewert]

Dandan в сообщении #192803 писал(а):

Ну дык если знать неравенство Йенсена (которое, кстати, даже на школьных олимпиадах считается известным фактом и которое элементарно выводится из определения выпуклости), то понятно, что для выпуклой g, которая больше f, должно выполняться g(...) >= sup(sum...).

Нет, не понятно. Неравенство Йенсена -- это, конечно, хорошо, но для угадывания Вашего варианта доказательства этого недостаточно. Чтобы такой вариант пришёл в голову, нужно знать о существовании такого понятия, как выпуклая оболочка.

Между тем на первом курсе этого никто как раз и не знает. Поскольку выпуклая оболочка графика -- вещь довольно экзотическая, она нужна только тогда, когда нужна.

------------------------------------------------------------------------
Да, а Ваше доказательство всё же стоит завершить. Если не ссылаться впрямую на слова "выпуклая оболочка", то мне не приходит в голову ничего проще, чем следующее.

Обозначим $\varepsilon(x)=\max\limits_{t\in[0;x]}|f(t)|$ и $M=\varepsilon(1)=\max\limits_{t\in[0;1]}|f(t)|$. Пусть $\{x_i^-\}$ -- совокупность чисел $x_i<\sqrt x$ и $\{x_i^+\}$ -- числа $x_i\geqslant\sqrt x$ (последнее множество может оказаться пустым); $\{\alpha_i^-\}$ и $\{\alpha_i^+\}$ -- соответствующие коэффициенты. Тогда

$$x\geqslant x-\sum\alpha_i^-x_i^-=\sum\alpha_i^+x_i^+\geqslant\sqrt x\sum\alpha_i^+,$$

откуда $\sum\alpha_i^+\leqslant\sqrt x.$ Следовательно,

$$\left|\sum\alpha_i f(x_i)\right|\leqslant\left|\sum\alpha_i^- f(x_i^-)\right|+\left|\sum\alpha_i^+ f(x_i^+)\right|\leqslant\varepsilon(\sqrt x)+\sqrt x\cdot M.$$

Но тогда и $|g(x)|\leqslant\varepsilon(\sqrt x)+\sqrt x\cdot M\to0$ при $x\to0.$ Случай $x\to1$ рассматривается аналогично.

[Dandan]

ладно, согласен, с касательными проще . Но метод через выпуклую оболочку всё равно не плохо знать.

[ewert]

Dandan в сообщении #192841 писал(а):

ладно, согласен, с касательными проще

У этого подхода есть ещё одно преимущество: на его основе очень легко построить строго выпуклую мажоранту. А вот в случае использования выпуклой оболочки пришлось бы ещё помучится.

[Lyoha]

Цитата:

$f(x)$ непрерывна на $[0,1]$, причем $f(0)=f(1)=0$. Докажите, что найдется выпуклая вверх функция $g(x)$, такая что $g(0)=g(1)=0$ и $g(x)\ge f(x)$ на всем отрезке.

$f(x)$ равномерно непрерывна на отрезке. Примем

$$g(0)=0; g(x)=x*\sup\limits_{|x_2-x_1|\ge x}(|\frac{f(x_1)-f(x_2)}{x_1-x_2}|), x\in(0;1/2]$$

. На отрезке $[1/2;0]$ примем $g(x)$ симметричной относительно точки 1/2 уже построенной. Вроде как выпуклость проверяется в лоб.