Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
 Заголовок сообщения: Монте-Карло: решение любых систем
СообщениеДобавлено: 26 янв 2016, 05:29 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 11069
Откуда: Москва
Cпасибо сказано: 950
Спасибо получено:
3234 раз в 2824 сообщениях
Очков репутации: 629

Добавить очки репутацииУменьшить очки репутации
Любые, самые сложные нелинейные системы, можно успешно решать методом научного тыка. Например, довольно непростую геометрическую задачу я обуздал за 5 минут методом Монте-Карло. Задачу недавно задал nicat:

Изображение

самое важное в ней было не только составить систему, но и ее численно решить. Мое решение:

Изображение

Как удалось так быстро это сделать? Да по очень простой программе. На языке Yabasic она выглядит так:

z=.0001:s1=10^60:nn=20000000
a0=1:b0=1:c0=1:t0=1
for j=1 to nn
a=a0*(1+z*(ran()-.5))
b=b0*(1+z*(ran()-.5))
c=c0*(1+z*(ran()-.5))
t=t0*(1+z*(ran()-.5))
s=0
d1=abs((2*a*b*cos(t/2))/(a+b)-4)
d2=abs((2*b*c*cos(pi/4-t/2))/(b+c)-3)
d3=abs(a^2+c^2-b^2)
d4=abs(c/sin(t)-a/sin(pi/2-t))
s=d1+d2+d3+d4
if s<=s1 then
print a,b,c,t,s
a0=a:b0=b:c0=c:t0=t:s1=s
fi
next j


Проделав 20 миллионов циклов, ровно через 3 мин. 37 сек был выдан результат:

[math]a=3.81620494[/math]

[math]b=4.65148338[/math]

[math]c=2.65948820[/math]

[math]t=0.60863798[/math]

Результаты потом я проверил в Maple (см. рисунок). Но хорошо, что этот гигант математики одолел-таки эту задачу.
В моей практике пришлось решать систему 22-х нелинейных уравнений настолько запутанного вида, что никакой Маткад с ней бы не справился. Зато Монте-Карло на допотопном 286-ом процессоре (дело было в 1988 году) совершил то, что не смогли сделать даже голландцы в своем мощнейшем ВЦ. Правда, комп мой тогда пахал трое суток без перерыва. Сейчас бы такая система решилась за полчаса.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Avgust "Спасибо" сказали:
nicat
 Заголовок сообщения: Re: Монте-Карло: решение любых систем
СообщениеДобавлено: 27 янв 2016, 17:03 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 11069
Откуда: Москва
Cпасибо сказано: 950
Спасибо получено:
3234 раз в 2824 сообщениях
Очков репутации: 629

Добавить очки репутацииУменьшить очки репутации
Решение нелинейных систем - одна из трудных задач математики. Даже если формулы очень простые. Покажу на примере, как обычно студентам рекомендуют производить вычисления (см. http://www.exponenta.ru/educat/systemat ... on/loc.asp )

Изображение
Изображение

Наверное, нужно затратить целый день, чтобы освоить метод.

А вот как просто стравляется с задачей моя прога:

z1=.001:s1=10^60:nn=20000000
x0=1:y0=1:z0=1
for j=1 to nn
x=x0*(1+z1*(ran()-.5))
y=y0*(1+z1*(ran()-.5))
z=z0*(1+z1*(ran()-.5))
s=0
d1=abs(x^2+y^2+z^2-1)
d2=abs(2*x^2+y^2-4*z)
d3=abs(3*x^2-4*y+z^2)
s=d1+d2+d3
if s<=s1 then
print x,y,z,s,z1
x0=x:y0=y:z0=z:s1=s
fi
next j


Через 2 мин. получим ответ:

[math]x=0.78519693[/math]
[math]y=0.49661139[/math]
[math]z=0.36992283[/math]

Maple тоже решает легко:

Изображение

Решает легко, потому что задача относительно простая.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Монте-Карло: решение любых систем
СообщениеДобавлено: 27 янв 2016, 17:10 
Не в сети
Light & Truth
Зарегистрирован:
10 фев 2013, 21:28
Сообщений: 2673
Cпасибо сказано: 232
Спасибо получено:
839 раз в 773 сообщениях
Очков репутации: 207

Добавить очки репутацииУменьшить очки репутации
Avgust, решить - это значит найти все решения!(Если они существуют)
Какой критерий в Вашем методе, что Вы уверены в том, что найдены все решения?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Монте-Карло: решение любых систем
СообщениеДобавлено: 27 янв 2016, 19:10 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 11069
Откуда: Москва
Cпасибо сказано: 950
Спасибо получено:
3234 раз в 2824 сообщениях
Очков репутации: 629

Добавить очки репутацииУменьшить очки репутации
Anatole
Отличный вопрос! Я-то конечно получил все решения этой системы. Просто в самом начале было оговорено: найти положительные решения.
Всего решений два. Второе получается так:

z1=.001:s1=10^60:nn=20000000
x0=-1:y0=1:z0=1
for j=1 to nn
x=x0*(1+z1*(ran()-.5))
y=y0*(1+z1*(ran()-.5))
z=z0*(1+z1*(ran()-.5))
s=0
d1=abs(x^2+y^2+z^2-1)
d2=abs(2*x^2+y^2-4*z)
d3=abs(3*x^2-4*y+z^2)
s=d1+d2+d3
if s<=s1 then
print x,y,z,s
x0=x:y0=y:z0=z:s1=s
fi
next j


То есть начальное значение [math]x0=-1[/math] . Вообще-то прога моя имеет небольшой блог вариаций знаков искомых неизвесных. В последнем случае результат такой:

[math]a= -0.78519693[/math]
[math]b= 0.49661139[/math]
[math]c= 0.36992283[/math]

Интересно отметить, что Maple второе решение не дает. Оба решения показывает Вольфрам.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Монте-Карло: решение любых систем
СообщениеДобавлено: 27 янв 2016, 20:11 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 4963
Откуда: Саратов
Cпасибо сказано: 559
Спасибо получено:
359 раз в 298 сообщениях
Очков репутации: 51

Добавить очки репутацииУменьшить очки репутации
Avgust
замечательно :good:

А вы владеете методом имитации отжига?
Мне думается, что псевдотройки можно поотжигать :)
Это был конкурс такой - по раскраскам. В той задаче было нечто очень похожее на ортогональные квадраты. И многие решали ту задачу методом отжига. Отжигали по полной! :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Монте-Карло: решение любых систем
СообщениеДобавлено: 27 янв 2016, 23:56 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 11069
Откуда: Москва
Cпасибо сказано: 950
Спасибо получено:
3234 раз в 2824 сообщениях
Очков репутации: 629

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak
Какой интересный метод! Судя по названию. В чем его суть?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Монте-Карло: решение любых систем
СообщениеДобавлено: 28 янв 2016, 08:37 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 4963
Откуда: Саратов
Cпасибо сказано: 559
Спасибо получено:
359 раз в 298 сообщениях
Очков репутации: 51

Добавить очки репутацииУменьшить очки репутации
Цитата:
Алгоритм основывается на имитации физического процесса, который происходит при кристаллизации вещества, в том числе при отжиге металлов. Предполагается, что атомы уже выстроились в кристаллическую решётку, но ещё допустимы переходы отдельных атомов из одной ячейки в другую.

Из статьи в Википедии «Алгоритм имитации отжига».

К сожалению, я данным алгоритмом не владею. Но ребята в том конкурсе много писали об этом методе (я в том конкурсе участвовала). Там тоже надо было строить квадраты с раскрашенными в них ячейками, причём раскраска эта должна удовлетворять определённым условиям. Так вот, в некотором решении имели такой раскрашенный квадрат, в котором было несколько ячеек, раскраска которых не удовлетворяла этим условиям. Эти-то неправильные ячейки и пытались исправить по данному алгоритму. Говорят, очень хорошо метод работает в подобных задачах.

Кстати, я написала о задаче того конкурса книгу
Monochromatic Squares или Математическая раскраска. 2012 - 2013 гг.
http://yadi.sk/d/SIXEr8l4CV9fY

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Монте-Карло: решение любых систем
СообщениеДобавлено: 28 янв 2016, 09:57 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 11069
Откуда: Москва
Cпасибо сказано: 950
Спасибо получено:
3234 раз в 2824 сообщениях
Очков репутации: 629

Добавить очки репутацииУменьшить очки репутации
Ну и книга! Красота просто завораживающая. Из некоторых раскрасок хоть ковры делай!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Монте-Карло: решение любых систем
СообщениеДобавлено: 28 янв 2016, 11:42 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 4963
Откуда: Саратов
Cпасибо сказано: 559
Спасибо получено:
359 раз в 298 сообщениях
Очков репутации: 51

Добавить очки репутацииУменьшить очки репутации
Да, раскраски поразительно красивые. Меня особенно пленила та, что на обложке книги.
Вот, просто набор чисел, а какая красота :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Монте-Карло: решение любых систем
СообщениеДобавлено: 29 янв 2016, 08:01 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 11069
Откуда: Москва
Cпасибо сказано: 950
Спасибо получено:
3234 раз в 2824 сообщениях
Очков репутации: 629

Добавить очки репутацииУменьшить очки репутации
Продолжу свою тему.
Я уже говорил, что с легкостью нахожу корни полинома четвертой степени.
Вывод формул и алгоритм.
Пусть надо найти корни полинома

[math]f(x)=x^4+k_1 x^3+k_2 x^2+k_3 x+k_4[/math]

Воспользуемся методом неопределенных коэффициентов. Будем искать решение в виде произведения двух квадратных уравнений:

[math]f(x)=(x^2+ax+b)(x^2+cx+d)[/math]

Если раскрыть скобки, привести подобные члены и сопоставить с исходником, то задача сведется к решению четырех нелинейных уравнений:

[math]a+c=k_1[/math]

[math]ac+b+d=k_2[/math]

[math]ad+cb=k_3[/math]

[math]bd=k_4[/math]

Первая и четвертая строки дают:

[math]c=k_1-a\, ; \quad d=\frac {k_4}{b}[/math]

То есть сводим задачу к решению системы уже двух нелинейных уравнений:

[math]a(k_1-a)+b+\frac {k_4}{b}=k_2[/math]

[math]a \frac {k_4}{b}+(k_1-a) b = k_3[/math]

Вручную решать такую систему, как неоднократно заявляли светила математики на данном форуме, очень сложно.
Но метод Монто-Карло требует ровно двух минут, чтобы получить ответ с точностью до шести знаков после запятой. (Если нужна точность выше, то увеличиваем в проге число циклов nn).

Рассмотрим пример:

[math]f(x)=x^4+8x^3+22x^2-184x+9[/math]

То есть здесь: [math]k_1=8\, ; \quad k_2=22\, ; \quad k_3=-184\, ; \quad k_4=9[/math]

Текст проги:

open #1,"ab.txt","r"
open #2,"ab2.txt","w"
k1=8:k2=22:k3=-184:k4=9
for v=1 to 4
input #1 a0,b0
z=.0001:s1=10^50:nn=20000000
for j=1 to nn
a=a0*(1+z*(ran()-.5))
b=b0*(1+z*(ran()-.5))
s=0
d1=abs(a*(k1-a)+b+k4/b-k2)
d2=abs(a*k4/b+(k1-a)*b-k3)
s=d1+d2
if s<=s1 then
ak=a:bk=b:sk=s:s1=s
a0=a:b0=b
fi
next j
ck=k1-ak:dk=k4/bk
print #2,ak using "#####.############",bk using "#####.############",ck using "#####.############",dk using "#####.############",sk
next v


Файл данных "ab.txt" (все варианты знаков перед числами [math]a[/math] и [math]b[/math] ) до смешного простой:

1 1
1 -1
-1 1
-1 -1


Ровно через 2 минуты выстреливается такая табличка ( файл "ab2.txt" ):

0.003887820298     0.417608102339     7.996112179702    21.551305996194 187.423
6.282181064458 -0.308167205092 1.717818935542 -29.204924635991 40.7214
-3.211102566164 0.155589797341 11.211102566164 57.844409812101 1.00065e-006
-0.109864803931 -22.693790349243 8.109864803931 -0.396584257698 45.9814


Каждая строка - это числа [math]a\, , \, b \, , \, c \, , \, d[/math], последнее число - точность вычислений. Видно, что решением является третья строка. То есть:

[math]a=-3.211102566164[/math]
[math]b=0.155589797341[/math]
[math]c=11.211102566164[/math]
[math]d=57.844409812101[/math]

Если загрузить эти числа в Вольфрам, то обнаружим радикальные (абсолютно точные) ответы:

[math]a=4-2\sqrt{13}[/math]

[math]b=29-8\sqrt{13}[/math]

[math]c=4+2\sqrt{13}[/math]

[math]d=29+8\sqrt{13}[/math]

И нам останется только найти четыре корня из равенства:

[math]\bigg [ x^2+(4-2\sqrt{13})x+29-8\sqrt{13}\, \bigg ] \bigg [ x^2+(4+2\sqrt{13})x+29+8\sqrt{13}\, \bigg ] =0[/math]

Maple подтвердил сказанное выше:

Изображение

И Вольфрам не подкачал:
http://www.wolframalpha.com/input/?i=so ... 2C+b%5D%29

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Метод Монте-Карло

в форуме Microsoft Excel

mariya1509

1

1058

24 апр 2013, 15:41

Метод Монте-Карло

в форуме Численные методы

galachel

4

220

24 фев 2016, 20:25

Метод Монте-Карло

в форуме Математическая статистика и Эконометрика

Yrii

2

188

13 сен 2015, 13:58

Задача по методу Монте-Карло

в форуме Исследование операций и Задачи оптимизации

swivelin

2

399

06 ноя 2014, 08:54

Пределы интегрирования в методе Монте Карло

в форуме Численные методы

sable102

1

169

29 фев 2016, 08:37

Метод Монте-Карло для двойного интеграла

в форуме Численные методы

Jexio

2

173

14 фев 2018, 16:38

Вычисление интегралов методом Монте-Карло

в форуме Интегральное исчисление

sweetberries

2

316

11 фев 2012, 08:50

Метод Монте-Карло, регрессионная модель

в форуме Математическая статистика и Эконометрика

EcoFace

16

267

27 окт 2017, 01:54

Нахождение площадей полигонов Вороного методом Монте Карло

в форуме Аналитическая геометрия и Векторная алгебра

kuzo

0

168

24 сен 2015, 01:37

Метод Монте Карло, разыграть значения нормально распр Сл.Вел

в форуме Математическая статистика и Эконометрика

olga21

6

972

22 ноя 2012, 13:43


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: pacha и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved