назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [ 10 ] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


10

Доказательство проводится по индукции по числу точек к. При к = 2 утверждение теоремы совпадает с определением выпуклого множества. Пусть уже показано, что любая выпуклая комбинация к-\ точек множества X ему принадлежит.

Рассмотрим к точеки выпуклую линейную комби-

нацию X = S/ • Если = 1, то а- = О при 1</<А:-1иа = х*еХ.

Пустьа]<\. Тогда 1 -= Z>О» сгруппируем слагаемые в вы-

ражении для х\ х = (1 - ) Z + л* -

Числа

1 У

/ = 1,.- неотрицательны и их сумма равна 1:

-(1-а,) = 1.

,=1S

Следовательно, выражение х = X--х представляет собой выпук-

/=11 -

лую линейную комбинацию точекмножества X. По

предположению индукции х е X, но тогда точка (1 - + ах* является выпуклой линейной комбинацией двух точек из X и, следовательно, X 6 X.

Рис. 2.5Рис. 2.6

Определение 2.5. Пусть М - множество точек из . Выпуклой оболочкой С(М) множества М называется множество всех выпуклых

линейных комбинаций точек из М.



в качестве примеров рассмотрим множество и : состоит из трех различных точек [А,В,С) плоскости (рис. 2.5); М2 есть окружность (рис. 2.6).

Нетрудно видеть, что выпуклой оболочкой множества является треугольник ABC (вместе с внутренними точками).

Действительно, пусть D - произвольная точка треугольника. Проведем через D и С прямую и пусть Е - пересечение этой прямой и отрезка [АВ] , где точка Е является выпуклой комбинацией точек А и

В: £ = ау4 + (1-а)5.Точка D принадлежит отрезку [ЕС] и поэтому

представлена в виде D = J3E-\-{\-J3)C 0< J3<\, отсюда

D = j3(aA + (\-а)В + (1 - J3)C . Правая часть этого выражения является

выпуклой линейной комбинацией точек А, В и С, поскольку а>8 + (1 - а)у5 + (1 - >8) = 1. Следовательно, любая точка треугольника

ABC принадлежит выпуклой оболочке множества М.

Выпуклой оболочкой множества М2 является круг, границей которого служит окружность М2. Действительно, всякая точка D внутри круга может быть представлена как выпуклая линейная комбинация точек А и В, лежащих на концах диаметра, проведенного через точку D.

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

Теорема 2.7. Выпуклая оболочка С[М) множества М совпадает с

наименьшим выпуклым множеством, содержащим М.

Доказательство следует из того факта, что с одной стороны выпуклая оболочка С(М) является выпуклым множеством, а с другой- если X

выпуклое множество, содержащее М, то оно содержит все выпуклые

линейные комбинации точек из М, следовательно, C(M)qX. Ранее

было дано неформальное определение крайней угловой точки. Проведем еще одно эквивалентное определение.

Определение 2.6. Точка х выпуклого множества X называется край-

11 1 2

ней, если ее нельзя представить в виде: х = -х +~х , где



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

Определение 2.7. Множество называется компактным, если оно ограничено и замкнуто.

Роль крайних точек выпуклого компактного множества определяет следующая теорема.

Теорема 2,8. Любое компактное выпуклое множество в является выпуклой оболочкой своих крайних точек.

Утверждение теоремы означает, что любая точка х g X, где X - выпуклый компакт, представлено в виде выпуклой комбинации конечного числа крайних точек из X. Покажем, что любая точка X выпуклого компакта X является выпуклой линейной комбинацией некоторых его граничных точек.

Пусть S любой вектор 5 g Л" (здесь К"" п -мерное евклидово пространство). Рассмотрим прямую /(х) = х + , -оо < Я < оо, проходящую

через точку х (при Я = О).

Так как X - ограниченное выпуклое множество, то прямая 1{х) пересекает его границу в двух точках х и (может быть, совпадающих).

и, следовательно, явля-

Тогдаточка хХ принадлежит отрезку

ется выпуклой линейной комбинацией граничных точек х и х множествах .

Остается показать, что всякая граничная точка х является выпуклой линейной комбинацией ограниченного числа крайних точек X. Для того чтобы это доказать, введем понятие размерности выпуклого множества. Из курса линейной алгебры известно, что линейным многообразием QR" называется множество вида Q = x -L, где L - некоторое подпространство. При этом, если Q может быть представлено так же как Q = x + L, то L = L, т.е. линейному многообразию Q соответствует только одно подпространство L, сдвигом которого получается Q = x -\-L, Размерностью линейного многообразия называется размерность подпространства L. На рис. 2.7 линейное многообразие Q получено параллельным сдвигом подпространства L: произвольная точка xeQ представлена в виде х = х° + /, где /gi . Точка

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [ 10 ] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]