Программа для вычисления кратных интегралов методом Монте-Карло

[TERAB1T]

Очень нуждаюсь в помощи по написанию программы для вычисления кратных интегралов методом Монте-Карло Язык - любой, кроме С# и паскаля. Цель такова - вводим параметры (подинтегральную функцию (для реализации чего, как я понял, нужен интерпритатор), пределы интегрирования), n (для точности), получаем число-ответ.

@темы: Алгоритм, Монте-Карло, численное интегрирование, PHP

Comments

[mr Gray]

для реализации чего, как я понял, нужен интерпритатор
Сам по себе этот метод интегрирования относительно простой, по сравнению с написанием интерпретатора (если не усложнять метод, например, собственным законом распределения для случайных точек), так что, как я понимаю, основная задача состоит в написании интерпретатора. Я пару лет назад в учебных целях писал интерпритатор, там были только 4 операции (+-*/) но он был построен так, что добавить другие было не проблемой. Сейчас этой программы уже нет, но суть его работы можно пояснить так:
1+2*(3+2*2)
1+2*(3+4)
1+2*(7)
1+2*7
1+14
15
Тоесть задача решается пошагово. И постепенно выражение упрощается. На каждом шаге либо выполняется одна из операции, либо раскрываются скобки.
Может быть метод и не самый оптимальный, но мне понравился, т.к. позволяет написать достаточно прозрачный код и добавлять, при необходимости, новые операции.

Начать нужно с парсинга входной строки с выражением: разбиваете ее на массив, в каждом элементе которого - или число, или код операции (можно создать второй массив, если в нем элемент = 1, то соответствующий элемент в первом массиве - код операции, иначе - число). Такая подготовка упростит дальнейшие проходы. Например для приведенного примера массивы могут выглядеть так (+ это 1, * - это 2, скобки это 3 и 4):

1 1 2 2 3 3 1 2 2 2 4
0 1 0 1 1 0 1 0 1 0 1

Попробуйте начать это решать, а будут вопросы - задавайте.

[mr Gray]

Если задача не учебная, а рабочая, то удобно использовать MatCad: www.exponenta.ru/educat/systemat/tarasevich/6_4...

[Vj_o-oy]

можно сделать финт ушами и воспользоваться банальным пыховым eval. тогда задача сведется к валидации строки, чтобы ничего лишнего юзер не вызывал. для учебной задачи хватит.

[mr Gray]

Можно нестандартно использовать СУБД в Delphi для расчета выражений:

procedure TForm1.Button1Click(Sender: TObject);
begin
  ADOQuery1.SQL.Add('SELECT ('+Edit1.Text+') AS rez');

  try
    ADOQuery1.Open;
    Caption :=ADOQuery1.Fields[0].AsString;

  except
    Caption:='Выражение некорректно';
  end;
end;

В Edit1 вводим выражение, в заголовке формы получаем ответ.

[Vj_o-oy]

ещё один вариант для крепких нервов
#include

int main(void)
{
char *expr = "10*50*$x";
char *cmd = new char[256];
sprintf(cmd, "let x=10; let y=%s; echo $y", expr);
FILE *out = popen(cmd, "r");
while(!feof(out))
{
char outc = ((char)getc(out));
printf("%c", outc);
}

return 0;
}


так что необходимость делать интерпритатор очень опциональна

[mr Gray]

Ну а чтобы понять, как использовать метод Монте-Карло для n-мерного интеграла, можно почитать эту работу: http://revolution.allbest.ru/mathematics/d00078708.html

[TERAB1T]

Итак, начнем с самого простого. На каком языке писать? Язык нужен кроссплатформенный, то есть и под линукс и под винду. На каком это будет легче реализовать? Сразу оговорюсь, что в программировании я силен не особо, имею только базовые навыки

[mr Gray]

На каком языке писать? Язык нужен кроссплатформенный, то есть и под линукс и под винду.
Если посмотреть исходный код VCL в Delphi, то можно убедиться, что она расчитана как на Windows, так и на Linux. Просто дважды нужно будет скомпилировать один и тот же код - сначала в Delphi а потом в его аналоге в Linux.
Java, Php - кроссплатформенные.
ИМХО и C++ можно использовать, только скомпилировать дважды.

Мне кажется, что вам было бы удобнее всего использовать PHP. Считаете выражение через eval, как сказал Vj_o-oy а потом генерируете n точек. Если не нужна очень высокая производительность, конечно.

[TERAB1T]

Ок, спасибо, будем писать на PHP. Теперь можно поподробнее про применение eval?

[mr Gray]

Теперь можно поподробнее про применение eval?
Эта функция позволяет выполнить код, который хранится в строке, которая передается в качестве аргумента: http://php.su/functions/?eval

[TERAB1T]

Ок, идем дальше. Как сгенерировать n точек?

[mr Gray]

Ок, идем дальше. Как сгенерировать n точек?
Вы бы хоть прочитали, что я вам предложил в посте от 2010-05-12 в 19:25. Все, что от вас требуется, это понять алгоритм, подкорректировать его для вашей задачи и перевести на PHP.

[TERAB1T]

Начал с основ, попытался переконвертировать программу паскальную на пхп для вычисления определенных интегралов. Вот исходники на паскале:
Program pmk;
Uses crt;
Var k,p,s,g,x,Integral : real;
n,i,a,b : integer;
BEGIN
writeln(‘Введите промежуток интегрирования (a;b):’);
readln(a);
readln(b);
writeln(‘Введите количество случайных значений(число испытаний):’);
readln(n);
k:=b-a; {Переменной“k”присвоим значение длины промежутка интегрирования}$
writeln(‘k=’,k);
for i:= 1 to n do begin {проведем n испытаний}
g:=random; {g – переменная вещественного типа, случайная величина из промежутка [0;1]}
x:= a + g*(b-a); {По этой формуле получается произвольная величина из [a; b] }
s:=s + (1+x); {s:=s +(x*x)} {Вообще можно подставить любую функцию}
delay(1000); {задержка, чтобы произвольные значения не повторялись}
end; {конец испытаний}
writeln(‘s=’,s); {Сумма функции для n произвольных значений}
Integral:=(1/n)*k*s ;
writeln(‘Интеграл=’,Integral);
readln;
END.


А вот что я из этого попытался сделать на PHP (не смейтесь только):



Калькулятор



<?php
$a=$_GET['a'];
$b=$_GET['b'];
$c=$_GET['c'];
$k=$b-$a;
$g=lcg_value();
$x=$a+$g*($b-$a);
$s=$s+(1+$x);
$z=(1/$n)*$k*$s;
echo "$z";
?>


Введите a:

Введите b:

Введите количество случайных значений:






Сразу видно - код кривейший, но тем не менее. Если пойму это, что попроще, то пойму и как сделать кратные. Eval пока не использовал, подинтегральная функция f(x)=1+x

[TERAB1T]

Неправильно вставил код пхп =( Вот он

<html> 
 <head> 
  <title>Калькулятор</title> 
 </head> 
 <body> 

 <?php
  $a=$_GET['a']; 
  $b=$_GET['b']; 
  $c=$_GET['c'];
  $k=$b-$a;
  $g=lcg_value();
  $x=$a+$g*($b-$a);
  $s=$s+(1+$x);
  $z=(1/$n)*$k*$s;
  echo "$z";
 ?> 

   
   Введите a: <input type=text name=a><br/> 
   Введите b: <input type=text name=b><br/> 
   Введите количество случайных значений: <input type=text name=?><br/> 
   <input type=submit value="Считай"> 
   
 </body> 
</html>

[mr Gray]

TERAB1T
Этот код можно перевести на PHP примерно так:

<html> 
 <head> 
  <title>Калькулятор</title> 
 </head> 
 <body> 

 <?php
  $a=$_GET['a']; 
  $b=$_GET['b']; 
  $c=$_GET['c'];
  $k=$b-$a;
  for ($i=1; $i<=$c; $i++)
  {
    $g=lcg_value();
    $x=$a+$g*($b-$a);
    $s=$s+(1+$x);
  }
  $z=(1/$c)*$k*$s;
  echo "$z";
 ?> 

  
 Введите a: <input type="text" name="a"><br/> 
 Введите b: <input type="text" name="b"><br/> 
 Введите количество случайных значений: <input type="text" name="c"><br/> 
 <input type=submit value="Считай"> 
  
   
 </body> 
</html>

http://paste.org.ru/?orz2o2

А для трехмерного пространства, например, нужно будет уже сгенерировать две переменные $g - одну для координаты x, а другую - для y. И т.д.

[TERAB1T]

Не работает. Запускаю - говорит деление на ноль в строке 18. В принципе логично, так как переменная с по умолчанию ноль. Как это обойти? И еще уверен, что неправильно привязал пхп к хтмл коду (ввод в формы и вывод результата). Как это исправить?

[TERAB1T]

Заработало Вот финальный код

<html> 
 <head> 
  <title>Калькулятор</title> 
 </head> 
 <body> 

 <?php
  $a=$_GET['a']; 
  $b=$_GET['b']; 
  $c=$_GET['c'];
  $k=$b-$a;
  for ($i=1; $i<=$c; $i++)
  {
    $g=lcg_value();
    $x=$a+$g*($b-$a);
    $s=$s+(1+$x);
  }
if ($c!=0)
{
  $z=(1/$c)*$k*$s;
  echo "$z";
}
else echo "Введите значения";
 ?> 

  
 Введите a: <input type="text" name="a"><br/> 
 Введите b: <input type="text" name="b"><br/> 
 Введите количество случайных значений: <input type="text" name="c"><br/> 
    <input type=submit value="Считай"> 
   
 </body> 
</html>

[TERAB1T]

Итак, теперь с этим eval не могу разобраться, при вводе его ответ в любом случае ноль. В чем ошибка?

paste.org.ru/?j5pcvx

[mr Gray]

http://paste.org.ru/?e4nzsc

входную функцию вводите в таком виде: 1 + $x т.е. переменную со знаком "$"

Не работает. Запускаю - говорит деление на ноль в строке 18. Видимо, все зависит от настроек сервера. У меня такую ошибку не выдавал.

[TERAB1T]

Спасибо, с основами покончили. Но теперь не понимаю алгоритм программы для вычисления кратных интегралов, с заданием всех параметров. Как реализовать?

[mr Gray]

Параметры: сперва указываем, сколько будет измерений. Потом - функцию и границы для каждого измерения.
Вычисление: то же самое, что и для интеграла по x, но только теперь уже будет интеграл по x1, x2, x3, x4, ... При этом для каждой точки нужно будет сгенерировать не одну, а несколько координат:

$g=lcg_value();
$x1=$a1+$g*($b1-$a1);
$g=lcg_value();
$x2=$a2+$g*($b1-$a2);
...
eval ("\$y = $d;");
$s=$s+$y;

Под конец считаем:

$z=(1/$c)*($k1+$k2+$k3+...)*$s;

Если измерений может быть много, то, наверное, можно организовать массивы a[] и b[], считывая их, например, из memo - но это уже дело вкуса. Тогда x1, x2, x3... можно заменить массивом x[], и входная функция будет иметь вид: $x[2]-10*$x[1]+$x[3]...

[TERAB1T]

Сделал верхнюю и нижнюю границы интегрирования через eval. paste.org.ru/?77t15y . Теперь когда в а и b вписываю не числа, а формулы, стандартные операции типа вычитания, сложения выполняются, а более сложные типа синуса, косинуса и тд нет, ответ выводится ноль. Почему так?

[mr Gray]

TERAB1T
eval ("\$a = $u;");
eval ("\$b = $v;");

[TERAB1T]

mr Gray Сделал так изначально. Считает с таким же успехом (в а и b вписываю не числа, а формулы, стандартные операции типа вычитания, сложения выполняются, а более сложные типа синуса, косинуса и тд нет, ответ выводится ноль), но кроме этого еще и выводятся ошибки:
"Parse error: syntax error, unexpected ';' in Z:\home\localhost\www\index.php(9) : eval()'d code on line 1
Parse error: syntax error, unexpected ';' in Z:\home\localhost\www\index.php(11) : eval()'d code on line 1"

UPD Переместил строки
eval ("\$a = $u;");
eval ("\$b = $v;");
$k=$b-$a;
в цикл, заработало без всяких ошибок, но тут попахивает уже неоптимизированностью, как этого избежать не внося в цикл?

[TERAB1T]

Вот код программы для двойного интеграла paste.org.ru/?a3p3rs (пока что без eval в цикле, добавлю потом). Можно ли как-то в нем реализовать быстрое решение таких интегралов :
integraly.ru/integral-base/vychislit-dvoinoi-in...
integraly.ru/integral-base/vychislit-dvoinoi-in...

То есть с неясно заданными границами интегрирования.

[mr Gray]

Сделал так изначально. Считает с таким же успехом
У меня сосчитал cos(3.14) = примерно -1, т.е. функции вызывает.

в цикл, заработало без всяких ошибок
Вы в границы интегрирования случайно переменные ($x, $y и т.д.) не подставляете? Они на момент вызова первых двух evalue не определены.

Можно ли как-то в нем реализовать быстрое решение таких интегралов
Посмотрите, как берется первый интеграл - он раскладывается на 2 интеграла.

Какая цель написания этой программы, если не секрет? Если задача не учебная, и требуется быстрая и точная реализация, то может быть стоит посмотреть в сторону уже готовых решений? Наверняка такие найдутся, может быть даже кроссплатформенные.

[TERAB1T]

Сделал так изначально. Считает с таким же успехом
У меня сосчитал cos(3.14) = примерно -1, т.е. функции вызывает.

в цикл, заработало без всяких ошибок
Вы в границы интегрирования случайно переменные ($x, $y и т.д.) не подставляете? Они на момент вызова первых двух evalue не определены.

переменные, естественно, не подставлял. Без цикла уже работает, но эти две ошибки остались (Parse error: syntax error, unexpected ';' in Z:\home\localhost\www\index.php(9) : eval()'d code on line 1
Parse error: syntax error, unexpected ';' in Z:\home\localhost\www\index.php(11) : eval()'d code on line 1). Хотелось бы избавиться от них...

Какая цель написания этой программы, если не секрет? Если задача не учебная, и требуется быстрая и точная реализация, то может быть стоит посмотреть в сторону уже готовых решений? Наверняка такие найдутся, может быть даже кроссплатформенные.

задача сугубо учебная, поэтому разобраться в этом должен сам

[TERAB1T]

Можно ли как-то сделать, чтоб переменные в поле для ввода можно было вводить без значка доллара?

[mr Gray]

Можно ли как-то сделать, чтоб переменные в поле для ввода можно было вводить без значка доллара?
Допустим вы знаете, что пользователь может ввести переменные x1, x2, ... Тогда значок $ можно добавить после запуска программы:

string str_replace('x1', '\$x1', $d);
string str_replace('x2', '\$x2', $d);
string str_replace('x3', '\$x3', $d);

[TERAB1T]

Спасибо. Только что ходил сдавать, выяснились новые подробности. пхп этот должен запускаться при желании на любом компьютере, то есть без серверов и тд Это раз. Второе интегрирование у меня происходит в двойном интеграле строго в квадрате. Сказали сделать так, чтоб область интегрирования могла быть и другой