Разреженная сетка

Разреженные сетки — это численные методы представления, интегрирования или интерполяции многомерных функций . Первоначально они были разработаны российским математиком Сергеем А. Смоляком , учеником Лазаря Люстерника , и основаны на конструкции разреженного тензорного произведения. Компьютерные алгоритмы для эффективной реализации таких сеток были позже разработаны Михаэлем Грибелем и Кристофом Ценгером .

Проклятие размерности [ править ]

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

Проклятие размерности выражается в порядке ошибки интегрирования, которую составляет квадратура уровня $l$ , с $N_{l}$ точки. Функция имеет регулярность $r$ , то есть есть $r$ раз дифференцируемы. Количество измерений $d$ .

$|E_{l}|=O(N_{l}^{-{\frac {r}{d}}})$

Правило квадратур Смоляка [ править ]

Смоляк нашел более эффективный в вычислительном отношении метод интегрирования многомерных функций, основанный на одномерном квадратурном правиле. $Q^{(1)}$ . $d$ -dimensional Smolyak integral $Q^{(d)}$ функции $f$ можно записать в виде формулы рекурсии с тензорным произведением .

$Q_{l}^{(d)}f=\left(\sum _{i=1}^{l}\left(Q_{i}^{(1)}-Q_{i-1}^{(1)}\right)\otimes Q_{l-i+1}^{(d-1)}\right)f$

Индекс $Q$ – уровень дискретности. Если одномерное интегрирование на уровне $i$ рассчитывается путем оценки $O(2^{i})$ точек, оценка погрешности функции регулярности $r$ будет $|E_{l}|=O\left(N_{l}^{-r}\left(\log N_{l}\right)^{(d-1)(r+1)}\right)$