|
Для решения задач многомерной оптимизации и при вычислении многомерных кратных интервалов широко используются методы Монте-Карло, сводящиеся к достаточно равномерному заполнению точками некоторой области пространства. Для этого используются как псевдослучайные, так и детерминированные последовательности точек (например, $%ЛП_{\tau}$%-последовательность или последовательность Холтона). Будем рассматривать равномерное заполнение точками $%m$%-мерного куба. Предположим, что у нас есть $%N$% точек. Как их расположить в таком кубе наиболее равномерно? Для ответа на этот вопрос необходимо предварительно ответить на вопрос "А что значит равномерно?". Обычное определение сводится к выяснению близости значений $%\frac{V_G}{V}$% и $%\frac{N_G}{N}$%, где $%V_G$% - это объем произвольной области $%G$% внутри куба, а $%N_G$% - это количество точек, попавших в эту область. Максимальный модуль разности этих величин - и есть количественный критерий неравномерности. При этом форма области $%G$% и величина $%V_G$% обычно фиксируются волевым порядком. Главный недостаток такого определения - оно является асимптотическим и плохо работает для больших $%m$% при реальных значениях $%N$%, т.к. способ заполнения, имеющий медленную асимптотику, при реальных $%N$% может оказаться значительно лучше, чем другой способ с быстрой, но "далеко включающейся" асимптотикой. В этой связи возникает вопрос: как дать определение равномерности так, чтобы оно было корректным для любых значений $%N$%? Например, для $%N=2,3,5,6,7$% при $%m=2$% ? Если у кого-то есть идеи на этот счет - было бы интересно обсудить. У меня такая идея есть, но пока я не хотел бы ее формулировать. задан 3 Окт '13 17:35 
Андрей Юрьевич |
|
Пусть $%\rho(\xi)$% - некоторая положительная фукция, определёная, интегрируемая и достаточно быстро убывающая на полуоси $%\xi \ge 0$% (например, $%\rho(\xi)=\rho_0 e^{-k^2\xi ^2}$% или $%\rho(\xi)=\frac{\rho_0}{1+k^2\xi ^2}$%, где $%\rho_0$% - нормировочный коэффициент, а k - большой параметр). Рассмотрим функцию $$F(\vec{x})=\frac{1}{N}\sum\limits_{n=1}^{N}\rho(N^{1/m} |\vec{x}-\vec{x}_n|),$$ где $%\vec{x}_n$% - точки, которыми заполнен единичный $%m$%-мерный куб. Она имеет смысл суммарного влияния всех точек в данной точке $%\vec{x}$%, причём радиус влияния отдельной точки обратно пропорционален среднему количеству точек на единицу длины, равному $%N^{1/m}$%. Это суммарное влияние будет больше там, где точки расположены гуще, и наоборот. В пределе при $%N \to \infty$% (и "равномерном" заполнении) эта функция должна быть константой, а при конечных $%N$% неравномерность распределения может измеряться её средним квадратичным отклонением от константы. Такое отклонение явно вычисляется по методу наименьших квадратов и равно $$\frac{1}{V}\int\limits_V F^2(\vec{x}) d\vec{x}-\left(\frac{1}{V}\int\limits_V F(\vec{x}) d\vec{x} \right)^2=\frac{1}{V}\int\limits_V \left(F(\vec{x})-\bar{F} \right)^2 d\vec{x},$$ где $$\bar{F} \equiv\frac{1}{V}\int\limits_V F(\vec{x}) d\vec{x}$$ - среднее значение функции $%F$% по всему кубу, а V - объём куба. Наиболее равномерное заполнение будет определяться в результате минимизации этого отклонения по всем точкам $%\vec{x}_n$%. Если коэффициент $%\rho_0$% выбран так, что функция $%\rho(N^{1/m} |\vec{x}|)$% нормирована на единицу (и её интеграл по всему пространству можно приближённо считать равным интегралу по кубу), то таковой же будет и функция $%F$%. Тогда $%\bar{F}=\frac{1}{V}=const,$% и достаточно будет минимизировать только $%\int\limits_V F^2(\vec{x}) d\vec{x}.$% Возможно, при удачном выборе функции $%\rho(\xi)$% минимизацию можно выполнить явно. $$$$ Можно предложить ещё один подход. Для простоты изложение ведётся для двумерного случая. Не ограничивая общности, можно считать, что рассматривается единичный квадрат $%[0;1]$%x$%[0;1]$%. Пусть $%F(x,y)$% - функция-счётчик, определённая на нём как доля точек, абсциссы которых не превосходят x, а ординаты - не превосходят y. В непрерывном равномерном случае $%F(x,y)=F_0 (x,y)=xy,$% и за степень неравномерности можно принять квадратичное отклонение реального распределения $%F(x,y)$% от $%F_0(x,y)$% в смысле квадрата нормы их разности в $%L^2$% на единичном квадрате. отвечен 3 Окт '13 21:15 
splen Спасибо, очень интересно, но пока полностью прокомментировать не могу, требуется время на обдумывание.
(4 Окт '13 12:32)
Андрей Юрьевич
Пожалуйста, конечно. Исправил некоторые неточности.
(4 Окт '13 16:02)
splen
Уважаемый @splen , извините за долгое молчание, был очень занят, а Ваши идеи требуют серьезного анализа. К сожалению, второй подход вряд ли реализуем. В качестве его опровержения можно построить функцию $%F(x,y)$% с дополнительным условием $%y=x$%. При этом легко добиться того, чтобы выполнялось точное равенство $%F(x,y)=F_0(x,y)$% для всех точек, но вряд ли такое распределение можно назвать равномерным заполнением квадрата.
(17 Окт '13 16:14)
Андрей Юрьевич
Что же касается первого подхода, то идея "минимальное количество точек вблизи каждой точки" вполне созвучна моему пониманию равномерности, реализация этой идеи с помощью вспомогательной функции влияния - очень интересна, но я пока не могу оценить ее эффективность. Пытался просчитать случаи $%m=1$% и $%N=2, \; 3, \; 4$%, но пока не довел расчеты до конца.
(17 Окт '13 16:14)
Андрей Юрьевич
Спасибо за внимание к моим соображениям. Ваше возражение совершенно справедливое. Этот пример пришёл мне в голову, когда сообщение было уже отправленно. Я не стал его удалять, т.к. казалось, что небольшимими исправлениями ситуацию можно спасти. Возможно, было бы достаточно, наряду с функцией $%F(x,y),$% рассмотреть аналогичные счётчики, приняв за точки отсчёта остальные три вершины квадрата, а в качестве степени неравномерности взяв сумму четырёх аналогичных слагаемых. Это тоже лишь соображения. Мне кажется, здесь больше шансов довести выкладки до конца, чем подбирая хорошую функцию влияния.
(17 Окт '13 16:43)
splen
Ну, это для двумерного пространства 4 слагаемых, а для $%m$%-мерного будет $%2^m$%. Боюсь, может оказаться слишком много. Сейчас я понял, что у меня вызывает сомнение в первом подходе. Если точки рассматривать как отталкивающиеся частицы, то Ваша функция влияния - это потенциал их взаимодействия. Разные функции влияния соответствуют разным взаимодействиям. Но, каков бы не был характер расталкивания, частицы будут разлетаться. Удержать их могут только стенки. Но для этого должно быть отталкивание со стороны стенок, которого у Вас нет.
(18 Окт '13 0:19)
Андрей Юрьевич
Движущиеся частицы здесь ни при чём. Задача - не о движении частиц, а о равномерности создаваемого ими потенциала, пусть даже такая конфигурация имеет место только в какой-то один момент времени. К тому же, ионы в металлах постоянно находятся в узлах кристаллической решётки (не считая тепловых колебаний) и не разлетаются, и ничто не мешает исследовать поле ионной подсистемы отдельно от поля свободных электронов. Это всё не имеет отношения к делу. А что касается большого числа слагаемых, не исключено, что задача будет достаточно симметрична, и суммы вычислятся явно. Заранее трудно утверждать.
(18 Окт '13 0:44)
splen
показано 5 из 7
показать еще 2
|
|
Возможно, мой ответ покажется немного наивным, но почему бы не выдвинуть гипотезу $%H_0$% о том, что координаты точек подчиняются многомерному равномерному распределению и воспользоваться многомерным критерием равномерности отвечен 3 Окт '13 20:47 
MathTrbl Дело в том, что случайное равномерное распределение не обеспечивает максимально равномерное распределение точек в пространстве. Например, асимптотическая неравномерность этого распределения ($%|\frac{V_G}{V}-\frac{N_G}{N}|$%) при $%N->\infty$% имеет вид $%\frac{1}{\sqrt{N}}$%, а, например, $%ЛП_{\tau}$% последовательность дает $%\frac{ln^m N}{{N}}$%
(4 Окт '13 12:25)
Андрей Юрьевич
|
|
Т.к. лимит комментариев исчерпан, пишу здесь.
Уважаемый @splen, я просто предложил следующую физическую интерпретацию. Предположим, что каждая точка - это частица, соответственно, распределение точек - это распределение частиц. Мы поместили каждую такую частицу в некоторую координатную точку с нулевой скоростью. Далее возникает вопрос, как физически проинтерпретировать Вашу функцию влияния. Это координатная убывающая функция расстояния от данной частицы до всех остальных частиц. Ее можно интерпретировать как потенциальную энергию взаимодействия частиц друг с другом. Из вида функции (убывание с расстоянием для любой пары частиц) следует, что такое взаимодействие будет отталкиванием. С этой точки зрения ситуация в корне отличается от кристалла - там существенно немонотонный (периодический) потенциал, поэтому кристалл и не разлетается. Для Вашей же (монотонной) функции влияния после какого-то размещения частиц начнется их разлетание. Дополнение 1. (ответ на комментарий). отвечен 18 Окт '13 2:36
Андрей Юрьевич Многое из написанного требует комментариев, а места мало. Начну с некоторых тезисов. Разлетятся частицы или нет, неважно. На частицы могут действовать и другие силы, которые необязательно учитывать. Функция $%F$% не связана со взаимодействием частиц между собой. Хотя функция $%\rho$% монотонна, функция $%F$% таковой не является. Я не пытался приблизить потенциал каждой частицы к среднему значению, а высказал соображения о том, чем можно было бы измерить "неконстантность" суммарного потенциала $%F$%. Не уверен, что эта мера имеет физический смысл. Что из этого нужно пояснить в первую очередь?
(18 Окт '13 13:29)
splen
... не очень уместна категоричность... + Что касается других сил - им взяться не откуда По-моему, эти утверждения не совсем согласуются. Такое впечатление, что мы говорим не совсем об одном и том же. Я, в частности, не был против того, чтобы считать $%F$% потенциалом. Может, нужно что-то пояснить? Я, собственно, это уже предлагал.
(18 Окт '13 16:23)
splen
Спасибо, @splen . Собственно вопрос, удерживающий пока от погружения в выкладки для проверки Вашей гипотезы (я имею в виду первую гипотезу) один - можно ли и нужно ли заменять интегрирование по кубу интегрированием по пространству? Все остальное у Вас написано в виде формул, так что пояснения вряд ли нужны.
(19 Окт '13 22:30)
Андрей Юрьевич
Ну, не знаю, Вам решать. Если не нужны - значит, не нужны. Интегрирование - только по кубу.
(19 Окт '13 22:43)
splen
|
Хотелось бы уточнить постановку вопроса. Так ли я понимаю, что в единичный квадрат бросается $%N$% точек, и надо придумать какую-то удобную функцию (скажем, от координат этих точек), которая бы задавала "степень равномерности" распределения этих точек в квадрате? Если да, то над этим интересно было бы подумать, причём начать можно даже с упрощённого случая $%m=1$%, т.е. единичного отрезка.
Да, совершенно верно, в идеале постановка задачи именно такая. Мы знаем координаты точек, нужно сказать, насколько равномерно они расположены? Но можно и упростить задачу, просто ответив на вопрос: "А какое расположение точек является наиболее равномерным?". Для $%m=1$% ответ на второй вопрос очевиден, для $%m=2$% - уже нет.