dmagin Oct 13 2017 at 13:45

Геометрия данных 3. Скалярное произведение пар

6 min

9.9K

Инвариант дистанции (квадрат расстояния) между элементами можно обобщить, если умножать разность элементов не на саму себя, а на другую разность элементов. Полученное значение будет отражать скалярное произведение упорядоченных пар.

Оглавление

1. Симплексы и графы
2. Определение ди- и би-координат
3. Скалярное произведение пар
4. Пространство графа
5. Преобразование базиса
6. Граф-звезда

Упорядоченная пара

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

Каждой упорядоченной паре можно сопоставить вектор — разность элементов, образующих пару. Для двух векторов можно определить скалярное произведение, которое можно также рассматривать как характеристику четырех элементов пространства.

Скалярное произведение

Для уменьшения громоздкости в данной части будем обозначать элементы строчными символами. Пара — это совокупность двух элементов: $inline$ . Вектор, соответствующий паре, — это разность элементов пары:

$\mathbf{v}_{ij} = j - i \quad(3.1)$

Норма элемента — это его скалярное произведение с самим собой:

$n_i=i \cdot i \quad(3.2)$

Это же определение можно использовать для вектора пары, которая, как известно, отражает квадрат расстояния между элементами пары:

$q_{ij} \equiv n_{ij} = (j - i) \cdot (j - i) \quad(3.3)$

Если заданы две разных пары $inline$ и $inline$ , то можно определить скалярное произведение между соответствующими векторами:

$g_{ij,kl} = (j - i) \cdot (l - k) = \mathbf{v}_{ij} \cdot \mathbf{v}_{kl} \quad(3.4)$

Индексы $inline$ задают одну пару, а индексы $inline$ — другую.

Выражение (3.4) определяет скаляр, зависящий от взаимного положения 4-х элементов. Важно, что данный скаляр может быть выражен через расстояния между элементами $q_{ij}$ .

Как известно, расстояние между элементами связано со скалярным произведением между ними:

$q_{ij} = n_i - 2 g_{ij} + n_j \quad(3.5)$ .

Раскрывая произведение (3.4) с учетом (3.5), получаем:

$g_{ij,kl} = (q_{il} + q_{jk} - q_{ik} - q_{jl}) / 2 \quad(3.6)$

Это общая формула скалярного произведения пар. Порядок индексов важен — задает пары и направление соответствующих им векторов.

Выражения, подобные (3.6), часто возникают в разных местах математики. Связано это с общностью вывода данной формулы. Отметим, что мы использовали только самые общие свойства алгебраического выражения. Поэтому в качестве элементов могут использоваться любые объекты, для которых определена операция произведения. Тождество будет справедливо и для них, в общей форме оно выглядит так:

$(A-B) \cdot (C-D) = ((A-D)^2 + (B-C)^2 - (A-C)^2 - (B-D)^2)/2 \quad(3.6.1)$

Пары с общей вершиной — смежные пары

Если пары имеют общую вершину $(k \equiv l)$ , то формула (3.6) упрощается:

$g_{ki,kj}=(q_{ik} + q_{jk} - q_{ij})/2 \quad(3.7)$

Формула (3.7) — это теорема косинусов для треугольника. Здесь пары, между которыми определена взаимная норма, имеют общий элемент k — смежные пары.

На 3-х вершинах можно определить три скалярных произведения. Их сумма выражается через сумму дистанций между вершинами:

$g_{ki,kj} + g_{ik,ij} + g_{ji,jk} = (q_{jk} + q_{ik} + q_{ij})/2 \quad(3.8.1)$

Квадрат скалярного произведения на 3-х вершинах связан с площадью образуемого ими треугольника $s_{ijk}$ (формула Герона):

$4 s_{ijk}^2 = q_{ik} q_{jk} - (g_{ik,jk})^2 \quad(3.8.2)$

Независимые пары — четыре разных вершины

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

Перечислим свойства скалярного произведения (3.6).

1) Не зависит от перестановки пар:

$g_{ij,kl}=g_{kl,ij} \quad(3.9.1)$

2) Антисимметрично относительно перестановки элементов в паре $inline$ или $inline$ :

$g_{ij,kl} = -g_{ji,kl} = -g_{ij,lk} \quad(3.9.2)$

3) Для 4-х элементов существует только два независимых скалярных произведения пар ввиду тождества:

$g_{ij,kl} + g_{ik,lj} + g_{il,jk} = 0 \quad(3.9.3)$

Математики увидят в формуле (3.9.3) первое тождество Бьянки. Из чего можно сделать вывод, что структуры тензора кривизны (Римана) и скалярного произведения пар — подобны.

4) Норма независимых пар может быть выражена через разность норм смежных пар:

$g_{ij,kl} = g_{ij,il} - g_{ij,ik} \quad(3.9.4)$

Этим тождеством воспользуемся в следующей статье.

5) Дистанция между элементами $inline$ и $inline$ может быть выражена через значения скалярных произведений смежных и независимых пар:

$q_{ij} = g_{ij,ik} - g_{ij,jk} = g_{il,ik} + g_{jl,jk} - g_{il,jk} - g_{jl,ik} \quad(3.9.5)$

Пары на элементах базиса

В качестве элементов, образующих пару, могут быть выбраны вершины базиса. Тогда скалярное произведение пар становится тензором — набором скалярных произведений между всеми возможными парами элементов данного базиса. Чтобы отличать тензоры от скаляров будем использовать для первых заглавные буквы. То есть вместо скаляра $g_{ij,kl}$ для элементов базиса получаем тензор $G_{ij,kl}$ .

Скалярное произведение и кофакторы лапласиана

Скалярное произведение пар, образованных элементами базиса, может быть выражено через свойства лапласиана базиса.

Если заданы две пары вершин $inline$ и $inline$ , то значение их скалярного произведения можно получить делением кофактора 2-го порядка $U_{ij,kl}(L)$ на скалярный потенциал лапласиана $inline$ :

$G_{ij,kl}=U_{ij,kl}(L) / u(L) \quad(3.10.1)$

Кофактором $U_{ij,kl}$ называется определитель минора квадратной матрицы (с учетом знака). Скалярный потенциал $inline$ — это кофактор 1-го порядка от лапласиана (см. (1.12) из первой статьи).

Таким образом необходимо из матрицы лапласиана удалить столбцы, соответствующие одному вектору (в формуле это $inline$ -й столбцы), и строки, соответствующие другому ( $inline$ ), после чего разделить определитель получившегося минора на скалярный потенциал $inline$ . Если удаляемые столбцы и строки лапласиана — одни и те же, то получим значение дистанции между узлами.

Скалярное произведение пар на графе

Между любыми парами вершин графа можно определить их взаимную норму — скалярное произведение. Поскольку граф обычно задан лапласианом, то для расчета можно использовать формулу (3.10.1).

Пусть, например, в качестве образующих вершин двух пар выбраны — $inline$ и $inline$ . Тогда скалярное произведение между данными парами дается формулой (3.6):

$G_{AB,MN}=(Q_{AN} + Q_{BM} - Q_{AM} - Q_{BN}) / 2$

Для графа, представляющего собой электрическую цепь, значение скалярного произведения отражает понятие обобщенного сопротивления в электрической цепи. Для измерения такого («кажущегося») сопротивления источник тока (напряжение) прикладывается к одним узлам (A и B), а разность потенциалов измеряется между другими (M и N). Взаимная норма (скалярное произведение) пар равна нулю, если внешняя разность потенциалов не приводит к разности потенциалов на измеряемой паре.

Граф не обязательно должен быть дискретным,- грунт является примером сплошного (непрерывного) графа, на котором можно проводить измерения скалярного произведения между выбранными элементами.

Схема установки для исследования методом сопротивления: A и B – питающие заземления; M и N – измерительные заземления; 1 – измерительный прибор (из книги «Электроразведка», Якубовский Ю. B., M., 1980).

На рисунке показана схема измерения скалярного произведения пар $inline$ и $inline$ на грунте.

В следующей статье разберем подробнее, почему отношение заданной и измеряемой разностей потенциалов узлов оказалось связанным со скалярным произведением пар.

Обращение минора лапласиана

Подматрицу значений взаимных норм (скалярных произведений) пар можно получить обращением минора лапласиана. Обозначим лапласиан, из которого удалены $inline$ -я строка и $inline$ -й столбец, как $L^{i(a),j(b)}$ . Тогда имеет место тождество:

$G_{jb,ia}=(L^{i(a),j(b)})^{-1} \quad(3.10.2)$

Отметим, что в матрице $G_{jb,ia}$ отсутствуют $inline$ -я строка и $inline$ -й столбец.

Если известна матрица скалярных произведений пар $G_{jb,ia}$ , то можно восстановить дистанционную матрицу $Q_{ij}$ на основании преобразования дистанции. Вначале расширяем подматрицу $G_{jb,ia}$ отсутствующей строкой $inline$ и столбцом $inline$ с нулевыми значениями. К полученной матрице применяем преобразование дистанции:

$Dist_{ij}(X) = X_{ii} + X_{jj} - X_{ij} - X_{ji}$

которое в нашем случае принимает вид тождества (3.9.5):

$Q_{ij} = G_{ib,ia} + G_{jb,ja} - G_{ib, ja} - G_{jb, ia} \quad(3.10.3)$

Совокупность формул (3.10.2) и (3.10.3) — один из способов получить дистанционную матрицу по заданному лапласиану. Удаляем из лапласиана какой-либо из узлов (пусть будет $inline$ ) и обращаем. Получаем матрицу скалярных произведений пар $G_{ia,ja}$ (ее другое название — фундаментальная матрица, см. следующую часть). Значение индекса $inline$ фиксировано — базовая вершина. В матрице $G_{ia,ja}$ первая вершина пар находится в базовом узле $inline$ , а вторая пробегает по остальным вершинам базиса.

Далее применяем к матрице $G_{ia,ja}$ преобразование дистанции (3.10.3).

Квадрат скалярного произведения, матрица Якоби

Если в графе изменить значение проводимости ребра (элемент лапласиана), то очевидно, что изменятся и все дистанции между вершинами (нормы векторов) $Q_{ij}$ . При увеличении проводимости дистанции должны сократиться (уменьшиться). Подарок богов в том, что можно оценить изменение дистанций не только качественно, но и количественно. Обозначим производную матрицы дистанций по лапласиану как

$Y_{ij,kl}=\partial Q_{ij} / \partial L^{kl} \quad(3.11.1)$

Тензор $Y_{ij,kl}$ — это матрица Якоби, то есть выражение изменений значений дистанционной матрицы $Q_{ij}$ при изменении значений лапласиана $L^{kl}$ . Оказывается, что данный тензор выражается через квадрат скалярного произведения пар:

$Y_{ij,kl}=(G_{ij,kl})^2=(Q_{il} + Q_{jk} - Q_{ik} - Q_{jl})^2/4 \quad(3.11.2)$

То есть изменение величины связи узлов $inline$ приводит к изменению дистанции между узлами $inline$ пропорционально величине скалярного произведения пар $inline$ и $inline$ .

Тензор квадросвязности вершин

Тензор квадратов скалярного произведения $Y_{ij,kl}$ обратим. Представим выражение (3.11) в следующем эквивалентном виде:

$\partial Q_{ij} = Y_{ij,kl} \space \partial L^{kl} \quad(3.11.3)$

Данную формулу можно трактовать как отклик $\partial Q_{ij}$ на воздействие $\partial L^{kl}$ . Тензор $Y_{ij,kl}$ играет роль передаточной функции (реакции на воздействие).

Возможна и обратная ситуация, при которой воздействие и отклик меняются местами. Прямая и обратная $Y^{ij,kl}$ передаточные функции связаны соотношением:

$Y_{ij,kl} Y^{kl,mn}=\delta_{ij}^{mn} \quad(3.12)$

Снова удача — тензор $Y^{ij,kl}$ можно выразить через лапласиан:

$Y^{ij,kl}=\partial L^{ij} / \partial Q_{kl}=( L^{il} L^{jk} + L^{ik} L^{jl})/2 \quad(3.13)$

Значения тензора $Y^{ij,kl}$ назовем квадросвязностью.

Свойства тензора квадросвязности

Значения тензора определены через значения лапласиана для 4-х вершин. Будем считать данные вершины вершинами графа. Допустим, что все 4 вершины различны:

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

Если пары имеют общую вершину, то смысл квадросвязности меняется. Это связано с тем, что диагональные элементы лапласиана не равны нулю (как в дистанционной матрице), а отражают общую связность (проводимость) узла.

$Y^{ki,kj}=( L^{ki} L^{kj} + L^{kk} L^{ij})/2 \quad(3.13.1)$

Пары вершин могут совпадать — диагональные элементы тензора квадросвязности.

$Y^{ij}=Q^{ij,ij}=(L^{ii} L^{jj} + (L^{ij})^2)/2 \quad(3.13.2)$

Здесь $Y^{ij}$ характеризует связь двух узлов i и j. Считается как сумма произведения их суммарной проводимости (степени вершины) $L^{ii} L^{jj}$ и квадрата связи между узлами $(L^{ij})^2$ .

Несмотря на то, что формально для тензора $Y^{ij,kl}$ могут вычисляться элементы вида $Y^{ij,ll}$ (одна из пар вырождена), данные (вырожденные) элементы являются линейно-зависимыми от остальных. Могут быть вычислены через сумму тензора по одному из индексов пары:

$Y^{ij,ll} = -Y^{ij,kl} 1_k \quad(3.13.3)$

___
Подведем итоги. Рассмотрено полезное во всех отношениях понятие скалярного произведения пар элементов. В следующей статье поработаем с подпространством графа — что это такое, и каковы его свойства.

Tags:

Hubs:

Mathematics