Alignment of time series with use of the generalized Legendre's transformation and methods of idempotenty mathematics

Maria V. Kurkina; Куркина Мария Викторовна; Sergey P. Semenov; Семенов Сергей Петрович; Viktor V. Slavsky; Славский Виктор Владимирович; Olga V. Samarina; Самарина Ольга Владимировна; Olga A. Petuhova; Петухова Ольга Анатольевна; Aleksey A. Petrov; Петров Алексей Аверьянович; Anton A. Finogenov; Финогенов Антон Анатольевич; Valeriy A. Samarin; Самарин Валерий Анатольевич

doi:10.17816/byusu2020375-82

Выравнивание временных рядов с использованием обобщенного преобразования Лежандра и методов идемпотентой математики

Авторы: Куркина М.В.¹, Семенов С.П.¹, Славский В.В.¹, Самарина О.В.¹, Петухова О.А.¹, Петров А.А.¹, Финогенов А.А.¹, Самарин В.А.¹
Учреждения:
1. Югорский государственный университет
Выпуск: Том 16, № 3 (2020)
Страницы: 75-82
Раздел: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
Статья опубликована: 28.10.2020
URL: https://vestnikugrasu.org/byusu/article/view/59631
DOI: https://doi.org/10.17816/byusu2020375-82
ID: 59631

Цитировать

Полный текст

Аннотация
Полный текст
Об авторах
Список литературы
Дополнительные файлы
Статистика

Аннотация

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

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

В последние годы в рамках международного центра «Софус Ли» получила интенсивное развитие новая область математики – идемпотентная, или «тропическая», математика, что отражено в работах академика В. П. Маслова и его учеников: Г. Л. Литвинова, А. Н. Соболевского и др.

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

По аналогии с полярным преобразованием конформно-плоской римановой метрики, введенным в работах Е. Д. Родионова и В. В. Славского, строится абстрактный идемпотентный аналог преобразования Лежандра. Исследуются его возможности для цифровой обработки временных рядов.

Ключевые слова

идемпотентный анализ, временные ряды, конформно-выпуклые функции, преобразование Лежандра, выпуклое и вогнутое замыкание функции

Полный текст

Введение

Пусть функция $f : R^{n} \to R$ задана на евклидовом арифметическом пространстве. Преобразованием Юнга – Фенхеля функции $f$ называют функцию $f^{*}$ , где

$f^{*} (ξ) = \underset{x}{s u p} [(ξ, x) - f (x)]$ (1)

Формула (1) есть обобщение классического преобразования Лежандра для достаточно гладких функций $f$ и $f^{*}$ , в этом случае $f$ и $f^{*}$ связаны соотношением

$(x, ξ) = f (x) + f^{*} (ξ)$ , где $ξ = \nabla f (x)$ , $x = \nabla f^{*} (ξ)$

Если ограничиться случаем n=1, то скалярное произведение $(ξ, x)$ есть просто произведение двух чисел, тогда:

$x \cdot ξ = f (x) + f^{*} (ξ)$ , $ξ = \frac{d f (x)}{d x}$ , $x = \frac{d f^{*} (ξ)}{d ξ}$ /

Преобразование Лежандра обладает рядом замечательных свойств. Нас в нашей работе будут интересовать следующие свойства:

неравенство x $ξ \leq f (x) + f^{*} (ξ)$ которое является обобщением неравенства Юнга,
в случае выпуклых функций преобразование Лежандра инволютивно $f^{* *} = f$ ,
в общем случае $f^{* *} \leq f$ и $f^{* *}$ есть выпуклая оболочка (или замыкание) функции $f$ .

Преобразование Лежандра применяется в физике, в теории дифференциальных уравнений, в теории выпуклых множеств [1-18]. Из новых применений преобразования Лежандра можно отметить применение в цифровой обработке сигналов [1-3].

Полярное преобразование конформно-плоской метрики с неотрицательной одномерной кривизной

В данной части мы используем обозначения и результаты работы [5]. Пусть R – числовая прямая, $R^{n + 1}$ – евклидово (n+1) -мерное арифметическое пространство, $M^{n + 2} = R^{n + 1} \times R$ – псевдоевклидово пространство, скалярный квадрат вектора $\vec{w} = [\vec{x}, ζ] \in M^{n + 2}$ в котором равен ${<\vec{w}>}^{2} = | \vec{x} |^{2} - ζ^{2}$ , где $| \vec{x} |^{2}$ – скалярный квадрат вектора $\vec{x} \in R^{n + 1}$ . Обозначим через

$C^{+} = {[\vec{x}, ζ] \in M^{n + 2} : | \vec{x} |^{2} - ζ^{2} = 0, ζ > 0}$ ,

верхнюю часть изотропного конуса в $M^{n + 2}$ . В дальнейшем, если будет ясно из контекста, мы будем обозначать $x^{2}$ через x.

Лемма 1. Пусть на единичной сфере $S^{n} \subset R^{n + 1}$ задана конформно-плоская метрика

$s^{2} = \frac{d x^{2}}{f^{2} (x)}$ , $x \in S^{n} \subseteq R^{n + 1}$ ,

где $f (x)$ функция класса c¹. Тогда определено каноническое изометрическое вложение, задаваемое формулой

$Z : x \in S^{n} \to [\frac{x}{f (x)}, \frac{1}{f (x)}] \in C^{+}$ . (2)

Образ $Z (S^{n}) = F \subseteq C^{+}$ – пространственно подобная n -мерная поверхность. Будем отождествлять конформно-плоскую метрику с поверхностью F. Предположим, что функция достаточно гладкая, тогда поверхность регулярна, и в каждой точке $Z (x) \in F$ определено касательное n -мерное пространство $T_{x} (F)$ . Существует единственный вектор $Z^{*} (x) \in C^{+}$ такой, что

$⟨ Z, Z^{*} ⟩ = - 1$ , $Z^{*} ⊥ T_{x} (F)$ , (3)

где ортогональность понимается относительно скалярного произведения в $M^{n + 2}$ .

Лемма 2. Пусть функция $f (\vec{x})$ , задающая конформно-плоскую метрику, по однородности распространена на все пространство $R^{n + 1}$ . Тогда вектор Z^* явно выражается через $f$ и $\vec{\nabla} f$ в $R^{n + 1}$ :

$Z^{*} (\vec{x}) = [- \vec{\nabla} f + \frac{| \vec{\nabla} f |^{2}}{2 f \vec{x}}, \frac{| \vec{\nabla} f |^{2}}{2 f}]$ , (4)

где $\vec{x} \in S^{n} \subset R^{n + 1}$ , $\vec{\nabla} f$ градиент функции $f$ в пространстве $R^{n + 1}$ .

Определение 1. Если точка $Z \in F$ пробегает поверхность F, то точка Z^* пробегает двойственную поверхность F^*. Соответствующую конформно-плоскую метрику $d {s^{*}}^{2} = \frac{d y^{2}}{{f^{*}}^{2} (y)}$ , $y \in S^{n}$ будем называть полярной к исходной метрике [14]. Сравнивая формулы (2) и (4), имеем:

$[- \vec{\nabla} f + \frac{| \nabla f |^{2}}{2 f} \vec{x}, \frac{| \nabla f |^{2}}{2 f}] \equiv [\frac{y}{f^{*} (y)}, \frac{1}{f^{*} (y)}]$ .

Откуда получаем формулы для перехода к полярной конформно-плоской метрике в параметрическом виде:

$f^{*} (y) = \frac{2 f (x)}{| \nabla f |^{2}}$ , $\vec{y} = \vec{x} - 2 f (x) \frac{\vec{\nabla} f}{| \nabla f |^{2}}$ . (5)

Лемма 3. Пусть $f : R^{n + 1} \to R$ произвольная однородная степени один функция на $R^{n + 1}$ . Отображение $H_{f} : S^{n} \to S^{n}$ , определяемое формулой

$H_{f} : \vec{x} \in S^{n} \to \vec{x} - 2 f (x) \frac{\vec{\nabla} f}{| \nabla f |^{2}} \in S^{n}$ , (6)

сохраняет норму вектора: $| H_{f} (\vec{x}) | = | \vec{x} |$ .

Определение 2. Отображение $H_{f}$ назовем конформным градиентом функции $f$ . Если отображение $H_{f}$ имеет обратное $H_{f}^{- 1}$ , то полярная метрика определяется в явном виде функцией:

$f^{*} (y) = \frac{2 f (x)}{| \nabla f |^{2}} |_{x = H_{f}^{- 1} (y)}$ .

Замечание. Из определения (1) следует двойственность метрики $d s^{2} = \frac{d x^{2}}{f^{2} (x)}$ , $x \in S^{n}$ и метрики $d {s^{*}}^{2} = \frac{d y^{2}}{{f^{*}}^{2} (y)}$ , $y \in S^{n}$ . Поэтому при наличии соответствующей регулярности функции $f^{*} (y)$ будут справедливы равенства:

$f^{*} (y) = \frac{2 f (x)}{| \nabla f (x) |^{2}}$ , $\vec{y} = \vec{x} - 2 f (x) \frac{\vec{\nabla} f (x)}{| \nabla f (x) |^{2}}$ ,

$f (x) = \frac{2 f^{*} (y)}{| \nabla f^{*} (y) |^{2}}$ , $\vec{x} = \vec{y} - 2 f^{*} (y) \frac{\vec{\nabla} f^{*} (y)}{| \nabla f^{*} (y) |^{2}}$ (7)

Определение 3. Одномерная секционная кривизна конформно-плоской метрики $d s^{2} = \frac{d x^{2}}{f^{2} (x)}$ в задается формулой [16-18]:

$K_{1 / 2} (f, x, ξ) = f \frac{d^{2} f}{d ξ^{2}} - \frac{1}{2} | \nabla f |^{2}$ . (8)

здесь $\frac{d^{2} f}{d ξ^{2}}$ – вторая производная функции в точке $x \in R^{n}$ вдоль единичного вектора $ξ$ , $\nabla f$ – градиент функции $f$ в $R^{n}$ . Формула верна как в плоском случае, так и для единичной сферы, в этом случае функция $f : S^{n} \to R$ продолжается по однородности на $R^{n + 1}$ , $x \in S^{n} \subset R^{n + 1}$ , $ξ$ – единичный касательный к сфере в точке x вектор, $\nabla f$ – градиент функции в $R^{n + 1}$ .

Определение 4. Формулу (1) можно распространить на конформно-плоские метрики, определенные на единичной n-мерной сфере $S^{n} \subset R^{n + 1}$ в форме:

$f^{*} (y) = \underset{x_{e} S^{n}}{m a x} \frac{P x - y P^{2}}{2 f (x)}$ , или $h^{*} (y) = \underset{x_{e} S^{n}}{m a x} \frac{P x - y P}{\sqrt{2} h (x)}$ , (9)

здесь $h (x) = \sqrt{f (x)}$ – положительная конформно-выпуклая функция на сфере [6], то есть функция, для которой конформно-плоская метрика $d s^{2} = \frac{d x^{2}}{f^{2} (x)}$ имеет неотрицательную одномерную секционную кривизну. Равносильное условие функции на $h (x)$ имеет вид:

$h (x) \leq \frac{h (x_{2}) ‖ x - x_{1} ‖}{‖ x_{2} - x_{1} ‖} + \frac{h (x_{1}) ‖ x - x_{2} ‖}{‖ x_{2} - x_{1} ‖}$

для произвольных точек $x_{2}, x, x_{1} \in S^{n}$ , $‖ y - x ‖$ – хордовое расстояние между точками на сфере, $h^{*} (y)$ , $y \in S^{n}$ – функция, задающая двойственную или полярную метрику $d s^{*} = \frac{d y}{h^{* 2} (y)}$ . Причем основные свойства (инволютивность и т. д.) сохраняются. В работе [8] было предложено также назвать преобразование (9) преобразованием Лежандра функции $f (x)$ , $x \in S^{n}$ .

Определение 5. Обобщая эти понятия, приходим к определению обобщенного преобразования Лежандра с формулой:

$h^{*} (y_{j}) = \underset{x_{i} \in S^{n}}{m a x} \frac{||y_{j} - x_{i}||}{\sqrt{2} h (x_{i})}$ , (10)

где X – компактное метрическое пространство, A(x, y) неотрицательная непрерывная симметричная функция $(x, y) \in X \times X$ , $A (x, x) \equiv 0$ , $, ℎ (𝑥)$ – положительная непрерывная функция, $h^{*} (y)$ её преобразование Лежандра. Функцию $A (x, y)$ будем называть ядром преобразования.

С вычислительной точки зрения формула (10) имеет дискретный вид;

$h^{*} (y_{j}) = \underset{x_{i} \in S^{n}}{m a x} \frac{||y_{j} - x_{i}||}{\sqrt{2} h (x_{i})}$ , (11)

где {x_i} – конечная сетка точек на сфере. В данной работе предлагается дальнейшее абстрактное обобщение формулы (11) для идемпотентной математики.

Определение 6. Пусть n>1, $R_{n}^{+}$ – множество наборов $f = {f_{i}}$ , i=1, ..., n положительных чисел, $A = ‖ A_{j i} ‖$ $i, j = 1, \dots, n$ – симметричная квадратная матрица неотрицательных чисел с нулевой диагональю. Обозначим через L_A отображение множества $R_{n}^{+}$ в себя $L_{A} : R_{n}^{+} \to R_{n}^{+}$ , определяемое формулой $L_{A} [{f_{i}}] = {f_{j}^{*}}$ , где

$f_{j}^{*} = \underset{i}{m a x} \frac{A_{j i}}{f_{i}}$ . (12)

Замечание. В формуле (12) участвуют только две операции над неотрицательными числами – умножение (деление) и max (min), с помощью функции log это множество чисел можно отождествить с идемпотентным полукольцом $R_{m a x}$ см. [9[, [7].

Теорема 1. Преобразование (12) полукольца обладает основными свойствами классического преобразования Лежандра:

справедливо неравенство $f_{j}^{*} \cdot f_{i} \geq A_{j i}$ ,
$f_{i}^{* * *} = f_{i}^{*}$ $i = 1, \dots, n$ ,
$f_{i}^{* *} = f_{i}^{}$ $i = 1, \dots, n$ .

где ${f_{i}^{*}} = L_{A} [{f_{i}}]$ , ${f_{i}^{* *}} = L_{A} [{f_{i}^{*}}],$ , ${f_{i}^{* * *}} = L_{A} [{f_{i}^{* *}}],$ .

Пример 1. Рассмотрим, как выглядит при , пусть матрица имеет вид:

$A = [\begin{matrix} 0 & a & b \\ a & 0 & c \\ b & c & 0 \end{matrix}]$

Тогда ${f_{i}^{*}} = L_{A} [{f_{i}}]$ , ${f_{i}^{* *}} = L_{A} [{f_{i}^{*}}],$ имеют вид:

$f_{1}^{*} = m a x (\frac{a}{f_{2}}, \frac{b}{f_{3}}), f_{1}^{* *} = m a x (a m i n (\frac{f_{1}}{a}, \frac{f_{3}}{c}), b m i n (\frac{f_{1}}{b}, \frac{f_{2}}{c}))$ ,

$f_{2}^{*} = m a x (\frac{a}{f_{1}}, \frac{c}{f_{3}}), f_{2}^{* *} = m a x (c m i n (\frac{f_{1}}{b}, \frac{f_{2}}{c}), a m i n (\frac{f_{2}}{a}, \frac{f_{3}}{b}))$ ,

$f_{2}^{*} = m a x (\frac{b}{f_{1}}, \frac{c}{f_{2}}), f_{3}^{* *} = m a x (c m i n (\frac{f_{1}}{a}, \frac{f_{3}}{c}), b m i n (\frac{f_{2}}{a}, \frac{f_{3}}{b}))$

Замечание. Как показали численные эксперименты, если матрица A в теореме 1 не обладает требуемыми свойствами, то теорема не верна.

Гипотеза. Теорема 1 справедлива в случае абстрактного полукольца.

Пример 2. Преобразование Лежандра периодического сигнала (временного ряда). Будем трактовать временной ряд как положительную функцию на единичной окружности и сопоставим ей конформно-плоскую метрику (меру) $d s = \frac{d φ}{h^{2} (φ)}$ на окружности S¹, здесь $h (ϕ)$ – периодическая функция. Формула (11) примет вид:

$h^{*} (ψ_{j}) = m a x_{i} \frac{a b s [\sin (\frac{ψ_{j} - φ_{i}}{2})]}{\sqrt{2} h (φ_{i})}$ ,

На рисунках 1, 2 приведены примеры преобразования Лежандра временного ряда P0. На рис. 1 P1=P0^* – нижний «выпуклый» огибающего ряда P0.

Рисунок 1 к примеру 2: $P 0 \geq P 0^{*} = P 1$

Рисунок 2 к примеру 2: $P 2 = {- P 0}^{*} \geq P 0 \geq P 0^{*}$

Код в системе MATLAB к примеру 2 n=1000.

Заключение

В данной работе по аналогии с полярным преобразованием конформно-плоской метрики (Родионов Е. Д., Славский В. В.) и классическим преобразованием Лежандра строится идемпотентный аналог преобразования Лежандра. Приведена программа в системе MATLAB, реализующая численное преобразование временных рядов. В дальнейшем предполагается использовать её возможности при цифровой обработке сигналов и изображений и в задачах распознавания временных рядов.