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

Sparse grid

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

Проклятие размерности

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

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

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

Квадратурное правило Смоляка

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

${ Displaystyle 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}$

Индекс к ${ displaystyle Q}$ - уровень дискретизации. А ${ displaystyle 1-d}$ интеграция на уровне ${ displaystyle i}$ вычисляется путем оценки ${ displaystyle O (2 ^ {i})}$ точки. Оценка погрешности функции регулярности ${ displaystyle r}$ является: