геометрический алгоритм Монте-Карло интегрирования

Когда говорят о интегрировании методом Монте-Карло, обычно подразумевают метод, при котором область интегрирования [a, b] делится случайным образом на участки шириной (a - b)/N, где N — количество случайных точек, и затем площадь получившихся столбиков суммируется. Формула для вычисления интеграла этим методом выглядит так:



Однако есть еще иной геометрический метод Монте-Карло, удивительный по своей простоте и эффективности.

Для этого метода нужно взять область интегрирования [a, b], ограничить ее прямоугольником с площадью Spar и набросать в этот прямоугольник случайным образом точек. Затем требуется посчитать количество точек K попавших в область под графиком функции и вычислить интеграл (площадь под кривой S) по формуле:

При этом, чем больше будет значение N, тем точнее окажется аппроксимация.

Для примера попробую посчитать этим методом интеграл функции f(x) = sin(x) / 2 на отрезке [0, 2]. При этом значение интеграла должно получиться приблизительно равным 0.708074.
Collapse )

Марс

Увлекательный видос, глядя который и, одновременно ворочая мышкой, можно представить, что сидишь верхом на Curiosity и крутишь головой по сторонам. Жаль, нельзя зумиться и разглядывать детальки. И ещё нет неба над головой. Про него они прям так и написали "Sky not imaged in this terrain mosaic".

Отдельно порадовало, что в середине видоса появляются подписи некоторых деталей марсохода.

RTG, если я правильно понял, — это Радиоизотопный термоэлектрический генератор (Radioisothope thermoelectric generator) или, проще говоря, ядерная батарейка.

Сначала я подумал, что CheMin Inlet — это какое-то странное устройство, названное в честь какого-то китайского учёного. Полез на сайт NASA за информацией и оказалось, попал пальцем в небо, потому что CheMin — это сокращение от Chemistry and Mineralogy. Это девайс для анализа горных пород при помощи XRD (X-ray Diffraction) и XRF (X-ray Fluorescence).

Третий девайс, с незнакомой аббревиатурой SAM, которая довольно неожиданно расшифровывается как Sample Analysis at Mars, — это прибор, при помощи которого на Марсе пытаются найти следы жизни.

почему факториал нуля равен единице

Как это часто бывает, школьный преподаватель, объясняя новую тему, некоторые факты предоставляет как данность, требующую не объяснения, а запоминания. Так было и с факториалом нуля.

— Дети, запомните, что факториал нуля равен единице. Запомнили? Повторите хором вслух.
— Факториал нуля равен единице.
— Отлично, пользуйтесь новым знанием!

Что такое факториал? Факториал — это произведение всех натуральных чисел от единицы до того числа, факториал которого требуется определить. В общем случае факториал числа n будет равен:,




Так, например, для числа 5 факториал будет выглядеть так:





Для числа 4 факториал можно посчитать как факториал пяти, делённый на пять:





Для числа 3 — как факториал четырёх, делённый на 4:





Для 2 — как факториал трёх, делённый на 3:





Для 1 — как факториал двух, делённый на 2:



Продолжение этого логического ряда для нуля даёт факториал единицы, делённый на единицу или просто единицу:



Можно объяснить этот факт немного по-другому. Факториал — это количество возможных перестановок или комбинаций. Например, три предмета можно комбинировать шестью способами:



Два предмета — двумя способами:





Один предмет — одним способом:


А ноль предметов? Ноль предметов можно переставить одним единственным способом — никак!

MSE

MSE (Mean Squared Error) или по-русски среднеквадратичная ошибка — это один из самых простых и популярных способов измерения качества работы модели.

Имея правильный ответ y и предсказание ŷ, можно вычислить их разность. Если сложить такие разности для всех ответов, возведённые в квадрат и разделить на количество элементов выборки, получится число, характеризующее качество модели:


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




Для этого случая MSE будет равна 69,2.

Тут мы сталкиваемся с проблемой интерпретации этого значения. В идеальном случае, когда все ответы предсказаны точно, MSE будет равна нулю. А как понять, что показывает число 69,2? Модель сделала предсказание плохо или хорошо? К сожалению, однозначно ответить на эти вопросы невозможно.

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

Когда работаешь с MSE, нужно всегда помнить о том, что эта оценка совершенно неустойчива к выбросам.

Расстояние между двумя точками на поверхности Земли

Представим, что для чего-то понадобилось измерить расстояние между двумя точками на поверхности Земли, например, расстояние между Красной площадью и Эрмитажем. Конечно, можно попробовать решить задачу в лоб и посчитать евклидово расстояние по формуле:


но этот подход не заработает по той простой причине, что евклидова метрика предназначена для вычисления расстояния на плоскости, а поверхность Земли — это всё-таки фигура, очень близкая к сфере.

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

Одна из таких функций, называется синус-верзус, или, по-другому, версинус. Он представляет собой расстояние от центральной точки дуги, измеряемой удвоенным данным углом, до центральной точки хорды, стягивающей дугу. Вычисляется версинус по формуле:




Гаверсинус — это просто половина версинуса, и именно эта функция поможет нам в решении задачи с поиском расстояния:





Для любых двух точек на сфере гаверсинус центрального угла между ними вычисляется по формуле:




В этой формуле:


  • d — это центральный угол между двумя точками, лежащими на большом круге

  • r — радиус сферы

  • φ₁ и φ₂ — широта первой и второй точек в радианах

  • λ₁ и λ₂ — долгота первой и второй точек в радианах

Обозначим временно гаверсинус отношения длины к радиусу как переменную h:


Тогда длину d можно вынести за знак равенства:


а для того, чтобы избавиться от дроби, выразим гаверсинус через арксинус:



затем раскроем переменную h:




подставим формулу гаверсинуса и получаем формулу вычисления расстояния:





Теперь вернёмся к исходной задаче поиска расстояния между Красной площадью и Эрмитажем.

Для Красной площади Гугл подсказал координаты (55.7539° N, 37.6208° E), а для Эрмитажа — (59.9398° N, 30.3146° E).

Прежде, чем подставлять координаты в формулу, их нужно перевести в радианы.

Для того, чтобы вычислить длину, в соответствии с формулой, нужно полученное значение арксинуса умножить на два радиуса сферы. Подсчёты усложняет тот факт, что Земля не является идеальной сферой и её радиус немного варьируется. Воспользуемся усреднённым значением радиуса, который, в соответствии со стандартом WGS84 приблизительно равен 6371км:




Произведя умножение, получаем искомое значение, которое приблизительно равно 634.57 км.

Кстати, из-за того, что Земля — не идеальная сфера, погрешность расчётов с использованием этой формулы, составляет около 0,5%.

Правило Стёрджеса

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

Железного стопроцентного правила, которое позволяет решить эту проблему, не существует. Однако, есть несколько популярных вариантов.

Первый и самый известный вариант — правило Стёрджеса, подойдет в том случае, когда данные имеют нормальное распределение:



где n — количество элементов выборки.

Вместо логарифма по основанию 2, в таком случае формула будет выглядеть так:



Для того, чтобы посчитать ширину интервалов, сначала следует вычислить размах варьирования признака, говоря проще, посчитать разницу между максимальным и минимальным значениями признака:





затем поделить получившееся значение на k:



Этот подход был предложен в далёком 1926 году, когда размеры выборок, по сравнению с современными, были микроскопичными, поэтому принято считать, что оно хорошо работает с массивами, содержащими до 200 элементов.

Для современных выборок, подчас имеющих десятки, сотни тысяч элементов и даже больше, правило Стёрджеса не подходит, поэтому была изобретена масса других подходов, например, для определения ширины можно использовать среднеквадратичное отклонение:


или интерквартильный размах:




В некоторых случаях для определения количества частей хорошо подходит простой метод — вычисление квадратного корня из количества элементов:


(no subject)

Для того, чтобы быстро найти тег LaTeX для символа, который никогда не писал или писал давно, но забыл, например, proportional to "", нужно пойти на сайт detexify.kirelabs.org, написать символ от руки и получить тег.

Норма Фробениуса

Норма Фробениуса или, как её ещё называют Евклидова норма, — это квадратный корень сумм квадратов модулей элементов матрицы размера m × n:

Простой пример. Есть матрица размера 3 × 3:

Она же, но с элементами, возведёнными в квадрат:

Сумма элементов этой матрицы будет равна 60. Квадратный корень из 60 примерно равен 7,746. Это число и есть норма Фробениуса для нашей матрицы.

Есть иной способ вычисления нормы Фробениуса: как квадратный корень произведения следа этой матрицы и эрмитово-сопряжённой матрицы:


https://ru.wikipedia.org/wiki/Норма_матрицы#Норма_Фробениуса

генератор, нарезанный на куски

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

Задача лаконично решается при помощи itertools.islice и itertools.chain:

from itertools import chain, islice

def batcher(data, b_size):
    iterator = iter(data)
    for first in iterator:
        yield list(chain([first], islice(iterator, b_size-1)))