!!§!! Материалы к докладу 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} \ . $$