Студопедия — Выпуклые множества
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Выпуклые множества






Рассмотрим множество вида

[x, y]={z/z=(1-a)x+ay, aÎ [0, 1], zÎ En}. (3.1)

Это отрезок прямой, проходящей через точки x и y, так как уравнение прямой, проходящей через точки x и y имеет вид:

z(a)=x+a(y-х)=(1-a)x+ay, (3.2)

причемпри a =0 Z(a)=x, при a=1 Z(a)=у.

Если a пробегает значения между 0 и 1, то Z(a) пробегает значения по прямой между x и y.

Определение 3.1. Множество ХÎ Еn называется выпуклым, если для любых

х точек х, уÎ Х отрезок [х, y ]Î Х.

Если при этом (х, y)Ì X0 (X0- множество

z(a) внутренних точек множества Х), то Х называется строго выпуклым множеством.

y Из этого определения следует, что у выпуклого множества для любых х, уÎ Х и aÎ [0, 1] точка z(a) = (1-a)x + a y Î Х, если Х – строго выпуклое множество, то

Рис. 3.1. при aÎ (0, 1) z(a) является внутренней точкой множества Х.

На рис. 3.2. приведен пример выпуклого множества, а на рис. 3.3 пример множества, не являющегося выпуклым.


 

 
 


 

Рис. 3.2 Рис. 3.3.

Для выпуклых множеств справедливы следующие теоремы:

Теорема 3.1. Пересечение любого числа выпуклых множеств выпукло.

Доказательство. Пусть Z = Ç Хl Возьмем х, уÎ Z и aÎ [0, 1].

lÎ L

Покажем, что z(a)= (1-a)x + a y. Действительно, т. к. х, уÎ Z, то для любого lÎ L х, уÎ Хl. Из выпуклостимножеств Хl следует, что z(a)Î Хl для всех lÎ L, поэтому z(a)Î Z, откуда следует выпуклость множества Z.

Теорема 3.2. Множество Х={x / < a, x> £ b, xÎ En }, где а – заданный вектор, b - скаляр, является выпуклым множеством.

Доказательство.

Пусть х, уÎ Z и aÎ [0, 1], докажем, что z(a)= (1-a)x + ay. Действительно

< z(a), a> = < (1-a)x + a y, a> = (1-a)< x, a> + a < y, a>

Так как

х, уÎ Х, то есть < x, a> £ b, < у, a> £ b, то < z(a), a> £ b, т.е. z(a)Î Х.

Следствие 3.1. Множество Х={x / Ах £ b, xÎ En }, где А – матрица размерности m× n, bÎ En выпукло.

Определение 3.2. Точка z = ai xi называется выпуклой комбинацией точек х1, х2, …, хn Î En, если ai ³ 0, i = , ai = 1.

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

Доказательство. Пусть Х – выпуклое множество, содержащее элементы хi,, i= , Произвольная система точек ai ³ 0 такова, что a i = 1. Покажем, что Z = aixi Î X.. Доказательство будем проводить методом математической индукции. При n=2 утверждение следует из определения 3.1, если положить:

a2 = a, a1 = 1- a.

Пусть утверждение верно для некоторого n ³ 2, покажем его справедливость для n+1.

Пусть Z= ai xi, где xi Î X, ai ³ 0, i= , +1, ai=1,

Z= aixi+an+1 xn+1 = = (1 - an+1 ) xi + an+1 xn+1.

По предположению точка x' = xi Î X, т. к. xi Î X,,

³ 0, i = , =1.

В силу выпуклости Х и определения 3.1 следует, что ZÎ X.

Теорема 3.4. Замыкание выпуклого множества Х выпукло.

Доказательство. Пусть х, у Î , a Î [0, 1]. Из определения замыкания множества следует, что в Х существуют последовательности {xk}, {yk} такие, что xk x, yk y при k ¥. В силу выпуклости множества Х точка zk(a)= (1-a)xk + a yk. Î X для любого целого k. Переходя к пределу при k ¥ в силу определения замыкания множества, получаем, что

z(a)= (1-a)x + a y Î (3.3)







Дата добавления: 2014-12-06; просмотров: 1268. Нарушение авторских прав; Мы поможем в написании вашей работы!



Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Тема: Изучение приспособленности организмов к среде обитания Цель:выяснить механизм образования приспособлений к среде обитания и их относительный характер, сделать вывод о том, что приспособленность – результат действия естественного отбора...

Тема: Изучение фенотипов местных сортов растений Цель: расширить знания о задачах современной селекции. Оборудование:пакетики семян различных сортов томатов...

Тема: Составление цепи питания Цель: расширить знания о биотических факторах среды. Оборудование:гербарные растения...

ОПРЕДЕЛЕНИЕ ЦЕНТРА ТЯЖЕСТИ ПЛОСКОЙ ФИГУРЫ Сила, с которой тело притягивается к Земле, называется силой тяжести...

СПИД: морально-этические проблемы Среди тысяч заболеваний совершенно особое, даже исключительное, место занимает ВИЧ-инфекция...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия