Численное интегрирование в высоких размерностях: метод разреженных сеток Смоляка

Экспоненциальный взрыв и тензорные произведения

Когда мы сталкиваемся с необходимостью вычислить определенный интеграл от функции многих переменных, классическая вычислительная математика предлагает использовать тензорное произведение одномерных квадратурных формул (например, методов Гаусса или Ньютона-Котеса). Если для достижения нужной точности по одной координатной оси нам требуется 10 узлов, то для двумерной задачи потребуется сетка из 100 узлов. Для трехмерной — 1000. В общем случае, для пространства размерности D нам потребуется N^D узлов. Это фатальное явление называется «проклятием размерности» (Curse of Dimensionality). Если мы моделируем квантовую систему или оцениваем финансовые риски по 20 параметрам, нам потребуется 10^20 вычислений подынтегральной функции, что абсолютно недостижимо ни для одного суперкомпьютера в мире.

Ранее мы обсуждали, что эту проблему решают методы Монте-Карло, сложность которых не зависит от размерности. Но Монте-Карло сходится катастрофически медленно. Существует ли детерминированный сеточный метод, который может разорвать оковы проклятия размерности, сохраняя при этом высокую (полиномиальную) скорость сходимости для гладких функций? Да, этот метод был изобретен в 1963 году выдающимся советским математиком Сергеем Александровичем Смоляком и получил название метода разреженных сеток (Sparse Grids).

Магия линейных комбинаций Смоляка

Идея Смоляка — это шедевр комбинаторной математики. Вместо того чтобы строить полное тензорное произведение одномерных сеток, Смоляк предложил использовать сложную линейную комбинацию тензорных произведений сеток относительно малого размера. Алгоритм выбирает только те узлы полного многомерного куба, которые вносят наибольший вклад в итоговую точность интерполяции или интегрирования, безжалостно отбрасывая подавляющее большинство «бесполезных» узлов.

Математически алгоритм Смоляка строится на основе разностей одномерных операторов интерполяции. Узлы располагаются не равномерно, а образуют красивую крестообразную структуру, плотно сгущаясь на осях координат и оставаясь абсолютно пустыми в углах многомерного гиперкуба. Если мы используем в качестве базовых одномерных сеток вложенные узлы (например, узлы Кленшоу-Кертиса), эффективность метода возрастает многократно. Количество узлов в разреженной сетке Смоляка растет как O(N * (log N)^(D-1)), а не как O(N^D). Это означает, что для 10-мерной задачи вместо триллиона узлов алгоритму потребуются лишь тысячи, при сохранении практически той же спектральной точности! Сегодня алгоритмы Sparse Grids являются золотым стандартом для решения стохастических дифференциальных уравнений и задач неопределенности (Uncertainty Quantification) в инженерии.