Инструменты сайта


English version

Вычисление расстояний между геометрическими объектами

Расстояние между точками $ X=(x_{1},\dots,x_n) $ и $ Y=(y_{1},\dots,y_n) $ из пространства $ \mathbb R^{n}_{} $ понимается в стандартной евклидовой метрике: $$ \sqrt{(x_1-y_1)^2+\dots+(x_n-y_n)^2} \ . $$ Для согласования дальнейших обозначений будем всегда считать точки пространства $ \mathbb R^{n}_{} $ векторами-столбцами.

Линейные многообразия

Расстояние от точки до линейного многообразия (плоскости)

Задача. Найти расстояние от точки $ X_{0} \in {\mathbb R}^{n} $ до линейного многообразия (плоскости) $ \mathbb M $ в $ {\mathbb R}^{n} $, заданного системой уравнений $$ \left\{ \begin{array}{ccc} c_{11}x_1+c_{12}x_2+\dots+c_{1n}x_n &=& h_1 \\ \dots & & \dots \\ c_{m1}x_1+c_{m2}x_2+\dots+c_{mn}x_n &=& h_m \end{array} \right. $$ или, в матричном виде $$ CX={\mathcal H} \quad npu \quad C=\left( \begin{array}{cccc} c_{11}& c_{12} & \dots & c_{1n} \\ \dots & & & \dots \\ c_{m1}& c_{m2} & \dots & c_{mn} \end{array} \right)_{m\times n} ,\ {\mathcal H} =\left( \begin{array}{c} h_1 \\ \vdots \\ h_m \end{array} \right),\ X=\left( \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right) $$ При этом предполагается, что $ m\le n_{} $ и что ранг матрицы $ C_{} $ равен $ m_{} $, то есть система уравнений совместна и определяемое ею многообразие в $ {\mathbb R}^{n} $ является $ (n-m)_{} $-мерным.

Т

Теорема 1. [1]. Составим квадратную матрицу порядка $ m+1_{} $:

$$ M=\left( \begin{array}{cc} C\cdot C^{\top} & CX_0- {\mathcal H} \\ (CX_0- {\mathcal H})^{\top} & 0 \end{array} \right) $$ Расстояние от точки $ X_{0} $ до линейного многообразия $ \mathbb M $ вычисляется по формуле $$ d= \sqrt{-\frac{\det M}{\det(C\cdot C^{\top})}} \ . $$

Доказательство ЗДЕСЬ.

=>

Расстояние от точки $ X_{0}=(x_{10},\dots,x_{n0})^{\top} $ до гиперплоскости (или, в случае $ n=2 $, прямой)

$$ c_1x_1+\dots+c_nx_n= h $$ равно $$ d= \frac{|c_1x_{10}+\dots+c_nx_{n0}-h|}{\sqrt{c_1^2+\dots+c_n^2}} \ . $$ Ближайшая к $ X_0 $ точка гиперплоскости: $$ X_{\ast}=X_0- \frac{c_1x_{10}+\dots+c_nx_{n0}-h}{c_1^2+\dots+c_n^2} \left(\begin{array}{c} c_1 \\ \vdots \\ c_n \end{array} \right) \, . $$


Пусть теперь линейное многообразие (плоскость) задано параметрически $$ \mathbb M= \{ Y_0+\lambda_1 Y_1+\dots+\lambda_k Y_k \quad \mid \quad \{\lambda_1,\dots,\lambda_k\} \subset {\mathbb R} \} $$ при фиксированных столбцах $$ \{Y_0,Y_1,\dots,Y_k \}\subset {\mathbb R}^n \ . $$ Предположим, что эти столбцы линейно независимы. Составим из них матрицы $$ L=\left[ Y_1|\dots|Y_k \right]_{n\times k} \quad u \quad \tilde L = \left[ Y_1|\dots|Y_k| X_0-Y_0 \right]_{n\times (k+1)} $$ (здесь $ |_{} $ означает конкатенацию).

Т

Теорема 2. Расстояние $ d_{} $ от точки $ X_{0} $ до линейного многообразия $ \mathbb M $ вычисляется по формуле

$$ d=\sqrt{\frac{\det(\tilde L^{\top}\cdot \tilde L)}{\det( L^{\top}\cdot L)}} \ . $$

Доказательство. Утверждение теоремы 2 является частным случаем общего результата о вычислении расстояния от точки до линейного многообразия в евклидовом пространстве.

На основании теоремы Бине-Коши
  • матрица $ \tilde L^{\top}\cdot \tilde L_{} $ имеет неотрицательный определитель при любых столбцах

$ \{Y_0,Y_1,\dots,Y_{k} \} $;

  • матрица $ L^{\top}\cdot L_{} $ является положительно определенной если система столбцов $ \{Y_1,\dots,Y_{k} \} $ линейно независима.
Т

Теорема 3. Ближайшая к точке $ X_0 $ точка многообразия $ \mathbb M_{} $ (проекция точки на многообразие) определяется по формуле

$$ X_{\ast}=Y_0+ L(L^{\top}\cdot L_{})^{-1} L^{\top} (X_0-Y_0) \, . $$

Доказательство ЗДЕСЬ.

П

Пример. Найти расстояние от точки $ X_{0}=(1,1,1,1)^{\top} $ до плоскости

$$ \left\{\begin{array}{rrrrc} 3x_1&+x_2&-x_3&+x_4&=1 \\ x_1 & -2x_2&+x_3&+2x_4&=2. \end{array} \right. $$

Решение. 1-й способ: применение теоремы 1. Имеем: $$ C=\left( \begin{array}{rrrr} 3 & 1 & -1 & 1 \\ 1 & -2 & 1 & 2 \end{array} \right), {\mathcal H}= \left( \begin{array}{r} 1 \\ 2 \end{array} \right), $$ $$ C\cdot C^{\top} = \left( \begin{array}{cc} 12 & 2 \\ 2 & 10 \end{array} \right),\ CX_0=\left( \begin{array}{r} 4 \\ 2 \end{array} \right), \ CX_0-{\mathcal H}=\left( \begin{array}{r} 3 \\ 0 \end{array} \right) \ , $$ $$ \frac{\left| \begin{array}{ccc} 12 & 2 & 3 \\ 2 & 10 & 0 \\ 3 & 0 & 0 \end{array} \right|}{\left| \begin{array}{cc} 12 & 2 \\ 2 & 10 \end{array} \right|}=\frac{-90}{116}=-\frac{45}{58} \ . $$

2-й способ: применение теоремы 2. Общее решение системы уравнений, задающей плоскость: $$ x_3=\frac{5}{3}x_1+\frac{4}{3}x_2, \ x_4=1-\frac{4}{3}x_1+\frac{1}{3}x_2 \ . $$ Таким образом, плоскость может быть представлена в параметрическом виде $$ Y_0+\lambda_1 Y_1 + \lambda_2 Y_2 \quad npu \quad Y_0 = \left( \begin{array}{r} 0 \\ 0 \\ 0 \\ 1 \end{array} \right),\ Y_1=\left( \begin{array}{r} 0 \\ 3 \\ 4 \\ 1 \end{array} \right),\ Y_2=\left( \begin{array}{r} 3 \\ 0 \\ 5 \\ -4 \end{array} \right) \ . $$ Имеем: $$ L= \left( \begin{array}{rr} 0 & 3 \\ 3 & 0 \\ 4 & 5 \\ 1 & -4 \end{array} \right), \ \tilde L =\left( \begin{array}{rrr} 0 & 3 & 1 \\ 3 & 0 & 1 \\ 4 & 5 & 1 \\ 1 & -4 & 0 \end{array} \right), \ \frac{\left| \begin{array}{ccc} 26 & 16 & 7 \\ 16 & 50 & 8 \\ 7 & 8 & 3 \end{array} \right|}{\left| \begin{array}{cc} 26 & 16 \\ 16 & 50 \end{array} \right|}=\frac{810}{1044}=\frac{45}{58} \ . $$ Координаты ближайшей точки к $ X_{0} $: $$ X_{\ast}= \left(\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \end{array}\right)+\left( \begin{array}{rr} 0 & 3 \\ 3 & 0 \\ 4 & 5 \\ 1 & -4 \end{array} \right)\left( \begin{array}{ccc} 26 & 16 \\ 16 & 50 \\ \end{array} \right)^{-1} \left(\begin{array}{rrrr} 0 & 3 & 4 & 1 \\ 3 & 0 & 5 & -4 \end{array} \right)\left(\begin{array}{c} 1 \\ 1 \\ 1 \\ 0 \end{array}\right)=\frac{1}{58} \left(\begin{array}{c} 16 \\ 37 \\ 76 \\ 49 \end{array}\right) \, . $$

Ответ. $ d=\sqrt{45/58} \approx 0.8808303295 $.

Расстояние между линейными многообразиями (плоскостями)

Пусть линейные многообразия в $ {\mathbb R}^{n} $ заданы параметрически $$ \mathbb M_1=\{ X_0+ \lambda_1 X_1+\dots + \lambda_k X_k \ \mid \ \{\lambda_1,\dots,\lambda_k \} \subset \mathbb R \} ; $$ $$ \mathbb M_2=\{ Y_0+\mu_1Y_1+\dots+\mu_{\ell}Y_{\ell} \ \mid \ \{\mu_1,\dots,\mu_{\ell} \} \subset \mathbb R \} $$ при фиксированных столбцах $$ \{X_0,X_1,\dots,X_k,Y_0,Y_1,\dots,Y_{\ell}\}\subset {\mathbb R}^n . $$ Составим из этих столбцов матрицы $$ P=\left[ X_1|\dots|X_k| Y_1|\dots | Y_{\ell} \right]_{n\times (k+\ell)} \quad u \quad \tilde P = \left[ X_1|\dots|X_k| Y_1|\dots | Y_{\ell}| X_0-Y_0 \right]_{n\times (k+\ell+1)} $$ (здесь $ |_{} $ означает конкатенацию).

Т

Теорема. Расстояние между линейными многообразиями $ \mathbb M_1 $ и $ \mathbb M_2 $ вычисляется по формуле

$$ d=\sqrt{\frac{\det(\tilde P^{\top}\cdot \tilde P)}{\det( P^{\top}\cdot P)}} \ . $$

§

На основании свойств определителя Грама имеем:

$$ \det (P^{\top}\cdot P) > 0 \quad \iff \quad \mbox{ столбцы } \ \{X_1,\dots,X_k,Y_1,\dots,Y_{\ell} \} \ \mbox{ линейно независимы}; $$ $$ \det(\tilde P^{\top}\cdot \tilde P) \ge 0 \quad \mbox{ при } \forall \ \{X_0,X_1,\dots,X_k,Y_0,Y_1,\dots,Y_{\ell} \} \ . $$

П

Пример. [2]. Найти расстояние между плоскостями

$$ \left( \begin{array}{r} 89 \\ 37 \\ 111 \\ 13 \\54 \end{array} \right) + \lambda_1 \left( \begin{array}{r} 1 \\ 1 \\ 0 \\ -1 \\ -1 \end{array} \right) + \lambda_2 \left( \begin{array}{r} 1 \\ -1 \\ 0 \\ -1 \\ 1 \end{array} \right) \quad \mbox{ и } \quad \left( \begin{array}{r} 42 \\ -16 \\ -39 \\ 71 \\3 \end{array} \right) + \mu_1 \left( \begin{array}{r} 1 \\ 1 \\ 0 \\ 1 \\ 1 \end{array} \right) + \mu_2 \left( \begin{array}{r} 1 \\ -1 \\ 0 \\ 1 \\ -1 \end{array} \right) \ . $$

Решение. $$ P^{\top}\cdot P=4\cdot E_{4 \times 4}, \quad \tilde P^{\top}\cdot \tilde P= \left(\begin{array}{ccccc} 4 & 0 & 0 & 0 & 107 \\ 0 & 4 & 0 & 0 & 103 \\ 0 & 0 & 4 & 0 & 93\\ 0 & 0 & 0 & 4 & -115 \\ 107 & 103 & 93 & -115 & 33483 \end{array} \right) \ . $$

Ответ. $ d=150_{} $.

Квадратичные многообразия (квадрики)

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

стационарные точки $ \rightarrow $ критические значения

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

Расстояние от точки до квадрики

Т

Теорема 1. Пусть квадрика в $ {\mathbb R}^{n} $, задана уравнением

$$ X^{\top}AX+2B^{\top}X-1=0 \ , (A=A^{\top}) \ . $$ Квадрат расстояния до нее от не лежащей на ней точки $$ X_{0} \in {\mathbb R}^{n}, \quad ( X_0^{\top}AX_0+2 B^{\top}X_{0}-1\ne 0 ) $$ равен минимальному положительному корню уравнения расстояний $$ {\mathcal F}(z)=0 \quad npu \quad {\mathcal F}(z)={\mathcal D}_{\mu} \left( \Phi(\mu,z) \right) \ . $$ Здесь $$ \Phi(\mu,z)=\det \left( \left[ \begin{array}{cc} A & B \\ B^{\top} & -1 \end{array} \right] + \mu \left[ \begin{array}{cc} -E & X_0 \\ X_0^{\top} & z-X_0^{\top}X_0 \end{array} \right] \right), $$ $ {\mathcal D}_{} $ означает дискриминант полинома $ \Phi(\mu,z) $, рассматриваемого относительно переменной $ \mu_{} $, а $ E_{} $ — единичная матрица порядка $ n_{} $. Дополнительно предполагается, что указанный корень не является кратным.

=>

[3]. Квадрат расстояния от начала координат $ {\mathbb O} \in {\mathbb R}^{n} $ до квадрики в $ {\mathbb R}^{n} $, заданной уравнением

$$ X^{\top}AX+2\,B^{\top}X-1=0 \ , $$ равен минимальному положительному корню уравнения расстояний $$ {\mathcal F}(z)=0, \quad npu \quad {\mathcal F}(z)={\mathcal D}_{\mu} \left( f(\mu)(\mu z-1)-B^{\top}q(A,\mu)B \right)\ , $$ и при условии, что указанный корень не является кратным. Здесь $ f(\mu_{})=\det (A-\mu E) $ — характеристический полином матрицы $ A_{} $, а $ q(A,\mu)_{} $ — матрица взаимная матрице $ A-\mu E_{} $.

=>

В частном случае $ B={\mathbb O}_{} $ (квадрика центрирована к началу координат), имеем:

$$ {\mathcal F}(z)=\left[z^nf(1/z) \right]^2{\mathcal D}_{\mu}(f(\mu)) \ , $$ и расстояние от начала координат до квадрики оказывается равным $ 1/\sqrt{\lambda_{\max}^{}} $, где $ \lambda_{\max}^{} $ — максимальное собственное число матрицы $ A_{} $.

П

Пример. Найти расстояние от начала координат до эллипсоида

$$ 7\,x_1^2+6\,x_2^2+5\,x_3^2-4\,x_1x_2-4\,x_2x_3-3\,x_1-4\,x_2+5\,x_3-18=0\ .$$

Решение. Здесь $$A = \left( {\begin{array}{rrr} \frac{7}{18} & -\frac{1}{9} & 0 \\ && \\ -\frac{1}{9} & \frac{1}{3} & -\frac{1}{9} \\ && \\ 0 & -\frac{1}{9} & \frac{5}{18} \end{array}} \right),\quad B = \left( \begin{array}{r} -\frac{1}{12} \\ \\ -\frac{1}{9} \\ \\ \frac{5}{36} \end{array} \right) ,$$ $$ f(\mu)=\det (A-\mu E)=-\mu ^{3} + \mu ^{2} - \frac{11}{36} \mu + \frac {1}{36} $$ Матрица взаимная матрице $ A-\mu E_{} $: $$ q(A, \mu)= \left( \begin{array}{ccc} \mu ^{2} - \frac{11}{18} \mu + \frac{13}{162} & - \frac{1}{9} \mu + \frac{5}{162} & \frac{1}{81} \\ && \\ - \frac{1}{9} \mu + \frac{5}{162} & \mu^2 -\frac{2}{3}\mu+\frac{35}{324} & - \frac{1}{9} \mu +\frac{7}{162} \\ && \\ \frac{1}{81} & - \frac{1}{9} \mu + \frac{7}{162} & \mu ^{2} - \frac{13}{18}\mu+\frac{19}{162} \end{array} \right) \ . $$ $$ \Phi(\mu,z)=f(\mu)(\mu z-1)-B^{\top}q(A,\mu)B= $$ $$ =-z \mu ^{4} + (z+1) \mu ^{3} + \left(-\frac {11}{36} z - \frac{673}{648}\right) \mu ^{2} +\left( \frac {1}{36} z + \frac {241}{729} \right) \mu - \frac {1621}{52488} \ . $$ Воспользуемся детерминантным представлением дискриминанта: $$ {\mathcal F}(z) = {\mathcal D}_{\mu} (\Phi(\mu,z)) = \frac{1}{16} \times $$ $$ \times \left| \begin{array}{cccccc} 4z & - 3z-3 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{36} z - \frac{241}{729} & 0 & 0 \\ &&&&& \\ 0 & 4z & - 3z-3 & \frac{11}{18} z + \frac{673}{324} & - \frac{1}{36} z - \frac{241}{729} & 0 \\ &&&&& \\ 0 & 0 & 4z & - 3z-3 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{36} z - \frac{241}{729} \\ &&&&& \\ 0 & 0 & - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12} z - \frac{241}{243} & \frac{1621}{13122} \\ &&&&& \\ 0 & - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12}z - \frac{241}{243} & \frac{1621}{13122} & 0 \\ &&&&& \\ - z - 1 & \frac{11}{18} z + \frac{673}{324} & - \frac{1}{12} z - \frac{241}{243} & \frac{1621}{13122} & 0 & 0 \end{array} \right| = $$ $$ =2^{-11}3^{-24} ( 38263752\,z^6-966487788\,z^5+9376985736\,z^4-43882396481\,z^3+$$ $$ +102982092872\,z^2-116747905827\,z+50898162294) \quad . $$ Вещественные корни уравнения расстояний: $$ z_1\approx 1.394685, \ z_2 \approx 5.701814, \ z_3 \approx 7.043941,\ z_4 \approx 7.590060 \ . $$

Ответ. $ d= \sqrt{z_1} \approx 1.180968 $.

Нахождение точки на квадрике, ближайшей к заданной точке $ X_{0} $, возможно с помощью следующего результата.

T

Теорема 2. При выполнении условий теоремы 1, координаты точки $ X_{\ast} $ квадрики, ближайшей к точке $ X_{0} $ находятся по формуле

$$ X_{\ast}=-A^{-1} B - \mu_{\ast} (A -\mu_{\ast}E)^{-1} (A^{-1} B+X_0)=(\mu_{\ast}E- A)^{-1} (B+\mu_{\ast} X_0)\ . $$ Здесь $ \mu_{\ast} $ означает кратный корень полинома $ \Phi(\mu,z_{\ast}) $, где полином $ \Phi(\mu,z) $ берется из формулировки теоремы 1, а $ z_{\ast}^{} $ означает минимальный положительный корень уравнения расстояний.

Этот результат требует пояснений. Итак, поскольку дискриминант полинома $ \Phi(\mu,z_{\ast}) $ обращается в нуль, то у этого полинома — как полинома по $ \mu_{} $ — имеется кратный корень $ \mu =\mu_{\ast} $. Можно доказать [4], что при условии простоты корня $ z=z_{\ast} $ уравнения расстояний $ \mathcal F(z)=0 $ кратность корня $ \mu =\mu_{\ast} $ для полинома $ \Phi(\mu,z_{\ast}) $ будет равна ровно $ 2_{} $, и других кратных корней этот полином не имеет. Но тогда, выражение для $ \mu_{\ast}^{} $ может быть найдено в виде рациональной функции коэффициентов полинома $ \Phi(\mu,z_{\ast}) $. Последнее утверждение может быть доказано разными способами, и в качестве самого наглядного выберем тот, что основан на свойствах дискриминанта, например, на том, что изложено ЗДЕСЬ.

=>

При выполнении условия предыдущей теоремы, координаты точки $ X_{\ast}^{} $, ближайшей на квадрике к точке $ X_{0} $, являются рациональными функциями от квадрата расстояния.

=>

Точка $ X_{\ast} $ квадрики $ X^{\top}AX+2\,B^{\top}X-1=0 $, ближайшая к началу координат $ X_0= \mathbb O $, находится по формуле:

$$ X_{\ast} = - \frac{1}{f(\mu_{\ast})} q(A,\mu_{\ast}) B \ . $$ Здесь $ f(\mu_{})=\det (A-\mu E) $ — характеристический полином матрицы $ A_{} $, $ q(A,\mu)_{} $ — матрица взаимная матрице $ A-\mu E_{} $, а $ \mu_{\ast} $ означает кратный корень уравнения $$f(\mu)(\mu z_{\ast}-1)-B^{\top}q(A,\mu)B=0 , $$ где $ z_{\ast}^{} $ — величина квадрата расстояния от $ \mathbb O_{} $ до квадрики.

П

Пример. Найти ближайшую к началу координат точку эллипсоида из предыдущего примера.

Решение. Подставляем $ z_{}=z_{\ast} \approx 1.394685 $ в формулу для определения кратного корня, т.е. в отношение двух конкретных миноров детерминантного представления дискриминанта: $$ \mu=-\frac{\left| \begin{array}{cccc} 4z & - 3z-3 & \frac{11}{18} z + \frac{673}{324} & 0 \\ &&& \\ 0 & 4z & - 3z-3 & - \frac{1}{36} z - \frac{241}{729} \\ &&& \\ 0 & - z - 1 & \frac{11}{18}z + \frac{673}{324} & \frac{1621}{13122} \\ &&& \\ - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12}z - \frac{241}{243} & 0 \end{array} \right|} {\left| \begin{array}{cccc} 4z & - 3z-3 & \frac{11}{18} z + \frac{673}{324} & - \frac{1}{36} z - \frac{241}{729} \\ &&& \\ 0 & 4z & - 3z-3 & \frac{11}{18}z + \frac{673}{324} \\ &&& \\ 0 & - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12}z - \frac{241}{243} \\ &&& \\ - z - 1 & \frac{11}{18}z + \frac{673}{324} & - \frac{1}{12}z - \frac{241}{243} & \frac{1621}{13122} \end{array} \right|} $$ получаем $ \mu_{\ast}^{} \approx 0.572670 $. Подставляем это значение в формулу для определения $ X_{\ast}^{} $ из последнего следствия: $$ X_{\ast}\approx \left(\begin{array}{r} 0.071171 \\ -0.867719 \\ 0.797924 \end{array} \right) \ . $$

Проверка. Если подставить вместо $ X_{\ast} $ его приближенное значение, то получим: $$ X_{\ast}^{\top} X_{\ast} \approx \mathbf{1.39468}4,\ X_{\ast}^{\top}AX_{\ast}+2\,B^{\top}X_{\ast}-1 \approx 2.9\cdot 10^{-5}\ , $$ и вектор $ {\mathbb O}X_{\ast} $ перпендикулярен эллипсоиду в точке $ X_{}=X_{\ast} $: $$ AX_{\ast}+B \approx \left(\begin{array}{r} 0.040757\\ -0.496917 \\ 0.456948 \end{array} \right)\approx \mu_{\ast} X_{\ast} \ . $$

Более подробный анализ уравнения расстояний для частных случаев плоскости $ \mathbb R^{2} $ и трехмерного пространства $ \mathbb R^{3} $ (в частности, почему существенно условие простоты минимального положительного корня, упомянутое в теореме 1) ЗДЕСЬ.

Расстояние от линейного многообразия (плоскости) до квадрики

Задача. Найти расстояние от эллипсоида в $ {\mathbb R}^{n} $, заданного уравнением $$ X^{\top}AX+2B^{\top}X-1=0 \ , (A=A^{\top}) $$ до линейного многообразия (плоскости) в $ {\mathbb R}^{n} $, заданной системой уравнений $$ \left\{ \begin{array}{ccc} c_{11}x_1+c_{12}x_2+\dots+c_{1n}x_n &=& 0 \\ \dots & & \dots \\ c_{m1}x_1+c_{m2}x_2+\dots+c_{mn}x_n &=& 0 \end{array} \right. \ \iff \ CX={\mathbb O} \quad npu \quad C=\left( \begin{array}{cccc} c_{11}& c_{12} & \dots & c_{1n} \\ \dots & & & \dots \\ c_{m1}& c_{m2} & \dots & c_{mn} \end{array} \right)_{m\times n} $$ При этом предполагается, что $ m\le n_{} $ и что ранг матрицы $ C_{} $ равен $ m_{} $, т.е. определяемая системой плоскость в $ {\mathbb R}^{n} $ является $ (n-m)_{} $-мерной.

Т

Теорема. [3]. Необходимое и достаточное условие того, что линейное многообразие (плоскость) пересекает эллипсоид зависит от знакоопределенности матрицы $ A_{} $:

$$0 \le \left| \begin{array}{lrc} A & B & C^{\top}\\ B^{\top} & -1 & {\mathbb O}\\ C & {\mathbb O} & \mathbb{O} \end{array} \right| \times \left\{ \begin{array}{l} (-1)^{m-1} \ \mbox{при} \ A\ \mbox{пол. определенной}, \\ (-1)^n \ \mbox{при} \ A\ \mbox{отр. определенной} \end{array} \right.$$

=>

Условие равенства нулю определителя из теоремы является необходимым и достаточным для существования точки касания эллипсоида и плоскости.

Т

Теорема. [3]. Если условие предыдущей теоремы не выполняется, то квадрат расстояния от эллипсоида до плоскости совпадает с минимальным положительным корнем полинома

$$ {\mathcal F}(z) ={\mathcal D}_\mu \left( \mu^m \left| \begin{array}{ccc} A & B & C^{\top}\\ B^{\top} & -1 + \mu z & \mathbb{O}\\ C & \mathbb{O} & \frac{1}{\mu} C \cdot C^{\top} \end{array} \right| \right), $$ в предположении, что этот корень не является кратным. Здесь $ {\mathcal D}_{} $ — дискриминант полинома, рассматриваемого относительно переменной $ \mu_{} $.

=>

Если строки матрицы $ C_{} $ ортонормированны, то преобразованием определителя в теореме можно понизить его порядок: выражение под знаком дискриминанта можно преобразовать в

$$\left| \begin{array}{cc} A-\mu C^{\top} C & B \\ B^{\top} & -1+\mu z \end{array} \right|.$$

П

Пример. Найти расстояние от оси $ {\mathbb O}x_{1} $ до эллипсоида

$$ 7\, x_1^2+6\, x_2^2 +5\, x_3^2 -4\,x_1x_2-4\,x_2x_3-37\,x_1-12\,x_2+3\,x_3+54=0 \ . $$

Решение. Здесь $$ A= \left( \begin{array}{rrr} -\frac{7}{54} & \frac{1}{27} & 0 \\ &&\\ \frac{1}{27} & -\frac{1}{9} & \frac{1}{27} \\ &&\\ 0 & \frac{1}{27} & -\frac{5}{54} \end{array} \right), \ B=\left( \begin{array}{r} \frac{37}{108} \\ \\ \frac{1}{9} \\ \\ -\frac{1}{36} \end{array} \right) $$ и можно взять $$ C= \left( \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) \ . $$ Матрица $ A_{} $ отрицательно определена, условие пересечения прямой и эллипсоида не выполняется: $$ \left| \begin{array}{ccc} A & B & C^{\top}\\ B^{\top} & -1 & {\mathbb O}\\ C & {\mathbb O} & \mathbb{O} \end{array} \right| \times (-1)^3 = - \frac{143}{11664} < 0 \ . $$ Имеем, на основании следствия: $$ \left| \begin{array}{cc} A-\mu C^{\top} C & B \\ B^{\top} & -1+\mu z \end{array} \right|=\left| \begin{array}{cccc} -\frac{7}{54} & \frac{1}{27} & 0 & \frac{37}{108} \\ &&&\\ \frac{1}{27} & -\frac{1}{9}-\mu & \frac{1}{27} & \frac{1}{9} \\ &&&\\ 0 & \frac{1}{27} & -\frac{5}{54}-\mu & -\frac{1}{36} \\ &&&\\ \frac{37}{108} & \frac{1}{9} & -\frac{1}{36} & -1 + \mu z \end{array} \right| = $$ $$ =-\frac{7}{54}z \mu^3+\left(-\frac{73}{2916}z+\frac{143}{11664}\right)\mu^2+\left(-\frac{1}{972}z-\frac{1069}{314928}\right)\mu-\frac{1621}{4251528} $$ и дискриминант полученного полинома по переменной $ \mu_{} $ равен $$ {\mathcal F}(z)=2^{-16}3^{-30} \left(1331935488\,z^4-38807307008\,z^3+245988221152\,z^2-1086769525104\,z+61289436065 \right) $$ Положительные корни последнего полинома: $ z_1 \approx 0.057128,\ z_2 \approx 22.545607_{} $.

Ответ. $ d_{} = \sqrt{z_1} \approx 0.239015 $.

Как правило, степень полинома $ {\mathcal F}(z)_{} $ равна $ 2m_{} $, т.е. удвоенному количеству линейных уравнений, задающих плоскость. В частном случае $ m=1_{} $ получаем квадратное уравнение:
=>

Расстояния в $ {\mathbb R}^{n} $ от гиперплоскости

$$ c_1x_1+\dots+c_nx_n = h \ \iff \ CX=h $$ до ближайшей и до самой дальней точек эллипсоида $$ X^{\top}AX+2B^{\top}X-1=0 \ , (A=A^{\top}) $$ совпадают с модулями корней полинома: $$ {\mathcal F}(Z)=\left| \begin{array}{ccc} A & B & C^{\top}/|C|\\ B^{\top} & -1 & Z-h/|C|\\ C/|C| & Z-h/|C| & 0 \end{array} \right| \ . $$ Здесь $ |C|=\sqrt{c_1^2+\dots+c_n^{2}} $ и предполагается, что поверхности не пересекаются.

П

Пример. Найти расстояние от прямой $ 2\, x_1- x_{2}=0 $ до эллипса

$$ 7\,x_1^2-4\,x_1x_2 + 6\, x_2^2-47\, x_1 -24\, x_{2} +124 = 0 .$$

Решение. Здесь $$ {\mathcal F}(Z)=\left| \begin{array}{ccc} A & B & C^{\top}/|C| \\ B^{\top} & -1 & Z-h/|C| \\ C/|C| & Z-h/|C| & 0 \end{array} \right| = \left| \begin{array}{cccc} -\frac{7}{124} & \frac{1}{62} & \frac{47}{248} & \frac{2}{\sqrt{5}} \\ &&& \\ \frac{1}{62} & - \frac{3}{62} & \frac{3}{31} &- \frac{1}{\sqrt{5}} \\ &&& \\ \frac{47}{248} & \frac{3}{31} & -1 & Z \\ &&& \\ \frac{2}{\sqrt{5}} & - \frac{1}{\sqrt{5}} & Z & 0 \end{array} \right| = $$ $$ =-\frac{1}{307520}\left(760\,Z^2+1592\sqrt{5}\, Z+2383 \right) $$ и корни этого полинома: $$ -\frac{199}{190}\sqrt{5}\pm \frac{1}{76} \sqrt{13570} \ . $$ Координаты ближайших точек на прямой и эллипсе соответственно $$ \approx \left( \begin{array}{c} 2.128155 \\ 4.256311 \end{array} \right) \quad \mbox{и} \quad \approx \left( \begin{array}{c} 2.851943 \\ 3.894417 \end{array} \right) \, . $$

Ответ. $$ d = \left| -\frac{199}{190}\sqrt{5}+ \frac{1}{76} \sqrt{13570} \right| \approx 0.809219_{} \ . $$

Расстояние между квадриками

Т

Теорема. Пусть $ X^{\top} A_{1} X =1 $ и $ X^{\top} A_{2} X =1 $ – квадрики в $ {\mathbb R}^{n} $, причем первая является эллипсоидом. Квадрики не пересекаются тогда и только тогда, когда матрица $ A_{1}-A_2 $ является знакоопределенной.

Доказательство ЗДЕСЬ.

Т

Теорема. [3,4]. Если выполняется условие предыдущей теоремы, то квадрат расстояния между

$$ \mbox{эллипсоидом} \ X^{\top} A_{1} X =1\ \mbox{и квадрикой}\ X^{\top} A_{2} X =1 $$ совпадает с минимальным положительным корнем уравнения расстояний $$ {\mathcal F}(z)=0 \quad npu \quad {\mathcal F}(z)={\mathcal D}_{\lambda} \left( \Phi(\lambda,z) \right) \ . $$ Здесь $$ \Phi(\lambda,z)=\det (\lambda A_1 + (z- \lambda) A_2 - \lambda (z-\lambda) A_1 A_2), $$ $ {\mathcal D}_{} $ — дискриминант полинома рассматриваемого относительно переменной $ \lambda_{} $. Дополнительно предполагается, что указанный корень не является кратным.

П

Пример. Найти расстояние между эллипсами

$$10\,x_1^2-12\,x_1x_2+8\,x_2^2=1 \qquad u \qquad x_1^2+x_1x_2+x_2^2=1 \ . $$

Решение. Здесь $$ A_1= \left( \begin{array}{rr} 10 & - 6 \\ -6 & 8 \end{array} \right), \quad A_2= \left( \begin{array}{rr} 1 & \frac{1}{2} \\ \frac{1}{2} & 1 \end{array} \right) $$ и матрица $ A_{1}-A_2 $ положительно определена. Следовательно эллипсы не пересекаются. $$ \Phi(\lambda,z)=\det (\lambda A_1 + (z- \lambda) A_2 - \lambda (z-\lambda) A_1 A_2)= $$ $$ =33\,\lambda^4+\left(-66z+\frac{149}{2}\right)\lambda^3+\left(33\,z^2-61\,z+\frac{83}{4}\right)\lambda^2+\left(-\frac{27}{2}z^2+\frac{45}{2}z\right)\lambda+\frac{3}{4}\,z^2 $$ и дискриминант этого полинома по переменной $ \lambda_{} $ равен $$ {\mathcal F}(z)=\frac{3}{16}z^2 ({\scriptstyle 936086976}\, z^6-{\scriptstyle 10969697376}\,z^5+ {\scriptstyle 50706209664}\, z^4 -{\scriptstyle 115515184664}\, z^3+{\scriptstyle 130176444432}\, z^2 -{\scriptstyle 59826725574}\,z+{\scriptstyle 2866271785}) \ . $$ Положительные корни уравнения расстояний $ {\mathcal F}(z)=0 $: $$ z_1 \approx 0.053945666,\ z_2 \approx 1.3340583883,\ z_3 \approx 1.95921364,\ z_4 \approx 2.8785867381 \ . $$

Ответ. $ d_{}= \sqrt{z_1} \approx 0.23226206 $.

Как правило, степень полинома $ {\mathcal F}(z)_{} $ из последней теоремы (после отбрасывания постороннего множителя $ z^{n(n-1)}_{} $) равна $ n(n+1)_{} $.

Нахождение координат ближайших точек на квадриках (обеспечивающих найденное расстояние) возможно по алгоритму:

1. Если $ z=z_{\ast} $ — корень полинома $ {\mathcal F}(z) $, то это значит, что полином $$ \Phi(\lambda, z_{\ast}) = \det ( \lambda A_1 +(z_{\ast}-\lambda)A_2 - \lambda (z_{\ast}-\lambda) A_2A_1) $$ имеет кратный корень $ \lambda_{} = \lambda_{\ast} $. При выполнении условий теоремы, этот корень будет единственным второй кратности и его можно выразить в виде рациональной функции от $ z_{\ast} $ с помощью субдискриминантов.

2. Столбец координат $ X_{\ast}^{} $ точки первой квадрики, удовлетворяет тогда однородной системе уравнений $$ ( \lambda_{\ast} A_1 +(z_{\ast}-\lambda_{\ast})A_2 - \lambda_{\ast} (z_{\ast}-\lambda_{\ast}) A_2A_1) X = \mathbb O \ , $$ которая имеет бесконечное множество решений, поскольку определитель ее матрицы равен нулю. Из этого бесконечного множества мы выделяем те решения, что удовлетворяют условию $ X^{\top}A_{1}X=1 $.

При выполнении условий теоремы таких решений будет два (что соответствует симметрии задачи, см. рисунок).

Аналогично, столбец координат $ Y_{\ast}^{} $ точки на второй квадрике $ Y^{\top}A_{2}Y=1_{} $ будет решением системы уравнений $$ ( \lambda_{\ast} A_1 +(z_{\ast}-\lambda_{\ast})A_2 - \lambda_{\ast} (z_{\ast}-\lambda_{\ast}) A_1A_2) Y = \mathbb O \ . $$

Заметим, что матрицы рассматриваемых линейных систем различаются лишь транспонированием.

Для нахождения решений воспользуемся одним из результатов теории систем линейных уравнений. Составим столбец из алгебраических дополнений к элементам какой-либо строки матрицы $$ M= \lambda_{\ast} A_1 +(z_{\ast}-\lambda_{\ast})A_2 - \lambda_{\ast} (z_{\ast}-\lambda_{\ast}) A_2A_1 \ . $$ Тогда вектор $ X_{\ast}^{} $ отличается от этого столбца лишь множителем, который определится из условия $ X^{\top}A_{1}X=1_{} $. Аналогично, для получения столбца координат $ Y_{\ast}^{} $ возьмем столбец из алгебраических дополнений к элементам какого-либо столбца той же матрицы $ M_{} $ и домножим его на константу, чтобы обеспечить выполнение условия $ Y^{\top}A_{2}Y=1_{} $.

3. Получившиеся пары $ X_{\ast},Y_{\ast}^{} $ надо согласовать: они должны подчиняться условию $$ (X_{\ast}-Y_{\ast})^{\top}(X_{\ast}-Y_{\ast})=z_{\ast} \ . $$

П

Пример. Найти ближайшие точки эллипсов из предыдущего примера.

Решение. Для найденного значения $ z_{\ast}=z_1 \approx 0.053945666_{} $ определитель матрицы $$ M=\left( \begin{array}{cc} 7\,\lambda^2+(-7z+9)\lambda+z & -2\lambda^2+(2\,z-\frac{13}{2})\lambda+\frac{1}{2}z \\ & \\ -\lambda^2+(z-\frac{13}{2})\lambda+\frac{1}{2}z & 5\lambda^2+(-5z+7)\lambda+z \end{array} \right) $$ как полином по $ \lambda_{} $ будет иметь кратный корень. Этот корень определяем1) с помощью субдискриминантов в виде: $$ \lambda=-\frac{-725274\,z^5+1455894\,z^4+\frac{11286981}{2}z^3-\frac{26486523}{2}z^2+\frac{42000075}{8}z} {17591706\,z^4-109992894\,z^3+\frac{450450691}{2}z^2-\frac{315606253}{2}z+\frac{77466805}{8}} \ . $$ Подстановка сюда $ z=z_{\ast}^{} $ даст $ \lambda_{\ast} \approx -0.13576051_{} $.

Далее, при найденных значениях $ z_{} $ и $ \lambda_{} $ система линейных уравнений $$ MX=\mathbb O_{2\times 1} $$ должна иметь бесконечное множество решений относительно вектора $ X_{2\times 1}^{} $. Одно из этих решений может быть построено (см. упражнение ЗДЕСЬ ) с помощью алгебраических дополнений к элементам, например, второй строки матрицы $ M_{} $: $$ \left( \begin{array}{c} 2\lambda^2-(2\,z-\frac{13}{2})\lambda-\frac{1}{2}z \\ \\ 7\,\lambda^2+(-7z+9)\lambda+z \end{array} \right) \quad \begin{array}{c} \longrightarrow \\ z=z_{\ast}, \lambda= \lambda_{\ast} \end{array} \quad X=\left( \begin{array}{c} -0.8579069 \\ \\ -0.9876166 \end{array} \right) \ . $$ Любое другое решение получается домножением полученного на произвольную константу («растяжением» вектора). Воспользуемся этим, чтобы добиться выполнения условия $ X^{\top}A_{1} X =1_{} $. $$ X_{\ast}=\frac{1}{\sqrt{X^{\top}A_1 X}} X \approx \left( \begin{array}{c} -0.3838312 \\ -0.4418639 \end{array} \right) \ . $$ Аналогично, для нахождения точки на другом эллипсе, мы решаем систему $$ M^{\top}Y=\mathbb O_{2\times 1} \ , $$ представив ее решение опять-таки с помощью алгебраических дополнений к элементам второго столбца матрицы $ M_{} $: $$ \left( \begin{array}{c} \lambda^2-(z-\frac{13}{2})\lambda-\frac{1}{2}z \\ \\ 7\,\lambda^2+(-7z+9)\lambda+z \end{array} \right) \quad \begin{array}{c} \longrightarrow \\ z=z_{\ast}, \lambda= \lambda_{\ast} \end{array} \quad \left( \begin{array}{c} -0.8836615 \\ \\ -0.9876166 \end{array} \right) \quad \Rightarrow \quad Y_{\ast} \approx \left( \begin{array}{c} -0.5449964 \\ \\ -0.6091105 \end{array} \right) \ . $$

Ответ. $ \pm (0.3838312,\, 0.4418639)_{} $ и $ \pm (0.5449964,\, 0.6091105)_{} $ соответственно (знаки должны быть согласованы).

Проверка. Если в ответе взять знак $ +_{} $: $$ X_{\ast}-Y_{\ast} = \left( \begin{array}{c} -0.1611652 \\ -0.1672466 \end{array} \right)= \lambda_{\ast} A_1X_{\ast}=(\lambda_{\ast}-z_{\ast})A_2Y_{\ast},\quad (X_{\ast}-Y_{\ast})^{\top}(X_{\ast}-Y_{\ast})\approx \mathbf{0.0539456}4 \ . $$

Т

Теорема. [3,4].Пусть

$$ X^{\top} A_{1}X+2\,B^{\top}_1X-1=0 \ \mbox{и} \ X^{\top} A_{2}X+2\,B^{\top}_2X-1=0 $$ — квадрики в $ {\mathbb R}^{n}_{} $, причем первая является эллипсоидом. Квадрики пересекаются тогда и только тогда, когда среди вещественных корней полинома

$$ \Theta (z) = {\mathcal D}_\lambda \left( \det \left( \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1-z \end{array} \right] - \lambda \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] \right) \right) $$ имеются числа разных знаков или нуль. Здесь $ {\mathcal D}_{} $ — дискриминант полинома рассматриваемого относительно переменной $ \lambda_{} $.

Условие теоремы проверяется чисто алгебраически, т.е. без привлечения численных методов нахождения корней полинома. См. следствие к теореме Йоахимшталя ЗДЕСЬ.
=>

Для того, чтобы существовала точка касания квадрик

$$ X^{\top} A_{1}X+2\,B^{\top}_1X-1=0 \ \mbox{и} \ X^{\top} A_{2}X+2\,B^{\top}_2X-1=0 $$ необходимо и достаточно, чтобы было выполнено условие $$ {\mathcal D}_\lambda \left( \det \left( \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1 \end{array} \right] - \lambda \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] \right) \right) =0 \ . $$

Т

Теорема. [3,4]. Если не выполняется условие предыдущей теоремы, то квадрат расстояния между

$$ \mbox{эллипсоидом} \quad X^{\top} A_{1}X+2\,B^{\top}_1X-1=0 \quad \mbox{ и квадрикой } \quad X^{\top} A_{2}X+2\,B^{\top}_2X-1=0 $$ совпадает с минимальным положительным корнем полинома $$ {\mathcal F}(z) = $$ $$ ={\mathcal D}_{\mu_1, \mu_2} \left( \det \left( \mu_1 \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] + \mu_2 \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1 \end{array} \right] - \left[ \begin{array}{cc} A_2 A_1 & A_2 B_1\\ B_2^{\top} A_1 & B_2^{\top}B_1 - \mu_1 \mu_2 z \end{array} \right] \right) \right), $$ в предположении, что этот корень не является кратным. Здесь $ {\mathcal D}_{} $ — дискриминант полинома рассматриваемого относительно переменных $ \mu_{1}, \mu_{2} $.

П

Пример. Найти расстояние между эллипсами

$$-\frac{1}{2}\,x_1^2+\frac{1}{2}\,x_1x_2-\frac{3}{2}\,x_2^2+\frac{5}{2}\,x_1+4\,x_2=1 $$ и $$-\frac{1}{84}\,x_1^2-\frac{4}{189}\,x_2^2-\frac{1}{3}\, x_1=1 \ . $$

Решение. Здесь $$ A_1= \left( \begin{array}{rr} -\frac{1}{2} & \frac{1}{4} \\ \\ \frac{1}{4} & -\frac{3}{2} \end{array} \right), \quad B_1=\left( \begin{array}{c} \frac{5}{4} \\ \\ 2 \end{array} \right), \quad A_2= \left( \begin{array}{cc} -\frac{1}{84} & 0 \\ \\ 0 & -\frac{4}{189} \end{array} \right),\quad B_2=\left( \begin{array}{r} -\frac{1}{6} \\ \\ 0 \end{array} \right) \ . $$ Проверяем сначала условия пересечения поверхностей. $$ \Theta (z) = {\mathcal D}_\lambda \left(-\begin{array}{c} \frac{157}{32} \end{array} \lambda^3-\left\{ \begin{array}{c} \frac{4315}{3024} \end{array} + \begin{array}{c} \frac{11}{16}z \end{array} \right\}\lambda^2+\left\{-\begin{array}{c} \frac{11}{2646} \end{array} + \begin{array}{c} \frac{43}{1512} \end{array} z \right\}\lambda- \begin{array}{c} \frac{1}{3969}\end{array} z + \begin{array}{c} \frac{4}{11907} \end{array}\right)= $$ $$ =\begin{array}{c}\frac{1}{{\scriptstyle 9219465541730304}} \end{array} ({\scriptstyle 505118694465}\,z^4-{\scriptstyle 1023679248858}\,z^3- {\scriptstyle 7568287236783}\,z^2+ {\scriptstyle 33720131260536}\,z +{\scriptstyle 34005894083152})\ . $$ Полином имеет два вещественных корня, оба отрицательны. Эллипсы не пересекаются. Далее, $$ \Psi(\mu_1,\mu_2,z)=\det \left( \mu_1 \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] + \mu_2 \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1 \end{array} \right] - \left[ \begin{array}{cc} A_2 A_1 & A_2 B_1\\ B_2^{\top} A_1 & B_2^{\top}B_1 - \mu_1 \mu_2 z \end{array} \right] \right) = $$ $$ =\frac{11}{16}z\mu_1^3 \mu_2+\frac{43}{1512}z\mu_1^2\mu_2^2+\frac{1}{3969}z\mu_1\mu_2^3+ \frac{157}{32}\mu_1^3-\frac{4315}{3024}\mu_1^2\mu_2+ $$ $$ +\frac{275}{12096}z\mu_1^2\mu_2+\frac{11}{2646}\mu_1\mu_2^2+\frac{2}{3969}z\mu_1\mu_2^2+\frac{4}{11907}\mu_2^3+\frac{3925}{24192}\mu_1^2+ $$ $$ +\frac{11}{63504}z\mu_1\mu_2-\frac{619}{31752}\mu_1\mu_2+\frac{8}{11907}\mu_2^2+\frac{157}{127008}\mu_1+\frac{11}{47628}\mu_2 \ . $$ Вычисляем дискриминант этого полинома по переменным $ \mu_{1} $ и $ \mu_{2} $, представив соответствующий результант $$ {\mathcal R}_{\mu_1,\mu_2}\left(\frac{\partial \Psi}{\partial \mu_1}, \frac{\partial \Psi}{\partial \mu_2}, \Psi \right) $$ в виде определителя матрицы Безу2): $$ \mathfrak B= \left( \begin{array}{cccc} -{\scriptstyle 949850}\,z-{\scriptstyle 38319304} & -{\scriptstyle 76994841}\,z+ {\scriptstyle 29798905836} & \dots & \\ {\scriptstyle 179712037934}\,z^2-{\scriptstyle 6628863332080}\,z-{\scriptstyle 18668859390944800} & & \dots & \\ \dots &&& \dots \\ & & & \end{array} \right) $$ Выражения для элементов первой и последней строк ЗДЕСЬ. $$ {\mathcal F}(z) =\det (\mathfrak B) \equiv 3869893(20090\,z+3526681)^2 \times $$ $$ \times ({\scriptstyle 12866891832025}\,z^{12}-{\scriptstyle 2445505463588880}\,z^{11}-{\scriptstyle 10867111637549652716}\,z^{10}-{\scriptstyle 3123865087697933253136}\,z^9+ $$ $$ +{\scriptstyle 1561852119815441835822424}\,z^8+{\scriptstyle 1041845279230362476059640640}\,z^7+{\scriptstyle 302844249329911871856294474624}\,z^6+ $$ $$ +{\scriptstyle 50781476668832773753935668661952}\,z^5+{\scriptstyle 2215513880036430404751762329796624}\,z^4- $$ $$ -{\scriptstyle 646131957386364232922218724008039168}\,z^3-{\scriptstyle 99189074464451279399168578577559865856}\,z^2- $$ $$ -{\scriptstyle 5789019527920299026625801973715386789888}\,z+{\scriptstyle 60730952901233749068462660878127980941312}) $$ Первый сомножитель по $ z_{} $ является «посторонним»3) и отбрасывается. Положительные корни второго сомножителя: $$ 9.0183982802, \ 121.59673276,\ 582.35840496,\ 1031.42118655 $$

Ответ. $ d \approx \sqrt{9.0183982802} \approx 3.00306481 $.

Нахождение ближайших точек на квадриках (обеспечивающих найденное расстояние) возможно по следующему алгоритму.

1. После нахождения (с необходимой точностью) минимального положительного корня $ z_{\ast}^{} $ полинома $ {\mathcal F}(z) $, установим соответствующие ему значения $ \mu_{1}^{} $ и $ \mu_{2}^{} $. Соответствие понимается в том смысле, что при $ z=z_{\ast}^{} $ дискриминант полинома $$ \Psi(\mu_1,\mu_2,z)=\det \left( \mu_1 \left[ \begin{array}{cc} A_1 & B_1\\ B_1^{\top} & -1 \end{array} \right] + \mu_2 \left[ \begin{array}{cc} A_2 & B_2\\ B_2^{\top} & -1 \end{array} \right] - \left[ \begin{array}{cc} A_2 A_1 & A_2 B_1\\ B_2^{\top} A_1 & B_2^{\top}B_1 - \mu_1 \mu_2 z \end{array} \right] \right) $$ — как полинома по переменным $ \mu_{1},\mu_{2} $ — обращается в нуль, то есть этот полином обладает кратным корнем, который мы обозначим $ (\mu_{1\ast},\mu_{2\ast}) $. Этот корень может быть найден в виде рациональной функции от $ z_{\ast}^{} $ с помощью миноров матрицы Безу. Если матрица Безу $ \mathfrak B_{} $ порядка $ N_{} $ построена для мономиального базиса, в котором первые три монома имеют вид $ 1,\mu_1, \mu_{2} $, то, обозначив $ {\mathfrak B}_{N1}, {\mathfrak B}_{N2}, {\mathfrak B}_{N3}^{} $ алгебраические дополнения элементов ее последней строки, будем иметь $$ \mu_{1\ast} = \frac{\mathfrak B_{N2}}{\mathfrak B_{N1}};\ \mu_{2\ast} = \frac{\mathfrak B_{N3}}{\mathfrak B_{N1}} \ . $$

2. Составим матрицу $$ M= \mu_{1\ast} A_1+\mu_{2\ast}A_2-A_2A_1 \ . $$ Тогда координатные столбцы ближайших точек на квадриках вычисляются по формулам: $$ X_{\ast}=M^{-1} (A_2B_1-\mu_{1\ast} B_1-\mu_{2\ast}B_2),\ Y_{\ast}=(M^{-1})^{^{\top}} (A_1B_2 - \mu_{1\ast} B_1-\mu_{2\ast}B_2). $$

П

Пример. Найти ближайшие точки эллипсов из предыдущего примера.

Решение. Подставляем найденное значение квадрата расстояния $ z=z_{\ast}^{} $ в формулы для определения компонент кратного корня: $$ \mu_1=\frac{\mathfrak B_{9,2}}{\mathfrak B_{9,1}}\equiv -\frac{2}{21} \frac{p_2(z)}{p_1(z)},\ \mu_2=\frac{\mathfrak B_{9,3}}{\mathfrak B_{9,1}}\equiv -\frac{1099}{8} \frac{p_3(z)}{p_1(z)} $$ при $$ p_1(z)={\scriptstyle 30581063813712982235616866861258531260075854083860480}+\dots +{\scriptstyle 42267948346218643456100}\,z^{13} \ , $$ $$ p_2(z)={\scriptstyle 6423295122838229007549546733287643446036432415004672}+\dots + {\scriptstyle 10295520700745795900000}\,z^{13} $$ и $$ p_3(z)={\scriptstyle 11528328181753695140063436659475618124233172074496}+\dots +{\scriptstyle 303317089743521700}\,z^{13} \ . $$ (Полные представления ЗДЕСЬ.) В результате, получаем: $$ \mu_{1\ast}\approx 0.0420933593 ,\ \mu_{2\ast}\approx 0.5932113733 \ . $$ Матрица $ M_{} $: $$ M=\mu_{1\ast} A_1+\mu_{2\ast}A_2-A_2A_1= \left(\begin{array}{rr} -0.0340611008 & 0.0134995303 \\ 0.0158143451 & -0.1074408089 \end{array} \right) $$ и по указанным выше формулам получаем

Ответ. $$ X_{\ast}\approx \left(\begin{array}{r} -0.4824707833 \\ 1.1065143947 \end{array} \right),\ Y_{\ast}\approx \left( \begin{array}{r} -3.46262940675\\ 0.73630788509 \end{array} \right)\ . $$

Проверка. $$ (X_{\ast}-Y_{\ast})^{\top}(X_{\ast}-Y_{\ast})\approx \mathbf{9.018398280}3\ , $$ $$ X_{\ast}^{\top}A_1X_{\ast}+2B_1^{\top}X_{\ast}-1 \approx 1\cdot 10^{-9}\ , \ Y_{\ast}^{\top}A_2Y_{\ast}+2B_2^{\top}Y_{\ast}-1\approx -3\cdot 10^{-10}\ , $$ и вектор $ X_{\ast}-Y_{\ast}^{} $ перпендикулярен обоим эллипсам в соответствующих ближайших точках: $$ A_1X_{\ast}+B_1= \left(\begin{array}{r} 1.767863990 \\ 0.219610712 \end{array} \right)=\mu_{2\ast} (X_{\ast}-Y_{\ast}), \ A_2Y_{\ast}+B_2= \left(\begin{array}{r} -0.1254448880 \\ -0.0155832356 \end{array} \right)=-\mu_{1\ast} (X_{\ast}-Y_{\ast}) \ . $$

Как правило, степень полинома $ {\mathcal F}(z)_{} $ из последней теоремы (после отбрасывания постороннего множителя) равна $ 2n(n+1)_{} $. Коэффициенты этого полинома могут быть чудовищны.
П

Пример. Найти расстояние между эллипсоидами

$$ 7\,x_1^2+6\,x_2^2+5\,x_3^2-4\,x_1x_2-4\,x_2x_3-37\,x_1-12\,x_2+3\,x_3+54=0$$ и $$ 189\,x_1^2+x_2^2+189\,x_3^2+2\,x_1x_3-x_2x_3-27=0\ .$$

Решение. Здесь $$ \mathcal F (z)= \underbrace{\scriptstyle{891807829233048602 \dots 129270962946048}}_{146} \, z^{24} + \dots + \underbrace{\scriptstyle{11195843896426573542 \dots 420939042193186989409}}_{189} $$

Ответ. $ d \approx \sqrt{1.3537785005} \approx 1.1635198754_{} $

Алгебраические кривые и многообразия

Расстояние от точки до плоской алгебраической кривой

Задача. Пусть алгебраическая кривая задана уравнением $$ \Phi(x,y)=0 \ . $$ Здесь $ \Phi_{}(x,y) $ — отличный от константы полином от $ x_{} $ и $ y_{} $ с вещественными коэффициентами. Требуется найти расстояние до этой кривой от начала координат.

Здесь возникает проблема, которую для рассмотренных выше случаев удавалось либо обойти, либо же сравнительно дешево решить: это проблема существования решения. Дело в том, что уравнение может не иметь вещественных решений, то есть не определять никакой кривой на плоскости $ \mathbb R^{2} $.

Будем решать задачу сначала для частного случая — пусть полином $ \Phi_{}(x,y) $ является четным по переменной $ y_{} $. Геометрически это означает, что кривая (если она существует) будет зеркально симметричной относительно оси $ \mathbb Ox $. А с аналитической точки зрения такой полином можно представить в виде полинома $$ F(x,Y) \equiv \Phi_{}(x,y) \quad npu \quad Y=y^2 \ . $$

Т

Теорема 1 [6]. Пусть $ \Phi_{}(x,y) \equiv \Phi_{}(x,-y) $. Уравнение $ \Phi_{}(x,y)=0 $ не имеет вещественных решений если одновременно выполняются два условия:

a) уравнение $ \Phi(x,0)=0 $ не имеет вещественных решений;

б) уравнение $$ \mathcal F(z)=\mathcal D_x( F(x,z-x^2))=0 $$ не имеет положительных решений.

Если хотя бы одно из этих условий не выполняется, то квадрат расстояния от начала координат до кривой $ \Phi(x_{},y)=0 $ равен либо квадрату минимального по модулю вещественного корня уравнения $ \Phi(x,0)=0 $, либо же минимальному положительному корню уравнения $ \mathcal F(z)= 0 $, при условии, что последний не является кратным. Здесь $ {\mathcal D}_{} $ — дискриминант полинома, рассматриваемого относительно переменной $ x_{} $.

П

Пример. Найти расстояние от начала координат до кривой

$$ \Phi(x,y)=x^6-5\,x^4y^2-y^6-6\,x^5+6\,xy^4+10\,y^4+25\,x-45=0 \ . $$

Решение. Уравнение $$ \Phi(x,0)=x^6-6\,x^5+25\,x-45=0 $$ имеет вещественные корни $ \mu_1\approx -1.621919 $ и $ \mu_2 \approx 5.986387 $. Далее, $$ F(x,Y)=x^6-5\,x^4Y-Y^3-6\,x^5+6\,xY^2+10\,Y^2+25\,x-45 $$ и полином $$ \mathcal F(z)=\mathcal D_x (F(x,z-x^2))= {\scriptstyle 124422592}\,z^{15}-{\scriptstyle 1996675968}z^{14}-{\scriptstyle 26107738048}\,z^{13}+{\scriptstyle 270691240064}\,z^{12}+ {\scriptstyle 1462429768576}z^{11} $$ $$ -{\scriptstyle 31070151855680}z^{10}+ {\scriptstyle 104850679100160}\,z^9+{\scriptstyle 106422502370800}\,z^8-{\scriptstyle 1956603249193600}\,z^7+{\scriptstyle 1683409252901600}\,z^6+ $$ $$ +{\scriptstyle 3565828983027500}z^5 -{\scriptstyle 23058839076745500}\,z^4+{\scriptstyle 30272455856370000}\,z^3+{\scriptstyle 28139412928130000}\,z^2-{\scriptstyle 97452805338000000}\, z+ $$ $$ +{\scriptstyle 171049864407603125} $$ имеет минимальный положительный корень равный $ \lambda \approx 1.965293 $. Поскольку $ \sqrt{\lambda} < |\mu_1| $, то получаем

Ответ. $ d \approx 1.334155 $.

Понятно как решать задачу и в случае четности полинома $ \Phi_{}(x,y) $ по переменной $ x_{} $. Но как решить задачу в общем случае — когда свойства четности нет ни по одной из переменных? — Надо эту четность «сделать». Рассмотрим полином $$ \tilde F(x,Y) \equiv \Phi_{}(x,y) \Phi_{}(x,-y) \quad npu \quad Y=y^2 \ . $$

Т

Теорема 2 [6]. Уравнение $ \Phi_{}(x,y)=0 $ не имеет вещественных решений если одновременно выполняются два условия:

a) уравнение $ \Phi(x,0)=0 $ не имеет вещественных решений;

б) уравнение $$ \widetilde{\mathcal F}(z)=\mathcal D_x( \widetilde{F} (x,z-x^2))=0 $$ не имеет положительных решений.

Если хотя бы одно из этих условий не выполняется, то квадрат расстояния от начала координат до кривой $ \Phi(x_{},y)=0 $ равен либо квадрату минимального по модулю вещественного корня уравнения $ \Phi(x,0)=0 $, либо же минимальному положительному корню уравнения $ \widetilde{\mathcal F}(z)= 0 $, при условии, что последний не является кратным. Здесь $ {\mathcal D}_{} $ — дискриминант полинома, рассматриваемого относительно переменной $ x_{} $.

П

Пример. Найти расстояние от начала координат до кривой

$$ \begin{array}{lll} \Phi(x,y) & = & 32\,x^4y+64\,x^2y^3+32\,y^5-16\,x^4-96\,x^2y^2-80\,y^4+ \\ && +48\,x^2y+80\,y^3+120\,x^2-576\,xy+56\,y^2+160\,x-118\,y+71=0 \ . \end{array} $$

Решение. Опуская промежуточные выкладки, привожу только выражение для дискриминанта: $$ \widetilde{\mathcal F}(z) \equiv \widetilde{\mathcal F}_1(z) \widetilde{\mathcal F}_2^2(z) $$ при $$ \widetilde{\mathcal F}_1(z) = {\scriptstyle 87241523200}\,z^{15}-{\scriptstyle 244343373824}\,z^{14}+ {\scriptstyle 6135125901312}\,z^{13}-{\scriptstyle 99762334334976}\,z^{12}+{\scriptstyle 122650759266304}\,z^{11}- $$ $$ -{\scriptstyle 2018722496380928}\,z^{10} +{\scriptstyle 36775841922285568}\,z^9+{\scriptstyle 83476886207856640}\,z^8-{\scriptstyle 125448251244072960}\,z^7-{\scriptstyle 3659244138715855872}\,z^6- $$ $$ -{\scriptstyle 16653164114254566912}\,z^5-{\scriptstyle 39789124482714260608}\,z^4+{\scriptstyle 21724179049244829584}\,z^3-{\scriptstyle 2250891598084946580}\,z^2+{\scriptstyle 484733011031273132}\,z- $$ $$ -{\scriptstyle117947376101831257} $$ и $$ \widetilde{\mathcal F}_2(z) =4096\,z^6+18432\,z^5+18176\,z^4-1501440\,z^3+305136\,z^2+2195912\,z+709721 \, . $$ Полином $ \widetilde{\mathcal F}_1(z) $ имеет три вещественных корня: $ \lambda_1 \approx 0.208349,\ \lambda_2 \approx 0.360823,\ \lambda_3 \approx 6.480707 $. Вещественные корни $ \Phi(x,0) $: $ \mu_1 \approx -1.835484, \mu_2 \approx 3.306151 $.

Сомножитель $ \widetilde{\mathcal F}_2^2(z) $ я отбросил как «посторонний», т.е. его корни — все они кратные — не сравнивал по величине с $ \lambda_1 $ и $ \mu_1^2 $. Откуда, собственно, этот сомножитель взялся? Будет ли он присутствовать и в общем случае, т.е. можно ли в полиноме $ \widetilde{\mathcal F} $ из теоремы $ 2 $ выделить сомножитель в виде квадрата некоторого другого полинома? — Для того, чтобы угадать происхождение этого множителя всё же вычислим его положительные корни: $ \xi_1 \approx 1.483677, \xi_2 \approx 5.553837 $. Теперь изобразим на последнем рисунке окружности $ x^2+y^2= \xi_{1,2} $:

Окружности прошли через точки пересечения кривых $ \Phi_{}(x,y) = 0 $ и $ \Phi_{}(x,-y) =0 $.

Гипотеза. Разложим полином $ \Phi_{}(x,y) $ по степеням $ y_{} $ и выделим четные и нечетные слагаемые по этой переменной: $$ \Phi_{}(x,y) \equiv F_1(x,Y)+ y F_2(x,Y) \qquad npu \quad Y=y^2 \ . $$ С точностью до постоянного сомножителя, имеет место тождество $$ \widetilde{\mathcal F}_2(z) \equiv \mathcal R_x(F_1(x,z-x^2),F_2(x,z-x^2)) \ . $$ Здесь $ \mathcal R_{} $ — результант полиномов, рассматриваемых относительно переменной $ x_{} $.

Ответ. $ d \approx 0.456453 $.

Расстояние в пространстве матриц

до некоторых критических многообразий:

  • до многообразия вырожденных матриц;
  • до многообразия матриц, имеющих собственное число на мнимой оси $ \mathfrak{Re}(z)=0 $ комплексной плоскости;
  • до многообразия матриц, имеющих кратные собственные числа

ЗДЕСЬ.

Разные задачи

Обобщенная задача Ферма-Торричелли

Задача. Пусть на плоскости заданы три точки $ P_1=(x_1,y_1),P_2=(x_2,y_2),P_3=(x_3,y_3) $, не лежащие на одной прямой. Определить координаты точки $ P_{\ast}=(x_{\ast},y_{\ast}) $, решающей задачу оптимизации: $$ \min_{(x,y)} F(x,y) \quad \mbox{ для } \quad F(x,y)= \sum_{j=1}^3m_j \sqrt{(x-x_j)^2+(y-y_j)^2} \ . $$ Здесь числа $ m_1,m_2,m_3 $ предполагаются положительными и в дальнейшем называются весами.

Задача известна под различными названиями: (обобщенная) задача Ферма-Торричелли-Штейнера, задача Вебера, задача об оптимальном расположении (узловой) станции4), задача о трёх заводах.
П

Пример. В точках $ P_{1},P_2,P_3 $ расположены источники полезных ископаемых: железной руды, угля и воды соответственно. Известно, что для производства одной тонны стали необходимо иметь $ m_{1} $ тонн руды, $ m_2 $ тонн угля и $ m_3 $ тонн воды. В предположении, что стоимость перевозки одной тонны груза не зависит от его природы, где следует расположить сталелитейное производство так, чтобы минимизировать транспортные издержки?

§

Подробное обсуждение этой задачи (и к ней примыкающих) ЗДЕСЬ.

Задача о точке Лемуана-Греба

Задача. Найти точку плоскости, cумма квадратов расстояний от которой до сторон треугольника, лежащего в этой же плоскости, минимальна.

В русскоязычной литературе [5] иногда называется задачей Кэзи5), однако в других источниках атрибуция приведенной задачи Кэзи не подтверждена. См. краткое описание истории задачи ЗДЕСЬ.

Решение. Пусть $ d_1, d_2,d_3 $ — расстояния от точки $ P_{} $ плоскости до сторон треугольника с длинами $ D_1, D_2, D_3 $ соответственно. Воспользуемся тождеством Лагранжа: $$ (d_1^2+ d_2^2+d_3^2)(D_1^2+ D_2^2+D_3^2)\equiv $$ $$ \equiv (d_1D_1+ d_2D_2+d_3D_3)^2+(d_1D_2-d_2D_1)^2+(d_2D_3-d_3D_2)^2+ (d_1D_3-d_3D_1)^2 \ . $$ Величина $ d_1D_1+ d_2D_2+d_3D_3 $ является постоянной, не зависящей от координат точки $ P_{} $: $$ d_1D_1+ d_2D_2+d_3D_3 =2S \ , $$ где $ S_{} $ — площадь данного треугольника. Следовательно $ \min (d_1^2+d_2^2+d_3^2) $ достигается при условиях $$ d_1D_2-d_2D_1=0,\ d_2D_3-d_3D_2=0,\ d_1D_3-d_3D_1=0 \ , $$ то есть когда $$ \frac{d_1}{D_1}=\frac{d_2}{D_2}=\frac{d_3}{D_3} \ . $$ Определяемая этими соотношениями точка называется точкой Лемуана6) или точкой Греба7); в ней пересекаются симедианы треугольника.

Интересна параллель этой задачи с решаемой в пункте РАССТОЯНИЕ ДО ПЛОСКОСТИ: в трехмерном пространстве найти ближайшую к началу координат точку плоскости $ D_1x+D_2y+D_3z=2 S $. Решением будет точка с координатами $ (d_1,d_2,d_3) $.

Еще некоторые задачи

§

Построение прямой на плоскости, сумма квадратов расстояний до которой от заданных точек минимальна ЗДЕСЬ

Задачи учебные

ЗДЕСЬ.

Источники

[1]. Чезаро Э. Элементарный учебник алгебраического анализа и исчисления бесконечно малых. c.360-361

[2]. Икрамов Х.Д. Задачник по линейной алгебре. М.Наука. 1975 .

[3]. Uteshev A.Yu., Yashina M.V. Distance Computation from an Ellipsoid to a Linear or a Quadric Surface in)) $ {\mathbb R}^{n} $. Lect.Notes Comput. Sci. 2007. V.4770. P.392-401

[4]. Uteshev A.Yu., Yashina M.V. Metric Problems for Quadrics in Multidimensional Space. J.Symbolic Computation, 2015, Vol. 68, Part I, P. 287-315. Текст ЗДЕСЬ (pdf)

[5]. Попов Г.Н. Сборник исторических задач по элементарной математике. М.-Л.ГТТИ.1932

[6]. Uteshev A.Yu., Goncharova M.V. Metric problems for algebraic manifolds: Analytical approach. Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA), 2017, IEEE, http://ieeexplore.ieee.org/document/7974027/

1)
Аналогично тому, как это было сделано в примере из ПУНКТА
2)
Пока не написал теорию вычисления дискриминанта полинома от двух переменных - предлагаю принять на веру все нижеследующее
3)
Всегда будет наличествовать квадрат некоторого полинома по $ z_{} $, который следует отбрасывать - потом поясню откуда берется.
4)
(Нем.) Problem des Knotenpunktes [4].
5)
Casey John (1820-1891) — английский математик. Биография ЗДЕСЬ
6)
Lemoine Emile (1840-1912) — французский математик. Биография ЗДЕСЬ.
7)
Grebe Ernst Wilhelm (1804-1874) — немецкий учитель математики.
algebra2/optimiz/distance.txt · Последние изменения: 2024/03/09 18:59 — au