ГЛАВА 8. НЕКОТОРЫЕ ДРУГИЕ ЗАДАЧИ

§ 1. Интерполирование функций от большого числа переменных

В книге уже встречались задачи, в которых методы Монте-Карло оказываются эффективнее классических методов при большом числе переменных (см. упражнение 9 гл. 3 и п. 5.6 гл. 5). Здесь изложена одна задача такого типа, рассмотренная впервые Дж. Хэммерсли [134].

1.1. Постановка задачи.

Рассмотрим функцию значения которой известны лишь в вершинах единичного -мерного куба Требуется проинтерполировать значение этой функции в точке расположенной внутри (рис. 70).

Рис. 70.

Интерполяция линейная по каждому из переменных.

В случае интерполяционная формула всем хорошо знакома:

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

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

Тогда (1) можно переписать в виде

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

Расчет по формулам (2) и (3) в принципе весьма прост. Однако количество слагаемых в (3) быстро растет с ростом и уже при превышает .

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