Обчислення площі криволінійної трапеції використовуючи метод Монте-Карло

В даному параграфі розглядається delphi-проект, який використовуючи метод Монте-Карло знаходить наближене значення площі криволінійної трапеції обмеженої відрізком , графіком функції і вертикальними прямими та . Відмітимо, що крім чисельного розв'язку програма виводить в компоненті типу TChart також і графічне представлення роботи методу, тобто здійснює побудову ста згенерованих випадковим чином точок в прямокутник, що містить криволінійну фігуру.

Обчислення площі криволінійної трапеції використовуючи метод Монте-Карло

Читати повністю

Рішення задачі комівояжера методом Монте-Карло

Методами Монте-Карло називать будь-яку статистичну процедуру, яка використовує статистичну вибірку. Сьогодні застосуємо дану процедуру, для знаходження розв'язку задачі комівояжера. Для цього припустимо, що у задачі комівояжер повинен проїхати міст, і побудувати свій маршрут таким чином, щоб побувати у кожному місті по одному разу і повернутися у початкове. Відмітимо, що, при цьому, витрати на переміщення між містами повинні бути мінімальними.

Отже, для рішення задачі комівояжера методом Монте-Карло, використовується датчик випадкових чисел. Тобто, на першому кроці, серед міст з зномерами (місто з номером один є початковим, тому його вибирати не потрібно) випадковим чином вибираємо по одному місту і запам'ятовуємо їх послідовність. Відмітимо, що в подальшому дана послідовність вважатиметься за оптимальний маршрут. Для цього маршруту розраховуємо функцію мети і також запам'ятовуємо її.

Зауваження: у середовищі програмування delphi, яке ми зазвичай використовуємо для програмної реалізації розглядуваних на даному сайті алгоритмів та методів, існує стандартна функція Random, яка дозволяє програмно формувати випадкові числа. Фактично ця та аналогічні функції в інших мовах програмування є датчиками випадкових чисел.

Читати повністю

Чисельне інтегрування довільної функції методом Монте-Карло

Перш ніж приступити до розгляду delphi-проекту, який наближено обчислює площу криволінійної фігури методом Монте-Карло, нагадаємо собі основну ідею даного методу.

Нехай маємо деяку фігуру, площу якої необхідно знайти. Обмежимо дану фігуру іншою фігурою, наприклад прямокутником, площа якого легко обчислюється. Далі, для даного прямокутника випадковим чином генкруємо скінченне число точок. Після того, як точки повністю покрили прямокутник, підрахуємо кількість тих точок які місттяться на фігурі, площу якої ми обчислюємо і поділимо дану кількість на число згенерованих точок. Таким чином ми зможемо знайти, яку частину площі прямокутника займає криволінійна фігура. Помноживши дане число на площу прямокутника ми отримаємо шукану площу.

Отже, запустимо проект на виконання і перевіримо працездатність даного алгоритму на конкретному прикладі. Нехай потрібно знайти інтеграл від функції y=x^2 на проміжку [-1; 1].

Інтерфейс програми "Чисельне інтегрування методом Монте-Карло"

Інтерфейс програми "Чисельне інтегрування методом Монте-Карло"

Зауваження: програма знаходить шуканий розв'язок двома способами, більш детально розглянути кожен з них можна перейшовши за посиланням Чисельне інтегрування методом Монте-Карло.

Читати повністю

Чисельне інтегрування методом Монте-Карло

Нехай потрібно обчислити інтеграл від деякої функції Метод Монте-Карло на інтерваді Метод Монте-Карло:

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

В попередніх темах ми розглядали методи (метод трапеційметод пр'ямокутниківметод Сімпсона), які використовують значення функції Метод Монте-Карло обчислені в рівновіддалених точках проміжку Метод Монте-Карло. Проте, для рішення даної проблеми можна застосувати дещо інший підхід, основна ідея якого полягає в наступному: розглянемо деякий прямокутник, для якого виберемо довжину (b-a) та висоту H таким чином, щоб функція Метод Монте-Карло повністю лежала в середині даного прямокутника.

Основна ідея методу Монте-Карло

Графічна інтерпритація методу Монте-Карло

Далі, згенеруємо N пар випадкових чисел рівномірно розподілених в отриманому прямокутнику.

Читати повністю