Эпсилон-энтропия

Эпсилон-энтропия или ε-энтропия — термин, введённый А. Н. Колмогоровым для характеристики классов функций. Он определяет меру сложности функции, минимальное количество знаков, необходимое для задания функции с точностью $\varepsilon$.

Введение в понятие

Рассмотрим компактное метрическое пространство $M$ и зададим в нём эпсилон-сеть, то есть такое конечное (состоящее из $N(\varepsilon )$ точек) множество, что шары радиуса $\varepsilon$ с центрами в этих точках целиком покрывают всё $M$. Тогда для задания любого элемента $M$ с точностью $\varepsilon$ (то есть, по сути, выбора одного из узлов сети) достаточно порядка $\log _{2}N(\varepsilon )$ знаков (бит).

Для отрезка $M=[0,\;1]$ величина $N$ растёт при уменьшении $\varepsilon$ как $1/\varepsilon$, для квадрата как $1/{\varepsilon ^{2}}$ и т. д. Тем самым показатель определяет размерность Минковского множества $M$.

В случае пространства $M$ гладких функций (на компактном кубе в $n$-мерном пространстве и с ограниченными константой производными до порядка $p$, чтобы это пространство было компактным) размерность пространства бесконечна, но число $N(\varepsilon )$ элементов сети конечно, хотя оно и растёт быстрее любой (отрицательной) степени величины $\varepsilon$.

Колмогоров доказал, что логарифм числа $N(\varepsilon )$ точек минимальной $\varepsilon$-сети растёт в этом случае как $(1/\varepsilon )^{n/p}$.

Применение

Введение понятия эпсилон-энтропии позволило понять и решить 13-ю проблему Гильберта.

Если бы функции $k$ переменных, участвующие в суперпозиции, имели гладкость $p$, то с их помощью можно было бы получить для представляемых функций сеть, логарифм числа точек которой был бы порядка $(1/\varepsilon )^{k/p}$. Если это число меньше минимально возможного для функций $n$ переменных гладкости $p$, то, значит, предполагавшееся представление суперпозициями функций столь большой гладкости невозможно.

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