Сумма двух эллипсоидов. Внутренние и внешние оценки

Данная глава посвящена рассмотрению суммы двух эллипсоидов, будут выведены внутренние и внешние оценки. Здесь и далее в главе рассматриваются исключительно невырожденные эллипсоиды. \begin{gather*} \mathcal{E}_{1} = \mathcal{E} (a, Q_{1}); \\ \mathcal{E}_{2} = \mathcal{E} (a, Q_{2}); \\ \end{gather*}

Определения

Определение 1

Пусть даны два множества $$\mathcal{H}_1, \mathcal{H}_2 \subset \mathbb{R}^n$$, геометрической суммой(суммой по Минковскому) называется следующая сумма: \begin{equation} \mathcal{H}_1 + \mathcal{H}_2 = \bigcup_{h_1 \in \mathcal{H}_1} \bigcup_{h_2 \in \mathcal{H}_2} \{ h_1 + h_2\} \end{equation}

Определение 2

Пусть даны два эллипсоида $$\mathcal{E}_{1} = \mathcal{E} (a, Q_{1}), \mathcal{E}_{2} = \mathcal{E} (a, Q_{2})$$, будем рассматривать их сумму $$\mathcal{E}_{1} + \mathcal{E}_{2}$$. Внешней оценкой будем называть $$\mathcal{E}_+^{(+)}$$: \begin{equation} \mathcal{E}_{1} + \mathcal{E}_{2} \subseteq \mathcal{E}_+^{(+)}; \end{equation} Внутренней оценкой будем называть $$\mathcal{E}_+^{(-)}$$: \begin{equation} \mathcal{E}_+^{(-)} \subseteq \mathcal{E}_{1} + \mathcal{E}_{2} \end{equation}

Леммы

Лемма 1

(a) Эллипсоид \( \mathcal{E} = \mathcal{E}(a_1 + a_2, Q(P)), p > 0\) верно определен, а его внешняя оценка суммы \(\mathcal{E}_1 + \mathcal{E}_2\) суть есть \[ \mathcal{E}_1 + \mathcal{E}_2 \subseteq \mathcal{E} (a_1 + a_2,Q(p)) \] для любого \(p > 0 \) \[\] (b) По данному вектору \( l \in R^n, \|l\| = 1\) выражение \[ p = (Q_1l,l)^{\frac{1}{2}}(Q_2l,l)^{-\frac{1}{2}} \] определяет параметр \(p \in \Pi^{+}\), такой что \[ \rho(l|\mathcal{E} (a_1 + a_2,Q(p))) = \rho(l|\mathcal{E}(a_1,Q_1) + \mathcal{E}(a_2,Q_2))\] И обратно, по данному параметру \(p \in \Pi^{+}\), существует вектор \( l \in R^n, \|l\| = 1\), удовлетворяющий вышеуказанные равенства.

Лемма 2

Зафиксируем вектор \( l \in R^n, \|l\| = 1\) и предположим, что для некоторого \( m \in [0,n]\) имеем \[ l_j = 0, если j \in \overline{1,m}\\ l_j \neq 0, если j = \overline{m+1,n} \] Помимо этого будем считать, что $$\mathcal{E}_1 = \mathcal{E}(0,Q_1), \mathcal{E}_2 = \mathcal{E}(0,Q_2)$$, а матрицы Q_1, Q_2 диагональные. В таком случае следующее верно: \[ \mathcal{E}_1 + \mathcal{E}_2 \subseteq \mathcal{E}(0, C) \subseteq \mathcal{E}(0, Q), \] а также \[\rho(l|\mathcal{E}(0, Q)) = \rho(l|\mathcal{E}_1 + \mathcal{E}_2) \] Тогда \[ c_{ij} \text{ для всех } i \neq j, i \in \overline{m+1,n} \]

Лемма 3

Возьмем эллипсоид \(\mathcal{E}(0, C)\)вместе с \(\mathcal{E}_1 = \mathcal{E}(0,Q_1), \mathcal{E}_2 = \mathcal{E}(0,Q_2),\) предполагая \(Q_1 \text{ и } Q_2 \)диагональными. Также считаем данным вектор \( l \in R^n, \|l\| = 1\), параметр \(p\) считается известным ввиду Леммы 1. Тогда: \[ \mathcal{E}_1 + \mathcal{E}_2 \subseteq \mathcal{E}(0, C) \subseteq \mathcal{E}(0, Q(p)) \] и \[ \rho(l|\mathcal{E}(0, Q(p))) = \rho(l|\mathcal{E}_1 + \mathcal{E}_2) \] тогда \[ \mathcal{E}(0,Q(p)) = \mathcal{E}(0, C)\text{ и }p\in\Pi^{+} \]

Теоремы

Теорема 1

Предполагая, что \(\mathcal{E}_1 = \mathcal{E}(a_1,Q_1), \mathcal{E}_2 = \mathcal{E}(a_2,Q_2),\) предполагая \(Q_1 \text{ и } Q_2 \) положительно определенными, а также \(Q(p)\) определенным в соответствии с Леммой 1.
Тогда внутренне множество достижимости сумм \( \mathcal{E}_1 + \mathcal{E}_2\) состоит из эллипсоидов вида \( \mathcal{E}(a_1 + a_2, Q(p)), где p\in\Pi^{+}\)

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

Не ограничивая общности, ссылаясь на Лемму из первого раздела, мы можем предложить, что все центры эллипсоидов находятся в нуле, т.е.\(a_1 = a_2 = 0\)
Пусть есть такой эллипсоид, что \( \mathcal{E}_1 + \mathcal{E}_2 \subseteq \mathcal{E}(0, Q)\).Давайте найдем параметр \(p\), такой, чтобы эллипсоид \(\mathcal{E}(0, Q(p))\) был зажат между \(\mathcal{E}(0, Q)\) и \( \mathcal{E}_1 + \mathcal{E}_2 \). Итого мы имеем \[ \mathcal{E}_1 + \mathcal{E}_2 \subseteq \mathcal{E}(0, Q(p)) \subseteq \mathcal{E}(0, Q) \] Мы можем считать, что \(\mathcal{E}(0, Q)\) касательно к \(\mathcal{E}_1 + \mathcal{E}_2\), предполагая существование вектора \( l = \overline l \in R^n, \|\overline l\| = 1\), такое, что \[ \rho(\overline l|\mathcal{E}(0, Q)) = \rho(\overline l|\mathcal{E}_1 + \mathcal{E}_2) \] Давайте теперь выберем обратимую матрицу T такую, чтобы матрицы \( Q^{*}_1 = T'Q^{*}_1T ,Q^{*}_2 = T'Q^{*}_2T\) были бы обе диагональными. Существование подобной трансформационной матрицы T следует из результатов Линейной Алгебры и теории матриц.
Трансформационная матрица Т очевидно не подчиняется включению \( \mathcal{E}_1 + \mathcal{E}_2 \subseteq \mathcal{E}(0, Q^{*})\) так мы имеем \( Q^{*} = T'QT\) \[ \mathcal{E}(0, Q^{*}_1) + \mathcal{E}(0, Q^{*}_2) \subseteq \mathcal{E}(0, Q^{*}) \] Пользуясь отображением \( l = T z \) можно преобразовать тождество \[ (\overline l, Q \overline l)^{\frac{1}{2}} = (\overline l, Q_1 \overline l)^{\frac{1}{2}} + (\overline l, Q_2 \overline l)^{\frac{1}{2}} \]

К виду \[ (\overline z, Q^{*} \overline z)^{\frac{1}{2}} = (\overline z, Q^{*}_1 \overline z)^{\frac{1}{2}} + (\overline z, Q^{*}_2 \overline z)^{\frac{1}{2}} \]

где \(\overline z = T^{-1} \overline l \) Далее можно будут справедливыми следующие преобразования:

\[ \overline p = (\overline z, Q^{*}_1 \overline z)^{\frac{1}{2}} (\overline z, Q^{*}_2 \overline z)^{-\frac{1}{2}} \]

\[ Q^{*}(\overline p) = (1 + \overline p^{-1})Q^{*}_1 + (1 + \overline p)Q^{*}_2 \] Приходим к соотношению

\[ \mathcal{E}(0, Q^{*}_1) + \mathcal{E}(0, Q^{*}_2) \subseteq \mathcal{E}(0, Q^{*}(\overline p)) \]

\[ \rho(\overline z|\mathcal{E}(0, Q^{*}_1)) +\rho(\overline z|\mathcal{E}(0, Q^{*}_2)) = \rho(\overline z|\mathcal{E}(0, Q^{*}(\overline p)) = \rho(\overline z|\mathcal{E}(0, Q^{*}) \]

Из Леммы 3 Существует вектор \( z^{*}\) удовлетворяющий следующее: \[ \rho(z^{*}|\mathcal{E}(0, Q^{*}(\overline p))) \gt \rho(z^{*}|\mathcal{E}(0, Q^{*})) \]

Очевидно , что вектора \( z^{*}\) и \(\overline z \) неколлинеарны. Определим пространство Z как пространство, натянутое на данные векторы. А \(\mathcal{E}_z (0, Q) \) есть проекция эллипсоида на пространство Z.

\[ \mathcal{E}_z (0, Q^{*}) \subseteq \mathcal{E}_z (0, Q^{*}(\overline p)) \]

\[ \rho(\overline z|\mathcal{E}_z (0, Q^{*})) = \rho(\overline z|\mathcal{E}_z (0, Q^{*}(\overline p))) = \rho(\overline z|\mathcal{E}_z (0, Q^{*}_1) + \mathcal{E}_z (0, Q^{*})_2) \]

Из результатов Леммы 3 \( \mathcal{E}_z (0, Q^{*}) = \mathcal{E}_z (0, Q^{*}(p)) \) ЧТД