chapter19.qq

\chapter \label chap:19:convexity
    Старшие производные и выпуклость

Посмотрим на графики функций $y=x^2$, $x \ge 0$, и $y=\sqrt{x}$. Что мы можем
сказать про их поведение при возрастании $x$? С одной стороны, они обе
возрастают. С другой — по графику видно, что возрастают они как-то по-разному.
График $y=x^2$ загибается вверх — чем больше $x$, тем быстрее растёт $x^2$, а
$y=\sqrt{x}$, наоборот, с увеличением $x$ растёт все медленнее, загибается как
бы вниз (хотя и никогда не убывает). Это неудивительно: производная $x^2$ равна
$2x$, это возрастающая функция, а у $\sqrt{x}$ производная равна
$1/(2\sqrt{x})$, она убывает, хоть и остаётся всегда положительной.

Такого типа разница в поведении функций часто оказывается важной с практической
точки зрения. Например, в экономике известен закон убывающей предельной
полезности. Увеличение какого-нибудь ресурса приносит разную отдачу в
зависимости от того, много его в наличии или мало: чем больше ресурса есть, тем
меньший эффект от его увеличения. Бывают и обратные ситуации. Например,
экономический эффект от коммуникационной сети при увеличении количества её
участников (можно думать о периоде истории, когда только-только изобрели
телефоны) растёт с ускорением (можно считать, что для каждого владельца телефона
полезность телефонной сети растёт линейно с ростом числа человек, которым можно
позвонить, и значит эффект от всей сети в целом для общества будет расти
квадратично).

С математической точки зрения эта разница в поведении функций связана со
свойством \emph{выпуклости}. Его-то мы и обсудим. Но сперва поговорим про
старшие производные.

\section Старшие производные

Пусть у нас есть какая-нибудь функция $f$ и мы хотим различать ситуации, когда
её график «загибается вверх» (то есть она растёт с ускорением) или «вниз» (то
есть замедляется). Поскольку скорость роста функции — это её производная, нас
интересует, возрастает производная или убывает. Чтобы исследовать функцию на
возрастание и убывание, мы можем воспользоваться производной, но что делать,
если мы хотим исследовать таким образом саму производную? Нужно посчитать
производную от производной! Она называется \emph{второй производной} исходной
функции.

\example
    Рассмотрим функцию $f(x)=x^3+2x^2+3x+1$. Её производная равна
    \eq
        f'(x)=3x^2+4x+3,
    а вторая производная — это просто производная первой производной:
    \eq
        f''(x)=(f'(x))'=(3x^2+4x+3)'=6x+4.

Аналогично можно определить третью производную (производную от второй
производной) и т.д. Формальное определение такое:

\definition
    Производной порядка $n$ или просто $n$-й производной функции $f$ называется
    производная $(n-1)$-й производной этой функции. Производная первого порядка
    — это обычная производная, $f'$. Как правило, первые три производные
    обозначаются соответствующим количеством штрихов ($f'$, $f''$, $f'''$),
    четвертая производная иногда обозначается $f^{IV}$ (от римского числа 4),
    более старшие производные — числом в скобках: $f^{(5)}$ и т.д. (не путать со
    степенью!). Нулевой производной часто удобно считать саму функцию $f$.

\question
    Пусть $P$ — некоторый многочлен степени $n$:
    \eq
        P(x)=a_0 + a_1 x + \ldots + a_n x^n.
    Найдите его $n$-ую производную $P^{(n)}(x)$.
    \quiz
        \choice 
            $0$
            \comment
                Нет, это $(n+1)$-я производная равна нулю: при каждом
                дифференцировании степень уменьшается на $1$, за $n$
                дифференцирований мы получим константу, её производная — ноль.
        \choice \correct
            $n! a_n$
            \comment
                Верно! Каждый раз при дифференцировании будет сноситься
                очередная степень, и каждый раз она будет уменьшаться на 1. В
                результате за $n$ дифференцирований вынесется $n!$.
        \choice
            $a_0$
            \comment
                Нет, уже в первой производной $a_0$ не будет фигурировать.
        \choice
            $a_n$
            \comment
                Не совсем. Попробуйте взять $n=2$ и проверьте, что получится.
        \choice
            $na_n$.
            \comment
                Ну нет. Попробуйте взять $n=3$ и проверьте, что получится.
            
\remark
    Может так оказаться, что функция дифференцируема в какой-то точке, но её
    вторая производная в этой точке не существует. Например, рассмотрим функцию
    \eq
        f(x)=\begin{cases}
            x^2,& x < 0; \\\\
            3x^2, & x \ge 0.
        \end{cases}
    Её первая производная имеет вид:
    \eq
        f'(x)=\begin{cases}
            2x,& x < 0; \\\\
            6x, & x \ge 0.
        \end{cases}
    Можно проверить по определению, что в нуле производная определена и
    действительно равна нулю (проверьте!). Однако, вторая производная в нуле уже
    не определена: функция $f'$ имеет в нуле излом.

Производные порядка больше двух нам понадобятся позже, когда мы будем обсуждать
формулу Тейлора. А вот вторая производная понадобится совсем скоро.

\section Выпуклость вверх и вниз
\subsection Геометрическое определение
Допустим, я хочу сказать, что некоторая функция растёт с ускорением. Можно было
бы сказать, что её производная возрастает. Однако, не у всякой функции есть
производная. Оказывается, можно дать определение, которое будет выражать ту же
идею «роста с ускорением», но не требовать производных.

Посмотрим ещё раз на график функции $x^2$. Возьмём две произвольные точки и
соединим их отрезком — он называется \emph{хордой} (по аналогии с хордами
окружности).  По графику $y=x^2$ видно, что любая хорда лежит выше графика (не
считая концов, которые, конечно, лежат на графике). Если аналогичную штуку
проделать с графиком $y=\sqrt{x}$, там ситуация обратная: любая хорда лежит ниже
графика.

\definition \label def:19:conv-geom
    Пусть областью определения функции $f$ является некоторый промежуток
    (интервал, отрезок, полуинтервал, луч, вся прямая). Говорят, что $f$
    \emph{выпукла вниз} (соответственно, \emph{выпукла вверх}), если любая хорда
    лежит выше графика (соответственно, \emph{ниже графика}). Выпуклость может
    быть строгой и нестрогой. В первом случае хорде не разрешается иметь общие
    точки с графиком, кроме концов. Во втором разрешается. Как правило, без
    дополнительных уточнений обычно подразумевается нестрогая выпуклость.

\example
    Функция $y=|x|$ является нестрого выпуклой вниз, а $y=x^2$ — строго выпуклой
    вниз. Эти факты можно строго доказать, но мы пока ограничимся картинками.

\remark
    Иногда вместо «выпуклость вверх» и «выпуклость вниз» говорят «выпуклость» и
    «вогнутость». Мало того, что невозможно запомнить, кто из них кто, так ещё и
    в разных источниках терминология отличается с точностью до наоборот. Мы не
    будем использовать эти термины, чтобы не создавать путаницу.

    Термины «выпуклость вниз» и «выпуклость вверх» кажутся достаточно
    наглядными: достаточно представить себе график $y=x^2$, который смотрит
    «выпуклостью вниз», и $y=-x^2$, который смотрит «выпуклостью вверх».

\subsection Аналитическое определение

Геометрическое определение в терминах хорд достаточно наглядно, но для
доказательств полезно переформулировать его аналитически. Для этого нужно
научиться параметрически задавать точки на хорде.

Рассмотрим две точки на декартовой плоскости: $A=(x_1, y_1)$ и $B=(x_2,
y_2)$. Пусть для определенности $x_2 > x_1$ и $y_2 > y_1$ (хотя рассуждения
будут верными и в других случаях). Пусть $t \in [0, 1]$ и
\align \nonumber
    \item x(t)&=(1-t)x_1 + tx_2;
    \item y(t)&=(1-t)y_2 + ty_2.
Точка $x(t)$ делит отрезок $[x_1, x_2]$ в отношении $t:(1-t)$, то есть отношение
длин отрезков $[x_1, x(t)]$ и $[x(t), x_2]$ равно $t/(1-t)$.  (Проверьте — это
простое вычисление!) Можно думать про $x(t)$ как о «средневзвешенном» между
точками $x_1$ и $x_2$: при $t=0$ получается точка $x_1$, по мере того, как $t$
увеличивается, точка сдвигается в сторону $x_2$, при $t=1$ получается $x_2$.
Если $t=1/2$, получается середина отрезка.

Аналогично ведёт себя точка $y(t)$. 

\proposition
    Рассмотрим точку на плоскости
    \align \nonumber
        \item 
            C(t):= \splonly{&} (x(t), y(t))=
        \splitem 
            \splonly{=&} ((1-t)x_1 + tx_2, (1-t)y_1 +ty_2).

    Она лежит на отрезке с концами в точках $A$ и $B$ и делит этот отрезок в
    отношении $t:(1-t)$.
\proof
    Это утверждение можно доказать аналитически: найти уравнение прямой,
    проходящей через точки $A$ и $B$, и показать, что $C$ принадлежит этой
    прямой, затем найти расстояния до $A$ и до $B$ и найти их отношение. Но мы
    ограничимся геометрическим рассуждением.

    Рассмотрим точку $\tilde C(t)$, которая лежит на отрезке $[A, B]$ и делит его в
    отношении $t:(1-t)$. Докажем, что $\tilde C(t)=C(t)$.

    Проведём через точки $A$, $\tilde C(t)$ и $B$ вертикальные прямые до
    пересечения с горазонтальной осью в точках $(x_1, 0)$, $(\tilde x(t), 0)$ и
    $(x_2, 0)$. По теореме Фалеса точка $\tilde x(t)$ разбивает отрезок $[x_1,
    x_2]$ в том же отношении, в котором точка $\tilde C(t)$ разбивает отрезок
    $[A, B]$. Значит, $\tilde x(t)=x(t)$.

    Аналогично проведём через точки $A$, $\tilde C(t)$ и $B$ горизонтальные
    прямые до пересечения в вертикальной осью в точках $(0, y_1)$, $0, \tilde
    y(t))$ и $(0, y_2)$. По той же теореме Фалеса точка $\tilde y(t)$ должна
    совпадать с точкой $y(t)$. Значит, $\tilde C(t)$ имеет координаты $(x(t),
    y(t))$, то есть совпадает с точкой $C(t)$.

Теперь мы готовы дать аналитическое определение выпуклости.

\definition \label def:19:conv-analytical
    Пусть областью определения функции $f$ является некоторый промежуток
    (интервал, отрезок, полуинтервал, луч, вся прямая). Говорят, что $f$
    (нестрого) \emph{выпукла вниз} , если для любых различных точек
    $x_1, x_2 \in D(f)$, и любого $t\in (0, 1)$:
    \eq
        f((1-t)x_1 + tx_2) \le (1-t) f(x_1) + tf(x_2).
    Соответственно, (нестрого) \emph{выпукла вверх}, если
    \eq
        f((1-t)x_1 + tx_2) \ge (1-t) f(x_1) + tf(x_2).
    Чтобы получить строгую выпуклость, надо нестрогое неравенство заменить на
    строгое.

\remark
    Пусть $x(t)=(1-t)x_1 + tx_2$, $y(t)=(1-t) f(x_1) + tf(x_2)$. Тогда точка
    $(x(t), f(x(t))$ лежит на графике функции $y=f(x)$, а точка $(x(t), y(t))$
    — на соответствующей хорде. Таким образом, неравенства в
    \ref[определении][def:19:conv-analytical] говорят ровно то же самое, что
    и в \ref[определении][def:19:conv-geom]: что точка на графике лежит над или
    под точкой на хорде.
\exercise \label exer:19:linear
    Докажите, пользуясь \ref[определением][def:19:conv-analytical], что линейная функция
    нестрого выпукла вверх и нестрого выпукла вниз.

\definition
    Скажем, что точка $(x_0, y_0)$ лежит (нестрого) \emph{выше} (или
    \emph{над}) графиком функции $y=f(x)$, если $y_0 \ge f(x_0)$. В
    частности, точка $(x_0, y_0)$ лежит над некоторой прямой $y=kx+b$, если
    $y_0 \ge kx_0 + b$.

\subsection Хорды, касательные и производные
\theorem \label thm:19:three
    Пусть областью определения функции $f$ является интервал $(a, b)$ и она
    дифференцируема в каждой его точке. В этом случае следующие утверждения
    эквивалентны:
    \enumerate
        \item Функция $f$ нестрого выпукла вниз на $(a, b)$.
        \item $f'$ нестрого возрастает на $(a, b)$.
        \item Для любой точки $x\in (a, b)$ справедливо утверждение: все точки
            графика $f$ лежат нестрого над касательной к этому графику,
            проведённой в точке $(x, f(x))$. Иными словами, график проходит выше
            любой касательной.

\proof 
    Мы докажем, что из первого утверждения следует второе, из второго третье, а
    из третьего — первое. Таким образом будет доказано, что все три утверждения
    эквивалентны.

    \paragraph{Из выпуклости следует возрастание производной} 
    Пусть $f$ выпукла вниз. Докажем, что производная неубывает. Рассмотрим
    две произвольные точки $x_2>x_1\in (a, b)$. Пусть $A=(x_1, f(x_1))$ и
    $B=(x_2, f(x_2))$ — соответствующие точки на графике функции. Пусть
    $t\in (0, 1)$
    \align \nonumber
        \item x(t)&=(1-t)x_1+tx_2
        \item y(t)&=(1-t)y_1+ty_2
        \item C(t)&=(x(t),\,y(t))
        \item F(t)&=(x(t), f(x(t))
    Точка $C(t)$ находится над $x(t)$ и лежит на хорде $[A,
    B]$, а точка $F(t)$ — на графике $y=f(x)$. В силу выпуклости $f$, точка
    $F(t)$ лежит ниже $C(t)$, то есть
    \eq
        f(x(t)) \le y(t).

    Рассмотрим секущую, проходящую через точки $A$ и $F(t)$. Обозначим её
    угловой коэффициент через $k(t)$. Он не больше, чем угловой коэффициент
    $K$ хорды $[A, B]$, поскольку $F(t)$ лежит не выше хорды. Действительно,
    угловой коэффициент $k(t)$ равен
    \eq
        k(t)=\frac{f(x(t))-y_1}{x(t)-y_1},
    а угловой коэффициент хорды совпадает с угловым коэффициентом отрезка
    $[A, C(t)]$ (т.к. этот отрезок лежит на хорде $[A, B]$), который равен
    \eq
        K=\frac{y(t)-y_1}{x(t)-y_1},
    и поскольку $y(t) \ge f(x(t))$, эта дробь не меньше, чем $k(t)$. (Несмотря
    на наличие $t$ в правой части, $K$ на самом деле от $t$ не зависит — меняя
    $t$, мы меняем точку $C(t)$, но она остаётся на хорде $[A, B]$ и
    следовательно угловой коэффициент $[A, C(t)]$ не меняется: он всегда
    совпадает с угловым коэффициентом хорды $[A, B]$.)

    Предел $k(t)$ при $t\to 0^+$ равен производной функции $f$ в точке $x_1$
    (по условию функция дифференцируема, значит односторонний прдеел равен
    обычному пределу). Предельный переход в неравенстве $k(t) \le K$ теперь
    гарантирует, что производная не больше $K$. Полностью аналогичными
    рассуждениями (проведите их!) доказывается, что производная $f'(x_2)$ не
    меньше $K$. Следовательно, $f'(x_2) \ge f'(x_1)$. Поскольку $x_1$ и
    $x_2$ выбраны произвольно, это доказывает неубывание производной.

    \paragraph{Из возрастания производной следует, что график лежит выше
    касательных} Докажем, что если производная неубывает,
    то любая точка на графике лежит выше любой касательной. От противного.
    Пусть нашлась точка $x_1 \in (a, b)$ и такая точка $x_2>x_1$, что точка
    $B:=(x_2, f(x_2))$ лежит под касательной, проведённой в точке $A:=(x_1,
    f(x_1))$. Тогда хорда $[A, B]$ имеет угловой коэффициент меньше, чем
    угловой коэффициент касательной в точке $A$, то есть меньше, чем
    $f'(x_1)$. По теореме Лагранжа из этого следует, что существует такая
    точка $c \in (x_1, x_2)$, что $f'(c)$ равна угловому коэффициенту хорды
    $[A, B]$ и таким образом $f'(c)<f'(x_1)$. Противоречие.

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

\section Выпуклые множества и функции

\definition \label def:19:conv-set
    Множество $K \subset \mathbb R^2$ на плоскости называется
    \emph{выпуклым}, если для любых точек $A, B \in K$, весь отрезок $[A,
    B]$ лежит внутри $K$. Например, круг и треугольник выпуклы, а звезда
    — нет.

\definition
    \emph{Надграфиком} функции $f$ называется множество точек плоскости,
    лежащих над её графиком (включая сам график). Формально:

    \eq
        \mathop{\mathrm{supergraph}}(f):=\set{(x, y)\in \mathbb R^2 \mid y \ge f(x)}.
\exercise
        Догадайтесь, что такое \emph{подграфик} функции.
\proposition \label prop:19:iff
    Функция является выпуклой вниз тогда и только тогда, когда её надграфик выпуклый.
\proof 
    Пусть надграфик функции выпуклый. График является подмножеством
    надграфика. Тогда для любых точек графика
    весь отрезок, соединяющий эти точки, лежит в надграфике. То есть
    весь отрезок проходит над графиком. Значит, функция выпукла вниз.

    Наоборот, пусть функция выпукла вниз. Докажем, что надграфик является
    выпуклым множеством. Рассмотрим две произвольные точки $A=(x_1, y_1)$ и
    $B=(x_2, y_2)$ в надграфике $f$:
    \align \nonumber
        \item y_1 & \ge f(x_1);
        \item y_2 & \ge f(x_2).
    Возьмём произвольное $t \in [0, 1]$. Умножим первое неравенство на $(1-t)$,
    а второе на $t$, и сложим. Получим такое неравенство:
    \eq
        (1-t) y_1 + t y_2 \ge (1-t) f(x_1) + tf(x_2).
    Но в силу выпуклости вниз функции $f$, правая часть этого неравенста не
    меньше $f((1-t) x_1 + tx_2)$. Таким образом, точка 
    \align \nonumber
        \item
            C(t):= \splonly{&} ((1-t)x_1 + tx_2, (1-t) y_1 + t y_2) \in 
        \splitem \splonly{\in &} [A, B]
    лежит в надграфике $f$. Поскольку $t$ произвольно, в качестве $C(t)$ можно
    получить любую точку отрезка $[A, B]$, то есть весь отрезок лежит в
    надграфике и надграфик является выпуклым множеством.
\remark
    Аналогично, если функция выпукла вверх, выпуклым является её подграфик.
\remark
    Рассмотрим произвольную невертикальную прямую на плоскости. Она является
    графиком некоторой функции $y=kx+b$ и делит плоскость на две полуплоскости
    — надграфик этой функции и подграфик. По \ref[упражнению][exer:19:linear],
    линейная функция одновременно выпукла вверх и вниз, и значит полуплоскости
    являются выпуклыми множествами.
\proposition
    Пусть $\{K_\alpha\}$ — набор выпуклых множеств . Тогда их пересечение 
    \eq
        W=\bigcap_{\alpha} K_\alpha
    выпукло.

    Множество $W$ по определению состоит их тех точек плоскости, которые
    содержатся во всех $K_\alpha$.
\example
    Здесь $\alpha$ — «номер» очередного множества в наборе, но при этом $\alpha$
    не обязан быть натуральным числом. Например, можно рассмотреть набор
    треугольников с вершинами $(0, 0)$, $(2, 0)$ и $(1, \alpha)$ для всех
    $\alpha\in \mathbb R$ (пусть каждый треугольник включает свои стороны).

    Упражнение: найти $W$ в этом примере. (Даже не пытайтесь двигаться
    дальше, если вы не можете выполнить это упражнение.)
\proof 
    Рассмотрим две любые точки $A, B \in W$. Поскольку $A \in W$, то для
    всех $\alpha$, $A \in K_\alpha$. Аналогично, для всех $\alpha$, $B
    \in K_\alpha$. Следовательно, для всех $\alpha$, отрезок $[A,
    B]\subset K_\alpha$ (поскольку каждое $K_\alpha$ выпукло).
    Следовательно, $[A, B] \subset W$.
\proof \of последней части \ref[теоремы][thm:19:three]
    Теперь мы готовы доказать, что в \ref[теореме][thm:19:three] из третьего
    утверждения (график лежит над касательной) следует первое (функция выпукла
    вниз). Пусть $\alpha \in (a, b)$.
    Проведём касательную через точку $(\alpha, f(\alpha))$. Эта касательная
    разбивает плоскость на две полуплоскости, верхнюю и нижнюю. Пусть
    верхняя полуплоскость (включая саму касательную) — это $K_\alpha$.
    Рассмотрим их пересечение:
    \eq
        W=\cap_\alpha K_\alpha.
    Докажем, что это надграфик функции $f$. (Строго говоря, надграфиком будет
    пересечение $W$ с полосой $x\in (a, b)$ — но эта полоса сама является
    выпуклым множеством и ничего не портит.) Действительно, по условию, любая
    точка графика лежит над любой касательной к этому графику. Значит, любая
    точка графика и весь луч от неё вверх
    лежит во всех $K_\alpha$ и значит лежит в $W$. Таким образом, весь надграфик
    лежит в $W$. Докажем теперь, что в $W$ нет
    лишних точек. Пусть некоторая точка $(x_0, y_0)$ лежит ниже графика, $x_0
    \in [a, b]$. Тогда она лежит ниже точки $(x_0, f(x_0))$. Но это самая нижняя
    точка в пересечении $K_{x_0}$ и вертикальной прямой $x=x_0$. Значит, $(x_0,
    y_0)$ не лежит в $K_{x_0}$ и не лежит в $W$. Следовательно, надграфик
    является выпуклым как пересечение выпуклых множеств. По
    \ref[утверждению][prop:19:iff], из этого следует, что функция выпукла вниз.
    Доказательство теоремы \ref[thm:19:three] завершено.

\corollary
    Если функция дважды дифференцируема на $(a, b)$ и $f''(x) > 0$ для всех $x$,
    то она выпукла вниз, а если $f''(x) < 0$, то вверх. Действительно, в первом
    случае производная $f'$ должна возрастать, а во втором — убывать. По только
    что доказанной теореме это влечёт соответствующую выпуклость.
\example
    Функция $f(x)=x^2$ выпукла вниз. Действительно, $f'(x)=2x$, $f''(x)=2>0$.
    Доказать это утверждение вручную, пользуясь
    \ref[определением][def:19:conv-analytical] тоже можно, но гораздо тоскливее
    (попробуйте!).

\section Заключение

Выпуклость — важное свойство функций и с теоретической, и с практической
точки зрения. Мы доказали полезную теорему, связывающую выпуклость с
поведением производной — она позволяет находить промежутки выпуклости,
анализируя знак второй производной. К старшим производным мы скоро вернёмся
— когда будем обсуждать формулы Тейлора.