Комитеты линейных функционалов
Пусть
,
,
в
– конечные множества в пространстве
признаков;
–
точки общего положения.
Определение.
Точки
пространства
называются
точками общего положения, если никакая
точка
не лежит в гиперплоскости размерности
.
Приме
р. Пусть
,
т.е. рассматривается пространство
(плоскость).
Тогда точки
–
точки общего положения, если никакие
три из них не лежат на одной прямой.
Теорема.
Существует
разделяющий комитет аффинных функционалов,
состоящий из не более, чем
членов
при нечетном
и
не более, чем
при
четном
.
Доказательство.
Рассмотрим случай
,
т.е. пространство
.
Пусть
,
.
Тогда возможны два случая.
Для первого случая (рис. слева) функционал имеет вид:
Для второго случая (рис. справа) функционал имеет вид:
–
количество
функционалов для худшего случая.
Пусть
,
.
Тогда возможны следующие варианты.
Все
случаи вида показанного на рис. слева
сводятся к предыдущему
.
Во всех остальных случаях функционалы
надо располагать аналогично рис. справа.
Для худшего случая
.
Пусть
(четное
количество точек). Рассмотрим худший
из возможных вариантов.
В
данном случае функционалы надо располагать
как показано на рис.
Пусть
(нечетное
количество точек). Рассмотрим худший
из возможных вариантов.
В
данном случае функционалы надо располагать
как показано на рис.
.
Все остальные случаи можно свести либо
к этим двум, либо к предыдущим.
Таким образом, по методу математической индукции существует разделяющий комитет аффинных функционалов из не более, чем членов при нечетном и не более, чем при четном в пространстве .
Многомерный
случай сводится к одномерному следующим
образом. Ищем подпространство
такое,
что
,
при
.
Проектируем все
на
соответствующие подпространства, пока
не получим одномерную задачу. В многомерном
случае для разделения
и
служит
гиперплоскость:
Функция Шеннона
Пусть
–
это число гиперплоскостей, достаточное
для разделения любых точечных множеств
и
точек
общего положения в пространстве
.
Лемма
1. Если
,
то
Доказательство.
Если
,
то добавим точки общего положения до
.
Через
точек
из
проводим
гиперплоскость:
Для
такого,
что
.
Выберем
и
возьмем гиперплоскости
и
.
и
отделяют
точки
от
всех остальных.
Аналогичным
образом из оставшихся
точек
выделяем еще
и
строим еще пару гиперплоскостей. Далее
из оставшихся
точек
выделяем еще
и
строим еще пару гиперплоскостей и т.д.
В конце получим
точек.
Следовательно:
Утверждение
1. Если
разделяют
множества
и
,
и
–
непрерывная кривая в
такая,
что
,
а
,
то существует
и
такие,
что
.
Утверждение 2. Любая гиперплоскость пересекает кривую не более, чем в точках.
Доказательство.
Рассмотрим линейный функционал
.
Запишем условие пересечения гиперплоскости
и кривой
:
Кривая
задана
многочленом степени
.
Следовательно,
–
то же многочлен степени
.
Значит, уравнение
является
уравнением степени
.
Следовательно, т.к. корни могут быть
кратными, данное уравнение имеет не
более
корней.
Лемма
2.
.
Доказательство. Построим . Рассмотрим последовательность точек:
Пусть
,
где
,
.
Тогда
–
точки в
.
Без
ограничения общности положим
,
при
нечетном,
и
,
при
четном.
Тогда получим непрерывную кривую (см.
рис).
Каждая
гиперплоскость дает не более, чем
пересечений.
Кривая должна иметь
разделение,
т.е. должно быть
гиперплоскостей.
Следовательно, всего гиперплоскостей
должно быть не менее, чем
,
т.е.
.
Т.к.
то
.
Следовательно,
,
при нечетном
,
,
при четном
.
Окончательно
получаем:
,
.
Пример.
Пусть
,
,
.
Обозначим
и
.
Тогда
