Содержание к диссертации
Введение
1 Специальные пространства метрических конфигураций 20
1.1 Метрики и метрические конфигурации 20
1.2 Метрические конфигурации как элементы линейного векторного пространства 23
1.3 Достаточные условия выполнения аксиом метрики 28
1.4 Ортогональные системы и аксиомы метрики 34
2 Неполные системы метрических конфигураций 39
2.1 Понятие оптимального разложения метрической конфигурации 39
2.2 Пример оптимального разложения по системе метрических конфигураций 43
3 Полные системы метрических конфигураций 50
3.1 Гомогенные системы и гомогенные базисы 50
3.2 Ранг метрической конфигурации и ранговые базисы . 57
3.3 Полуметрические ранговые базисы 60
4 Представление метрических конфигураций в конечно мерных евклидовых пространствах 64
4.1 Задача оптимального представления метрической конфигурации в конечномерном евклидовом пространстве . 64
4.2 Построение точечной конфигурации в конечномерном евклидовом пространстве по матрице попарных расстояний . 67
4.3 Ортогональное проектирование, оптимальные свойства разложения по системе ортогональных векторов 73
5 Оптимальные точечные конфигурации: связь качества и размерности представления 86
5.1 Функционалы сравнения метрических конфигураций и свойства оптимальной точечной конфигурации 86
5.2 06 асимптотическом поведении ошибки представления , 90
5.3 Понятие эффективности размерности 93
5.4 Об одной задаче финансового анализа 108
Заключение 111
Список литературы
- Метрические конфигурации как элементы линейного векторного пространства
- Пример оптимального разложения по системе метрических конфигураций
- Ранг метрической конфигурации и ранговые базисы
- Построение точечной конфигурации в конечномерном евклидовом пространстве по матрице попарных расстояний
Введение к работе
Актуальность темы. В последние десятилетия в распознавании образов, прогнозировании и интеллектуальном анализе данных получило широкое распространение использование мер сходства, когда описание объектов распознавания оказывается связанным с попарным сравнением этих объектов между собой. Практика решения задач распознавания показала, что во многих случаях указанные описания представляются гораздо более адекватными, чем признаковые. Попарные оценки сходства или различия объектов эффективно используются как в теории распознавания и прогнозирования, так и при решении конкретных прикладных задач.
Во многих задачах меры сходства вычисляются и используются только для конечного множества объектов. В практике интеллектуального анализа данных указанные задачи встречаются настолько часто, что возникла своя собственная терминология. В таком случае принято говорить о конфигурациях сходства. Если результатом попарного сравнения объектов является числовая оценка, которая интерпретируется как расстояние между этими объектами, то соответствующую конфигурацию сходства называют метрической конфигурацией (МК).
Не во всех задачах интеллектуального анализа данных существует некоторый единственный «объективный» способ наделить пространство объектов метрикой. Справедливо утверждать, что во многих задачах сами МК могут быть объектами исследования и обработки. И в настоящее время уже можно говорить о появлении в распознавании образов и интеллектуальном анализе данных комплекса технических приемов, предназначенных для работы с МК. В частности, интенсивно развиваются методы их синтеза и преобразования, позволяющие проявить скрытые структуры и закономерности, присутствующие в исходных данных.
Среди разделов математики, изучающих свойства метрик на конечных множествах, в первую очередь следует упомянуть геометрию расстояний. В частности, в работах по геометрии расстояний можно встретить упоминания о пространствах полуметрик. При этом среди стандартных конструкций исследования МК в основном упоминаются только различные конусы таких конфигураций. Однако развитие методов работы с МК в интеллектуальном
/ НОС. НАЦИОНАЛЬНАЯ/
1 I БИБЛИОТЕКА I
анализе данньк показало, что сами МК и различные их совокупности до сих пор остаются недостаточно изученными. Указанное состояние дел затрудняет создание и теоретическое обоснование новых методов, способных глубже раскрыть метрические свойства исходных данных.
Целью настоящей диссертационной работы является создание и исследование новых методов обработки и преобразования метрической информации, имеющих низкую вычислительную сложность и позволяющих работать с представлениями МК, учитывающими различные требования, дополнительные к метрическим. Для достижения данной цели выделяются два направления исследований.
Целью первого направления является исследование некоторых свойств разложений МК но различным конечным системам МК. Особое внимание при этом уделяется линейным разложениям как по полным, так и по неполным системам МК.
Целью второго направления является исследование некоторых свойств решений задачи представления МК точками конечномерного евклидова пространства, в частности, поведение ошибки представления в зависимости от размерности представления. При этом исследуются характеристики МК, позволяющие обоснованно выбирать размерность указанного представления.
Предметом исследования настоящей диссертационной работы являются сами МК, специальные совокупности МК и различные способы их представления. Во-первых, рассматриваются специальные пространства МК, возникающие при наделении множества всех МК некоторой фиксированной мощности свойствами линейного векторного пространства; рассматриваются специальные представления МК в указанных пространствах, базирующиеся на линейном разложении исходной МК по системе МК; исследуются методы эффективного преобразования данных представлений. Во-вторых, рассматривается задача построения в конечномерном евклидовом пространстве множества точек (точечной конфигурации), расстояния между которыми наилучшим образом приближают заданную МК; при этом предметом исследования оказывается последовательность ошибок представления заданной конфигурации в зависимости от размерности представления.
Методика исследования. В работе для решения поставленных задач используется аппарат линейной алгебры, теории аппроксимации и оптимиза-
ции. При этом следует отметить, что постановки большинства задач можно отнести к теории распознавания, геометрии расстояний и многомерному статистическому анализу.
Научная новизна. Тот факт, что к метрикам на конечном множестве объектов могут применяться операции сложения и умножения на скаляр, был известен ранее. В данной диссертационной работе, по-видимому, впервые МК рассматриваются одновременно как элементы специального линейного векторного пространства и конструкции интеллектуального анализа данных, удовлетворяющие каким-либо дополнительным проблемно-ориентированным требованиям.
Предложены и исследованы новые способы представления МК, при использовании которых требования полуметрики и дополнительные проблемно-ориентированные требования выполнены по построению. Рассмотрены требования, соответствующие задачам, в которых индивидуальные объекты отделены от остальных объектов, пары объектов отделены от остальных объектов, задан ранг МК.
Введено и исследовано понятие ортогональных МК. Введены понятия полных и неполных систем МК. При рассмотрении неполных систем предложены и исследованы понятия оптимального разложения и оптимального приближения заданной МК по системе МК. При рассмотрении полных систем предложены и исследованы некоторые семейства базисов в пространствах МК, соответствующие различным дополнительным проблемно-ориентированным требованиям.
Введено и исследовано новое семейство функционалов сравнения МК. При рассмотрении задачи представления МК точками конечномерного евклидова пространства для указанного семейства функционалов получены новые результаты о поведении ошибки представления для тех МК, которые не могут быть точно представлены ни в каком конечномерном евклидовом пространстве. Предложена и исследована новая характеристика МК — «эффективная размерность», — позволяющая обоснованно выбирать размерность представления.
Теоретическая и практическая ценность. Результаты, полученные в диссертационной работе, ориентированы как на непосредственное практическое применение, так и на разработку и теоретическое обоснование новых
методов преобразования метрической информации в распознавании образов и интеллектуальном анализе данных. В частности, предлагаемые в работе способы представления МК позволяют разработать вычислительно эффективные реализации широкого круга методов распознавания образов и кластерного анализа. Эффективность предложенных процедур подтверждена решением модельных задач и практических задач из области финансового анализа.
Апробация работы. Результаты, изложенные в диссертации, докладывались на Всероссийских конференциях «Математические методы распознавания образов VIII, IX, X, XII» (Москва, ВЦ РАН, 1997, 1999, 2001, 2005 гг.); Международных конференциях «Интеллектуализация обработки информации — 2000, 2002, 2004» (Симферополь, ТНУ); Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов — 2001» (Москва, МГУ); семинарах отделов «Математических проблем распознавания и методов комбинаторного анализа» и «Вычислительных методов прогнозирования» ВЦ РАН.
Публикации. По теме диссертации опубликовано 10 работ [1 -10], в том числе 2 в ЖВМ и МФ и 1 в журнале «Искусственный Интеллект». Описания отдельных результатов, полученных в диссертации, включались в научные отчеты по проектам РФФИ 99-01-00562, 02-01-00326, НШ №1721.2003.1.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка иллюстраций (11 пунктов) и списка литературы (86 наименований). Общий объем работы составляет 122 страницы.
Метрические конфигурации как элементы линейного векторного пространства
Для представления метрической конфигурации можно использовать матрицу попарных расстояний г = (pij), i,j Є [l,m]. Матрицы попарных расстояний являются элементами пространства Штхт. По свойствам метрических конфигураций матрица попарных расстояний симметрична, на ее главной диагонали находятся нули. Чтобы избежать дублирования элементов в матрице, введем множество неупорядоченных пар индексов Ет = { (ij) i,j Є [1, т],і ф j }. Мощность множества Ет, очевидно, равна С — т(т — 1)/2. Отметим, что граф (Vm,Em) есть клика мощности т. В литературе некоторые результаты, применяемые в настоящее время к метрическим конфигурациям, впервые были сформулированы для взвешенных графов. Пользуясь введенным обозначением, метрическую конфигурацию р можно представить как вектор в простраистве ШЕт размерности \Ет\. Компоненты такого вектора индексируются неупорядоченными парами индексов (ij) и равны /. Обратно, по каждому вектору из указанного пространства можно однозначно восстановить метрическую конфигурацию. Для обозначения мощности пространства Ет в некоторых случаях будет использоваться символ t.
Таким образом, в данной работе метрические конфигурации мощности т отождествляются с векторами размерности t — m(m — 1)/2. Для обозначения векторного представления метрической конфигурации р будет использоваться тот же самый символ р. В результате такого отождествления на множестве метрических конфигураций одной мощности оказываются заданы операции сложения и умножения на действительное число, фактически соответствующие традиционным операциям в 3R . Это позволяет говорить о метрических конфигурациях как об элементах линейного векторного пространства К т. В пространстве ЖЕт, как в линейном векторном пространстве, основными операциями являются сложение векторов и умножение вектора на число.
Применение операций линейного векторного пространства к метрическим конфигурациям в последние десятилетия использовалось в работах по геометрии расстояний, теории графов и комбинаторной оптимизации. В частности, наиболее интенсивно с метрическими конфигурациями работают при анализе структурных и алгоритмических свойств мультипо-токов, где «конечные метрики» возникают как сущности, двойственные к мультипотокам. Сжатый обзор результатов по некоторым тематикам, явно или неявно использующим отождествление метрических конфигураций с элементами какого-либо линейного векторного пространства, можно найти в [66]. Интерес к геометрии расстояний в настоящее время стимулируется ее приложениями, среди которых существенную роль играют задачи и методы многомерного шкалирования (см. [13, 67]).
В соответствии с обозначениями, введенными в разделе 1.1, для обозначения вектора в пространстве ЖЕт, все компоненты которого равны 1, будет использоваться символ j. В тривиальном базисе вектор ] соответствует метрике пространства изолированных точек. Для обозначения вектора в пространстве Е "1, все компоненты которого равны О, будет использоваться символ 0.
Укажем элементы р линейного векторного пространства ЖЕт, которые удовлетворяют аксиомам расстояния, полуметрики или метрики. Если вектор р неотрицателен (р 0), то метрическая конфигурация уже удовлетворяет условиям (1)-(3) из определения 1, т.е. условиям расстояния. Если вектор р строго положителен (р 0), то метрическая конфигурация удовлетворяет условиям (1)-(3) и (5). Неравенства треугольника для метрической конфигурации превращаются в конечную систему линейных однородных нестрогих неравенств. Отметим, что из выполнения этой системы неравенств треугольника следует неотрицательность вектора р. Таким образом, если вектор р удовлетворяет системе неравенств треугольника, то метрическая конфигурация удовлетворяет условиям полуметрики (1)-(4), а если, кроме того, вектор р строго положителен, то он удовлетворяет всем аксиомам метрики (1)-(5).
Определение 5 ([65]). Множество всех векторов пространства REm, которые соответствуют метрическим конфигурациям, удовлетворяющим аксиомам полуметрики, называется полуметрическим конусом и обозначается МЕТт.
Объясним возникновение термина конус. Система неравенств треугольника для конечного набора объектов мощности т является конечной, линейной и однородной. Следовательно, геометрическим местом векторов, удовлетворяющих этой системе, является полиэдральный конус [16].
Строго положительные векторы, принадлежащие полуметрическому конусу, и только они соответствуют метрическим конфигурациям, удовлетворяющим всем условиям метрики.
Пусть R+ — множество неотрицательных действительных чисел. Напомним определения следующих понятий, которые в работе будут использованы для множеств метрических конфигураций.
Пример оптимального разложения по системе метрических конфигураций
Чтобы проиллюстрировать использование понятия оптимального разложения, рассмотрим систему всех двухклассовых метрических конфигураций, в которых один объект множества Vm отделен от всех остальных. В качестве нормы на множестве №Ет будем использовать евклидову норму. Каждая метрическая конфигурация данной системы удовлетворяет условиям полуметрики. Данная система содержит q — т метрических конфигураций и имеет вид tf={% })l [l,m]}. (2.4)
Пусть р — разложение некоторой метрической конфигурации р но системе (2.4). Тогда векторное представление метрической конфигурации и ее разложение по указанной системе связаны следующим образом: т р = Sp = 2Рій{{і}) = X) ІРі +Рз)Чз или V(y) Ет Pij = Pi +pj
Если для некоторой метрической конфигурации р такое разложение будет найдено, то оно может быть очевидным образом использовано для описания или интерпретации отдельных объектов в сравнении со всеми остальными. При этом компоненты разложения показывают удаленность каждого объекта от остальных объектов в совокупности.
Используя тот факт, что для фиксированного т и t = С матрица перехода Зт для рассматриваемой системы метрических конфигураций имеет регулярную структуру можно получить, что S Sjn — J + (т — 2)1. С учетом формул (1.1) и (1.2) это соотношение позволяет прийти к явной записи ответа для оптимального разложения и оптимального приближения произвольной метрической конфигурации р по рассматриваемой системе (2.4):
Полученные выражения имеют смысл только при т 2. Действительно, при т — 1 расстояний между объектами вообще нет и парі не налагается каких-либо ограничений, а при т = 2 соотношение р& = р\ +р не позволяет найти коэффициенты разложения однозначно. Процедуру вычисления выражений (2.5) и (2.6) можно организовать таким образом, что потребуется порядка 0(т2) операций. Это эффективнее, чем в общем случае, когда матрица перехода имеет размер і х т и для вычисления оптимального разложения требуется порядка 0(т3) операций.
Вектор р может быть точно разложен по данной системе тогда и только тогда, когда р = ppt. Условие неотрицательности оптимального разложения (popt 0) можно записать в виде Vi6[l,m] —Y]pik 7;Pav (2.7) Условие неотрицательности оптимального приближения (popt 0) можно записать в виде і і Vi,J [l,m],t j 2pik + — 2pjk Pav кфі кфі
Согласно полученным ранее утверждениям 1-4, если для некоторой метрической конфигурации выполнено popt 0, то оптимальное приближение такой метрической конфигурации удовлетворяет условиям полуметрики. Полученное выражение (2.7) есть линейное описание полиэдрального конуса, а именно конуса Ш+(К). В данном случае достаточное условие выполнения аксиом метрики говорит об оптимальных метрических конфигурациях, которые все находятся в линейном подпространстве пространства REm размерности т. Ясно, что указанный конус является собственным подмножеством разрезного конуса: R+(K) С CUT.
Если точное разложение метрической конфигурации по данной системе конфигураций (2.4) существует, то оно единственно. Кроме того, даже если некоторую метрическую конфигурацию невозможно точно разложить по рассматриваемой системе, оптимальное разложение сохраняет среднее расстояние в конфигурации.
Ранг метрической конфигурации и ранговые базисы
Среди наиболее используемых приложений геометрии расстояний можно указать многомерное шкалирование. В ряде задач и методов многомерного шкалирования существенным образов используется понятие ранга метрической конфигурации (см. [67, 13]).
Определение 15. Рангом метрической конфигурации р называется такой линейный порядок на множестве неупорядоченных пар индексов Ет, что порядок на парах индексов совпадает с нестрогим порядком значений соответствующих компонент метрической конфигурации в том смысле, что для порядка на парах выполнены соотношения
Следует отметить, что если некоторые компоненты метрической конфигурации равны, то ей соответствует сразу несколько рангов.
В соответствии с линейным порядком неупорядоченные пары из Ет можно занумеровать числами от 1 до t = С . Далее в тексте вместо пар (ij) из Ет будут использоваться одинарные индексы из [1,].
Рассмотрим представление р метрической конфигурации р последовательными приращениями. Пусть р\ = р\, а для г = 2,3,..., t выполнено pi = Pi — pi-v Оказывается, что от р к р можно перейти по формуле р = Sp, где матрица перехода S в новой нумерации пар объектов имеет вид /10 0. 110. 5 = 111 о V уі і і .
Отметим, что множество Ет можно линейно упорядочить С \ способами. Но после указанной выше перенумерации пар объектов и фиксации порядка запись матрицы перехода во всех случаях выглядит одинаково.
Из результатов раздела 1.2 следует, что предложенное представление р составляют коэффициенты разложения метрической конфигурации по базису, элементы которого в тривиальном базисе имеют вид V\ = /Л 1 1 Vі/ = 3, Р2 = 1 Vі/ Рз = /о\ о 1 W Pt = о о (3.4) Определение 16. Базисы вида (3.4) называются ранговыми базиса ми.
Еще раз отметим, что каждому линейному порядку на Ет соответствует свой ранговый базис, но после фиксации порядка и перенумерации
пар из множества Ет записи элементов всех ранговых базисов выглядят одинаково.
Утверждение 30. Линейная комбинация с неотрицательными коэффициентами набора метрических конфигураций, имеющих один и тот же ранг, снова имеет тот же самый ранг.
Доказательство данного утверждения непосредственно следует из определения 15 и свойств числовых неравенств.
Таким образом, множества всех метрических конфигураций, имеющих один и тот же ранг, являются выпуклыми. По аналогии с разделом 1.3 найдем связь между неотрицательносью разложения некоторой метрической конфигурации по ранговому базису и наличием соответствующего ранга у этой метрической конфигурации.
Утверждение 31. Пусть задан некоторый ранг и по нему построен ранговый базис. Тогда все элементы рангового базиса сами имеют заданный ранг.
Утверждение 32. Пусть по заданному рангу построен ранговый базис. Компоненты Р2)РЗ) -чР( разложения некоторой метрической конфигурации по этому ранговому базису неотрицательны тогда и только тогда, когда эта метрическая конфигурация имеет заданный ранг.
Утверждение 33. Пусть по заданному рангу построен ранговый базис. Представление р некоторой метрической конфигурации по этому ранговому базису неотрицательно тогда и только тогда, когда эта метрическая конфигурация имеет заданный ранг и удовлетворяет аксиомам расстояния.
Очевидно, что переход между рирв любую сторону требует порядка 0(т2) арифметических операций.
Чтобы использовать результаты раздела 1.3, перейдем к исследованию взаимного расположения элементов рангового базиса и полуметрического конуса. Утверждение 34. Для произвольного і Є [l,t] выполнено соотношение Утверждение 35. Для произвольного і Є [ 1, і ] если pi Є 9METm, то pi лежит на экстремальном луче МЕТт. Утверждения 34 и 35 следуют из результатов раздела 1.4 о соответствии метрической конфигурации отношению эквивалентности и из приведенных в [66] результатах для таких отношений эквивалентности. Отметим, что линейная комбинация (pi + j)/2 соответствует замене в pi всех нулевых компонент на 1/2.
Построение точечной конфигурации в конечномерном евклидовом пространстве по матрице попарных расстояний
При работе с прикладными задачами бывает оправдано привести описания объектов к форме векторов в евклидовом пространстве. Например, хорошо изучены и нередко используются методы линейного преобразования пространства признаков, требующие именно такого представления.
Отметим, что если при каком-то М в Жм существует набор точек XQ, ...,а;дг_і, удовлетворяющий заданной матрице попарных расстояний \\pij\\, то и в Е -1 существует такой набор точек Уо,--,ук-і. Действительно, при М N — 1 это очевидно. В противном случае рассмотрим в Жм набор векторов Zi = XQX{, І = 1,..., iV — 1. Начав с этих векторов процесс ортоганализации, в Шм можно получить базис еі,...,ем, в котором набор векторов z\,..., z -i и ZQ = 0 выражаются только через первые N — 1 базисных векторов. Такое представление и дает искомую точечную конфигурацию в R -1, причем уо = 0 . Можно быть уверенным, что мы не выйдем из размерности N — 1, размещая в пространстве TV объектов.
Рассмотрим алгоритм, позволяющий но матрице попарных расстоя
ний [py) ij — 0,..., ЛГ — 1, разместить N объектов в конечномерном евклидовом пространстве наименьшей необходимой размерности, либо показывающий, что такое размещение невозможно. Будем считать, что аксиомы метрики для матрицы попарных расстояний выполнены, т.е. это симметричная матрица с неотрицательными элементами и нулями на диагонали, в которой для любой тройки г, j, к Є {О, ...,N — 1} выполнено неравенство треугольника pij+pjk рік- В противном случае нельзя было бы говорить даже о построении метрического пространства. Как было показано, полученная точечная конфигурация будет иметь размерность не более N — 1, причем первый объект можно поместить в начало координат. Объекты будут нумероваться от 0 до N — 1, им будут соответствовать нижние индексы. Верхние индексы задают соответствующие компоненты в координатном представлении. Через хі будем обозначать точку в М -1, сопоставляемую г-тому объекту. Через xt будем обозначать вектор из точки XQ в точку Xf. Когда точка XQ помещена в начало координат, координатное представление точек Х{ и векторов Х{ совпадает.
На первом шаге точку х$ помещаем в начало координат, а х\ полагаем равной (/701,0,...,0). Далее алгоритм последовательно добавляет объекты к уже полученной части конфигурации согласно матрице попарных расстояний.
Пусть точки хо,...,хп удовлетворяют заданным расстояниям, и при всех і х\ф 0 и х\ — 0 для j — і + 1,..., N — 1. Очевидно, что в этом случае векторы х\,...,хп линейно независимы. Попытаемся добавить точку xn+i согласно матрице попарных расстояний. Для этого рассмотрим все тройки точек XQ,Xi,xn+i,i = 1,...,п и соответствующие им треугольники со сторонами р0чі, р0іП+і,ріуП+1. Аксиому треугольника для этих троек считаем выполненной по исходным предположениям. Используя каждый из треугольников, найдем проекции Pi точки xn+i на векторы ХІ, которые должна иметь точка хп+\ в евклидовом пространстве, чтобы удовлетворять расстояниям ро.ь о.п+ьрі,п+і- Все рисунки 4.1 выполнены в ПЛОСКОСТИ XQ, Xj, Хп+\. Во всех трех случаях
С другой стороны, в евклидовом пространстве проекцию вектора на вектор можно найти по скалярному произведению. В нашем случае Хо = 0 и координатное представление точек Х{ и векторов щ совпадает. Поэтому можно записать Pi = Пр; :Сп+1 = {%i} %n+l) Xi Векторы xl ненулевые, ведь по условию х\ 0. Мы получили систему из п линейных уравнений на хп+\: п+1 Хх„±-\ — %п+1 V (РЛ \Рп) где р - вектор найденных проекций. В матрице X все столбцы с номерами больше п нулевые. Поэтому мы можем перейти к квадратной матрице X , в которой только п столбцов, и, соответственно, к вектору х п+1, у которого п компонент. Векторы хх,..,,хп линейно независимы, поэтому матрица X невырождена. Тогда система X xfn+l = р имеет единственное решение х п+іГ — (#„+1,..., n+i)- Здесь же отметим, что матрица Xі треугольная с ненулевыми диагональными элементами. Это позволяет находить решение системы простой однопроходной прогонкой. Дальнейшие действия зависят от знака величины
Если Д 0, что возможно и при выполнении всех аксиом метрики, то ни в каком конечномерном евклидовом пространстве невозможно построить точечную конфигурацию, удовлетворяющую матрице попарных расстояний \\pij\\, i,j = 0,..., п 4- 1, а тем более матрице 11/II) ЬЗ — 0, -., N — 1. Действительно, длина вектора хп+\ должна быть Ро,п+1- Но уже первые п компонент, которые определены единственным образом, дают большую длину.
Если Д 0, то положим хХ\ vA, а следующие компоненты оставим нулевыми. Проверим, что построенная точка хп+\ удовлетворяет всем заданным расстояниям до точек жо ..., хп: Po,n+i удовлетворено по построению #"+}. \XiXn+{\ = {x i - ХІ)Т{Х [ - х-) = \х ?х\ + \x-\ 2(z i, х-) = - A),n+1 + Po,i - lPipQ,i — Po,n+l + P0,i - 2P0,i 2 - Pi,n+V
Необходимо особо выделить случай Д — 0, показывающий линейную зависимость векторов x\, ...,xn+i. (При Д 0 имеем х+\ = уД 0, и векторы Хх,...,хп+\ линейно независимы.) Линейная зависимость или независимость векторов — свойство линейного векторного пространства. Но в евклидовых пространствах линейная зависимость оказывается тесно связанной с расстояниями между векторами, ведь возможность линейно выразить какой-то вектор через другие накладывает более сильные ограничения на возможные расстояния, чем аксиомы метрики. У кол-линеарных векторов длины пропорциональны. На прямой, задаваемой двумя векторами, все неравенства треугольника, в которых суммируются меньшие стороны, превращаются в строгие равенства — из трех точек на прямой одна находится между двумя другими.