Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
x 2 )| < ?. 30 Гл. 1. Основы многомерного анализа Легко видеть, что равномерно непрерывная на множе- стве M функция непрерывна на M. Обратное, вообще говоря, неверно. Пример 3. Рассмотрим функцию f (x) = 1 x , заданную на интервале (0, 1). Эта функция непрерывна на всем интервале (0, 1), но не равномерно непрерывна. В самом деле, как ни мало бы было число ?, взяв натуральное число N столь большим, чтобы выполнялось неравенство 1 N 2 < ?, имеем 0 < 1 N ? 1 N + 1 = 1 N (N + 1) < ?; в то же самое время, Ї Ї Ї Їf µ 1 N ¶ ? f µ 1 N + 1 ¶Ї Ї Ї Ї = 1. Переходя от векторных обозначений к скалярным, поло- жим x = (x 1 , . . . , x p ), f (x) = (f 1 (x), . . . , f q (x)). Тогда вместо одной векторной функции f векторного перемен- ного x имеем q скалярных функций p скалярных переменных: f j (x) = f j (x 1 , . . . , x p ), j = 1, . . . , q. (24) Легко проверить, что непрерывность векторной функции f вектора x равносильна непрерывности всех функций (24) по совокупности переменных x = (x 1 , . . . , x p ) и обратно; то же самое относится и к равномерной непрерывности. Связь между непрерывностью, раномерной непрерывно- стью и компактностью устанавливает следующая Теорема 6. Пусть M компактное подмножество про- странства R p и пусть f : R p ? R q отображение, непрерыв- ное на M. Тогда отображение f равномерно непрерывно на M, а множество f(M) компактно. џ1. Топология евклидовых пространств 31 Доказательство. Прежде всего, докажем, что отобра- жение f равномерно непрерывно. Для этого предположим про- тивное и приведем это предположение к противоречию. Если отбражение f непрерывно, но не равномерно непре- рывно, то найдется такое положительное число ?, что для каж- дого положительного числа ? можно указать две такие точки a и x множества M, для которых из условия |x?a| < ? следует неравенство |f (x) ? f (a)| ? ?. Тогда можно построить бесконечную последовательность (a 1 , x 1 ), (a 2 , x 2 ), . . . , (a k , x k ), . . . пар точек, для которых выполнены условия |f (x k ) ? f (a k )| ? ?, k = 1, 2, 3, . . . (25) и lim k?? |x k ? a k | = 0. (26) Так как последовательность a 1 , a 2 , . . . , a k , . . . (27) содержится в компактном множестве M, то в силу теоремы 4 из нее можно выбрать некоторую подпоследовательность, схо- дящуюся к точке a ? M. При этом для простоты обозначений будем считать, что выбранная подпоследовательность совпа- дает с последовательностью (27). Поскольку функция f непрерывна в точке a, то существу- ет такое положительное число ?, что при |x?a| < ? выполнено неравенство |f (x) ? f (a)| < ? 2 . Но так как последовательность (27) сходится к точке a, то в силу соотношения (26) найдется столь большое натуральное число k, что |a k ? a| < ? и |x k ? a| < ? (см. упражнение 1). Поэтому для данного значения k имеем |f (x k ) ? f (a k )| < |f (x k ) ? f (a)| + |f (a k ) ? f (a)| < 2 · ? 2 = ?, что противоречит неравенству (25). 32 Гл. 1. Основы многомерного анализа Переходя теперь к доказательству компактности множе- ства f(M), рассмотрим некоторое бесконечное подмножество E множества f(M); можно считать, что такое множество су- ществует (см. замечание к теореме 5). Из множества E выбе- рем некоторую бесконечную последовательность b 1 , b 2 , . . . , b k , . . . (28) попарно различных точек. Для каждой точки b k последова- тельности (28) выберем такую точку a k ? M , что b k = f (a k ), k = 1, 2, 3, . . . Точки a 1 , a 2 , . . . , a k , . . . (29) попарно различны и потому имеют предельную точку a в мно- жестве M. Покажем, что точка b = f (a) является предельной точкой множества (29). В самом деле, пусть V произвольная окрестность точки b , т.е. шар некоторого радиуса ? с центром в точке b. Поскольку функция f непрерывна в точке a, найдется такое положитель- ное число ?, что для некоторой точки x ? M при |x ? a| < ? выполнено неравенство |f (x) ? f (a)| < ?. Так как точка a является предельной точкой множества (29), в шаре U радиуса ? с центром в точке a найдутся по край- ней мере две различные точки a k и a l этого множества (см. упражнение 2). Точки b k и b l принадлежат к шару V , и, так как они различны, по крайней мере одна из них не совпадает с точкой b. Поэтому произвольная окрестность V точки b содер- жит по крайней мере одну точку множества (24), отличную от b , т.е. точка b является предельной точкой множества (24) и, следовательно, множества E. Таким образом, множество f(M) компактно. ¤ Важнейшим (в том числе и для теории экстремальных за- дач) следствием теоремы 6 является следующая џ1. Топология евклидовых пространств 33 Теорема 7 (Вейерштрасс). Пусть M некоторое мно- жество в пространстве R n и пусть f : R n ? R отобра- жение, непрерывное на M. Тогда, если множество M ком- пактно, то функция f достигает на множестве M точной верхней и точной нижней грани. Доказательство. Поскольку множество M компактно, то в силу теоремы 6 множество f(M) также компактно. По- этому точная верхняя ? f (M ) и точная нижняя грани ? f (M ) множества f(M) принадлежат f(M) (см. упражнение 7). ¤ Упражнения. (1) Докажите, что для любых трех векторов a, b и c простран- ства R n справедливо неравенство |a ? c| ? |a ? b| + |b ? c|. (2) Пусть a предельная точка множества M пространства R n . Покажите, что каждая окрестность точки a содержит бесконечное множество точек из M. (3) Используя упражнение 2, покажите, что если последова- тельность (10) содержит бесконечное множество различ- ных точек, то точка a в формуле (11) является предельной точкой множества точек последовательности (10), причем единственной. (4) Докажите теорему Коши: последовательность (9) сходит- ся тогда и только тогда, когда lim k,l?? |a k ? a l | = 0. (5) Пусть R p и R q два евклидовых векторных пространства и пусть f непрерывное отображение некоторого откры- того множество G ? R p в R q . Покажите, что прообраз f ?1 (H) любого открытого множества H ? R q является открытым множеством пространства R p (6) Докажите, что непрерывность (равномерная непрерыв- ность) векторной функции f векторного переменного x равносильна непрерывности (равномерной непрерывно- сти) всех функций (20) и обратно. (7) Пусть M некоторое компактное множество на действи- тельной прямой R. Покажите, что точная верхняя грань ? M и точная нижняя грань ? M множества M принадле- жат M. 34 Гл. 1. Основы многомерного анализа (8) Число A называется пределом числовой функции f при x ? a , A = lim x?a f (x), если для кажого значения ? > 0 можно указать такое зна- чение ? > 0, что всякий раз, когда |x ? a| < ?, выполнено неравенство |f (x) ? A| < ?. Покажите, что функция f непрерывна в точке a тогда и только тогда, когда lim x?a f (x) = f (a). (9) Покажите, что числовая функция f непрерывна в точке a тогда и только тогда, когда для произвольной последо- вательности (9), удовлетворяющей условию lim k?? a k = a, выполнено также и условие lim k?? f (a k ) = f (a). џ2. Дифференцирование В џ2 рассматриваются вопросы дифференцирования отоб- ражений многомерных евклидовых пространств. Важнейшим для теории экстремальных задач здесь является понятие про- изводной по направлению или вариации, поскольку попытка изложения общей теории экстремальных задач с единых по- зиций во многом базируется собственно на понятии вариации. При этом в отличие от случая функции одного действитель- ного переменного в многомерном случае анализ функции на экстремум проделать гораздо сложнее, поскольку свойства чи- словых функций, заданных на плоскости, уже существенно от- личаются от свойств функций, заданных на действительной прямой (см. џ4, упражнения 36). Помимо понятия вариации в џ2 вводится понятие произ- водной многомерного отображения. Данная производная ока- зывается функциональной матрицей, называемой матрицей Якоби. џ2. Дифференцирование 35 Дифференцирование числовых функций. Пусть f отображение евклидова пространства R n на действительную прямую R, для краткости называемое в дальнейшем числовой функцией. Предположим, что в некоторой точке x ? R n функ- ция f для всех ?x ? R n допускает представление f (x + ?x) = f (x) + hk, ?xi + R(?x), (1) где k некоторая точка пространства R n и R некоторая числовая функция. Функция f называется дифференцируемой в точке x ? R n , если в представлении (1) выполнено условие lim |?x|?0 |R(?x)| |?x| = 0. Вектор k в формуле (1) называется производной или гра- диентом функции f в точке x и обозначается f 0 (x) или ?f(x). Таким образом, градиент ?f(x) дифференцируемой числовой функции f в точке x есть вектор в пространстве R n , задавае- мый равенством f (x + ?x) = f (x) + h?f (x), ?xi + o(?x). (2) Если размерность n пространства R n равна единице, то формула (2) принимает вид f (x + ?x) = f (x) + f 0 (x)?x + o(?x), (3) где f 0 (x) производная функции f в точке x, задаваемая ра- венством f 0 (x) = lim ?x?0 f (x + ?x) ? f (x) ?x , непосредственно вытекающим из равенства (3). Таким обра- зом, в силу равенства (3) числовая функция f скалярного пе- ременного x дифференцируема в точке a, если она допускает линейную аппроксимацию первого порядка в этой точке, т.е. если ее приращение ?y = f (a + ?x) ? f (a) удовлетворяет условию ?y = f 0 (a)?x + o(?x). 36 Гл. 1. Основы многомерного анализа Аналогичным образом, в силу равенства (2) числовая функция f векторного переменного x дифференцируема в точке a, если ее приращение ?y = f (a + ?x) ? f (a) удовлетворяет условию ?y = h?f (a), ?xi + o(?x). При этом дифференциалом dy функции f в точке a называется линейная часть приращения ?y, т.е. dy = h?f (a), ?xi. Заметим теперь, что в силу формулы (2) градиент ?f функции f определяется однозначно, причем имеет место ра- венство ?f = µ ?f ?x 1 , . . . , ?f ?x n ¶ , (4) т.е. градиент можно вычислять как непосредственно по опре- делению (2), так и с использованием частных производных по формуле (4). Пример 4. В качестве одного из примеров вычисления градиента рассмотрим квадратичную функцию f (x) = hAx, xi/2 ? hb, xi, где A действительная симметрическая матрица размерности (n Ч n) и b вектор в пространстве R n . Тогда имеет место цепочка равенств f (x + ?x) = hA(x + ?x), x + ?xi/2 ? hb, x + ?xi = = hAx, xi/2 ? hb, xi + hAx ? b, ?xi + hA?x, ?xi/2 = = f (x) + hAx ? b, ?xi + hA?x, ?xi/2. При этом, однако, в силу неравенства Коши Буняковского hA?x, ?xi 2 ? |A?x| 2 |?x| 2 . Поэтому lim |?x|?0 |hA?x, ?xi/2| |?x| = 0 џ2. Дифференцирование 37 и, следовательно, функция f дифференцируема в любой точке x ? R n и ?f (x) = Ax ? b. (5) Числовая функция f называется дифференцируемой на множестве Q ? R n , если она дифференцируема во всех точ- ках Q. Если же числовая функция f дифференцируема во всем пространстве R n , то говорят просто, что функция f дифферен- цируема. Легко видеть, что разрывная функция не является диффе- ренцируемой, поскольку, например, в силу формулы (2) имеет место следующая очевидная Теорема 8. Если числовая функция f : R n ? R диффе- ренцируема в некоторой точке x ? R n , то она непрерывна в этой точке. Доказательство. Пусть ?x 1 , ?x 2 , . . . , ?x k , . . . (6) некоторая последовательность точек пространства R n , удо- влетворяющих условию lim k?? ?x k = 0. Поскольку функция f дифференцируема в точке x, то f (x + ?x k ) = f (x) + h?f (x), ?x k i + o(?x k ), k = 1, 2, 3, . . . Поэтому имеет место цепочка равенств lim k?? |f (x + ?x k ) ? f (x)| = lim k?? |h?f (x), ?x k i + o(?x k )| = 0. Но так как при этом последовательность (6) выбиралась произвольным образом, отсюда непосредственно следует, что функция f непрерывна в точке x (см. џ2, упражнение 10). ¤ Пусть числовая функция f дифференцируема на некото- ром отрезке [x, x + y], т.е. для всех точек вида x + ?y, где 0 ? ? ? 1 . Рассмотрим функцию ? действительного перемен- ного ?, ?(? ) = f (x + ? y), 38 Гл. 1. Основы многомерного анализа и для всех значений 0 ? ? ? 1 вычислим ее производную ? 0 (? ) = lim ?? ?0 ?(? + ?? ) ? ?(? ) ?? . (7) Для этого запишем ?(? + ?? ) ? ?(? ) ?? = h?f (x + ? y), ?? yi + o(?? y) ?? . Тогда в силу соотношения (7) функция ? дифференцируема на отрезке [0, 1], причем ? 0 (? ) = h?f (x + ? y), yi. (8) Пусть f некоторая числовая функция. Величина f 0 (x; y) = lim ??0+ f (x + ?y) ? f (x) ? называется производной по направлению или вариацией функ- ции f в точке x по направлению y. Заметим теперь, что производная по направлению может существовать не только для гладких, но и для негладких функций. Например, для функции f (x) = |x| производная по направлению в точке x = 0 имеет вид f (0; y) = |y|. Если функция f имеет в точке x производную по всем направлениям, причем линейную по y, т.е. производную вида f 0 (x; y) = ha, yi, то говорят, что функция f дифференцируема по Гато в точке x . Такая функция имеет частные производные. При этом f 0 (x; e i ) = ?f (x) ?x i , i = 1, . . . , n, где e i координатные орты и a = µ ?f (x) ?x 1 , . . . , ?f (x) ?x n ¶ . Определенный таким образом вектор a называется производ- ной Гато в точке x. џ2. Дифференцирование 39 6 - E 1 x 1 x 2 E 2 E 3 s Рис. 1 Из формулы (8) непосредственно следует, что если функ- ция f дифференцируема в точке x, то она дифференцируема и по Гато, причем f 0 (x, y) = ? 0 (0) = h?f (x), yi. Обратное, вообще говоря, неверно. Пример 5. Пусть n = 2. На плоскости R 2 обозначим че- рез E 1 действительную прямую x 2 = 0 , через E 2 множество точек, удовлетворяющих условию x 2 ? (x 1 ) 2 , а через E 3 мно- жество точек, удовлетворяющих условию x 2 ? ?(x 1 ) 2 . Далее, положим E = E 1 ? E 2 ? E 3 и рассмотрим функцию f : R 2 ? R вида f (x) = Ѕ 1, x ? E, 0, x / ? E (9) (см. рис. 1). 40 Гл. 1. Основы многомерного анализа Легко видеть, что функция f, задаваемая равенством (9), дифференцируема по Гато в начале координат. При этом, од- нако, в точке x = 0 данная функция имеет разрыв и, следова- тельно, не дифференцируема (см. теорему 8). Замечание. Необходимо отметить, что во многих случа- ях вместо термина дифференцируемость используется тер- мин дифференцируемость по Фреше. Это делается для того, чтобы более четко подчеркнуть отличие дифференцируемости по Гато от дифференцируемости. Приведем два примера, отражающие достаточно важные свойства дифференцируемых числовых функций. Пример 6. Если числовая функция f дифференцируема на отрезке [x, x+y], то в силу формулы (8) и формулы Ньютона Лейбница ?(1) = ?(0) + 1 Z 0 ? 0 (? ) d? (10) легко получаем представление остаточного члена в равенстве (2) в интегральной форме. В самом деле, согласно равенствам (8) и (10) имеем f (x + y) = f (x) + 1 Z 0 h?f (x + ? y), yi d? = = f (x) + h?f (x), yi + 1 Z 0 h?f (x + ? y) ? ?f (x), yi d?. (11) Отсюда в силу равенства (2) получим o(y) = 1 Z 0 h?f (x + ? y) ? ?f (x), yi d?. Пример 7. Для дифференцируемых числовых функций имеет место теорема о среднем f (x + y) = f (x) + h?f (x + ?y), yi, џ2. Дифференцирование 41 где ? некоторое действительное число, удовлетворяющее условию 0 ? ? ? 1. Чтобы убедиться в этом, достаточно вос- пользоваться формулой (8) и формулой конечных приращений ?(1) = ?(0) + ? 0 (?), в которой 0 ? ? ? 1. Дифференцирование векторных функций. Дейст- вуя по аналогии с дифференцированием числовых функ- ций, можем ввести понятие дифференцируемости и векторных функций. Векторная функция g : R n ? R m называется дифференци- руемой в точке x ? R n , если найдется такая действительная матрица A размерности m Ч n, что для всех ?x ? R n имеет место равенство g(x + ?x) = g(x) + A?x + R(?x), (12) в котором R: R n ? R m векторная функция, удовлетворяю- щая условию lim |?x|?0 |R(?x)| |?x| = 0. Матрица A называется производной или матрицей Якоби отображения g. Как и в случае производной отображения чи- словой функции обозначать матрицу Якоби будем либо g 0 (x) , либо ?g(x). Функция g : R n ? R m называется дифференцируемой на множестве Q ? R n , если она дифференцируема во всех точках Q . Если же функция g дифференцируема во всем простран- стве R n , то будем говорить просто, что функция g дифферен- цируема. Действуя по аналогии с формулами (1) и (2), перепишем равенство (12) в следующем виде: g(x + ?x) = g(x) + g 0 (x)?x + o(?x). (13) Равенство (13) означает, что векторная функция g, дифферен- цируемая в точке x, допускает в этой точке линейную аппрок- симацию. При этом, как легко видеть, для дифференцируемой функции g(x) = (g 1 (x), . . . , g m (x)) 42 Гл. 1. Основы многомерного анализа элементы матрицы Якоби определяются равенством g 0i j (x) = ?g i (x) ?x j , i = 1, . . . , m, j = 1, . . . , n. Приведем два примера, иллюстрирующие свойства диф- ференцируемых векторных функций. Пример 8. Пусть g : R n ? R m функция, дифференци- руемая в точке x, и пусть h: R m ? R s функция, дифферен- цируемая в точке g(x). Тогда, как легко видеть, справедли- во следующее цепное правило дифференцирования сложных функций: [h(g(x))] 0 = h 0 (g(x))g 0 (x). Пример 9. Теорема о среднем для векторных функций, вообще говоря, неверна: в общем случае не существует такого действительного числа ?, удовлетворяющего условию 0 ? ? ? 1 , что g(x + y) = g(x) + g 0 (x + ?y)y для некоторой дифференцируемой на отрезке [x, x+y] вектор- ной функции g : R n ? R m . При этом, однако, для дифферен- цируемой на отрезке [x, x + y] функции g : R n ? R m справед- лива следующая формула, аналогичная формуле (11): g(x + y) = g(x) + 1 Z 0 g 0 (x + ? y)y d? = = g(x) + g 0 (x)y + 1 Z 0 (g 0 (x + ? y) ? g 0 (x))y d?. Более того, несложно заметить, что найдутся такие действи- тельные числа ? 1 , . . . ? m , для которых выполнено равенство g i (x + y) = g i (x) + n X j=1 g 0i j (x + ? i y)y j , i = 1, . . . , m. (14) При этом именно равенство (14), очевидно, представляет собой аналог теоремы о среднем для дифференцируемых векторных функций. џ2. Дифференцирование 43 Условие Липшица. Предположим, что на некотором множестве M ? R n определена векторная функция g : M ? R n . Говорят, что функция g удовлетворяет на множестве M условию Липшица, если найдется такое положительное число L , что для всех x, y ? M выполенено неравенство |g(x) ? g(y)| ? L|x ? y|. (15) Легко видеть, что каждая функция, удовлетворяющая на множестве M условию Липшица, непрерывна на этом множе- стве. Обратное, конечно, неверно. Вместе с тем, если функция g дифференцируема на множестве M и для всех x ? M вы- полнено неравенство Ї Ї Ї Ї ?g i ?x j Ї Ї Ї Ї < K, i, j = 1, . . . , n, (16) где K некоторое положительное число, то функция g удо- влетворяет на множестве M условию Липшица. Последнее утверждение легко доказать, если использо- вать понятие нормы матрицы. Напомним, что неотрицатель- ное число ? называется нормой матрицы A типа (n Ч n), если ? наименьшее число, для которого еще выполняется условие |Ax| ? ?|x|, где x произвольный вектор в пространстве R n . Норма мат- рицы A обычно обозначается через kAk. При этом, как легко проверить, если A и B две произвольные (n Ч n) матрицы, то kA + Bk ? kAk + kBk и kA · Bk ? kAk · kBk. Выполнение условия (16), очевидно, влечет за собой нера- венство kg 0 (x)k ? L, (17) справедливое для всех значений x ? M, где L некоторое по- ложительное число, зависящее только от K. Тогда из неравен- ства (17) и формулы (14) непосредственно следует, что каждая дифференцируемая функция, удовлетворяющая на множестве 44 Гл. 1. Основы многомерного анализа M условию (16), удовлетворяет на этом множестве условию Липшица. Условие Липшица (15) играет огромную роль, например, в теории дифференциальных уравнений. В теории же экс- тремальных задач чаще используется условие Липшица для функциональных матриц. Пусть G функциональная (n Ч n) матрица, G(x) = (g i j (x)), где g i j числовые функции, определенные на некотором мно- жестве M ? R n . Говорят, что матрица G удовлетворяет на множестве M условию Липшица, если найдется такое поло- жительное число L, что для всех точек x, y ? M выполнено неравенство kG(x) ? G(y)k ? L|x ? y|. (18) Условие (18) существенным образом используется при формулировке и доказательстве теорем сходимости числен- ных методов математического программирования (см. џ3 гла- вы 2). Некоторые же простейшие утверждения, связанные с дифференцируемостью функциональных матриц и условием (18), приведены ниже в качестве упражнений 4 и 5. Упражнения. (1) Докажите равенство (5) используя координатную форму записи и представление (4). (2) Докажите, что при x 6= 0 функция f (x) = |x| дифференцируема и ?f (x) = x |x| . Более того, докажите, что при x = 0 данная функция недифференцируема. (3) Докажите, что из непрерывности по x производной Гато следует дифференцируемость (если угодно, дифференци- руемость по Фреше). (4) Пусть G(x) = (g i j (x)) џ3. Дважды дифференцируемые функции 45 некоторая функциональная матрица и пусть все функ- ции g i j определены и непрерывно дифференцируемы. По- кажите, что если все частные производные функций g i j ограничены, то матрица G удовлетворяет условию Лип- шица. Указание: Используйте теорему о среднем (см. примеры 7 и 9). (5) Пусть g : R n ? R m дифференцируемая функция и пусть функциональная матрица g 0 удовлетворяет условию Лип- шица на отрезке [x, x + y], т.е. kg 0 (u) ? g 0 (v)k ? L|x ? y| для всех значений u, v ? [x, x + y]. Покажите, что в этом случае |g(x + y) ? g(x) ? g 0 (x)y| ? L|y| 2 . Указание: Используйте пример 9. џ3. Дважды дифференцируемые функции В џ3 изучаются основные свойства дважды дифференци- руемых числовых функций и вторых производных многомер- ных отображений. Данная производная оказывается функци- ональной матрицей, называемой матрицей Гессе. Роль матриц Гессе в теории экстремальных задач трудно переоценить, по- скольку они часто используется при доказательстве теорем су- ществования и выводе достаточных условий минимума. Кро- ме того, матрицы Гессе нашли широкое применение и при конструировании различных численных методов минимиза- ции (см. џ3 главы 2). Вторые производные и дифференцируемость. Чи- словая функция f : R n ? R называется дважды дифференци- руемой в точке x ? R n , если она дифференцируема в этой точке вместе со своими частными производными ?f ?x i , i = 1, . . . , n. (1) Из данного определения непосредственно следует, что ес- ли функция f дважды дифференцируема в точке x ? R n , то 46 Гл. 1. Основы многомерного анализа частные производные (1) определены в некоторой окрестно- сти E точки x и непрерывны в самой точке x (см. теорему 8). Более того, в точке x определены также и вторые частные производные ? 2 f ?x i ?x j , i, j = 1, . . . , n этой функции. И, наконец, имеет место следующая 1 Теорема 9 (Юнг). Если числовая функция f : R n ? R дважды дифференцируема в точке x ? R n , то ? 2 f (x) ?x i ?x j = ? 2 f (x) ?x j ?x i для всех i 6= j. Доказательство. Исключительно для простоты обозна- чений докажем теорему 9 для случая функции двух перемен- ных (см., например, [5]). Положим ? 2 f = f (a 1 + h, a 2 + h) ? f (a 1 + h, a 2 ) ? f (a 1 , a 2 + h) + f (a 1 , a 2 ) и ?(x) = f (x, a 2 + h) ? f (x, a 2 ). Тогда имеем ? 2 f = ?(a 1 + h) ? ?(a 1 ). Отсюда согласно теореме Лагранжа о среднем следует, что ? 2 f = ? 0 (a 1 + ?h)h = = µ ?f (a 1 + ?h, a 2 + h) ?x 1 ? ?f (a 1 + ?h, a 2 ) ?x 1 ¶ h, где 0 ? ? ? 1. Поскольку функция ?f ?x 1 дифференцируема в точке (a 1 , a 2 ) , имеем ?f (a 1 + ?h, a 2 + h) ?x 1 ? ?f (a 1 , a 2 ) ?x 1 = 1 Вообще говоря, думается, что данную теорему все-таки уместно на- зывать теоремой Янга (см. [28]). џ3. Дважды дифференцируемые функции 47 = ? 2 f (a 1 , a 2 ) ?x 1 ?x 1 ?h + ? 2 f (a 1 , a 2 ) ?x 2 ?x 1 h + o(h) и ?f (a 1 + ?h, a 2 ) ?x 1 ? ?f (a 1 , a 2 ) ?x 1 = ? 2 f (a 1 , a 2 ) ?x 1 ?x 1 ?h + o(h). Поэтому ? 2 f = ? 2 f (a 1 , a 2 ) ?x 2 ?x 1 h 2 + o(h 2 ). (2) Теперь положим ?(y) = f (a 1 + h, y) ? f (a 1 , y). Тогда ? 2 f = ?(a 2 + h) ? ?(a 2 ). Следовательно, действуя как и при выводе соотношения (2), получим ? 2 f = ? 2 f (a 1 , a 2 ) ?x 1 ?x 2 h 2 + o(h 2 ) или, что эквивалентно, ? 2 f (a 1 , a 2 ) ?x 2 ?x 1 = ? 2 f (a 1 , a 2 ) ?x 1 ?x 2 . ¤ Матрица H = (h i j ), где h i j = ? 2 f ?x j ?x i , i, j = 1, . . . , n, называется матрицей вторых производных или матрицей Гессе и часто обозначается через f 00 (x) или ? 2 f (x) . Из ска- занного выше следует, что для дважды дифференцируемых функций матрица H определена однозначно, причем в силу теоремы 9 H симметрическая матрица. 48 Гл. 1. Основы многомерного анализа Формула Тейлора с остаточным членом в форме Пеано. Следующий пример дополняет теорему 9 и устанав- ливает второе важнейшее свойство дважды дифференцируе- мых числовых функций. Пример 10. Рассмотрим скалярную функцию ?(? ) = f (x + ? y), где 0 ? ? ? 1. Пусть числовая функция f дважды дифферен- цируема на некотором отрезке [x, x + y]. Тогда, действуя как и при доказательстве дифференцируемости функции ? (см. џ3, (7)), несложно показать, что эта функция дважды дифферен- цируема на отрезке [0, 1], причем ? 00 (? ) = hy, ? 2 f (x + ? y)yi. Воспользовавшись формулой Тейлора с остаточным чле- ном в форме Лагранжа, для функции ? запишем ?(1) = ?(0) + ? 0 (0) + 1 2 ? 00 (?), где 0 ? ? ? 1. Тогда, как легко видеть, найдется такое дей- ствительное число ?, удовлетворяющее условию 0 ? ? ? 1, что f (x + y) = f (x) + h?f (x), yi + 1 2 h? 2 f (x + ?y)y, yi. Последнее равенство принято называть формулой Тейлора для дважды дифференцируемых числовых функций с остаточ- ным членом в форме Лагранжа. В дальнейшем для нас гораздо большее значение будет иметь формула Тейлора для дважды дифференцируемых чи- словых функций с остаточным членом в форме Пеано. Теорема 10 (формула Тейлора с остаточным членом в форме Пеано). Если числовая функция f : R n ? R дважды дифференцируема в точке x ? R n , то для всех y ? R n имеет место равенство f (x + y) = f (x) + h?f (x), yi + 1 2 h? 2 f (x)y, yi + o(y 2 ). (3) џ3. Дважды дифференцируемые функции 49 Доказательство. Следуя [5], докажем теорему 10 в обо- значениях, позволяющих переписать равентсво (3) в виде f (Ї x) = f (Їa)+h?f (Їa), Ї x?Їai+ 1 2 h? 2 f (Їa)(Ї x?Їa), Ї x?Їai+o(|Ї x?Їa| 2 ). В последних обозначениях положим R(Ї x) = f (Ї x) ? (f (Їa) + h?f (Їa), Ї x ? Їai + 1 2 h? 2 f (Їa)(Ї x ? Їa), Ї x ? Їai). Тогда R(Ї x) = R(Ї x) ? R(Їa) = R(Їa + ?x) ? R(Їa), где ?x = Їx ? Їa. Более того, R(Їa + ?x) ? R(Їa) = D 1 + . . . + D n , где для всех i = 1, . . . , n D i = R(a 1 + ?x 1 , . . . , a i + ?x i , a i+1 , . . . , a n )? ?R(a 1 + ?x 1 , . . . , a i?1 + ?x i?1 , a i , . . . , a n ) = = g(a i + ?x i ) ? g(a i ). Поскольку функция f дважды дифференцируема в точке a , она также дифференцируема и в некоторой окрестности E этой точки. Поэтому функция R дифференцируема в E. Сле- довательно, согласно теореме Лагранжа о среднем D i = ?g(a i + ? i ?x i ) ?x i ?x i , где 0 ? ? i ? 1 . Поэтому D i = ?R(a + ? i ) ?x i ?x i , где ? i = (?x 1 , . . . , ?x i?1 , ? i ?x i , 0, . . . , 0). Отсюда окончательно получаем, что R(Ї x) = ?R(Їa + ? 1 ) ?x i ?x 1 + . . . + ?R(Їa + ? n ) ?x i ?x n . (4) Заметим теперь, что для всех i = 1, . . . , n точка a + ? i содержится в множестве E. Поэтому ?R(Їa + ? i ) ?x i = o(|Ї x ? Їa|). 50 Гл. 1. Основы многомерного анализа Отсюда в силу равенства (4) немедленно следует, что R(Ї x) = o(|Ї x ? Їa| 2 ). ¤ Таким образом, если функция f дважды дифференцируе- ма в точке x ? R n , то в этой точке она допускает квадратич- ную аппроксимацию второго порядка, т.е. для квадратичной формы F (?x) = f (x) + h?f (x), ?xi + 1 2 h? 2 f (x)?x, ?xi выполнено неравенство |f (x + ?x) ? F (?x)| = o(?x 2 ). Упражнения. (1) Докажите теорему 9 в общем случае. (2) Функция f : R n ? R называется k раз дифференцируемой в точке x ? R n , если она k?1 раз дифференцируема в этой точке вместе со своими частными производными (k ? 1)- порядка. Сформулируйте и докажите для такой функции теоремы 9 и 10. (3) Пусть A некоторая симметрическая (n Ч n)-матрица и пусть b некоторый вектор в пространстве R n . Рассмот- рим функцию f (x) = hAx, xi/2 ? hb, xi. Покажите, что данная функция дважды дифференциру- ема и ? 2 f (x) ? A. (4) Покажите, что при x 6= 0 функция f (x) = |x| дважды дифференцируема и ? 2 f (x) = I|x| ?1 ? xx T |x| ?3 , где T означает транспонирование и I единичная матри- ца. џ4. Экстремальные задачи в анализе 51 џ4. Экстремальные задачи в анализе Экстремальные задачи в анализе это задачи, связан- ные с отысканием минимумов и максимумов гладких число- вых функций. Как и в случае числовых функций скалярного переменного, в случае гладких числовых функций векторного переменного и необходимые, и достаточные условия экстрему- ма связаны с дифференцированием (по крайней мере в клас- сическом анализе). Более того, в обоих случаях как необходи- мые, так и достаточные условия, вообще говоря, носят локаль- ный характер. Поэтому для получения условий глобального экстремума приходится накладывать на исследуемую функ- цию некоторые дополнительные условия, например, условие выпуклости. Необходимое и достаточное условия минимума. Во избежание возможных разночтений, прежде всего, приве- дем следующее определение минимума и максимума числовой функции. Пусть f : R n ? R некоторая числовая функция. Точка x ? ? R n называется точкой минимума (или точкой локального минимума), если для всех x из некоторой окрестности E точки x ? выполнено неравенство f (x ? ) ? f (x). Аналогичным образом, точка x ? 1 ? R n называется точкой мак- симума (или точкой локального максимума), если для всех x из некоторой окрестности E 1 точки x ? 1 выполнено неравенство f (x ? 1 ) ? f (x). Легко видеть, что если x ? точка минимума функции f, то эта точка является точкой максимума функции ?f. Поэтому везде в дальнейшем, если, конечно, особо не будет оговорено противное, условия экстремума для функции f будут отожде- ствляться с условиями минимума функции f. Для гладких числовых функций необходимое условие ми- нимума дает следующая классическая 52 Гл. 1. Основы многомерного анализа Теорема 11 (Ферма). Пусть x ? точка минимума чи- словой функции f. Предположим, что функция f дифферен- цируема в точке x ? . Тогда ?f (x ? ) = 0. Доказательство. Предположим, что ?f (x ? ) 6= 0. (1) Так как x ? точка минимума функции f, для всех x из неко- торой окрестности E точки x выполнено неравенство f (x ? ) ? f (x). (2) Пусть ? некоторое действительное число. Тогда, поскольку функция f дифференцируема в точке x ? , то f (x ? + y) = f (x ? ) + h?f (x ? ), yi + o(y) или, что при y = ???f(x ? ) эквивалентно, f (x ? ? ? ?f (x ? )) = f (x ? ) ? ? |? 2 f (x ? )| ? o(? ). (3) Поэтому из соотношений (1) и (3) следует, что при всех доста- точно малых положительных ? имеет место неравенство f (x ? ? ? ?f (x ? )) < f (x ? ), противоречащее неравенству (2). ¤ Приведенное доказательство, конечно, не единственное. Основное его достоинство состоит в том, что оно иллюстри- рует общий принцип вывода необходимых условий в экстре- мальных задачах. Кроме того, данное доказательство весьма поучительно: если в некоторой точке x ? R n условие мини- мума не выполняется, оно (доказательство) показывает, что точку с меньшим значением функции f следует, вообще гово- ря, искать в направлении y = ??f (x). Несколько усиливая требования относительно гладкости функции f, имеем следующее достаточное условие существо- вания минимума. џ4. Экстремальные задачи в анализе 53 Теорема 12. Пусть в точке x ? для числовой функции f выполнены условия теоремы 11 и пусть в точке x ? функция f дважды дифференцируема. Тогда, если матрица ? 2 f (x ? ) по- ложительно определена, то x ? точка локального миниму- ма. Доказательство. Пусть y произвольный вектор еди- ничной длины. Поскольку в точке x ? для функции f выпол- нены условия теоремы 11, то в силу теоремы 10 имеем f (x ? + ? y) = f (x ? ) + ? 2 2 h? 2 f (x ? )y, yi + o(? 2 ), (4) где ? некоторое действительное число. С другой стороны, ес- ли l и L соответственно наименьшее и наибольшее собствен- ные числа матрицы ? 2 f (x ? ) , то, как известно, справедливы неравенства lhy, yi ? h? 2 f (x ? )y, yi ? Lhy, yi. (5) Поэтому в силу условия |y| = 1 из соотношений (4) и (5) сле- дует, что f (x ? + ? y) ? f (x ? ) + ? 2 l 2 + o(? 2 ). (6) Заметим теперь, что найдется такое достаточно малое по- ложительное число ? 0 , что для всех значений ?? 0 ? ? ? ? 0 выполнено неравенство ? 2 l 2 ? o(? 2 ). Но матрица ? 2 f (x ? ) положительно определена. Поэтому из неравенства (6) следует, что f (x ? + ? y) ? f (x ? ). Но выбор направления y выше не играл никакой роли, т.е. x ? точка минимума. ¤ Если в точке x ? выполняются условия теоремы 11, но не выполняются условия теоремы 12, то в этой точке, конечно, может и не быть экстремума. При этом для числовых функ- ций скалярного переменного исследование точки x ? на пред- мет экстремума может быть продолжено с использованием 54 Гл. 1. Основы многомерного анализа известной техники высших производных. Для многомерного случае такое исследование в принципе возможно. Однако, оно чрезвычайно трудоемко ввиду сложности используемого здесь математического аппарата (см. упражнения 46). Точку x ? , удовлетворяющую условиям теоремы 12, приня- то называть невырожденной точкой минимума. Если в неко- торой окрестности точки x ? локального минимума нет других точек локального минимума, то эту точку называют локаль- но единственной точкой минимума. Оказывается, что поня- тия невырожденной точки минимума и локально единственной точки минимума тесно связаны друг с другом. Теорема 13. Невырожденная точка минимума x ? два- жды дифференцируемой числовой функции f : R n ? R локаль- но единственна. Доказательство. Прежде всего, заметим, что по опре- делению дважды дифференцируемой функции для всех зна- чений x ? R n имеет место равенство ?f (x) = ?f (x ? ) + ? 2 f (x ? )(x ? x ? ) + o(x ? x ? ). Поэтому всякий раз, когда величина |x ? x ? | достаточно мала |?f (x)| = |? 2 f (x ? )(x ? x ? )| + o(|x ? x ? |) ? ? l|(x ? x ? )| + o(|x ? x ? |) > 0, где l наименьшее собственное число матрицы ? 2 f (x ? ) и x 6= x ? . Отсюда следует, что в некоторой окрестности M точки x ? нет стационарных точек функции f, отличных от x ? . Значит, в окрестности M нет точек минимума функции f, отличных от x ? ¤ Глобальный минимум. Пусть как и ранее f : R n ? R некоторая числовая функция. Точка x ? ? R n называется точкой глобального минимума функции f, если для всех x ? R n выполнено неравенство f (x ? ) ? f (x). џ4. Экстремальные задачи в анализе 55 6 - ````` ````` ```` s f (x) s f (y) s ?f (x) + (1 ? ?)f (y) x ?x + (1 ? ?)y y Рис. 2 Аналогичным образом, точка x ? 1 ? R n называется точкой гло- бального максимума функции f, если для всех x ? R n выпол- нено неравенство f (x ? 1 ) ? f (x). Ясно, что точка глобального минимума (максимума) яв- ляется точкой локального минимума (максимума); обратное, конечно, неверно. При этом в отличие от локального экстре- мума исследование функций на глобальный экстремум обычно связывают с понятием выпуклости. Числовая функция f : R n ? R называется выпуклой, если для всех x, y ? R n и любого действительного числа 0 ? ? ? 1 имеет место неравенство f (?x + (1 ? ?)y) ? ?f (x) + (1 ? ?)f (y). (7) Геометрически сказанное означает, что график функции f ска- лярного переменного x на отрезке [x, y] лежит ниже хорды, соединяющей точки (x, f(x)) и (y, f(y)) (см. рис. 2). В приведенном выше определении выпуклой функции фи- гурируют две точки x, y ? R n и их выпуклые комбинации 56 Гл. 1. Основы многомерного анализа ?f (x) + (1 ? ?)f (y) , удовлетворяющие неравенству (7). Анало- гичное неравенство, известное как неравенство Иенсена, имеет место для любого конечного числа точек и их выпуклых ком- бинаций. Неравенство Иенсена обычно формулируют в виде следующего предложения, приводимого здесь без доказатель- ства. 2 Предложение 1. Пусть f : R n ? R некоторая вы- пуклая функция. Тогда для всех x 1 , . . . , x k ? R n и неотрица- тельных действительных чисел ? 1 , . . . , ? k , удовлетворяющих условию ? 1 + . . . + ? k = 1, справдливо неравенство f (? 1 x 1 + . . . + ? k x k ) ? ? 1 f (x 1 ) + . . . + ? k f (x k ). При работе с выпуклыми функциями обычно используют не определение (7), а некоторые другие соотношения, эквива- лентные (7). Для гладких функций такие соотношения доста- точно просты и вытекают из следующего тривиального пред- ложения. Предложение 2. Пусть f : R ? R дифференцируемая функция. Тогда, если функция f выпукла, то для всех значе- ний x 1 ? x 2 f 0 (x 1 ) ? f 0 (x 2 ) и обратно. Первое из важнейших свойств выпуклых функций уста- навливает следующее Предложение 3. Пусть f : R n ? R дифференцируе- мая функция. Тогда, если функция f выпукла, то для всех значений x, y ? R n f (x + y) ? f (x) + h?f (x), yi и обратно. 2 Относительно доказательства предложений 14 и других важных свойств выпуклых функций см., например, [9, 14, 20]. џ4. Экстремальные задачи в анализе 57 Второе из важнейших свойств выпуклых функций уста- навливает следующее Предложение 4. Пусть f : R n ? R дважды дифферен- цируемая функция. Тогда, если функция f выпукла, то для всех x ? R n матрица ? 2 f (x) неотрицательно определена и обратно. Замечание. В подавляющем большинстве практических ситуаций проверку выпуклости дважды дифференцируемых функций осуществляют с помощью предложения 4. Понятие выпуклости играет огромную роль в теории экс- тремальных задач. В самом деле, теорема 11 гарантирует су- ществование лишь стационарных точек, т.е. точек, в которых ?f (x) = 0 ; такая точка, как известно, может быть не только точкой экстремума, но и точкой перегиба или, скажем, седло- вой точкой. С другой стороны, теорема 12 гарантирует суще- ствование лишь локального минимума. Для выпуклых функ- ций, однако, все эти случаи невозможны, поскольку справед- лива следующая важнейшая Теорема 14. Пусть f : R n ? R выпуклая функция, дифференцируемая в некоторой точке x ? ? R n , и пусть ?f (x ? ) = 0. (8) Тогда x ? точка глобального минимума. Доказательство. Поскольку f выпуклая функция, в силу предложения 3 для всех x ? R n имеет место неравенство f (x) ? f (x ? ) + h?f (x ? ), x ? x ? i. Но в силу условия (8) отсюда следует, что f (x) ? f (x ? ) для всех x ? R n , т.е. x ? точка глобального минимума. ¤ Замечание. Теорема 14 дает необходимое и достаточное условие глобального минимума выпуклой функции. Вместе с тем, следует иметь ввиду, что данная теорема не гарантирует единственность такого минимума. |