<<
>>

11.5. ЛИНЕЙНЫЕ КОМБИНАЦИИ ВЕКТОРОВ. ВЫПУКЛЫЕ МНОЖЕСТВА

Рассмотрим в двумерном декартовом пространстве два единичных вектора єі= (1, 0) и 82= (Of 1), которые представлены точками Аг и лежащими на координатных осях на плоскости Охгх2. По правилам векторной алгебры любой вектор х = (хг, х2) может быть выражен так:

X === ?282,

307

20*

где х1 и х2— скаляры, являющиеся оба компонентами х и скалярными множителями е1 и е2.

В этом случае говорят, что вектор х является линейной комбинацией векторов гг и е2. Любой вектор х является такой линейной комбинацией. Говорят, что векторы 8Х и е2 образуют базис декартова двумерного* пространства62— базис в том смысле, что двух векторов гх и е2 достаточно^ чтобы воспроизвести всю систему векторов двумерного пространства. С геометрической точки зрения то, что х является линейной комбинацией базиса ег и е2, является просто выражением следующего факта. Векторы базиса et и е2 представлены ОАі и OA 2, образующими координатные оси и единицы измерения в двумерном пространстве. Тогда любой вектор ОР является суммой двух векторов, один из которых получается умножением ОАі на а другой—умножением ОА2 на х2. Другими словами, к точке Р можно прийти, если отсчитать хг единиц в направлении ОА19 а затем х2 единиц в направлении ОА2. Все, что мы сказали, легко распространяется на декартово трехмерное пространство.

Вообще декартово и-мерное пространство охватывается п единичными векторами ех, е2, ..., гп9 которые образуют базис пространства. Это значит, что любой вектор х = (ж1, х2, ..., хп) являете я линейной комбинацией базиса:

п

X = 2 Хгег = Х1е1 + #2Є2 + . . . + хпгп' г= і

Или в развернутом виде:

®i81 = x1(lf 0, ..0) = 0, 0), х2г2=х2{0, 1, ..., 0) = (0, х2, 0),

хпгп = хп(°> • • 1) = (0, 0,..., хп). И, такйм образом, получаем

п

2 хггг=(xi> о» . - -» о)+(О, Х29 ...» 0) ...

г—і

...-(- (0, 0, ..., #п) = (х19 х29 ..

• > %п) = х.

Рассмотрим теперь в декартовом тг-мерном пространстве два вектора:

v __/г<1> ~и> и Y(2) — fr(2) т<2) <Г(2Л

А ^^ , Л/2 , • • • , Лц ^ JO. Л » у • • • « J.

Линейной комбинацией векторов х(1) и х<2) является вектор

Я1хС1) + Я2Х(2) для любых Х±> Х2.

Элемент г-й (или г-я координата. — Ред.) линейной комбинации есть + %2xf*. Он получается сложением r-элементов х(1) и х(2), умноженных соответственно на Хх и Х2. Рассмотрим два частных случая линейной комбинации векторов. Положительной линейной комбинацией векторов х(1) и х<2) является вектор

ЯіХ(1) + Х2х™9 где Х19 Х2>0;

выпуклой линейной комбинацией векторов х(1) и х(2) является вектор, для которого сумму скаляров, + 1, можно записать следующим образом:

цх<1> + (1 — и<)х<2>, где 0<[Х<1.

Способ образования этих комбинаций виден на рис. 37. Данные векторы х(0 и х(2> представлены в виде направленных отрезков ОР1 и OP2i определяющих в /г-мерном пространстве плоскость ОРхР2.

На рис. 37 показана только двумерная плоскость (плоскость чертежа). Ее нужно вообразить как гг-мерную плоскость, образованную координатными осями Охгх2 ... хп9 которые не показаны на рисунке (и вообще не могут быть представлены графически). Пусть ОР—выпуклая линейная комбинация |іхФ + (1 —где \i принимает значения от 0 до 1. Легко показать на основании формул аналитической геометрии (см. упражнение 2), что Р лежит на прямой линии, соединяющей Рх и Р29 и делит ее в отношении р,:(1 — |х). Следовательно, когда fx возрастает от 0 до 1, Р движется от Р2 к Рг и ОР передвигается от ОР2 к OPv Рассмотрим

OQ — положительную линейную комбинацию:

+ ^<2) = + К) + (1 - |1) Х(2)},

где

Следовательно, OQ получается умножением ОР на положительное число. Если множитель А,1 + Х2>1, ТО Q лежит на ОР дальше точки Р, как это показано на рис. 37. Если 0<Яг + Х2<1, то в этом случае Q лежит между О и Р. Таким образом, для того чтобы получить"Г0(? при данных К и Х2, надо сначала определить местонахождение ОР при р, = ^/(^ + Я,2), а затем увеличением (или умножением) ОР в отношении : 1 полу

чить OQ.

При различных значениях Х1 и OQ лежит в углу между векторами ОРх и ОР2 и имеет разную длину. Наконец, любая линейная комбинация представляется вектором OR, лежащим где-нибудь в плоскости, образованной ОР± и ОР2г.

Все эти определения и свойства легко распространяются на случай любого числа векторов в га-мерном пространстве.

Определение. Линейной комбинацией данных векторов

x* = (x[k\ хявляется

при любых значениях скаляров Хк. Линейная комбинация является положительной, если все Xk > 0, и выпуклой, если ^>0и, кроме того,

+ + • • • + Кг = 1 *

Геометрически линейная комбинация выражается через точки Рх, Р2, ..., Рт, соответствующие данным векторам гс-мерного пространства. Выпуклая линейная комбинация представляется некоторой точкой Р на фигуре или внутри фигуры (многогранника), определяемойР2,..., Рт на гиперплоскости, натянутой на эти векторы (если т < п). Положительной линейной комбинацией является точка Q, лежащая на прямой линии, проведенной через Q и Р и продолженной за Р (точка Р соответствует некоторой выпуклой линейной комбинации данных векторов.— Ред.). Таким образом, Q лежит на гиперконусе, образуемом ОРх, ОР2, ОРт, или внутри него. Любая линейная комбинация представляется точкой R в подпространстве (самое большее т измерений), определяемом О, Рг, Р2, ..., Рт.

Теперь мы сосредоточим внимание на свойствах множества точек

Pk(k = 1, 2, 3, ...)

/г-мерного пространства. Это точечное множество, обозначаемое нами через S, может содержать конечное число точек; оно, например, может быть составлено из угловых точек геометрического тела, ограниченного плоскостями в трехмерном пространстве. S может быть и бесконечным множеством точек, например если оно содержит все точки на поверхности сферы в трехмерном пространстве. Мы не будем рассматривать тривиальный случай, когда б63 содержит только одну точку. Если установлены координатные оси Охгх2 хп и единицы измерения, любая точка Рк может рассматриваться как вектор, имеющий координаты

X = (s<*>, xf) *№)).

Однако в данном случае это не существенно.

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

Рассмотрим две точки Рг и Р2 множества S, которым соответствуют векторы х*64) и х<65>. Выпуклая линейная комбинация х = jxx^1) + (1 — [х)х<2> представляется некоторой точкой Р, которая лежит на отрезке прямой РгР2 и делит ее в отношении Р2Р : РРХ = |л : (1 — р). Когда [х увеличивается (в пределах 0<|л<1), Р движется непрерывно от Р2 к Рг. Это свойство не зависит от способа измерения пространства или от того, как пространство может быть искривлено. Отношение [х : (1 — р) и «прямизна» линии РгР2 вовсе не необходимы. Однако если |х возрастает от нуля до единицы, то точка Р всегда движется по какому-то пути от Р2 к Рг. Следовательно, точка Р может быть выражена так:

Р^^ + Ц-^Р* (0<ц<1),

и можно сказать, что Р находится «между» Рг и Р2 на некоторой линии в пространстве. Ограниченная таким образом точками Рг и Р2 точечного множества S, сама точка Р может принадлежать, а может и не принадлежать S. Множество S называется выпуклым, если все точки между любыми двумя точками из S также принадлежат S. Выпуклое множество может быть бесконечным, и его характерной чертой, если говорить просто, хотя и не очень точно, является то, что оно «сплошное» и не имеет «входящих углов» («вмятин»). Рассматривая выпуклое множество S, важно отличать его «граничные точки» от «внутренней» части. Экстремальной точкой (extreme point) выпуклого множества S называется такая точка, которая не лежит между какими-либо двумя другими точками S; Р есть экстремальная точка S, если она не может быть выражена как выпуклая линейная комбинация jл/>1+ (1 — каких- либо двух точек Рг и Р2 из множества S. «Границы» множества S образуются именно экстремальными точками1.

В двумерном пространстве все точки четырехугольника (рис. 38, а) и круга (рис. 38, б) образуют выпуклое множество. В первом случае экстремальными точками являются А, В, С и Z), во втором — все точки окружности круга.

В то же время точки площади четырехугольника с вмятиной ABCD (площадь, заштрихованная перекрестными линиями на рис. 38,в) не образуют выпуклое множество, так как этому множеству не принадлежат, например, точки между і и С. Рассмотрим теперь любое множество S, конечное или бесконечное. Прибавим к нему все точки, лежащие между двумя любыми членами S. В результате этого S «наполнится» в определенной степени, но не полностью, ибо в расширенном таким образом множестве могут быть такие точки, что все другие между ними не будут принадлежать полученному множеству. Этот процесс прибавления к исходному множеству S всех промежуточных точек можно продолжать до тех пор, пока S не дополнится до выпуклого множества, которое будет включать не только первоначальные точки Рк, но и все точки Р, получающиеся как всевозможные выпуклые линейные комбинации точек Pk:

P = K1P1 + b2P*+.--+hPk+--- (Ч>0, ^1 + ^2+ =1),

то есть

X = А,хх(1) + Я2Х(2) + ... + KKXIK) +

Получающееся таким образом расширенное множество называется выпуклой оболочкой («convex hull») первоначального множества.

Пусть выпуклая оболочка К данного точечного множества S содержит все точки, являющиеся выпуклыми линейными комбинациями точек S, а также и сами точки S. В широком смысле К является бесконечным выпуклым множеством всех точек «внутри» конфигурации точек Рг, Р2, ... множества S. Оно является «сплошным», не имеющим «входящих углов» (вмятин) множеством, которое можно построить из множества S. Экстремальным множеством Е (extremal) выпуклой оболочки К является множество экстремальных точек К. Это экстремальное множество является «границами» К.

Следовательно, из множества S получается другое множество Е, являющееся экстремальным множеством выпуклой оболочки множества S. Между S и Е существует тесная связь. Ясно, что каждая точка Е должна также принадлежать S. Рассмотрим, например, точку Р множества Е. Если точка Р не входит в S, то она должна принадлежать выпуклой оболочке множества S, являющейся линейной комбинацией точек S.

Однако это исключено, ибо это противоречит определению экстремальной точки. Следовательно, точка Р должна входить в S. Также очевидно, что Е не должно совпадать с S: все точки множества S не обязательно принадлежат Е, так как невыпуклость множества S делает возможным нахождение его точек внутри, а не на «границе» выпуклой оболочки.

Все вышеуказанное для случая двумерного пространства иллюстрируется на рис. 38. Заштрихованные части фигур — это выпуклые оболочки. Множество S четырех точек А, В, С и D на рис. 38, а является одновременно и экстремальным множеством Е. Аналогично множество S всех точек на окружности круга на рис. 38, б также рвляется экстремальным множеством Е. В данном случае это бесконечное множество. Однако на рис. 38, в первоначальное множество S четырех точек А, В, С лВ образует выпуклую оболочку, которая может быть образована и при помощи только трех точек, а оставшаяся точка будет лежать внутри оболочки. В данном случае экстремальное множество Е содержит только три точки А, В и С.

Таким образом, мы отправляемся от данного множества S, включаем все выпуклые линейные комбинации точек xS, получаем выпуклую оболочку К, а затем находим экстремальное множество Е. Это позволяет устранить из S все не «необходимые» члены, то есть такие точки, которые являются выпуклыми линейными комбинациями других точек множества S. Если с самого начала S не содержит таких точек, то оно само является экстремальным множеством (extremal) собственной выпуклой оболочки. Однако обычно S содержит такие точки, и они устраняются при приведении S к экстремальному множеству Е выпуклой оболочки множества S.

Иногда удобнее использовать не точки Pk множества S, а линии OPk, соединяющие эти точки с началом координат. В данном случае выпуклую оболочку множества S можно рассматривать как «сплошной» пучок линий ОР, где Р является выпуклой линейной комбинацией точек Pk. Эта выпуклая оболочка называется выпуклым многогранным конусом, полученным из данного множества S. При соединении точек экстремального множества Е с О получается множество линий, которые образуют «границы» конуса66.

Задачи и упражнения 1.

В двумерном пространстве даны два единичных вектора: е1 = ОЛ1, идущий вдоль Охъ и 82 = 0Л2, идущий вдоль Ох2. Показать, что уравнение прямой линии АХА2 имеет вид х1+х2 = 1. Вывести, что точка х=х1е1-\-х2г2, если она может быть выражена как х=р,е1-(-(1—р,)г2 для любого \i (при 0Развивая результат предыдущего упражнения, показать, что точка Р, представляемая как конец вектора х = р,х(1)-|-(1—р) х<2), лежит на прямой линии между Рх и Р2. На основе координат этих точек проверить, что Р2Р: РРг=\і: (1 — р.). Истолкуйте P как «среднюю взвешенную» из Рх и Р2. 3.

Дано множество S конечного числа точек Р& (? = 1,2,3, Показать, что если взять всевозможные положительные линейные комбинации точек Pfc, то получится выпуклый многогранный конус, а если взять выпуклые линейные комбинации этих точек, то получится выпуклая оболочка. 4.

Множество S в трехмерном пространстве состоит из четырех точек, которые могут иметь или не иметь входящий угол (вмятину). Что будет выпуклой оболочкой этого множества и экстремальным множеством? Если S является множеством всех точек на поверхности сферы, то что будет его выпуклой оболочкой и экстремальным множеством?

<< | >>
Источник: Р. Аллен. МАТЕМАТИЧЕСКАЯ ЭКОНОМИЯ. 1963

Еще по теме 11.5. ЛИНЕЙНЫЕ КОМБИНАЦИИ ВЕКТОРОВ. ВЫПУКЛЫЕ МНОЖЕСТВА:

  1. 11.5. ЛИНЕЙНЫЕ КОМБИНАЦИИ ВЕКТОРОВ. ВЫПУКЛЫЕ МНОЖЕСТВА
  2. 12.6. УМНОЖЕНИЕ ВЕКТОРОВ И МАТРИЦ
  3. 13.1. ЛИНЕЙНАЯ КОМБИНАЦИЯ И ЛИНЕЙНАЯ ЗАВИСИМОСТЬ
  4. 13.2. СИСТЕМА ЛИНЕЙНЫХ УРАВНЕНИЙ И ЕЕ РЕШЕНИЕ
  5. 13.3. ЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ
  6. 14.7. ОБЩИЙ СЛУЧАЙ ИГРЫ ДВУХ^УЧАСТНИКОВ НУЛЕВОЙ СУММОЙ
  7. 14.8. РЕШЕНИЯ КОНКРЕТНЫХ ИГР
  8. 14.9. ИЛЛЮСТРИРУЮЩИЕ ПРИМЕРЫ^
  9. 15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  10. 15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ
  11. 15.7. НЕКОТОРЫЕ СВОЙСТВА ВЫПУКЛЫХ МНОЖЕСТВ
  12. 15.8. СИМПЛЕКСНЫЙ МЕТОД
  13. 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  14. 16.5. ПРЕДСТАВЛЕНИЕ ТЕХНОЛОГИЧЕСКИХ ВОЗМОЖНОСТЕЙ
  15. 17.4. ТЕХНОЛОГИЯ ФИРМЫ
  16. 18.6. СПОСОБЫ ПОТРЕБЛЕНИЯ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
  17. ПРИЛОЖЕНИЕ В РЕШЕНИЯ И УКАЗАНИЯ К ЗАДАЧАМ И УПРАЖНЕНИЯМ 1.2
  18. 3.5. Проверка гипотез. Доверительные интервалы и доверительные области
  19. 1. Векторное пространство