УказательРазделыОбозначенияАвторО проектеEnglish version


Вспомогательная страница к разделу ☞ ЗАДАЧА ФЕРМА-ТОРРИЧЕЛЛИ И ЕЕ РАЗВИТИЕ.


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

Задача. Подобрать величины весов \{m_j\}_{j=1}^K так, чтобы минимум функции \displaystyle f(P)=\sum_{j=1}^K m_j |PP_j| находился в наперед заданной точке P_{\ast} \not\in \{P_j\}_{j=1}^K.

Плоский случай

Т

Теорема [3]. Пусть вершины треугольника P_{1}P_2P_3 пронумерованы против часовой стрелки. Тогда для значений

m_1^{\ast} = |P_{\ast}P_1| \cdot \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|, \ m_2^{\ast} = |P_{\ast}P_2| \cdot \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|,\ m_3^{\ast} = |P_{\ast}P_3| \cdot \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right|

функция

F(x,y) = \sum_{j=1}^3 m_{j}^{\ast} \sqrt{(x-x_j)^2+(y-y_j)^2}

имеет стационарную точкой точку P_{\ast}=(x_{\ast},y_{\ast}). Если последняя выбирается внутри треугольника P_{1}P_2P_3, то величины m_1^{\ast},m_2^{\ast},m_3^{\ast} все положительны и

F(x_{\ast},y_{\ast})=\min_{(x,y)\in \mathbb R^2} F(x,y)= \left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ x_{\ast}^2+y_{\ast}^2 & x_1^2+y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2 \end{array} \right| \ .

Доказательство. Подставим выражения для весов в уравнения для частных производных функции F_{}:

\left\{ \begin{array}{ll} \displaystyle \frac{\partial F}{\partial x} &= \displaystyle \frac{m_1^{\ast}(x_{\ast}-x_1)}\sqrt{(x_{\ast}-x_1)^{2}+(y_{\ast}-y_1)^2}+\frac{m_2^{\ast}(x_{\ast}-x_2)}\sqrt{(x_{\ast}-x_1)^{2}+(y_{\ast}-y_1)^2}+ \frac{m_3^{\ast}(x_{\ast}-x_3)}\sqrt{(x_{\ast}-x_3)^2+(y_{\ast}-y_3)^2}, \\ \displaystyle \frac{\partial F}{\partial y} &= \displaystyle \frac{m_1^{\ast}(y_{\ast}-y_1)}\sqrt{(x_{\ast}-x_1)^{2}+(y_{\ast}-y_1)^2}+\frac{m_2^{\ast}(y_{\ast}-y_2)}\sqrt{(x_{\ast}-x_1)^{2}+(y_{\ast}-y_1)^2}+ \frac{m_3^{\ast}(y_{\ast}-y_3)}\sqrt{(x_{\ast}-x_3)^2+(y_{\ast}-y_3)^2}. \end{array} \right.

Получаем

(x_{\ast}-x_1)\left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|+ (x_{\ast}-x_2) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|+ (x_{\ast}-x_3) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| \ ,
(y_{\ast}-y_1)\left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|+ (y_{\ast}-y_2) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|+ (y_{\ast}-y_3) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| \ .

Нужно показать, что оба выражения равны 0_{}. Воспользуемся для доказательства некоторыми свойствами определителя. Представим первую сумму в виде определителя 4-го порядка:

\left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ 0 & x_{\ast}-x_1 & x_{\ast}-x_2 & x_{\ast}-x_3 \end{array} \right|

(см. ☞ разложение определителя по последней строке). Теперь прибавим к последней строке вторую:

\left| \begin{array}{llll} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ x_{\ast} & x_{\ast} & x_{\ast} & x_{\ast} \end{array} \right| \ ;

величина определителя не изменится (свойство 6 ЗДЕСЬ). У получившегося определителя две строки пропорциональны, следовательно (свойства 3 и 4 ЗДЕСЬ) он равен 0_{}. Для второй суммы доказательство аналогично.

Оценим теперь F(x_{\ast},y_{\ast}):

F(x_{\ast},y_{\ast}) =
= \left[(x_{\ast}-x_1)^2+(y_{\ast}-y_1)^2 \right] \left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right| + \left[(x_{\ast}-x_2)^2+(y_{\ast}-y_2)^2 \right] \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right| + \left[(x_{\ast}-x_3)^2+(y_{\ast}-y_3)^2 \right] \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| \ .

Для того, чтобы показать эквивалентность этого выражения определителю четвертого порядка из теоремы, разобьем его на x_{}- и y_{}-части. Оставим сначала только члены, содержащие букву x_{} в квадратных скобках предыдущей формулы:

(x_{\ast}-x_1)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right| + (x_{\ast}-x_2)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right| + (x_{\ast}-x_3)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| \ .

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

\left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ 0 & (x_{\ast}-x_1)^2 & (x_{\ast}-x_2)^2 & (x_{\ast}-x_3)^2 \end{array} \right| \ .

Прибавим к последней строке первую строку, умноженную на (-x_{\ast}^2) и вторую, умноженную на 2\, x_{\ast}:

\left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ x_{\ast}^2 & x_1^2 & x_2^2 & x_3^2 \end{array} \right| \ .

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

(y_{\ast}-y_1)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right| + (y_{\ast}-y_2)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right| +(y_{\ast}-y_3)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| = \left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ y_{\ast}^2 & y_1^2 & y_2^2 & y_3^2 \end{array} \right| \ .

Линейное свойство определителя доказывает справедливость выражения для F(x_{\ast},y_{\ast}) из теоремы.

Геометрический смысл величин из теоремы

Величина

\left| \begin{array}{ccc} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|

равна удвоенной площади треугольника P_{\ast} P_2P_3. Равенства

(x_{\ast}-x_1)\left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|+ (x_{\ast}-x_2) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|+ (x_{\ast}-x_3) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right|=0 \ ,
(y_{\ast}-y_1)\left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|+ (y_{\ast}-y_2) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|+ (y_{\ast}-y_3) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right|=0 \ ,

появившиеся в доказательстве теоремы, эквивалентны известному геометрическому свойству [1]:

\overrightarrow{P_{\ast}P_1} \cdot S_{_{\triangle P_{\ast}P_2P_3}}+\overrightarrow{P_{\ast}P_2} \cdot S_{_{\triangle P_{\ast}P_3P_1}}+\overrightarrow{P_{\ast}P_3} \cdot S_{_{\triangle P_{\ast}P_1P_2}}=\overrightarrow{\mathbb O} \ .

Геометрический смысл определителя

\left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ x_{\ast}^2+y_{\ast}^2 & x_1^2+y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2 \end{array} \right|

связан с величиной

h=-\frac{1}{S} \left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ x_{\ast}^2+y_{\ast}^2 & x_1^2+y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2 \end{array} \right| \quad npu \quad S= \left| \begin{array}{cccc} 1 & 1 & 1\\ x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \end{array} \right| ,

известной как степень точки P_{\ast} относительно окружности, проходящей через точки P_1, P_2 и P_3 (описанной окружности треугольника) [2]. Если обозначить через C_{} центр этой окружности, то

h=|CP_{\ast}|^2-|CP_j|^2 \quad npu \ j \in \{1,2,3\} \ ,

и если P_{\ast} лежит внутри треугольника, то эта величина отрицательна.

Пространственный случай

Как аналитика, так и иллюстрирующие ее геометрические соображения позволяют немедленно обобщить полученные результаты для случая \mathbb R^3 и K=4 точек. Пусть точки \{P_j=(x_{j},y_j,z_j) \}_{j=1}^4 некомпланарны и пронумерованы таким образом, чтобы выполнялось условие:

V=\left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ x_1 & x_2 & x_3 & x_4 \\ y_1 & y_2 & y_3 & y_4 \\ z_1 & z_2 & z_3 & z_4 \end{array} \right| > 0 \ .
Т

Теорема [3]. Положим

m_1^{\ast}= |P_{\ast}P_1|\cdot \left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 & x_4 \\ y_{\ast} & y_2 & y_3 & y_4 \\ z_{\ast} & z_2 & z_3 & z_4 \end{array} \right|,\ m_2^{\ast}= |P_{\ast}P_2|\cdot \left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 & x_4 \\ y_1 & y_{\ast} & y_3 & y_4 \\ z_1 & z_{\ast} & z_3 & z_4 \end{array} \right|,\ \dots ;

т.е. m_j^{\ast}=|P_{\ast}P_j| V_j, где значение V_j равно определителю, полученному из определителя V_{} заменой j-го столбца на1) \left[1,x_{\ast},y_{\ast},z_{\ast} \right]^{\top}. При таких значениях весов функция

F(x,y,z) = \sum_{j=1}^4 m_{j}^{\ast}\sqrt{(x-x_j)^2+(y-y_j)^2+(z-z_j)^2}

имеет своей стационарной точкой P_{\ast}=(x_{\ast},y_{\ast},z_{\ast}). Если P_{\ast} лежит внутри тетраэдра P_1P_2P_3P_4 то значения \{m_{j}^{\ast} \} все положительны и

F(x_{\ast},y_{\ast},z_{\ast})=\min_{(x,y,z)\in \mathbb R^3} F(x,y,z)
=-\ \left| \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ x_{\ast} & x_1 & x_2 & x_3 & x_4 \\ y_{\ast} & y_1 & y_2 & y_3 & y_4 \\ z_{\ast} & z_1 & z_2 & z_3 & z_4 \\ x_{\ast}^2+y_{\ast}^2+z_{\ast}^2 & x_1^2+y_1^2+z_1^2 & x_2^2+y_2^2+z_2^2 & x_3^2+y_3^2+z_3^2 & x_4^2+y_4^2+z_4^2 \end{array} \right| \ .

Доказательство полностью аналогично доказательству для плоского случая.

Геометрический смысл величин V,\{V_j\}, F(x_{\ast},y_{\ast},z_{\ast}) также аналогичен смыслу соответствующих величин для плоского случая. Величина V_{} равна шестикратному объему тетраэдра P_1P_2P_3P_4. Величина

-\frac{1}{V}\ \left| \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ x_{\ast} & x_1 & x_2 & x_3 & x_4 \\ y_{\ast} & y_1 & y_2 & y_3 & y_4 \\ z_{\ast} & z_1 & z_2 & z_3 & z_4 \\ x_{\ast}^2+y_{\ast}^2+z_{\ast}^2 & x_1^2+y_1^2+z_1^2 & x_2^2+y_2^2+z_2^2 & x_3^2+y_3^2+z_3^2 & x_4^2+y_4^2+z_4^2 \end{array} \right|

известна как степень точки P_{\ast} относительно сферы [2], описанной вокруг тетраэдра; она равна

|CP_{\ast}|^2-|CP_j|^2 \quad npu \ j\in \{1,2,3,4 \} \ ,

где C_{} означает центр описанной сферы.

Если точка P_{\ast} лежит внутри тетраэдра, то эта величина отрицательна.

Многомерный случай

Т

Теорема [4]. Пусть точки \{P_j=(x_{j1},\dots,x_{jn})\}_{j=1}^{n+1} некомпланарны и пронумерованы таким образом, что выполняется условие

V= \left| \begin{array}{llll} 1 & 1 & \dots & 1\\ x_{11} & x_{21} & \dots & x_{n+1,1} \\ \vdots & \vdots & & \vdots \\ x_{1n} & x_{2n} & \dots & x_{n+1,n} \end{array} \right| > 0 \ .

Обозначим V_j определитель, получающийся заменой j_{}-го столбца определителя V_{} на столбец \left[1,x_{\ast 1},\dots,x_{\ast n} \right]^{\top}. Тогда для значений весов

\left\{m_j^{\ast} = |P_{\ast}P_j| V_j \right\}_{j=1}^{n+1}

функция

F(P) = \sum_{j=1}^{n+1} m_{j}^{\ast} |PP_j|

имеет своей стационарной точкой точку P_{\ast}=(x_{\ast 1},\dots,x_{\ast n}). Если P_{\ast} лежит внутри симплекса P_1P_2\dots P_{n+1}, то все значения \{ m_j^{\ast} \} положительны и

F(P_{\ast})= \displaystyle \sum_{j=1}^{n+1} V_j |P_{\ast}P_j|^2 =- \left| \begin{array}{lllll} 1 & 1 & \dots & 1 & 1 \\ x_{11} & x_{21} & \dots & x_{n+1,1} & x_{\ast 1} \\ \vdots & \vdots & & \vdots & \vdots \\ x_{1n} & x_{2n} & \dots & x_{n+1,n} & x_{\ast n} \\ \displaystyle \sum_{\ell=1}^n x_{1\ell}^2 & \displaystyle \sum_{\ell=1}^n x_{2\ell}^2 & \dots & \displaystyle \sum_{\ell=1}^n x_{n+1,\ell}^2 & \displaystyle \sum_{\ell=1}^n x_{\ast\ell}^2 \end{array} \right| \ .

Источники

[1]. Прасолов В.В. Задачи по планиметрии. Часть 2. М.Наука. 1991, с. 10

[2]. Uspensky J.V. Theory of Equations. New York. McGraw-Hill. 1948

[3]. Uteshev A.Yu. Analytical Solution for the Generalized Fermat-Torricelli Problem. Amer.Math.Monthly. V. 121, N 4, 318-331, 2014. Препринт ☞ arXive:1208.3324v1 (220 Kb)

[4]. Uteshev A.Yu., Yashina M.V. Stationary Points for the Family of Fermat-Torricelli-Coulomb-like potential functions. Proc. 15th Workshop CASC (Computer Algebra in Scientific Computing), Berlin 2013. Springer. Lecture Notes in Computer Science. V.8136 , 2013, P. 412-426.


2014/05/28 11:07 редактировал au