Эллипсоид и его основные свойства: различия между версиями
Artem (обсуждение | вклад) |
Artem (обсуждение | вклад) |
||
| (не показано 39 промежуточных версий этого же участника) | |||
| Строка 7: | Строка 7: | ||
\mathcal{E} (q, Q) = \{x \in \mathbb{R}^n | \langle x - q, Q^{-1}(x-q) \rangle \leqslant 1 \}. | \mathcal{E} (q, Q) = \{x \in \mathbb{R}^n | \langle x - q, Q^{-1}(x-q) \rangle \leqslant 1 \}. | ||
\end{equation} | \end{equation} | ||
| + | [[Файл:Ell.jpg|мини|Эллипсоид]] | ||
| + | Предполагается, что матрица $$Q$$ положительно определена, однако это не всегда так. В случае, если матрица $$Q$$ является вырожденной, эллипсоид также будет вырожденным, и плоским в направлениях собственных значений матрицы $$Q$$, равных нулю. | ||
===Опорная функция=== | ===Опорная функция=== | ||
| Строка 15: | Строка 17: | ||
==Основная часть== | ==Основная часть== | ||
| − | ===Утверждение=== | + | ===Аффинное преобразование=== |
| + | Аффинное преобразование - одна из простейших операций над эллипсоидами. Пусть дан эллипсоид $$\mathcal{E}(q,Q) \subseteq \mathbb{R}^n$$, матрица $$A \in \mathbb{R}^{m \times n}$$, вектор $$b \in \mathbb{R}^m$$. Тогда: | ||
| + | \[ | ||
| + | A\mathcal{E}(q,Q) + b = \mathcal{E}(Aq + b, AQA^T), \forall A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m. | ||
| + | \] | ||
| + | |||
| + | ===Утверждение 1=== | ||
''Опорной функцией эллипсоида является функция: | ''Опорной функцией эллипсоида является функция: | ||
\begin{equation}\label{eq2} | \begin{equation}\label{eq2} | ||
| Строка 24: | Строка 32: | ||
x^*(l) = q + \frac{Ql}{\sqrt{\langle l, Ql \rangle}}. | x^*(l) = q + \frac{Ql}{\sqrt{\langle l, Ql \rangle}}. | ||
\end{equation} | \end{equation} | ||
| − | ===Доказательство=== | + | ===Доказательство 1=== |
Пусть для начала $$q = 0$$ (рассмотрим эллипсоид, расположенный в нуле). Тогда требуется минимизировать скалярное произведение $$\langle l, x \rangle$$ при условии: | Пусть для начала $$q = 0$$ (рассмотрим эллипсоид, расположенный в нуле). Тогда требуется минимизировать скалярное произведение $$\langle l, x \rangle$$ при условии: | ||
\begin{equation}\label{eq1} | \begin{equation}\label{eq1} | ||
| Строка 39: | Строка 47: | ||
Приравняв правую часть к нулю, выразим опорный вектор: | Приравняв правую часть к нулю, выразим опорный вектор: | ||
\[ | \[ | ||
| − | x^* = -\frac{ | + | x^* = -\frac{Ql}{2\lambda}. |
\] | \] | ||
Тогда, подставив его в $$\eqref{eq1}$$, найдем $$\lambda$$ и получим опорный вектор: | Тогда, подставив его в $$\eqref{eq1}$$, найдем $$\lambda$$ и получим опорный вектор: | ||
| Строка 45: | Строка 53: | ||
x^* = \frac{Ql}{\sqrt{\langle l, Ql \rangle}}. | x^* = \frac{Ql}{\sqrt{\langle l, Ql \rangle}}. | ||
\] | \] | ||
| − | Следовательно, опорная функция в направлении $l \neq 0$ равна: | + | Следовательно, опорная функция в направлении $$l \neq 0$$ равна: |
\[ | \[ | ||
\rho(l|\mathcal{E}) = \bigg\langle l, \frac{Ql}{\sqrt{\langle l, Ql \rangle}} \bigg\rangle = \sqrt{\langle l, Ql \rangle}. | \rho(l|\mathcal{E}) = \bigg\langle l, \frac{Ql}{\sqrt{\langle l, Ql \rangle}} \bigg\rangle = \sqrt{\langle l, Ql \rangle}. | ||
\] | \] | ||
| − | + | Согласно свойству аффинного преобразования, при смещении центра эллипсоида в точку $$q \neq 0$$, выражения для опорной функции и соответствующего ей вектора также сместятся, т.е. мы получим $$\eqref{eq2}$$ и $$\eqref{eq3}$$. Утверждение доказано. | |
| + | |||
| + | ===Немного о поиске $$\lambda$$=== | ||
| + | \[ | ||
| + | x = -\frac{Ql}{2\lambda} | ||
| + | \] | ||
| + | Подставим это значение в $$\eqref{eq1}$$: | ||
| + | \begin{equation}\label{eq4} | ||
| + | \bigg\langle -\frac{Ql}{2\lambda}, -Q^{-1}\frac{Ql}{2\lambda} \bigg\rangle = 1. | ||
| + | \end{equation} | ||
| + | При этом, | ||
| + | \[ | ||
| + | \langle l, x \rangle \rightarrow \max\limits_{x \in \mathcal{E}}. | ||
| + | \] | ||
| + | Преобразуем $$\eqref{eq4}$$: | ||
| + | \[ | ||
| + | \bigg\langle -\frac{Ql}{2\lambda}, -\frac{l}{2\lambda} \bigg\rangle = 1 \Leftrightarrow | ||
| + | \bigg( \frac{1}{2\lambda} \bigg)^2 \langle Ql, l \rangle = 1 \Leftrightarrow | ||
| + | \frac{1}{4\lambda^2} \langle Ql, l \rangle = 1. | ||
| + | \] | ||
| + | Из этого следует: | ||
| + | \[ | ||
| + | \lambda^2 = \frac{\langle Ql, l \rangle}{4} \Rightarrow \lambda_{1,2} = \pm \frac{\sqrt{\langle | ||
| + | Ql, l \rangle}}{2} = \pm \frac{\sqrt{\langle l, Ql \rangle}}{2}. | ||
| + | \] | ||
| + | $$Q$$ --- положительно определенная матрица, поэтому подходит положительная $$\lambda$$. | ||
| − | ===Замечание=== | + | ===Замечание 1=== |
Поскольку выпуклое множество однозначно определяется своей опорной функцией, то эллипсоид можно определить как: | Поскольку выпуклое множество однозначно определяется своей опорной функцией, то эллипсоид можно определить как: | ||
\[ | \[ | ||
| − | \mathcal{E}(q, Q) = \{ x \in \mathbb{R}^n| \langle x, l \rangle\ \leqslant \langle l, q \rangle\ + \langle l, Ql \rangle^{\frac{1}{2}}}, | + | \mathcal{E}(q, Q) = \{ x \in \mathbb{R}^n| \langle x, l \rangle\ \leqslant \langle l, q \rangle\ + \langle l, Ql \rangle^{\frac{1}{2}} \}, |
\] | \] | ||
| + | где $$q \in \mathbb{R}^n, Q \in \mathbb{R}^{n \times n}, Q' = Q > 0$$. | ||
| + | |||
| + | ===Объем эллипсоида=== | ||
| + | Объем эллипсоида $$\mathcal{E}(q,Q), Q \in \mathbb{R}^{n \times n}, q \in \mathbb{R}^n $$ вычисляется по формуле: | ||
| + | \begin{equation} | ||
| + | \mathbb{V}(\mathcal{E(q,Q)}) = | ||
| + | \begin{cases} | ||
| + | \frac{\pi^{\frac{n}{2}}}{(\frac{n}{2})!}\sqrt{\det(Q)}, n = 2k, k \in \mathbb{N}, \\ | ||
| + | \frac{2^n\pi^{\frac{n-1}{2}}(\frac{n-1}{2})!}{n!}\sqrt{\det(Q)}, n = 2k-1, k \in \mathbb{N}. | ||
| + | \end{cases} | ||
| + | \end{equation} | ||
Текущая версия на 16:09, 28 декабря 2022
Данная глава посвящена рассмотрению эллипсоида и его основных свойств.
Содержание
Определения
Эллипсоид
Эллипсоидом $$\mathcal{E} (q, Q)$$ с центром в точке $$q \in \mathbb{R}^n$$ и матрицей $$Q \in \mathbb{R}^{n \times n}$$, такой, что $$Q' = Q > 0$$, будем называть множество точек: \begin{equation} \mathcal{E} (q, Q) = \{x \in \mathbb{R}^n | \langle x - q, Q^{-1}(x-q) \rangle \leqslant 1 \}. \end{equation}
Предполагается, что матрица $$Q$$ положительно определена, однако это не всегда так. В случае, если матрица $$Q$$ является вырожденной, эллипсоид также будет вырожденным, и плоским в направлениях собственных значений матрицы $$Q$$, равных нулю.
Опорная функция
Опорной функцией выпуклого замкнутого множества $$A$$ в направлении $$l \neq 0$$ называется функция: \begin{equation} \rho(l|A) = \sup\limits_{x \in A} \langle l, x \rangle. \end{equation}
Основная часть
Аффинное преобразование
Аффинное преобразование - одна из простейших операций над эллипсоидами. Пусть дан эллипсоид $$\mathcal{E}(q,Q) \subseteq \mathbb{R}^n$$, матрица $$A \in \mathbb{R}^{m \times n}$$, вектор $$b \in \mathbb{R}^m$$. Тогда: \[ A\mathcal{E}(q,Q) + b = \mathcal{E}(Aq + b, AQA^T), \forall A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m. \]
Утверждение 1
Опорной функцией эллипсоида является функция: \begin{equation}\label{eq2} \rho(l|\mathcal{E}) = \langle l, q \rangle + \sqrt{\langle l, Ql \rangle}, \end{equation} а опорный вектор в направлении $$l$$ равен: \begin{equation}\label{eq3} x^*(l) = q + \frac{Ql}{\sqrt{\langle l, Ql \rangle}}. \end{equation}
Доказательство 1
Пусть для начала $$q = 0$$ (рассмотрим эллипсоид, расположенный в нуле). Тогда требуется минимизировать скалярное произведение $$\langle l, x \rangle$$ при условии: \begin{equation}\label{eq1} \langle x, Q^{-1}x \rangle = 1. \end{equation} Выпишем лагранжиан для данной задачи: \[ \mathcal{L} = \langle l, x \rangle + \lambda(\langle x, Q^{-1}x \rangle -1). \] Отсюда получим: \[ \frac{\partial \mathcal{L}}{\partial x} = l + 2 \lambda Q^{-1}x. \] Приравняв правую часть к нулю, выразим опорный вектор: \[ x^* = -\frac{Ql}{2\lambda}. \] Тогда, подставив его в $$\eqref{eq1}$$, найдем $$\lambda$$ и получим опорный вектор: \[ x^* = \frac{Ql}{\sqrt{\langle l, Ql \rangle}}. \] Следовательно, опорная функция в направлении $$l \neq 0$$ равна: \[ \rho(l|\mathcal{E}) = \bigg\langle l, \frac{Ql}{\sqrt{\langle l, Ql \rangle}} \bigg\rangle = \sqrt{\langle l, Ql \rangle}. \] Согласно свойству аффинного преобразования, при смещении центра эллипсоида в точку $$q \neq 0$$, выражения для опорной функции и соответствующего ей вектора также сместятся, т.е. мы получим $$\eqref{eq2}$$ и $$\eqref{eq3}$$. Утверждение доказано.
Немного о поиске $$\lambda$$
\[ x = -\frac{Ql}{2\lambda} \] Подставим это значение в $$\eqref{eq1}$$: \begin{equation}\label{eq4} \bigg\langle -\frac{Ql}{2\lambda}, -Q^{-1}\frac{Ql}{2\lambda} \bigg\rangle = 1. \end{equation} При этом, \[ \langle l, x \rangle \rightarrow \max\limits_{x \in \mathcal{E}}. \] Преобразуем $$\eqref{eq4}$$: \[ \bigg\langle -\frac{Ql}{2\lambda}, -\frac{l}{2\lambda} \bigg\rangle = 1 \Leftrightarrow \bigg( \frac{1}{2\lambda} \bigg)^2 \langle Ql, l \rangle = 1 \Leftrightarrow \frac{1}{4\lambda^2} \langle Ql, l \rangle = 1. \] Из этого следует: \[ \lambda^2 = \frac{\langle Ql, l \rangle}{4} \Rightarrow \lambda_{1,2} = \pm \frac{\sqrt{\langle Ql, l \rangle}}{2} = \pm \frac{\sqrt{\langle l, Ql \rangle}}{2}. \] $$Q$$ --- положительно определенная матрица, поэтому подходит положительная $$\lambda$$.
Замечание 1
Поскольку выпуклое множество однозначно определяется своей опорной функцией, то эллипсоид можно определить как: \[ \mathcal{E}(q, Q) = \{ x \in \mathbb{R}^n| \langle x, l \rangle\ \leqslant \langle l, q \rangle\ + \langle l, Ql \rangle^{\frac{1}{2}} \}, \] где $$q \in \mathbb{R}^n, Q \in \mathbb{R}^{n \times n}, Q' = Q > 0$$.
Объем эллипсоида
Объем эллипсоида $$\mathcal{E}(q,Q), Q \in \mathbb{R}^{n \times n}, q \in \mathbb{R}^n $$ вычисляется по формуле: \begin{equation} \mathbb{V}(\mathcal{E(q,Q)}) = \begin{cases} \frac{\pi^{\frac{n}{2}}}{(\frac{n}{2})!}\sqrt{\det(Q)}, n = 2k, k \in \mathbb{N}, \\ \frac{2^n\pi^{\frac{n-1}{2}}(\frac{n-1}{2})!}{n!}\sqrt{\det(Q)}, n = 2k-1, k \in \mathbb{N}. \end{cases} \end{equation}
