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

Обсуждается вопрос: почему оптимальные алгоритмы на классах функций иногда оказываются практически бесполезными. В качестве примера возьмем классы функций, удовлетворяющих общему условию Липшица. Рассматриваются методы оценки интеграла по единичному кубу очень большой размерности $d$. Предполагается, что подынтегральная функция интегрируема с квадратом. Можно использовать оценку простейшего метода Монте-Карло. Тогда вероятная ошибка оценки пропорциональна $1/\sqrt{N}$, где $N$ — количество значений функции. Если от метода Монте-Карло перейти к методу квази-Монте-Карло, то, как показали многочисленные примеры, погрешность зависит не от размерности $d$, а от средней размерности $\hat{d}$ подынтегральной функции. При малых $\hat{d}$ порядок погрешности близок к $1/N$.