Выпуклые функции — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(LOAAADS OF BUGS (куда смотрел наборщик вообще?))
Строка 1: Строка 1:
 
== Определения ==  
 
== Определения ==  
  
Будем рассматривать отрезок <tex>[a; b]</tex>, набор чисел <tex>x_1, x_2, x_3, \ldots x_n \in [a; b]</tex> и коэффициенты <tex>\alpha_1, \alpha_2, \ldots, \alpha_n > 0</tex>
+
Будем рассматривать отрезок <tex>[a; b]</tex>, набор чисел <tex>x_1, x_2, x_3, \ldots x_n \in [a; b]</tex> и коэффициенты <tex>\alpha_1, \alpha_2, \ldots, \alpha_n \ge 0</tex>
 
такие, что <tex>\sum\limits_{i = 1}^n \alpha_i = 1</tex>.
 
такие, что <tex>\sum\limits_{i = 1}^n \alpha_i = 1</tex>.
  
Строка 36: Строка 36:
 
Неравенство Йенсена
 
Неравенство Йенсена
 
|statement=
 
|statement=
Пусть <tex>f(x)</tex> выпукла вверх на <tex>[a; b]</tex>. Тогда <tex>\forall x_1; x_2 \ldots x_n \in [a; b]</tex> и их выпуклой комбинации выполнено неравенство
+
Пусть <tex>f(x)</tex> выпукла вверх на <tex>[a; b]</tex>. Тогда <tex>\forall x_1, x_2 \ldots x_n \in [a; b]</tex> и их выпуклой комбинации выполнено неравенство
 
<tex>\sum\limits_{k = 1}^n \alpha_k f(x_k) \leq f\left(\sum\limits_{k = 1}^n \alpha_k x_k\right)</tex>.
 
<tex>\sum\limits_{k = 1}^n \alpha_k f(x_k) \leq f\left(\sum\limits_{k = 1}^n \alpha_k x_k\right)</tex>.
 
|proof=
 
|proof=
Строка 51: Строка 51:
 
<tex>
 
<tex>
 
\sum\limits_{k = 1}^{n + 1} \alpha_k f(x_k) =  
 
\sum\limits_{k = 1}^{n + 1} \alpha_k f(x_k) =  
s_n \sum\limits_{k = 1}^n \beta_k f(x_k) + \alpha_{n + 1}f(x_{n + 1}) \leq
+
s_n \sum\limits_{k = 1}^n \beta_k f(x_k) + \alpha_{n + 1}f(x_{n + 1}) \leq</tex> (по предположению индукции) <tex>
s_n f\left(\sum\limits_{k = 1}^n \beta_k x_k + \alpha_{n + 1}x_{n + 1}\right) \leq </tex> (так как <tex>s_n + \alpha_{n + 1} = 1</tex>)  
+
s_n f\left(\sum\limits_{k = 1}^n \beta_k x_k \right) + \alpha_{n + 1}f(x_{n + 1}) \leq </tex> (так как <tex>s_n + \alpha_{n + 1} = 1</tex>)  
 
<tex> f\left(\sum\limits_{k = 1}^{n + 1} \alpha_k x_k\right)</tex>
 
<tex> f\left(\sum\limits_{k = 1}^{n + 1} \alpha_k x_k\right)</tex>
  
Значит, шаг индукции проделан, нерваенство доказано для произвольного <tex>n</tex>.
+
Значит, шаг индукции проделан, неравенство доказано для произвольного <tex>n</tex>.
  
 
}}
 
}}
Строка 71: Строка 71:
 
<tex>f(x) - L_n(x) = \frac{f^{(2)}(c_x)}{2!}(x - x_0)(x - x_1)</tex>, <tex>x_0 \leq x \leq x_1</tex>.
 
<tex>f(x) - L_n(x) = \frac{f^{(2)}(c_x)}{2!}(x - x_0)(x - x_1)</tex>, <tex>x_0 \leq x \leq x_1</tex>.
  
Если <tex>f^{(2)} = 0</tex> на <tex>\langle a; b\rangle</tex> то правая часть будет неотрицательная, так как <tex>x \in [x_0; x_1]</tex>, поэтому  
+
Если <tex>f^{(2)} \leq 0</tex> на <tex>\langle a; b\rangle</tex> то правая часть будет неотрицательная, так как <tex>x \in [x_0; x_1]</tex>, поэтому  
<tex>f(x) - L_n(x) \leq 0</tex>, так как <tex>x_0</tex> и <tex>x_1</tex> произвольны, то <tex>f</tex> выпукла вверх.
+
<tex>f(x) - L_n(x) \geq 0</tex>, и т. к. <tex>x_0</tex> и <tex>x_1</tex> произвольны, то <tex>f</tex> выпукла вверх.
  
Итак, <tex>f^{(2)} = 0 \Rightarrow f </tex> &mdash; выпукла вверх.
+
Итак, <tex>f^{(2)} \leq 0 \Rightarrow f </tex> &mdash; выпукла вверх.
  
 
Пусть <tex>f</tex> выпукла вверх. Будем считать, что <tex>f^{(2)}</tex> &mdash; непрерывна. <tex>x \in \langle a; b\rangle</tex>.
 
Пусть <tex>f</tex> выпукла вверх. Будем считать, что <tex>f^{(2)}</tex> &mdash; непрерывна. <tex>x \in \langle a; b\rangle</tex>.
  
<tex>x_0 = x - \Delta x</tex>, <tex>x_1 = x + \Delta x</tex>, где <tex>\Delta x</tex> &mdash; малое положительное число.
+
Пусть <tex>x_0 = x - \Delta x</tex>, <tex>x_1 = x + \Delta x</tex>, где <tex>\Delta x</tex> &mdash; малое положительное число.
 +
Рассмотрим полином Лагранжа <tex>L_n</tex> для системы узлов <tex>(x_0, x_1)</tex> :
  
<tex>f(t) - L_n(t) = \frac{f^{(2)}(c_t)}{2!} (t - x_0)(t - x_1), \, (t - x_0)(t - x_1) < 0 \Rightarrow f^{(2)}(c_t) \leq 0</tex>
+
<tex>f(t) - L_n(t) = \frac{f^{(2)}(c_t)}{2!} (t - x_0)(t - x_1) \geq 0, \, (t - x_0)(t - x_1) < 0 \Rightarrow f^{(2)}(c_t) \leq 0</tex>
  
 
<tex>c_t \in \langle x - \Delta x; x + \Delta x \rangle</tex>
 
<tex>c_t \in \langle x - \Delta x; x + \Delta x \rangle</tex>
  
<tex>\Delta x \to 0 : x_0 \to x : f^{(2)}(x) \leq 0</tex>
+
<tex>\Delta x \to 0 : c_t \to x : f^{(2)}(x) \leq 0</tex>
  
Если <tex>f</tex> выпукла вверх, то <tex>f^{(2)} \leq 0</tex>.
+
Итак, если <tex>f</tex> выпукла вверх, то <tex>f^{(2)} \leq 0</tex>.
  
 
=== Пример ===  
 
=== Пример ===  
  
В качестве примера рассмотрим <tex>y = \ln x</tex>, <tex>y^{(2)} = \frac{-1}{x^2} \leq 0 \Rightarrow \ln x</tex> выпукла вверх.  
+
В качестве примера рассмотрим <tex>y = \ln x</tex>, <tex>y'' = \frac{-1}{x^2} \leq 0 \Rightarrow \ln x</tex> выпукла вверх.  
 
Это мы применим в следующем параграфе.
 
Это мы применим в следующем параграфе.
  
 
[[Категория:Математический анализ 1 курс]]
 
[[Категория:Математический анализ 1 курс]]

Версия 07:45, 17 ноября 2010

Определения

Будем рассматривать отрезок [math][a; b][/math], набор чисел [math]x_1, x_2, x_3, \ldots x_n \in [a; b][/math] и коэффициенты [math]\alpha_1, \alpha_2, \ldots, \alpha_n \ge 0[/math] такие, что [math]\sum\limits_{i = 1}^n \alpha_i = 1[/math].


Определение:
Выпуклая комбинация чисел [math]x_k[/math] — это [math]\bar x = \sum\limits_{i = 1}^n \alpha_kx_k[/math]


Частный случай — [math]\alpha_k = \frac1n[/math]. В этом случае [math]\bar x[/math] — среднее арифметическое.

Обозначим за [math]x_* = \min \{x_1; x_2; \ldots x_n \}[/math], а [math]x^* = \max \{x_1; x_2; \ldots x_n \}[/math]. Тогда [math]x_* \leq \bar x \leq x^*[/math], а так как [math]x_* \in [a; b][/math] и [math]x^* \in [a; b]$, то $\bar x \in [a; b][/math].

В этом смысле отрезок — выпуклое множество, так как он содержит выпуклую комбинацию любых своих чисел.

(типа определение) Выпуклое множество вместе с парой своих точек содержит отрезок, их соединяющий.


Определение:
Пусть [math]f(x)[/math] задана на [math][a; b][/math]. Тогда она выпукла вверх на этом отрезке, если

[math]\forall x_1, x_2 \in [a; b] \forall \alpha \in [0; 1] \quad \alpha f(x_1) + (1 - \alpha) f(x_2) \leq f(\alpha x_1 + (1 - \alpha)x_2)[/math].

Если же всё время неравенство противоположно, то функция называется выпуклой вниз.


В силу того, что было сказано о выпуклой комбинации, определение корректно: [math]\alpha x_1 + (1 - \alpha)x_2 \in [a; b][/math].

Легко понять, что с геометрической точки это значит, что для выпуклой вверх функции её график будет лежать выше хорды.

Замечание: если [math]f(x)[/math] выпукла вниз, то [math]-f(x)[/math] выпукла вверх.

Неравенство Йенсена

Теорема (Неравенство Йенсена):
Пусть [math]f(x)[/math] выпукла вверх на [math][a; b][/math]. Тогда [math]\forall x_1, x_2 \ldots x_n \in [a; b][/math] и их выпуклой комбинации выполнено неравенство [math]\sum\limits_{k = 1}^n \alpha_k f(x_k) \leq f\left(\sum\limits_{k = 1}^n \alpha_k x_k\right)[/math].
Доказательство:
[math]\triangleright[/math]

Докажем по индукции.

База: [math]n = 2[/math]. Неравенство превращается в определение выпуклой вверх функции, для которой это, очевидно, выполняется.

Переход. Пусть это верно для [math]n[/math]. Докажем, что это верно для [math]n + 1[/math]:

[math]\sum\limits_{k = 1}^{n + 1} \alpha_k = 1[/math], обозначим за [math]s_n = \sum\limits_{k = 1}^n \alpha_k[/math]

Пусть [math]\beta_k = \frac{\alpha_k}{s_n}[/math]. Тогда получаем: [math]\sum\limits_{k = 1}^{n} \beta_k = 1[/math].

[math] \sum\limits_{k = 1}^{n + 1} \alpha_k f(x_k) = s_n \sum\limits_{k = 1}^n \beta_k f(x_k) + \alpha_{n + 1}f(x_{n + 1}) \leq[/math] (по предположению индукции) [math] s_n f\left(\sum\limits_{k = 1}^n \beta_k x_k \right) + \alpha_{n + 1}f(x_{n + 1}) \leq [/math] (так как [math]s_n + \alpha_{n + 1} = 1[/math]) [math] f\left(\sum\limits_{k = 1}^{n + 1} \alpha_k x_k\right)[/math]

Значит, шаг индукции проделан, неравенство доказано для произвольного [math]n[/math].
[math]\triangleleft[/math]

Связь выпуклости и дифференцируемости

Применим линейную интерполяцию (в случае [math]2[/math] узлов) чтобы выяснить связь между выпуклостью и дифференцируемостью функции [math]f[/math]. Будем считать, что [math]f[/math] дифференцируема столько раз, сколько нам нужно. Имея [math]2[/math] узла на [math]\langle a; b\rangle[/math] и [math]y_0 = f(x_0)[/math], [math]y_1 = f(x_1)[/math], составим [math]L_n(x)[/math]:

[math]L_n(x) = y_0 \frac{x - x_1}{x_0 - x_1} + y_1\frac{x - x_0}{x_1 - x_0}[/math] — прямая, проходящая через точки [math](x_0, y_0)[/math] и [math](x_1, y_1)[/math]. Значит, между [math]x_0[/math] и [math]x_1[/math] получаем хорду, соединяющую две точки графика.

В вопросе о выпуклости надо проверять знак такой разности: [math]f(x) - L_n(x) = \frac{f^{(2)}(c_x)}{2!}(x - x_0)(x - x_1)[/math], [math]x_0 \leq x \leq x_1[/math].

Если [math]f^{(2)} \leq 0[/math] на [math]\langle a; b\rangle[/math] то правая часть будет неотрицательная, так как [math]x \in [x_0; x_1][/math], поэтому [math]f(x) - L_n(x) \geq 0[/math], и т. к. [math]x_0[/math] и [math]x_1[/math] произвольны, то [math]f[/math] выпукла вверх.

Итак, [math]f^{(2)} \leq 0 \Rightarrow f [/math] — выпукла вверх.

Пусть [math]f[/math] выпукла вверх. Будем считать, что [math]f^{(2)}[/math] — непрерывна. [math]x \in \langle a; b\rangle[/math].

Пусть [math]x_0 = x - \Delta x[/math], [math]x_1 = x + \Delta x[/math], где [math]\Delta x[/math] — малое положительное число. Рассмотрим полином Лагранжа [math]L_n[/math] для системы узлов [math](x_0, x_1)[/math] :

[math]f(t) - L_n(t) = \frac{f^{(2)}(c_t)}{2!} (t - x_0)(t - x_1) \geq 0, \, (t - x_0)(t - x_1) \lt 0 \Rightarrow f^{(2)}(c_t) \leq 0[/math]

[math]c_t \in \langle x - \Delta x; x + \Delta x \rangle[/math]

[math]\Delta x \to 0 : c_t \to x : f^{(2)}(x) \leq 0[/math]

Итак, если [math]f[/math] выпукла вверх, то [math]f^{(2)} \leq 0[/math].

Пример

В качестве примера рассмотрим [math]y = \ln x[/math], [math]y'' = \frac{-1}{x^2} \leq 0 \Rightarrow \ln x[/math] выпукла вверх. Это мы применим в следующем параграфе.