!!§!! Материалы к докладу 01.04.2014
----
От
Ферма
до
Максвелла
:
стационарные
точки семейства потенциалов
Алексей Юрьевич Утешев
----
Alexei Uteshev
From Fermat to Maxwell:
on the stationary points of a family of potential functions
----
~~TOC~~
==Задача 1==
$$
F(P) = m_1 |PP_1|+\dots+ m_K |PP_K| \to \min_{P\in \mathbb R^n}
$$
\\
\\
\\
\\
$$ \{P_1,\dots,P_K\} \subset \mathbb R^n,\ \{m_1,\dots,m_K\} \subset \mathbb R_{+} $$
\\
$$ | \cdot | - \mbox{ евклидово расстояние } $$
\\
\\
\\
\\
\\
===Классическая задача Ферма-Торричелли==
$$
F(x,y)= \sum_{j=1}^{3} \sqrt{(x-x_j)^2+(y-y_j)^2} \to \min_{(x,y)\in \mathbb R^2}
$$
Декарт,
1638
=>
Ферма
=>
(Мерсенн ?)
=>
Торричелли, Фаньяно, Симпсон,...
\\
\\
>
Datis tribus punctis, quartum reperire, a quo si ducantur tres rectæ ad data puncta, summa trium harum rectarum sit minima quantitas
\\
> (//лат.// Для трех заданных точек найти четвертую, такую что если от нее провести прямые линии до данных точек, сумма расстояний будет наименьшей)
>**P. de Fermat**, <<Œuvres de Fermat>>, 1679, Livre I, Paris.
\\
\\
\\
\\
===Обобщенная задача Ферма-Торричелли==
$$
F(x,y)= \sum_{j=1}^{3} m_j \sqrt{(x-x_j)^2+(y-y_j)^2} \to \min_{(x,y)\in \mathbb R^2}
$$
\\
Штейнер, Лаунхардт, Вебер,...
\\
\\
\\
\\
==Задача 2==
$$
F(P) = \frac{m_1}{|PP_1|}+\dots+ \frac{m_K}{|PP_K|}
$$
\\
\\
$$ \{P_1,\dots,P_K\} \subset \mathbb R^n,\ \{m_1,\dots,m_K\} \subset \mathbb R $$
\\
$$ | \cdot | - \mbox{ евклидово расстояние } $$
\\
\\
Кулоновский или ньютоновский потенциал
\\
?
Стационарные точки
$ F(P) $
(положения равновесия)
?
==Задача 1-2==
$$
F(P) = m_1|PP_1|^L+\dots+ m_K|PP_K|^L
$$
\\
\\
$$ 0\ne L \in \mathbb R $$
\\
\\
\\
$$
\begin{array}{c} P_1 \\ m_1
\end{array} ; \dots ;
\begin{array}{c} P_K \\ m_K
\end{array}
\qquad \qquad \mbox{ конфигурация весов }
$$
\\
\\
\\
\\
\\
==Актуальность==
$$
F(P) = m_1 |PP_1|+\dots+ m_K |PP_K| \to \min_{P\in \mathbb R^2}
$$
Теория оптимального размещения (location theory, location analysis).
\\
\\
В городах
$ P_{1},P_2,P_3 $
расположены источники полезных ископаемых: железной руды, угля и воды соответственно.
Для производства
$ 1_{} $
тонны стали необходимо иметь
$ m_{1} $
тонн руды,
$ m_2 $
тонн угля и
$ m_3 $
тонн воды.
Где расположить сталелитейное производство так, чтобы минимизировать транспортные издержки
?
{{ algebra2:optimiz:distance:standort.jpg |}}
>//Положим, мы имеем перед собой производство, работающее с двумя локализованными материалами, причем для выработки// $ 1_{} $ //т. продукта требуется// $ 3/4 $ //т. одного материала и// $ 1/2 $ //т. другого. В таком случае мы получаем штандортную фигуру, на// «материальных компонентах» (//линиях, соединяющих штандорт с// «материальными складами») //которого передвигаются веса в// $ 3/4 $ и $ 1/2 $, //в то время как// «потребительская компонента» //отягощена// $ 1_{} $.
> **Альфред Вебер (1909)**
\\
\\
\\
Сети Штейнера
\\
\\
==Методы решения: геометрия==
Только для плоского случая.
Circinus et regula
((лат.) циркуль и линейка)
\\
\\
$ m_1=m_2=m_3=1 $,
Торричелли
,
1642
{{ algebra2:optimiz:distance:geometry_torri1.jpg |}}
Точка
Ферма
-
Торричелли
{{ algebra2:optimiz:distance:torri_point.jpg |}}
$ \{m_1,m_2,m_3\} \subset \mathbb R_{+} $,
Лаунхардт
,
1872
\\
\\
$ m_1=m_2=m_3=m_4=1 $,
Штейнер
,
1850
Точка пересечения диагоналей четырехугольника
$ P_1P_2P_3P_4 $.
==Методы решения: механика==
Только для плоского случая.
{{ algebra2:optimiz:distance:torri:picture21.png |}}
\\
\\
\\
\\
\\
==Существование и единственность==
!!Т!! //Минимум//
$$ F(P)=\sum_{j=1}^K m_j |PP_j| $$
//существует и единствен.//
1.
// Если // $ \exists P_{i} $:
$$
\left|\sum_{j=1 \atop j \ne i}^K m_j \frac{P_j-P_i}{|P_jP_i|} \right| \le m_i \ , $$
//то//
$$ \min F(P) = F(P_{i}) \ . $$
2.
//Если // $ \forall i \in \{1,\dots,K\} $:
$$
\left|\sum_{j=1 \atop j \ne i}^K m_j \frac{P_j-P_i}{|P_jP_i|} \right| > m_i \ , $$
//то//
$$ \min F(P) = F(P_{\ast}) , $$
//где// $ P_{\ast} $ --- решение градиентной системы:
$$ \sum_{j=1}^K m_j \frac{P-P_j}{|PP_j|}=\mathbb O_{n\times 1}\, ; $$
//в этом случае,// $ P_{\ast} \not\in \{P_j\}_{j=1}^K $.
===Численное решение==
Вайсфельд
,
1937
: $ \mathbb R^{n}_{}, m_1=\dots=m_K=1 $
$$
\frac{P-P_1}{|PP_1|}+\dots+\frac{P-P_K}{|PP_K|}= \mathbb O_{n\times 1},
$$
$$
\Updownarrow
$$
$$
P=\underbrace{\left(\frac{P_1}{|PP_1|}+\dots+\frac{P_K}{|PP_K|} \right) \bigg/ \left(\frac{1}{|PP_1|}+\dots+\frac{1}{|PP_K|} \right)}_{=\Phi(P)} \, .
$$
Метод простой итерации:
$$
P^{(k)}=\Phi(P^{(k-1)}) \to P_{\ast}
$$
\\
\\
\\
\\
\\
===Мультифокусные эллипсы==
$$
F(x,y)= \sum_{j=1}^{K} m_j\sqrt{(x-x_j)^2+(y-y_j)^2} \ ,
$$
\\
\\
$$ F(x,y)=const \ . $$
\\
$ K=2 $ --- **овалы Декарта**.
\\
\\
$$ P_1=(1,1),P_2=(3,5),P_3=(7,2) $$
{{ algebra2:optimiz:distance:gen_ellipse3.jpg |}}
$$ K\ge 3, m_1:m_2:\dots:m_K= \mbox{ рациональное } \ : \ \mbox{ рациональное } \ : \dots \ : \ \mbox{ рациональное } $$
Чирнгауз, Максвелл...
$ K=3, m_1=m_2=m_3 $ --- **изодапаны**((//др.греч.//) $ \iota \sigma o \varsigma $ --- равный, $ \delta \breve{\alpha} \pi \acute{\alpha} \nu \alpha $ --- расходование, расход, трата; isodapane (//англ//.), А.Вебер);
кривая состоит из точек одинаковой суммарной стоимости транспортных перевозок до них из $ \{P_j\} $.
==Сети Штейнера==
$$ \{P_1,\dots,P_K\} \subset \mathbb R^2 $$
Построить **минимальное дерево Штейнера**: связную систему $ \mathbf L_{} $ прямолинейных отрезков:
1.
любые две точки $ P_{j} $ и $ P_{\ell} $ могли быть связаны ломаной линией, звенья которой входили бы в состав системы $ \mathbf L_{} $;
2.
общая длина всей системы $ \mathbf L_{} $ была наименьшей.
$$ P_1=(2,1) , P_2=(1,6) , P_3=(8,7) , P_4=(6,1) $$
решение задачи заключается в построении двух точек $ T_{1} $ и $ T_{2} $, таких, что они являются точками Ферма-Торричелли для, соответственно, треугольников $ P_1P_2T_2 $ и $ P_3P_4T_1 $.
$$
T_1 \approx (2.91184,\ 2.49410) \ ,
T_2 \approx (5.21583,\ 2.43798) \ .
$$
{{ algebra2:optimiz:steiner41.gif |}}
$$ |P_1P_3|+|P_2P_4|\approx 15.55634 \ ;\ $$
$$ | \mathbf{L} |= |P_1T_1|+|P_2T_2|+|P_3T_2|+|P_4T_2|+|T_1T_2| \approx 15.03073 \ . $$
\\
\\
$$ P_4=(6,4) $$
{{ algebra2:optimiz:steiner42.gif |}}
==Аналитическое решение обобщенной задачи Ферма-Торричелли==
$$ F(x,y)=\sum_{j=1}^3 m_j \sqrt{(x-x_j)^2+(y-y_j)^2} $$
!!Т!! //Обозначим величину угла треугольника// $ P_{1}P_2P_3 $ //при вершине// $ P_{j} $ //через// $ \alpha_j $. // Если нарушено// $ j $-//е из трех условий//
$$
\ m_2^2+m_3^3+2\, m_2m_3 \cos \alpha_1 > m_1^2 , \ \ m_1^2+m_3^2+2\, m_1m_3 \cos \alpha_2 > m_2^2,\ m_1^2+m_2^2+2\, m_1m_2 \cos \alpha_3 > m_3^2\, ,
$$
//то//
$$ \min F(x,y) = F(x_j,y_j) \ . $$
//Если все неравенства выполняются, то//
$$ \min F(x,y) = F(x_{\ast},y_{\ast}) $$
//при//
$$
x_{\ast}=\frac{K_1K_2K_3}{4 |S| \sigma d} \left(\frac{x_1}{K_1}+\frac{x_2}{K_2}+\frac{x_3}{K_3} \right), \
y_{\ast}=\frac{K_1K_2K_3}{4 |S| \sigma d} \left(\frac{y_1}{K_1}+\frac{y_2}{K_2}+\frac{y_3}{K_3} \right)\ .
$$
//При этом//
$$
F(x_{\ast},y_{\ast})=\min_{(x,y)} F(x,y)=\sqrt{d} \ .
$$
//Здесь//
$$
d= 2\, |S| \sigma + \frac{1}{2}\left[m_1^2(r_{12}^2+r_{13}^2-r_{23}^2)+
m_2^2(r_{23}^2+r_{12}^2-r_{13}^2)+m_3^2(r_{13}^2+r_{23}^2-r_{12}^2) \right] \ ;
$$
$$
r_{j\ell}=\sqrt{(x_j-x_{\ell})^2+(y_j-y_{\ell})^2}=|P_jP_{\ell}| \quad npu \ \{j,\ell\} \subset \{1,2,3\} \ ;
$$
$$
S=x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_3y_2-x_2y_1=\left|\begin{array}{cc}
x_2-x_1 & x_3-x_1 \\
y_2-y_1 & y_3-y_1
\end{array}
\right|=\left|
\begin{array}{ccc}
1 & 1 & 1 \\
x_1 & x_2 & x_3 \\
y_1 & y_2 & y_3
\end{array}
\right| \ ;
$$
$$
\sigma= \frac{1}{2} \sqrt{-m_1^4-m_2^4-m_3^4+2\,m_1^2m_2^2+2\,m_1^2m_3^2+2\,m_2^2m_3^2} \ ;
$$
$$
\left\{
\begin{array}{ccc}
K_1&=&(r_{12}^2+r_{13}^2-r_{23}^2)\sigma+(m_2^2+m_3^2-m_1^2) |S| , \\
K_2&=&(r_{23}^2+r_{12}^2-r_{13}^2)\sigma+(m_1^2+m_3^2-m_2^2) |S| , \\
K_3&=&(r_{13}^2+r_{23}^2-r_{12}^2)\sigma+(m_1^2+m_2^2-m_3^2) |S| .
\end{array}
\right.
$$
==Обратная задача==
$$ F(P)=\sum_{j=1}^K m_j |PP_j| $$
Подобрать $ \{m_j\}_{j=1}^K $:
$$ \min F(P)= F(P_{\ast}), \qquad P_{\ast} \not\in \{P_j\}_{j=1}^K . $$
\\
\\
\\
\\
!!Т!!
$$
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}) $.
$$
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| \ .
$$
{{ algebra2:optimiz:distance:torri:inverse1.jpg |}}
==Кулоновский потенциал==
Найти стационарные точки функции
$$
F(P)= \sum_{j=1}^K \frac{m_j}{\left|PP_j \right|} \ .
$$
\\
\\
$$ \{P,P_1,\dots,P_K\} \subset \mathbb R^3 $$
\\
\\
Гипотеза
Максвелла
. Число стационарных точек $ \le (K-1)^2 $. Не доказана.
\\
\\
\\
$$ P_1=(1,1), P_2=(5,1) , P_3=(2,6) . $$
Cтационарные точки функции
$$
F(x,y)=\frac{1}{\sqrt{(x-1)^2+(y-1)^2}}+ \frac{m_2}{\sqrt{(x-5)^2+(y-1)^2}}+\frac{m_3}{\sqrt{(x-2)^2+(y-6)^2}}
$$
{{ algebra2:optimiz:distance:coulomb_50.jpg |}}
$$
\begin{array}{rrr}
\displaystyle \frac{x-1}{\sqrt{(x-1)^2+(y-1)^2}^3}& \displaystyle +\frac{m_2(x-5)}{\sqrt{(x-5)^2+(y-1)^2}^3}& \displaystyle +\frac{m_3(x-2)}{\sqrt{(x-2)^2+(y-6)^2}^3}=0\, , \\
\displaystyle \frac{y-1}{\sqrt{(x-1)^2+(y-1)^2}^3}& \displaystyle +\frac{m_2(y-1)}{\sqrt{(x-5)^2+(y-1)^2}^3}& \displaystyle +\frac{m_3(y-6)}{\sqrt{(x-2)^2+(y-6)^2}^3}=0 \,
\end{array}
$$
$$
\Updownarrow
$$
Обозначим $ A_1, A_2 $ и $ A_3 $ слагаемые в любом из этих уравнений.
Последовательность возведений в степень по схеме
$$ A_1+A_2+A_3=0 \quad \Rightarrow \quad (A_1+A_2)^2=A_3^2 \quad \Rightarrow \quad (2\, A_1A_2)^2 = (A_3^2-A_1^2 - A_2^2)^2 $$
$$
F_1(x,y,m_2,m_3)=0,\ F_2(x,y,m_2,m_3)=0
$$
где $ F_{1} $ и $ F_{2} $ --- полиномы $ \deg F_j=28 $, коэффициенты ~ $ 10^{19} $.
Число стационарных точек --- от $ 2_{} $ до $ 4_{} $, в зависимости от $ m_2,m_3 $.
===Обратная задача==
$$
F(P) = m_1|PP_1|^L+\dots+ m_K|PP_K|^L
$$
\\
\\
Задача управления: подобрать $ \{m_j\} $ так, чтобы $ F(P) $ имела стационарную точку в заданной точке $ P_{\ast} $.
!!Т!!
$$
m_1^{\ast} = |P_{\ast}P_1|^{2-L} \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|^{2-L} \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|^{2-L} \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} |PP_j|^L $$
//имеет стационарную точкой точку// $ P_{\ast}=(x_{\ast},y_{\ast}) $. //При этом//
$$
F(x_{\ast},y_{\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+y_{\ast}^2 & x_1^2+y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2
\end{array}
\right| \ .
$$
==Кулоновский потенциал (продолжение)==
!!Т!!
$$
S_1(x,y)=
\left|
\begin{array}{ccc}
1 & 1 & 1 \\
x & x_2 & x_3 \\
y & y_2 & y_3
\end{array}
\right|,\
S_2(x,y)=
\left|
\begin{array}{ccc}
1 & 1 & 1 \\
x_1 & x & x_3 \\
y_1 & y & y_3
\end{array}
\right|,\
S_3(x,y)=
\left|
\begin{array}{ccc}
1 & 1 & 1 \\
x_1 & x_2 & x \\
y_1 & y_2 & y
\end{array}
\right| \, .
$$
$$ \partial F / \partial x = 0, \partial F / \partial y = 0 \ , $$
$$
\Downarrow
$$
$$
m_1:m_2:m_3=|PP_1|^{2-L} S_1(x,y):|PP_2|^{2-L} S_2(x,y):|PP_3|^{2-L} S_3(x,y) \ .
$$
!!=>!! Cтационарные точки функции $ F_{} $ удовлетворяют системе алгебраических уравнений
$$
\left\{ \begin{array}{ll}
m_2^2S_1^2(x,y) |PP_1|^{2(2-L)} - m_1^2S_2^2(x,y) |PP_2|^{2(2-L)} & =0, \\
m_2^2S_3^2(x,y) |PP_3|^{2(2-L)} - m_3^2S_2^2(x,y) |PP_2|^{2(2-L)} & =0.
\end{array}
\right.
$$
\\
\\
\\
$$
F(x,y)=\frac{1}{\sqrt{(x-1)^2+(y-1)^2}}+ \frac{m_2}{\sqrt{(x-5)^2+(y-1)^2}}+\frac{m_3}{\sqrt{(x-2)^2+(y-6)^2}}
$$
$$
\Downarrow
$$
$$
\widetilde F_1(x,y,m_2,m_3)=0,\ \widetilde F_2(x,y,m_2,m_3)=0 \ ,
$$
при
$$
\begin{array}{c}
\widetilde F_1(x,y,m_2,m_3)= \\
=m_2^2\,(5\,x+3\,y-28)^2(x^2+y^2-2\,x-2\,y+2)^3 -(5\,x-y-4)^2(x^2+y^2-10\,x-2\,y+26)^3 , \\
\widetilde F_2(x,y,m_2,m_3)= \\
=m_2^2\,(4\,y-4)^2(x^2+y^2-4\,x-12\,y+40)^3 -m_3^2\,(5\,x-y-4)^2(x^2+y^2-10\,x-2\,y+26)^3.
\end{array}
$$
$$
\Downarrow
$$
Исключение переменной $ x_{} $
$$
\mathcal Y(y,m_2,m_3)=\mathcal R_{x}(\tilde F_1,\tilde F_2), \ \deg_y \mathcal Y = 34
$$
\\
\\
\\
$$ m_2=2, m_3=2 \quad \Rightarrow \quad
\mathfrak S_1 \approx (2.666216,\, 1.234430),\ \mathfrak S_2 \approx (2.744834,\, 3.244859) ; $$
$$ m_2=2, m_3=4 \quad \Rightarrow \quad
\mathfrak S_1 \approx (1.941246,\, 2.552370) , \mathfrak S_2 \approx (2.655622,\, 1.638871) ,\ \mathfrak S_3 \approx (3.330794,\ 2.826444),
$$
$$ \mathfrak N \approx (2.552939,\, 2.271691) \ . $$
Граница на плоскости $ (m_2,m_3) $ между двумя областями?
$$ \Psi (m_2,m_3) = 0 $$
--- ровно $ 3 $ стационарных точки (одна вырождена)
$$
\Psi(m_2,m_3)=
$$
$$
=3^{36}(64\,m_3^2+192\,m_2m_3+169\,m_2^2)^5(64\,m_3^2-192\,m_2m_3+169\,m_2^2)^5(28561\,m_2^4+19968\,m_2^2m_3^2+4096\,m_3^4)^7 $$
$$ + \dots + $$
$$ + 2^2\cdot 3^{31} \cdot 17^{40} (5545037166327\, m_2^4-161882110764644\,m_2^2m_3^2+1656772227072\,m_3^4) $$
$$ + 2^3\cdot 3^{36}\cdot 17^{44} (51827\,m_2^2+28112\,m_3^2)+ 3^{36}\cdot 17^{48} \ . $$