§ 2. n-мерные псевдослучайные точки

2.1. Равномерно распределенные последовательности.

Рассмотрим произвольный алгоритм Монте-Карло с к. и соответствующую ему функцию . Как мы видели в п. 1.1, этот алгоритм сводит решаемую задачу к вычислению интеграла (7).

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

для всех функций Ф из достаточно широкого класса?

Определение. Последовательность точек называется равномерно распределенной в если соотношение (9) справедливо для любой функции интегрируемой в по Риману.

Понятие это было введено в 1916 г. Г. Вейлем [182], который построил также примеры равномерно распределенных последовательностей.

Сопоставление формул (9) и (7) показывает, что для реализации алгоритмов Монте-Карло с можно попытаться вместо случайных точек Г использовать точки равномерно распределенной последовательности Для этого надо при реализации «испытания» вместо случайных чисел использовать декартовы координаты точки Соотношение (9) гарантирует сходимость такого способа вычислений для большинства встречающихся на практике алгоритмов.

Легко заметить, что равенство (9) не нарушается, если изменить в последовательности любое конечное число точек. Однако сходимость средних к пределу может при этом очень замедлиться. Поэтому далеко каждую равномерно распределенную последовательность разумно использовать на практике в качестве псевдослучайных точек. Среди всех равномерно распределенных последовательностей следует отобрать в некотором смысле (см. ниже п. 2.2) «хорошие». Отыскание таких последовательностей обычно наталкивается на серьезные трудности.

Например, еще Г. Вейль доказал, что любые последовательности точек с декартовыми координатами

где алгебраически независимые иррациональные числа, равномерно распределены в Но ни одного «хорошего» набора при до сих пор не известно.

Рис. 67.

(На рис. 67, а изображены точки в квадрате, полученные при )