Беклемишев - Дополнительные главы линейной алгебры (947281), страница 57
Текст из файла (страница 57)
Решения неоднородной системы линейных уравнений в этом случае изображаются точками, а все множество решений — плоскостью. Решения приведенной однородной снагемы естественно 'изобразить векторами. Тогда все множевтво решевнй вриведвввой 25в гл, ч. системы нвнхввнств и лннвиноа пяогялммияовлнив системы составляет направляющее подпространство той плоскости, которая задается неоднородной системой. Так же мы поступим и с неоднородными системами линейных неравенств — их решения будут изображаться точками в аффинном пространстве.
Этот пункт будет посвящен важному для дальнейшего классу точечных множеств в аффннноь1 пространстве — выпуклым множествам. Допустим, что система линейных неравенств (1) совместна и хы „х,— ее решения. Если коэффициенты а„..., а, удовлетворяют условиям а,)0, ..., а,)0, а,+...+а,=1, то линейная комбинация х = К1х| +... + я,х, (3) также является решением системы (1).
Такие линейные комбинации столбцов, коэффициенты которых удовлетворяют услови1о (2), называются выпи лыми кол~бинаииями. Точку Х, координатный столбец которой есть выпуклая комбинация координатных столбцов точек Х„..., Х„называют выциклой комбинацией этих точек. При этом выбор системы координат не играет роли. Разумеется, коэффициенты линейной комбинации ие изменятся при замене базиса, но и начало координат может быть сдвинуто на произвольный вектор, Действительно, из (3) следует х+ р а, (х, +)э) +... + а, (х, +Р). Пусть У вЂ” некоторое множество точек в аффннном пространстве.
Вьи|уклой оболочкой множества Ф называется множество всевозможных выпуклых комбинаций точек из У. П р и м е р ы. !) Покажем, что отрезок Х,Х, есть выпуклая оболочка его концов. Отрезок лежит на прямой с параметрическим уравнением х - х, +! (х, — х,), где х, и х,— координатные столбцы концов отрезка. При этом точка со значением параметра ! принадлежит отрезку тогда и только тогда, когда ! ен !О, !1. Поэтому, преобразовав уравнение прямой к виду х=а,х,+а,х„ имеем а, = 1 — 1 ) О, аз = ! » 0 и а, + аз = 1, как и требовалось. 2) Пусть точки Хы Х и Ха не лежат на одной прямой.
Выберем четвертую точку О, не лежащую в двумерной плоскости Зм проходящей через Х„Х, и Х,. 'В трехмерной плоскости, натянутой на точки О, Хм Хм Хз, выберем систему координат о началом О 257 5 Е НЕОДНОРОДНЫЕ СИСТЕМЫ ЛИНЕННЫХ НЕРАВЕНСТВ и базисом ОХ„ОХА, ОХ,. В этой системе координат плоскость Ж имеет уравнение а, + а, + а, = 1. Поэтому пересечение плоскости 8 с положительным октантом рассматриваемой системы координат и есть выпуклая оболочка точек Х„Х„Х,. Таким образом, выпуклая оболочка трех точек, не лежащих на прямой, — треугольник с вершинами в этих точках. 3) Пусть точки Х„Х„Х, лежат на одной прямой, причем Х, лежит между Х, и Х,.
Покажем, что их выпуклая оболочка есть отрезок Х,Х,. Действительно, по нашему предположению существует число а ей !0, 1! такое, что х,=ах, + (1 — а)х,, Пусть У =Лх, + рх, + чх„причем Л, р и ч неотрицательиы и в сумме равны 1. Тогда У=(Л+а1!) х,+(ч+(! — сс) р) х,. Очевидно, что коэффициенты этой комбинации неотрицательны и Л+ ар + ч + (1 — а) р = 1. Этим наше утверждение доказано. Множество точек в аффинном пространстве называется выпуклым, если вместе с любыми двумя своими точками оио содержит отрезок, соединяющий эти точки. Заметим, что пустое множество и множество, состоящее из одной точки, считаются выпуклыми. Нетрудно проверить, что выпуклыми являются: все пространство, полупространство, ограниченное произвольной гиперплоскостью (К., Э 1 гл.
1Х), плоскость любого числа измерений, в частности прямая линия. Круг на обычной евклидовой плоскости— множество выпуклое, а окружность — не выпуклое. Непосредственно из определения вытекает, что выпуклым является пересечение любого (ие обязательно конечного) множества выпуклых множеств. П р едл аж е н и е 1. Выпуклая оболочка любого множества является выпуклым множеством.
Действительно, пусть точки Х! и Я, принадлежат выпуклой оболочке множества л"'. Это значит, что их координатные столбцы представимы в виде выпуклых комбинаций я!=а!х!+...+а,х, ев = рзуг+ ° ° + ()су! координатных столбцов точек, принадлежащих У. Если числа Л н р таковы, что Л ) О, 1! = 0 и Л + р = 1, то Ле!+ Ре! =,Е (Лег!) х!+,~ Я(14!) Ум !=! Ава Гл. ч системы неРАВенстВ и линеиное пРОГРАммиРОВАние причем здесь все коэффициенты неотрицательны и » ! .).,' (~ ~!)+ Х И>)-)!+И=1 ! ! 1=! Таким образом, отрезок с концами Я! и Е, также принадлежит выпуклой оболочке множества д>, и предложение доказано. П р едл о же н и е 2. Если точки Х„..., Х, принадлежат выпуклому множеству Й, то любая их выпуклая комбинация принадлежит этому множесп>ву. Докажем это предложение индукцией по числу точек. Для двух точек утверждение совпадает с определением выпуклого множества (см, пример 1)).
Рассмотрим выпуклую комбинацию Х точек Х„..., Х». Ее координатный столбец х выражается через координатные столбцы этих точек выпуклой комбинацией х=а,х,+...+а„х . Если а» = О, то утверждение прямо сводится к предположению индукции. Если а» =- 1, то все остальные коэффициенты равны нулю, и утверждение тривиально. В общем случае О - а» (! введем числа р>= — А, 1=1...,, я — !. Все они не отрицательны и, кроме того, » — 1 » †! -! 1 %> ! '~ а>= (1 — а,)=1. ! — а» Л ' ! — а» !'= ! ! ! Поэтому, согласно предположению индукции, у = (),х! + ... ...
+()>,х» ! Ева. Но тогда в силу выпуклости Й имеем а»х»+ + (1 — а,) у ен (А', т. е. а,х,+...+а,,х,,+а»х» енй, как нам и требовалось. Из предложения 2 следует, что каждое выпуклое множество 6, содержащее множество Ю, содержит также и его выпуклую оболочку. Отсюда и из предложения ! вытекает П р е д ло же н и е 3. Выпуклая оболочка множества д> есть пересечение всех выпуклых л>ножеств, содержащих д». Множество д> точек в аффинном пространстве назовем ограниченным, если в некоторой системе координат все координаты всех его точек по абсолютной величине ограничены одним и тем же числом. Это равносильно тому, что множество координатных столбцов точек У ограничено в с-норме.
В силу теоремы 1 э 4 гл. 1, мы можем заключить отсюда, что множество в аффинном пространстве ограни- $ Е НЕОДНОРОДНЫЕ СИСТЕМЫ ЛИНЕИНЫХ НЕРАВЕНСТВ 259 чена тогда и только тогда, когда соответствующее множество координатных столбцов ограничено в какой-либо норме. Нетрудно показать независимость приведенного определения от выбора системы координат. Действительно, при изменении системы координат координатный столбец х заменяется на х'=Бх+ р, и мы можем написать оценку )х'~ «)Всс,)х) +)р~, из которой следует доказываемое утверждение. П р е д л о ж е н н е 4.
Если множество Ф ограничено, то его выпуклая оболочка также ограничена. В частности, выпуклая оболочка конечного множества ограничена. Д о к а з а тел ь от в о. Для координатного столбца произвольной точки нз выпуклой оболочки имеет место разложение у=асх,+...+ысх, в выпуклую комбинацию координатных столбцов точек из У. Отсюда мы получаем 3 )у ) ==. ~' а; ) х; ) «шах ) хс ) ~х~ а, = гп ах ~) х, ).
с,, с Так как У ограничено, существует такое число р, что Ц х Ц «р для всех Х ен У. Поэтому шах П хс 1! «р н ~!у!! ~ р, как и трес бовалось. Пусть в аффинном пространстве выбрана система координат, То~да каждое линейное неравенство, содержащее ненулевые коэффициенты при переменных, определяет замкнутое полупространство относительно плоскости, вообще говоря, не проходящей через начало координат. Система таких неравенств определяет пересечение полупространств. Тривиальное неравенство (с нулевой левой частью) или несовместно, или выполнено тождественно. Поэтому добавление таких неравенств или не меняет множества решений, или делает его пустым.
Пересечение полупространств является выпуклым множеством, так как каждое полупространство выпукло. Введем следующее О и р вдел е н и е. Пересечение полупространств аффниного пространства называется вьтуклым многогранным множеством. Если выпуклое многогранное множество ограничено, то его называют выпуклым многогранником.
В силу этого определения множество решений неоднородной системы линейных неравенств изображается выпуклым многогранным множеством. Заметим, что часто любые выпуклые многогранные множества называют выпуклыми многогранниками. Такого употребления слов мы придерживались в К., 5 1 гл. 1Х. 26О гл, ч. систвмы нвялввнств и линвпнов пяогихммиговлнна Выпуклые многогранные конусы, определенные в э 1, можно рассматривать и как точечные множества в аффинном пространстве.
Тогда они представляют собой специальный случай выпуклых многогранных множеств, в котором граничные плоскости всех полу- пространств проходят через общую точку — начало координат. 2. Множество решений неоднородной системы линейных неравенств. Мы видели, что множество точек, изображающих решения системы вида (1), является пересечением полупространств и, следовательно, выпукло. Мы даже дали таким множествам название. Теперь изучим их подробнее. С этой целью введем дополнительную переменную х"+' и рассмотрим систему Ах — х"+'Ь ~ О, (4) Для каждого решения х системы (1) столбец д = 1~хг, 1Г удовлетворяет системе (4), и наоборот, при условии х"" = 1 первые п элементов решения системы (4) удовлетворяют системе (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
