N точечных зарядов на поверхности сферы

[Droog_Andrey]

В заглавии темы описана физическая модель этой задачи на поиск минимума, однако задача явно математическая, поэтому с подфорумом я вроде как не ошибся.

Итак, необходимо найти такое расположение $N$ одинаковых точечных зарядов на поверхности сферы, при котором их взаимное отталкивание минимально (т.е. при постоянном радиусе сферы минимальна сумма величин, обратных расстояниям между зарядами).

Решения этой задачи для первых шести значений $N$ могут быть получены аналитически и хорошо известны. Это расположение: в произвольной точке сферы; на концах диаметра; в вершинах правильного треугольника, вписанного в экватор; в вершинах правильного тетраэдра; в вершинах правильной треугольной бипирамиды; в вершинах правильного октаэдра (симметрии $C_{\infty v}, D_{\infty h}, D_{3h}, T_{d}, D_{3h}, O_{h}$ соответственно).

Однако о решениях для $N > 6$ информации в известных мне источниках оказалось не так уж и много. Я попробовал найти решения численными методами и на скорую руку получил следующие результаты.

Для $N = 7$ получается хиральное расположение симметрии $C_2$, которое можно получить некоторым смещением вершин правильной пентагональной бипирамиды:

$$\begin{array}{ccc}point & \varphi & \theta \\ 1 & 0 & 0 \\ 2 & \varphi_1 & \theta_1 \\ 3 & \varphi_1+\pi & \theta_1 \\ 4 & \varphi_2 & \theta_2 \\ 5 & \varphi_2+\pi & \theta_2 \\ 6 & $\varphi_3+\frac{\pi}{2} & \frac{\pi}{2}+\theta_3 \\ 7 & $\varphi_3-\frac{\pi}{2} & \frac{\pi}{2}+\theta_3 \end{array}$$

где $\varphi_1 \approx -0.1$, $\varphi_2 \approx 0.2$, $\varphi_3 \approx -0.01$; $\theta_1 \approx 1.3$, $\theta_2 \approx 2.5$, $\theta_3 \approx -0.02$.

Случай $N = 8$, по-видимому, имеет решением расположение зарядов в вершинах квадратной антипризмы (симметрия $S_8$):

$$\begin{array}{ccc}point & \varphi & \theta \\ 1 & 0 & \theta_1 \\ 2 & \pi & \theta_1 \\ 3 & \frac{\pi}{2} & \theta_1 \\ 4 & -\frac{\pi}{2} & \theta_1 \\ 5 & \frac{\pi}{4} & \pi-\theta_1 \\ 6 & -\frac{\pi}{4} & \pi-\theta_1 \\ 7 & \frac{\pi}{4}-\pi & \pi-\theta_1 \\ 8 & -\frac{\pi}{4}+\pi & \pi-\theta_1 \end{array}$$

где $\theta_1 \approx 0.97$.

При $N = 9$ шесть зарядов располагаются по вершинам правильной треугольной призмы, а остальные три - напротив центров её боковых граней (симметрия $D_{3h}$):

$$\begin{array}{ccc}point & \varphi & \theta \\ 1 & 0 & \theta_1 \\ 2 & \frac{2\pi}{3} & \theta_1 \\ 3 & -\frac{2\pi}{3} & \theta_1 \\ 4 & \frac{\pi}{3} & \frac{\pi}{2} \\ 5 & -\frac{\pi}{3} & \frac{\pi}{2} \\ 6 & \pi & \frac{\pi}{2} \\ 7 & 0 & \pi-\theta_1 \\ 8 & \frac{2\pi}{3} & \pi-\theta_1 \\ 9 & -\frac{2\pi}{3} & \pi-\theta_1 \end{array}$$

где $\theta_1 \approx 0.78$.

Случай $N = 10$ похож на случай $N = 8$ (та же симметрия $S_8$), только добавляется два заряда на оси симметрии, и антипризма, соответственно, уменьшается в высоте:

$$\begin{array}{ccc}point & \varphi & \theta \\ 1 & 0 & \theta_1 \\ 2 & \pi & \theta_1 \\ 3 & \frac{\pi}{2} & \theta_1 \\ 4 & -\frac{\pi}{2} & \theta_1 \\ 5 & \frac{\pi}{4} & \pi-\theta_1 \\ 6 & -\frac{\pi}{4} & \pi-\theta_1 \\ 7 & \frac{\pi}{4}-\pi & \pi-\theta_1 \\ 8 & -\frac{\pi}{4}+\pi & \pi-\theta_1 \\ 9 & 0 & 0 \\ 10 & 0 & \pi \end{array}$$

где $\theta_1 \approx 1.14$.

И если икосаэдрическое (симметрия $I_h$) расположение зарядов для $N = 12$ очевидно, то для $N = 11$ найти симметричных решений мне вовсе не удалось.

* * * * * * * * * * *

Задача эта, я так думаю, уже давно известна и давно решалась. Однако почему-то очень трудно найти информацию об этом. Было бы весьма интересно проверить полученные мной конфигурации, найти аналитические выражения для упомянутых углов, найти решение для $N = 11$ и т.д., а также изучить вопрос единственности (с точностью до поворотов и отражений) решений для различных $N$.

[maxal]

см. http://relf.livejournal.com/31867.html

[Droog_Andrey]

maxal, спасибо за ссылку

Всё-таки для $N = 7$ получается пентагональная бипирамида. Интересно

По ссылке один из участников обсуждения предлагает в качестве решения для $N = 60$ усечённый икосаэдр, хотя мне вероятным кажется хиральный вариант (как и для случая $N = 24$).

Вопрос об аналитическом решении, или хотя бы об аналитическом выражении углов остаётся открытым...

Добавлено спустя 39 минут 4 секунды:

Droog_Andrey писал(а):

хотя мне вероятным кажется хиральный вариант

Согласно расчётным данным Слона, случай $N = 60$ имеет симметрию $D_3$, в то время как косой (курносый) додекаэдр появляется в случае $N = 72$ с симметрией $I$: здесь его пятиугольные грани немного увеличиваются относительно расстояний между ними, и появляется по точке над их центрами.

Что интересно - именно такую конфигурацию из 72 точек я получил, исследуя геометрию ряда кластерных химических соединений

[Circiter]

2Droog_Andrey

Цитата:

Задача эта, я так думаю, уже давно известна и давно решалась.

Это же вроде задача Томсона (вообще говоря, не решенная). О ней многое известно в теории приближений функций, но точные решения получены лишь в некоторых частных случаях.

[R.Deyanov]

прошу прощения, возможно не в тему: как-то считал численно расположение 240-а(до 300-т) одинаковых зарядов (задача Томсона) на сфере. Интересно было бы сравнить координаты с приведенными здесь.
Координаты можно посмотреть http://math-lab.ru/?i=17 (не в курсе как пользоваться [url][/url])

Отделено от темы Интересный граф с 240 вершинами, натянутый на 3-сферу.

[Droog_Andrey]

R.Deyanov в сообщении #382917 писал(а):

прошу прощения, возможно не в тему: как-то считал численно расположение 240-а(до 300-т) одинаковых зарядов (задача Томсона) на сфере.

Об этом сюда: topic20466.html

При расположении $240$ зарядов на $3$-сфере они расположатся так, что у каждого заряда будет существенно больше четырёх соседей.

[R.Deyanov]

всем привет,
эту задачку я решал численно исходя из минимума потенциальной энергии.
Но занимался её как тестовой задачей для своего метода глобальной минимизации.
Координаты N зарядов( до 300-т) можно скачать на http://math-lab.ru/?i=17 (не в курсе как пользоваться [url][/url]) - получил за один прогон программы.
Можно посчитать и для N более 1000 зарядов, - если кому интересно практическое применение пишите в личку, просто занят текущими задачами.

Предупреждение за дублирование сообщений!

[Droog_Andrey]

R.Deyanov, совпадают ли результаты с результатами Слона? http://www.research.att.com/~njas/electrons/index.html

[мат-ламер]

Что касается аналитического решения, то задача имеет много локальных минимумов. Для данного конкретного локального минимума, найденного численно, мы можем доказать, что это действительно локальный минимум. Насчёт глобальности непонятно.

[AD]

(как пользоваться [url])

R.Deyanov в [url=http://dxdy.ru/post383065.html#p383065]сообщении #383065[/url] писал(а):

(не в курсе как пользоваться [url][/url])

Вот так: [url=ссылка]слово[/url]

[R.Deyanov]

Droog_Andrey в сообщении #383264 писал(а):

R.Deyanov, совпадают ли результаты с результатами Слона? http://www.research.att.com/~njas/electrons/index.html

ну, если взять его последнее значение для N=282:
282 37147.2944185 - J. A. Sloane

282 37147.99302 8.88E-04 0.000790584 11.7365 - это у меня

совпадают или нет?
ну, надо сравнивать координаты(посовмещать). Хотя потенциалы и близки( 0.002%), утверждать что-либо с уверенностью нельзя.
именно поэтому я и выложил координаты - потенциал легко воспроизвести по простой формуле.
не забывайте, координаты были найдены сразу для ВСЕХ N до 300.
8.88E-04 - это норма градиента( 282*2=564 переменных), можно было бы дожимать и до -06

-- Пт дек 03, 2010 23:06:44 --

AD в сообщении #383275 писал(а):

(как пользоваться [url])

R.Deyanov в [url=http://dxdy.ru/post383065.html#p383065]сообщении #383065[/url] писал(а):

(не в курсе как пользоваться [url][/url])

Вот так: [url=ссылка]слово[/url]

да, спасибо (вчера только зарегился)

-- Пт дек 03, 2010 23:12:22 --

мат-ламер в сообщении #383271 писал(а):

Что касается аналитического решения, то задача имеет много локальных минимумов. Для данного конкретного локального минимума, найденного численно, мы можем доказать, что это действительно локальный минимум. Насчёт глобальности непонятно.

- да, золотые слова

можно отловить седловую точку(легко)

а вот отличить лок.минимум от глобального в принципе невозможно, если только нет априорных оценок.

этот момент у меня в программе просто беда - минимум находится быстро, но потом основное время уходит на то, чтобы принять решение что ничего глубже нет.

[Droog_Andrey]

R.Deyanov в сообщении #383311 писал(а):

Droog_Andrey в сообщении #383264 писал(а):

R.Deyanov, совпадают ли результаты с результатами Слона? http://www.research.att.com/~njas/electrons/index.html

ну, если взять его последнее значение для N=282:
282 37147.2944185 - J. A. Sloane

282 37147.99302 8.88E-04 0.000790584 11.7365 - это у меня

совпадают или нет?

Судя по тому, насколько точно совпадают значения потенциалов для многих $N$, это отклонение весьма существенно, т.е. минимум, по-видимому, не является глобальным для $N \in \{37,38,52,54,55,56,58,59,68,69,70,78,81,82,83,85,86,87,90,94,98,100,101\}$, а также для всех $N>103$ из таблицы Слона, кроме $N=119$ и $N=121$.

[ИСН]

Тут какую-то визуализацию уже прикручивать надо, а то что это такое - по одной цифре сравнивать...

[R.Deyanov]

да, вроде я нигде и не утверждал, что достигнуты глобальные значения.

ну, напишите г-ну J.A.Sloane - попросите выложить координаты(для программы это ноль секунд).
по этим координатам я воспроизведу, скорее всего, его значение 37147.2944185.
после этого скажу ему что он молодец(чихал он на мое мнение) и спрошу его что ему помешало посчитать как и другим дальше? Ответ знаю - время счета. Для справки: время счета одного варианта для N>200 на суперкомпе с распараллеливанием(и с подбором константы Липшица) порядка 5-8 часов без гарантии что найден глобальный минимум.
здесь же я прогнал ВСЕ N за считанные минуты(в лом искать архивы, сказать точнее) для ТЕСТИРОВАНИЯ программы.
кстати, кто занимается поиском этих координат для своих задач(в частности, в кодированиях), могут взять их и как начальное приближение. Получится глубже - хорошо, не получится - обращайтесь, поможем.

по визуализации - придерживаюсь критерия: совмещаются конфигурации или нет (ну, и совпадение потенциалов с некоторой точностью )

[ИСН]

Дак у него уже выложены координаты (оттуда по ссылке "library of 3-d arrangements"). Вопрос - как совмещать...