Моделирование блуждания частицы методом Монте – Карло в сложной области

Моделирование блуждания частицы методом Монте – Карло в сложной области,
Антиплагиат 72 процента по етхт. ру.
Работа оригинальная, аналогов нет. ...

Введение……………………………………………………………………….3
ГЛАВА 1. ОБЩАЯ ХАРАКТЕРИСТИКА МЕТОДА МОНТЕ – КАРЛО..6
1.1. Метод статистических испытаний……………………………………6
1.2. Алгоритмы метода Монте - Карло для решений интегральных уравнений 2-го рода……………………………………………………10
1.3. Прямое моделирование методом Монте-Карло…………………….11
1.4.Квантовый метод Монте-Карло………………………………………….12
ГЛАВА 2. МОДЕЛИРОВАНИЕ БЛУЖДАНИЯ ЧАСТИЦ МЕТОДОМ МОНТЕ – КАРЛО………………………………………………………………14
2.1 Случайное блуждание. Простая выборка……………………………….14
2.2 Случайное блуждание без возвратов…………………………………….21
2.3 Случайное блуждание без самопересечений…………………………….22
2.4 Перколяция…………………………………………………………………..27
2.5. Ограниченная выборка……………………………………………………..29
Заключение………………………………………………………………………43
Список литературы………………………………………………………….….45

Методы компьютерного эксперимента, широко используемые в настоящее время, являются весьма полезным инструментом научного исследования. В статистической физике, например, задача термодинамического усреднения для систем многих частиц с сильным взаимодействием решается с использованием выборки по значимости методом Монте-Карло.
Хотя эти методы в принципе просты и широко известны, при их практическом применении требуется некоторый опыт и умение, необходимо знать о "ловушках" методов и их ограничениях, таких как эффекты конечных размеров системы, "статистическая неэффективность" (из-за "динамической" корреляции средних значений, в особенности "критического замедления"),
проблемы начальных и граничных условий, систематические погрешности и др.
Информация, получаемая из аналитической теории, является точной лишь в ряде "чистых" случаев, в то время как в большинстве других необходимо использовать неконтролируемые приближения. Например, задачи статистической физики, разрешимые в трехмерном случае, являются идеализированными предельными случаями, такими как идеальные газы или растворы, связанные гармонические осцилляторы и др. Даже очень простые модели статистической физики, такие как трехмерная модель Изинга, не могут быть решены точно, а о моделях с реальными межатомными потенциалами известно еще меньше. Поэтому компьютерное моделирование часто используется для проверки точности приближений, сделанных в аналитической модели.
Экспериментальная информация также почти никогда не является точной (в том смысле, что точно известен эффективный гамильтониан экспериментального образца). В ряде случаев даже стоит вопрос о том, обусловлено ли экспериментально наблюдаемое явление природой образца или, например, наличием в нем неизвестных примесей (напомним, что химический состав экспериментального образца известен лишь приблизительно). Это лишь несколько примеров, которые показывают, что результаты аналитической теории и эксперимента не всегда достаточны для понимания природы изучаемого явления.
Компьютерное моделирование призвано заполнить этот пробел. Сравнивая результаты моделирования модели с результатами эксперимента, мы не ограничены погрешностями приближений, что часто неизбежно в аналитической теории, и, следовательно, можем выяснить, хорошо описывает рассматриваемая модель реальную систему или нет.
Конечно, компьютерное моделирование является привлекательным не только по этой причине. Необходимо отметить, что моделирование изучаемой системы дает информацию, в том числе и любую количественную, с требуемой степенью детализации. Например, эксперименты по рассеянию на реальных системах дают информацию о двухчастичных корреляционных функциях, однако получение прямой экспериментальной информации о трехчастичных или более высокого порядка корреляционных функциях крайне затруднено. При компьютерном моделировании можно легко получить трехчастичную корреляционную функцию или даже функции более высокого порядка по крайней мере в принципе.
Кроме того, хотя экспериментатор может изменять температуру и давление образца, он не может столь же легко добиться изменения межатомногр потенциала. В компьютерном же эксперименте изменение межатомного потенциала любым образом не представляет сложности. Ввиду выше сказанного компьютерное моделирование представляет самостоятельный интерес. Это—достоверный научный подход к пониманию законов природы, дополнительный к аналитической теории или эксперименту.
В этой ситуации не удивительно, что объем литературы по этому вопросу испытывает стремительный рост. Многие исследователи, занимавшиеся ранее теоретической физикой (теоретической химией, биологией и т. п.), начали заниматься моделированием, впрочем, как и некоторые экспериментаторы. И наконец, но не в последнюю очередь многие студенты, не имеющие каких-либо навыков исследовательской работы, мгновенно втягиваются в сферу компьютерного эксперимента.
Цель данной курсовой работы: рассмотреть моделирование блуждания частиц в сложной области.
Исходя из цели решаются следующие задачи:
1. Выявить литературу и источники по теме;
2. Характеристика особенностей метода Монте – Карло;
3. Моделирование блуждания частиц с использованием метода Монте – Карло.
В результате проведенного исследования сложилась следующая структура курсовой работы: введение , две главы, заключение, список использованной литературы.

enddo [1]
2.3 Случайное блуждание без самопересечений
Генерация случайных блужданий без самопересечений требует использования более сложного алгоритма, чем для блуждания без возвратов.
В случае простого случайного блуждания при генерации следующего шага траектории не накладывается никаких ограничений на направление движения. На каждом шаге информация о предыдущем шаге полностью теряется. Таким образом, из каждого текущего узла возможен переход по 2d (для простой d- мерной решетки) направлениям.
При случайном блуждании без самопересечений переход из текущего узла в соседние разрешен не по всем направлениям. Не допустимы пересечения своей же траектории и запрещены возвраты траектории (поворот на 180°).
В каждом текущем узле мы имеем локальную информацию о предыдущем шаге и максимум2d — 1 возможных направлений перехода.
Одно направление всегда запрещено из-за запрета возврата траектории. Локальное окружение может также привести к запрету перехода по ряду других направлений вследствие запрета самопересечения траектории. Возможны ситуации, когда из текущего узла все направления движения запрещены!
Если 13-й шаг будет сгенерирован по направлению вправо или вниз, оба эти направления запрещены. В первом случае траектория пересекла бы саму себя; во втором случае наблюдался бы возврат траектории. Как следствие, в обоих случаях генерирование траектории обрывается на 12-м шаге.
Завершение генерации траектории в случае выбора в качестве следующего узла из 2d — 1 возможных соседних узлов уже занятого узла
является ключевым для конструирования алгоритма случайного блуждания без самопересечений. [1]
При моделировании случайных блужданий мы не делали никаких замечаний относительно траектории блуждания. Для блуждания без самопересечений мы вынуждены проверять на каждом шаге, является ли он разрешенным. Для этого необходимо записывать (сохранять) траекторию блуждания (см. алгоритм 2.5). Генерация же блуждания осуществляется так же, как и в задаче о случайном блуждании.
Появляется только один новый момент: мы не знаем заранее длину
генерируемой траектории в отличие от простого случайного блуждания. Блуждание может быть прервано из-за ограничений на любом шаге. Для реализации генерации неизвестного заранее числа шагов заменим в алгоритме 2.5 безусловный цикл по N шагам на цикл типа repeat-until, при котором после генерации каждого следующего шага выполняется проверка на допустимость этого шага и на превышение максимальной длины траектории (N шагов). В обоих случаях генерирование траектории прекращается. При этом длина траектории не будет превышать N шагов. Напомним, что для простого случайного блуждания она всегда равна N шагам.
Алгоритм 2.5. Случайное блуждание без самопересечений
do sample := 1 to n-of-samples
begin
step := 0
repeat
(* Генерировать-один-шаг *)
generate-one-step
step := step+ 1;
until {step-invalid or step = N)
end
(* Накопить-результаты *)
accumulate-results
enddo [1]
Как выполнить проверку, разрешен ли текущий шаг? Присвоим каждой траектории уникальную метку: для первой траектории метку 1, для второй метку 2 и т. д. Эти метки присваиваются траекториям автоматически во внешнем цикле алгоритма. В процессе генерации траектории узлы решетки, через которые проходит траектория, помечаются меткой траектории . На каждом шаге осуществляется проверка, занят ли следующий узел траекторией с той же меткой или нет. Если да, это значит, что произойдет самопересечение траектории. Следовательно, из-за запрета самопересечения генерация данной траектории прекращается.
Теперь мы должны определить, каким образом генерировать один шаг траектории. Мы имеем тот же выбор, что и в случае генерации случайного блуждания без возвратов. Мы можем при генерации следующего шага либо игнорировать информацию о предыдущем шаге, либо выбирать лишь из 2d— 1 потенциально возможных направлений.
Будем придерживаться первого варианта. Метка траектории еще не
позволяет различить, когда был занят данный узел — на предыдущем шаге или раньше. Если узел был занят на предыдущем шаге, мы должны повторить процедуру генерации шага. В противном случае генерирование траектории заканчивается.
Использование меток позволяет, однако, легко разрешить эту проблему. Мы можем снова использовать уникальность меток. Перед генерацией следующего шага увеличим метку предыдущего узла траектории на единицу. Затем, после генерации следующего хода, проверим метку следующего узла. Она может быть равна метке траектории (в этом случае генерирование траектории прекращается), метке, увеличенной на единицу (это случай возврата траектории и необходимо заново генерировать шаг), или метке, меньшей метки текущей траектории. Кроме того, узел может быть пустым (нулевая метка). В последних двух случаях генерирование траетории продолжается. Описанную процедуру можно реализовать с помощью массива (раньше — в других примерах — мы не использовали массив).
Какова должна быть размерность массива? Максимальная длина траектории блуждания может достигать N шагов. Поэтому мы должны иметь массив максимального размера. Поскольку траектория может генерироваться в любом направлении, массив необходимо описать как integer lattice(—N : N, — N : N). Алгоритм генерации траектории случайного блуждания без самопересечений приведен ниже (см. алгоритм 2.6).
Алгоритм 2.6. Случайное блуждание без самопересечений
integer lattice(-N : N, — N : N);
do sample := 1 to n-of-samples
begin
step := 0;
x := 0; у := 0;
x с := 0; у c := 0;
repeat
repeat
(* Генерировать-один-шаг *)
generate-one-step(xnew, ynew);
until lattice(xneyf, yneyf) ≠ sample + 1;
if lattice(xnew, ynew) = sample then
terminate :=true
else
begin
lattice(x,y) := sample;
x := xc; у := yc;
lattice(x}y) := sample + 1;
хс := хnew Ус := ynew
step := step + 1;
end
until(terminate or step ~ ЛГ);
(* Накопить-результаты *)
accumulate-results
end
enddo [1]
2.4 Перколяция
Применение метода простой выборки для моделирования перколяции является более простой задачей, чем моделирование случайных блужданий, рассмотренное в предыдущих разделах. Метод простой выборки означает здесь генерацию конфигураций и их последующий анализ с учетом равных статистических весов этих конфигураций.
Напомним, что мы ищем точку рс геометрического фазового перехода при перколяции. При р < рс существуют только конечные кластеры. При р > рс существует по крайней мере один бесконечный кластер. Этот геометрический фазовый переход является аналогом фазового перехода второго рода в термодинамике при Т = Тс. Воспользуемся возможностью и начнем этот раздел с изучения фазовых переходов, с их анализа, оставив в стороне специфические задачи перколяции.
Алгоритм 2.7. Перколяция
do no-of-conftg := 1 to N
begin
(* Генерировать-конфигурацию *)
generate-a-configuration\
(* Анализировать-конфигурацию *)
analyze-the-configuration;
(* Вычислить-величины *)
calculate-quantities]
(* Накопить-результаты *)
accumulate-results;
end
enddo
(* Выполнить-усреднение *)
ре rfo rm -a vera ging [1]
Прежде всего определим величину рс фазового перехода. В методе простой выборки мы должны сгенерировать N перколяционных конфигураций, получить из них требуемые величины и усреднить их затем по всем конфигурациям. Сказанное реализует базовый алгоритм, приведенный выше.
При моделировании перколяции — более точно ячеечной перколяции — мы рассматриваем решетки (для удобства снова предполагаемые двухмерными), заполненные с вероятностью р. Заполненная решетка рассматривается как конфигурация в методе простой выборки.
Для генерации конфигурации необходимо просмотреть по одному разу
все узлы решетки, заполняя или оставляя их при этом свободными, как это сделано в следующем алгоритме:
Алгоритм 2.8. Генерация конфигурации
(* generate-a-configuration *)
do i := l to L
do j := 1 to L
if p < random(iseed) then
lattice(i,j) := 0
else
lattice^, j) := 1;
enddo
enddo
Здесь random — вещественная функция, возвращающая в качестве своего значения случайное число из интервала (0,1), iseed — целая переменная, которая служит при первом вызове генератора случайных чисел для его инициализации.
Алгоритм 2.9. Анализ бинарного дерева
(* analyze-the-configuration *)
burned := 0;
repeat
select~an-unburned-site(i)
n:= 1
go-through-tree(i, n)
burned := burned + n
until occupied-sites=burned
(* Просмотр дерева *)
procedure go-through-tree(i, n)
begin
if tree(i, 1) ≠ 0 then go-through-tree(tree(i, l),n);
if tree{i, 2) ≠ 0 then go-through-tree(tree(i,2),n)]
tree{i, 1) : = 0;
tree(i, 2) := 0;
n:=n+l;
end
В алгоритме 2.9 дерево из п узлов хранится в двухмерном массиве tгее(1:п,1:2). Первый элемент массива определяет текущий узел дерева. Второй элемент массива задает соседа слева или справа. Он может принимать значение нуль, либо целое число из множества {1, 2, ..., n}. Если он равен нулю, значит текущий узел является листом, иначе он указывает на следующий узел. [1]
2.5. Ограниченная выборка
Рассмотрение случайного блуждания без самопересечений выявило
ограничения метода простой выборки. Хотя этот метод достаточно прост в применении, для многих задач его польза ограничена: даже для малого числа шагов сложно набрать необходимую статистику.
Проблемы возрастают экспоненциально с увеличением числа шагов.
Концепция ограниченной выборки помогает (по крайней мере частично) преодолеть эту проблему. Для демонстрации того, как ограниченная выборка может увеличить эффективность, рассмотрим случайное блуждание без самопересечений. При этом читатель сможет непосредственно сравнить эффективность метода простой выборки с методом
ограниченной выборки.
В методе ограниченной выборки мы осуществляем выборку только из
этого списка соседей, причем вероятности выборки различных соседей равны. Следовательно, вероятность выбора одного из узлов равна 1/l. Алгоритм 2.10. Случайное блуждание без самопересечений
do sample := 1 to n-of-samples
begin
step := 0;
repeat
(* Генерация-одного-шага *)
generate-one-step
step := step+1;
until (step-invalid or step = N)
end
(* Накопление-результатов *)
accumulate-results
enddo
Алгоритм 3.11. Случайное блуждание без самопересечений
integer lattice(-N : N, —N : N);
do sample := 1 to n-of-samples
begin
step := 0;
repeat
produce-valid-neighbor- list(x, y)\
if list = empty then
terminate := true
else
begin
choose-new-site- from-list(xnew, ynew);
X := xnew У =: У new
step := step+ 1;
end
until (terminate or step = N)
end
(* Накопление-результатов *)
accumulate-results
enddo
Концепция выбора только ближайших узлов еще не гарантирует того, что длина траектории блуждания будет равна N шагам.
Проблема захода блуждания в тупик до достижения N шагов все еще
остается, однако вероятность увеличения длины траектории вплоть до N шагов возрастает (см. алгоритм 2.11). [1]
Выборка по значимости
Концепции простой и ограниченной выборок оказываются неприемлемыми на практике для задач, в которых средние значения вычисляемых величин определяются практически полностью статистическими вкладами из определенных областей фазового пространства.
Использование равномерной выборки в этом случае может потребовать
огромного числа попыток. Знание расположения областей фазового пространства, дающих наибольшие вклады, может быть использовано для организации процесса выборки в основном из этих областей. [3]
Типичным примером, в котором используется эта идея, является модель Изинга.
Модель Изинга
Как и при изучении предыдущих примеров, мы сосредоточим наше внимание на изучении задачи в двухмерном пространстве. Рассмотрим модельный изинговский потенциал
H = -jΣ siSj
(i, j)
где константа взаимодействия между ближайшими узлами J может быть либо положительной (в случае моделирования ферромагнетика), либо отрицательной (в случае антиферромагнетика). Переменная s равна +1 или —1. Ограничим наше рассмотрение случаем простой квадратной решетки, для которой (i, j) означает четыре ближайших к узлу (i, j) узла:
(i, j+1)
(i-1, j) (i+1, j)
(i, j-1)
Пусть х означает конфигурацию спинов. Напомним, что мы хотим сгенерировать марковскую цепь x0, x1 ..., хn такую, что конфигурация xi+1, зависит только от предыдущей конфигурации Хi. Вероятность перехода от xi к xi+1 определяется величиной W(xi+1 xi).
Зачем нам нужно генерировать цепь Маркова? Идея выборки по значимости состоит в преимущественной выборке конфигураций, дающих наибольший вклад, например, в намагниченность. Для этого нужно выбрать конфигурации спинов с максимальным больцмановским фактором ехр[—H(х)/квТ]. Мы не знаем заранее, где расположены такие области фазового пространства. Допустим, что мы придумали алгоритм, генерирующий состояния, дающие наибольшие вклады в намагниченность или в любую другую наблюдаемую величину. [2]
Тогда процесс генерации состояний является марковским с априорной
вероятностью перехода между конфигурациями.