Журнал вычислительной математики и математической физики, 2021, T. 61, № 5, стр. 776-786

1. ВВЕДЕНИЕ

Относительно недавние успехи по преодолению “проклятия размерности” позволяют оперировать с дискретизациями функций на очень густых сетках. Например (в духе работ [1]–[5]), заданную на отрезке $[L,R]$ функцию $f(x)$ можно дискретизировать, т.е. превратить в вектор c элементами $f(x(i))$, где $\{ x(i)\} _{{i = 0}}^{{N - 1}}$ – произвольная сетка на $[L,R]$. Если $N = {{n}_{1}} \times \ldots \times {{n}_{d}}$, то полученный вектор можно рассматривать (см. [6]) как тензор (многомерный массив) размером ${{n}_{1}} \times \ldots \times {{n}_{d}}$ с элементами:

Тензор $A$ будем называть тензоризацией функции $f$ на сетке $\{ x(i)\} $. Этот тензор на практике часто допускает приближение другим тензором $B$, имеющим малопараметрическое представление. К примеру, можно использовать ТТ-разложение [2], [7] (tensor train, тензорный поезд): где ${{H}_{k}}$ имеет размеры ${{r}_{{k - 1}}} \times {{n}_{k}} \times {{r}_{k}}$, а индекс суммирования ${{\alpha }_{k}}$ пробегает значения от $1$ до ${{r}_{k}}$. Числа ${{r}_{k}}$ называются ТТ-рангами представления (1), причем для единообразия определения тензоров ${{H}_{k}}$ считается, что ${{r}_{0}} = {{r}_{d}} = 1$.

Стоит также отметить, что в случае тензоризаций высокой размерности, когда число $N$ очень велико, вычисление и хранение в памяти элементов тензора $A$ не представляется возможным. Тем не менее иногда есть возможность получить сразу представление (1), вычисляя $f(x(i))$ лишь для небольшого количества точек $x(i)$. Например, можно использовать крестовое приближение (TT-cross approximation) из [8].

Величины ТТ-рангов играют ключевую роль для применимости ТТ-разложения, ведь требуемая для хранения тензоров ${{H}_{k}}$ память и сложность распространенных операций над тензорами в этом формате растут пропорционально полиномам малой степени от ${{r}_{k}}$ [7]. Поэтому представляется интересным исследовать, насколько малы могут быть ТТ-ранги приближений тензоризаций функций.

Для некоторых классов функций известны компактные представления для тензоризаций, например, для экспоненты, синуса и некоторых других [1], [3]. Для тензоризации полинома степени $n$ на равномерной сетке известно [2], [3], что все ее ТТ-ранги ограничены $n + 1$. В [2] было показано, что ТТ-ранги приближений тензоризаций так называемых асимптотически гладких (т.е. бесконечно дифференцируемых с “не слишком быстро” растущими при приближении к сингулярностям производными) функций ограничены числом, растущим при уменьшении требуемой погрешности $\varepsilon $ как $ - lo{{g}_{2}}(\varepsilon )$. В [5] были получены оценки ТТ-рангов приближений тензоризаций полиномов на равномерных сетках, улучшающие известную оценку $n + 1$.

В данной работе для тензоризаций вещественнозначных функций, являющихся следами аналитических в некотором эллипсе функций комплексного переменного, доказаны верхние и нижние оценки ТТ-рангов приближений. Полученные оценки были применены к тензоризациям полиномов, существенно улучшив известные результаты: вместо $O(\sqrt[3]{n})$ из [5] доказана оценка $O(lnn)$.

2. НЕОБХОДИМЫЕ ОПРЕДЕЛЕНИЯ

Определение 1. Матрицами развертки тензора $A \in {{\mathbb{R}}^{{{{n}_{1}} \times \ldots \times {{n}_{d}}}}}$ называются матрицы

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

Для тензора $A \in {{\mathbb{R}}^{{{{n}_{1}} \times \ldots \times {{n}_{d}}}}}$ определим нормы

В основном мы будем рассматривать “кубические” тензоризации на равномерных сетках, т.е. тензоры, все размеры которого равны одному и тому же числу $b$, а элементы заданы значениями функции $f(x)$ в равноудаленных узлах. Такие $d$-мерные тензоризации с шагом $(R - L){{b}^{{ - d}}}$ на отрезке $[L,R]$ будем обозначать через ${{T}_{{b,d,[L,R]}}}(f)$.

Для ТТ-разложения вида (1) $d$-мерного тензора $B \in {{\mathbb{R}}^{{b \times \ldots \times b}}}$ определим $\mathcal{R}({{H}_{1}}, \ldots ,{{H}_{d}})$ как максимальный из его ТТ-рангов. Далее определим $\mathcal{R}(B) = min\mathcal{R}({{H}_{1}}, \ldots ,{{H}_{d}})$, где минимум берется по всевозможным ТТ-разложениям вида (1) тензора $B$. Для оценки ТТ-рангов наилучших приближений нам понадобится функция

Определение 2. Эллипс на комплексной плоскости с центром в нуле и осями, параллельными осям координат, чьи полуоси равны $(\rho + {{\rho }^{{ - 1}}}){\text{/}}2$ и $(\rho - {{\rho }^{{ - 1}}}){\text{/}}2$ для некоторого $\rho > 1$, будем называть эллипсом Бернштейна и обозначать через ${{\Gamma }_{\rho }}$. Также эллипс Бернштейна можно рассматривать (см. [9]) как образ окружности $\{ \rho {{e}^{{i\varphi }}}\,:\varphi \in [0,2\pi )\} $ под действием отображения Жуковского $w \to (w + {{w}^{{ - 1}}}){\text{/}}2$. Такой же эллипс, но с центром в точке $z \in \mathbb{C}$, будем обозначать через ${{\Gamma }_{\rho }}(z)$.

Определение 3. Чебышёвской сеткой на $[ - 1,1]$ с числом узлов $n$ будем называть упорядоченное множество точек $\{ {{x}_{0}}, \ldots ,{{x}_{{n - 1}}}\} $, где ${{x}_{j}} = cos(\pi {\text{/}}(2n) + \pi j{\text{/}}n)$. Известно [9], что числа ${{x}_{j}}$ являются корнями полинома Чебышёва степени $n$, т.е. ${{T}_{n}}(x) = cos(arccos(nx))$.

Круг радиуса $r$ с центром в точке $z$ на комплексной плоскости будем обозначать через $U(r,z)$.

3. ВЕРХНИЕ ОЦЕНКИ

Докажем некоторые верхние оценки ТТ-рангов и связанных с ними величин для приближений тензоризаций функций на равномерных сетках. Основная лемма 1 уточняет известную (см., например, [9]) оценку точности приближения функции, являющейся следом аналитической в эллипсе Бернштейна. Теорема 1 демонстрирует возможность низкорангового приближения матриц развертки тензоризаций функций, аналитических в круге, чей диаметр является отрезком дискретизации. Следствие 1 дает оценку непосредственно для величины ${{\mathcal{R}}_{\epsilon }}({{T}_{{b,d,[L,R]}}}(f))$ для функций $f$ с указанным свойством. Наконец, теорема 2 рассматривает более простой случай, когда функция является аналитической в достаточно большом эллипсе. Заметим, что теорему 1 может иметь смысл применять даже для функций, являющихся аналитическими в произвольно больших множествах, так как в оценку теоремы 2 входит максимум модуля $f(z)$ на некотором эллипсе – число, которое может быть нежелательно велико для интересующей нас функции $f(z)$. Эта особенность будет использована ниже при применении полученных результатов к полиномам.

Лемма 1. Пусть $f(x)$ – след аналитической внутри эллипса Бернштейна ${{\Gamma }_{\rho }}$, $\rho > 1$, функции $f(z)$, причем ${\text{|}}{\kern 1pt} f(z){\kern 1pt} {\text{|}} \leqslant M$ на ${{\Gamma }_{\rho }}$. Пусть также ${{P}_{n}}(x)$ – полином Лагранжа степени $n$ для $f(x)$ на чебышёвской сетке на $[ - 1,1]$ с $(n + 1)$ узлом $\{ {{x}_{0}}, \ldots ,{{x}_{n}}\} $. Тогда для всех $x \in [ - 1,1]$ выполнено следующее:

Доказательство. Зафиксируем произвольное $x \in [ - 1,1]{{\backslash }}\{ {{x}_{0}}, \ldots ,{{x}_{n}}\} $. Далее рассмотрим функцию

и, применяя теорему о вычетах и домножая на $\prod\nolimits_j {(x - {{x}_{j}})} $ (т.е. рассуждая аналогично [9, Теорема 13.6]), придем к представлению: Так как ${{x}_{j}}$ суть в точности корни полинома Чебышёва ${{T}_{{n + 1}}}(x)$ степени $n + 1$, то можно записать

Используя доказанное в [9, Теорема 13.6] для $z \in {{\Gamma }_{\rho }}$ неравенство $\left| {{{T}_{{n + 1}}}(z)} \right| \geqslant ({{\rho }^{{n + 1}}} - {{\rho }^{{ - n - 1}}}){\text{/}}2$, а также очевидное для $x \in [ - 1,1]$ неравенство $\left| {{{T}_{{n + 1}}}(x)} \right| \leqslant 1$, при $x \in [ - 1,1]$ получаем

Для оценки длины эллипса ${{\Gamma }_{\rho }}$ воспользуемся упомянутым фактом, что первый является образом окружности ${{S}_{\rho }} = \{ \rho {{e}^{{i\varphi }}}\,:\varphi \in [0,2\pi )\} $ под действием отображения $w \to (w + {{w}^{{ - 1}}}){\text{/}}2$:

Далее вычислим $min{{\left| {z - x} \right|}^{2}}$ для $z \in {{\Gamma }_{\rho }}$ и $x \in [ - 1,1]$. Обозначим через ${{r}_{1}}$ и ${{r}_{2}}$ большую и меньшую полуоси эллипса ${{\Gamma }_{\rho }}$ соответственно. Тогда точки этого эллипса параметризуются углом $\varphi {\kern 1pt} :\;z = {{r}_{1}}cos\varphi + i{{r}_{2}}sin\varphi $. Преобразуем минимизируемое выражение

В силу симметрии достаточно рассмотреть $x \geqslant 0$. При фиксированном $x$ выражение (2) – это квадратный трехчлен относительно $cos\varphi $, причем вершина соответствующей параболы имеет абсциссу ${{r}_{1}}x{\text{/}}(r_{1}^{2} - r_{2}^{2}) = {{r}_{1}}x$. При ${{r}_{1}}x \leqslant 1$ минимум по $\varphi $ достигается при $cos\varphi = {{r}_{1}}x$ и равен $r_{2}^{2}$. При ${{r}_{1}}x > 1$ минимум достигается при $cos\varphi = 1$ и равен ${{({{r}_{1}} - x)}^{2}}$, причем это выражение достигает минимума по $x$ при $x = 1$. Так как ${{r}_{1}} - 1 < {{r}_{2}}$, то и $min\left| {z - x} \right| = {{r}_{1}} - 1 = (\rho + {{\rho }^{{ - 1}}}){\text{/}}2 - 1$.

В итоге имеем

Теорема 1. Пусть $f{\kern 1pt} :\;[L,R] \to \mathbb{R}$ является следом аналитической в круге с диаметром $[L,R]$ функции $f(z)$, причем $\left| {f(z)} \right| \leqslant M$ для всех $z$ из этого круга.

Тогда для произвольного $\varepsilon > 0$, каждой матрицы развертки ${{A}_{k}} \in {{\mathbb{R}}^{{{{b}^{k}} \times {{b}^{{d - k}}}}}}$ тензора ${{T}_{{b,d,[L,R]}}}(f)$ и любого натурального $\mu \in [1,{{b}^{k}} - 1]$ существует матрица ${{B}_{k}} \in {{\mathbb{R}}^{{{{b}^{k}} \times {{b}^{{d - k}}}}}}$ такая, что

где $s = \left\lfloor {lo{{g}_{\rho }}(3M{\text{/}}\varepsilon + 1)} \right\rfloor $, $\rho = 2\mu + 1 + 2\sqrt {{{\mu }^{2}} + \mu } $.

Доказательство. Обозначим через $h$ шаг дискретизации: $h = (R - L){{b}^{{ - d}}}$. Строка матрицы ${{A}_{k}}$ с индексом $j$ соответствует отрезку $[L + jh,L + (j + 1)h]$.

Рассмотрим функцию

а также соответствующую функцию комплексного аргумента ${{g}_{j}}(w)$, $w \in U((\rho + {{\rho }^{{ - 1}}}){\text{/}}2,0)$.

Отображение $w \mapsto \alpha + \beta w$ переводит круг $U((\rho + {{\rho }^{{ - 1}}}){\text{/}}2,0)$ в $U(\beta (\rho + {{\rho }^{{ - 1}}}){\text{/}}2,\alpha )$. В нашем случае $\alpha = L + jh + h{\text{/}}2$, $\beta = h{\text{/}}2$.

Покажем, что при $j = \mu ,\mu + 1, \ldots ,{{b}^{k}} - \mu - 1$ круг $U(\beta (\rho + {{\rho }^{{ - 1}}}){\text{/}}2,\alpha )$ лежит внутри круга с диаметром $[L,R]$, т.е.

Действительно, для заданного в условии значения $\rho $ верно равенство $\rho + {{\rho }^{{ - 1}}} = 4\mu + 2$, поэтому указанная пара условий переписывается в виде

Внутри круга с диаметром $[L,R]$ по условию выполнено неравенство $\left| {f(z)} \right| \leqslant M$, поэтому и $\left| {{{g}_{j}}(w)} \right| \leqslant M$ для $w \in U((\rho + {{\rho }^{{ - 1}}}){\text{/}}2,0)$, а значит, и для $w \in {{\Gamma }_{\rho }}$. Поэтому из леммы 1 следует, что для полинома Лагранжа ${{\hat {P}}_{{s,j}}}(y)$ степени $s$ на чебышёвской сетке для $g(y)$ верно неравенство:

Пусть ${{P}_{{s,j}}}(x) = {{\hat {P}}_{{s,j}}}\left( {\tfrac{2}{h}(x - L - jh) - 1} \right)$. Из неравенства (3) получаем, что $\left| {f(x) - {{P}_{{s,j}}}(x)} \right| \leqslant \varepsilon $ на отрезке $[L + jh,L + (j + 1)h]$ для $j = \mu $, $\mu + 1, \ldots ,{{b}^{k}} - \mu - 1$. Поэтому строки $a_{j}^{{\text{T}}}$ с этими индексами приблизим строками:

Так как степень полиномов ${{P}_{{s,j}}}(x)$ не превосходит $s$, все строки ${\mathbf{P}}_{{s,j}}^{{\text{T}}}$ лежат в линейной оболочке векторов ${{p}_{0}}, \ldots ,{{p}_{s}} \in {{\mathbb{R}}^{{d - k}}}$, ${{p}_{t}}(\ell ) = {{\ell }^{t}}$.

Строки $a_{j}^{{\text{T}}}$ матрицы ${{A}_{k}}$ с индексами $j \in \{ 0, \ldots ,\mu - 1\} \cup \{ {{b}^{k}} - \mu , \ldots ,{{b}^{k}} - 1\} $ “приблизим” ими самими, т.е. матрицу ${{B}_{k}}$ построим в виде

Очевидно, $rank{{B}_{k}} \leqslant 2\mu + s + 1$ и ${{\left\| {{{A}_{k}} - {{B}_{k}}} \right\|}_{\infty }} \leqslant \varepsilon $.

Следствие 1. В условиях теоремы 1 для любого $\hat {\varepsilon } > 0$ выполнено

Доказательство. Положим в теореме 1 $\mu = 1$ (чтобы удовлетворить условию $\mu \in [1,{{b}^{k}} - 1]$ для всех $k = 1, \ldots ,d - 1$) и

и рассмотрим приближения ${{B}_{k}}$ к матрицам развертки ${{A}_{k}}$ со свойствами $rank{{B}_{k}} \leqslant \hat {s} + 3$ и ${{\left\| {{{A}_{k}} - {{B}_{k}}} \right\|}_{\infty }} \leqslant \varepsilon $. Из последнего неравенства следует, что ${{\left\| {{{A}_{k}} - {{B}_{k}}} \right\|}_{F}} \leqslant \varepsilon {{b}^{{d/2}}}$.

Теорема 2.2 из [8] гарантирует существование тензора $\widehat B$ с ТТ-рангами ${{r}_{k}}$, приближающего тензор $A$ в норме Фробениуса с точностью:

где ${{r}_{k}}$ суть ${{\varepsilon }_{k}}$-ранги матриц развертки ${{A}_{k}}$.

Положим ${{\varepsilon }_{k}} = \varepsilon {{b}^{{d/2}}}$, тогда ${{r}_{k}} \leqslant rank{{B}_{k}} \leqslant \hat {s} + 3$ и при этом

Теорема 2. Пусть $\widehat \Gamma $ – образ эллипса ${{\Gamma }_{\rho }}$ под действием линейного отображения

а $f(z)$ – аналитическая внутри $\widehat \Gamma $ функция, для которой $\left| {f(z)} \right| \leqslant M$ для $z \in \widehat \Gamma $ и имеющая вещественнозначный след на $[L,R]$.

Тогда для произвольного $\varepsilon > 0$ и натуральных $b$ и $d$ существует тензор $B$ такой, что

Доказательство. Будем обозначать через $(f \circ \xi )(x)$ композицию функций $f$ и $\xi $, т.е. $(f \circ \xi )(x) = f(\xi (x))$. Заметим, что $(f \circ \xi )(z)$ аналитична в ${{\Gamma }_{\rho }}$ как композиция аналитических функций $f$ и $\xi $. Приблизим $(f \circ \xi )(x)$ полиномом Лагранжа ${{\hat {P}}_{s}}(x)$ степени $s$ на чебышёвской сетке на $[ - 1,1]$, $(f \circ \xi )(x)$ – след аналитической в ${{\Gamma }_{\rho }}$ функции $(f \circ \xi )(z)$. Аналогично доказательству теоремы 1 можно показать, что для параметра $s$ из условия выполнено неравенство:

где $({{\hat {P}}_{s}} \circ {{\xi }^{{ - 1}}})(y)$ есть полином степени не более $s$, поэтому согласно [3], [2] его тензоризация $B$ допускает ТТ-разложение с ТТ-рангами, не превосходящими $s + 1$.

4. НИЖНИЕ ОЦЕНКИ

Рассмотрим пример функции $f(x)$, являющейся следом аналитической в $\mathbb{C}$ функции. Для приближенных ТТ-рангов тензоризации этой функции будет доказана нижняя оценка (теорема 3).

Зафиксируем натуральные $b \geqslant 2$, $d \geqslant 2$ и $k \geqslant d{\text{/}}3$. Определим $f(z) = sin(2\pi {{b}^{{2k}}}{{z}^{2}})$, $z \in \mathbb{C}$, и обозначим через $f(x)$ ее (вещественнозначный) след на $\mathbb{R}$. Пусть $A = {{T}_{{b,d,[0,1]}}}(f)$.

Введем в рассмотрение функции:

Строка матрицы развертки ${{A}_{k}}$ с индексом $s$ есть дискретизация функции ${{f}_{s}}(\xi )$ на равномерной сетке на $[0,2\pi ]$.

Для всех $s,t \in \{ 0, \ldots ,{{b}^{k}} - 1\} $ определим интегралы

Для тех же $s,t$ введем величины (здесь ${{a}_{{s,i}}}$ – элементы матрицы ${{A}_{k}}$): Матрицу из элементов ${{\hat {d}}_{{s,t}}}$ обозначим через $\hat {D}$.

Лемма 2. Для всех $s,t \in \{ 0, \ldots ,{{b}^{k}} - 1\} $ верно неравенство

где ${{\delta }_{{s,t}}}$ – символ Кронекера.

Доказательство. Преобразуем выражения для ${{f}_{s}}(\xi )$:

Отсюда получим Пусть $\beta = 1{\text{/}}\pi $, $p = 2(s + t)$. Исследуем интеграл $\int_0^{2\pi } {{{e}^{{ip\xi + i\beta {{\xi }^{2}}}}}d\xi } $: Первый член в скобках равен 0, так как ${{e}^{{i\beta {{{(2\pi )}}^{2}}}}} = {{e}^{{i4\pi }}} = 1 = {{e}^{{ip2\pi }}}$. Повторяя интегрирование по частям, получаем Взяв вещественную часть от обеих частей полученного равенства, имеем Поэтому верно Отсюда и из (5) следует, что

Лемма 3. Для всех $s,t \in \{ 0, \ldots ,{{b}^{k}} - 1\} $ верно неравенство

Доказательство. Напомним, что формулой левых прямоугольников для вычисления интеграла $\int_{{{x}_{i}}}^{{{x}_{{i + 1}}}} {\varphi (x)dx} $ называется выражение $({{x}_{{i + 1}}} - {{x}_{i}})\varphi ({{x}_{i}})$, а составной формулой для сетки $\{ {{x}_{0}}, \ldots ,{{x}_{n}}\} $ с шагом $h$ называется сумма $\sum\nolimits_{i = 0}^{n - 1} {\varphi ({{x}_{i}})h} $. Простая формула имеет погрешность:

где $\xi (x) \in [{{x}_{i}},{{x}_{{i + 1}}}]$. При применении составной формулы на отрезке $[L,R]$ с шагом $h$ погрешность не превосходит ${{\left\| {\varphi {\kern 1pt} '{\kern 1pt} } \right\|}_{{C[L,R]}}}(R - L)h{\text{/}}2$.

Ясно видно, что выражение (4) для ${{\hat {d}}_{{s,t}}}$ есть в точности составная формула левых прямоугольников для вычисления интеграла ${{d}_{{s,t}}}$ на отрезке $[0,2\pi ]$. Погрешность аппроксимации интеграла оценивается (подразумевается норма ${{\left\| {\, \cdot \,} \right\|}_{{C[0,2\pi ]}}}$) в виде

Лемма 4. Пусть $F$ – главная подматрица матрицы $\hat {D}$, находящаяся на пересечении строк и столбцов с индексами $s,t \in [\ell ,u)$, где

причем ${{b}^{{d - k}}} \geqslant {{2}^{{10}}}$. Тогда младшее сингулярное число ${{\sigma }_{{min}}}(F) > 1{\text{/}}2$.

Доказательство. Обратим внимание, что заявленное в началe раздела условие $k \geqslant d{\text{/}}3$ гарантирует, что $\ell ,u < {{b}^{k}}$, поэтому выбирать подматрицу с указанными индексами в матрице $\hat {D} \in {{\mathbb{R}}^{{{{b}^{k}} \times {{b}^{k}}}}}$ корректно.

Пусть $G = F - I$. Заметим, что

Из лемм 2 и 3 следует, что все элементы матрицы $\hat {D} - I$, а значит, и $F - I$, по модулю не превосходят

Поэтому имеем

По условию ${{b}^{{d - k}}} \geqslant {{2}^{{10}}}$, тогда получаем

Отсюда и из неравенства (6) следует утверждение леммы.

Теорема 3. Пусть $b \geqslant 2$, $d \geqslant 2$ и $k \geqslant d{\text{/}}3$ – натуральные числа, удовлетворяющие условию ${{b}^{{d - k}}} \geqslant {{2}^{{10}}}$, а $f(x) = sin(2\pi {{b}^{{2k}}}{{x}^{2}})$, $x \in [0,1]$. Тогда верно неравенство

Доказательство. Исследуем сингулярные числа ${{\sigma }_{s}}({{A}_{k}})$ матрицы ${{A}_{k}}$. Для этого воспользуемся известным фактом, что

Из определения (4) матрицы $\hat {D}$ следует, что $A_{k}^{{\text{T}}}{{A}_{k}} = {{b}^{{d - k}}}\hat {D}{\text{/}}2.$ Далее, для главной подматрицы $F$ матрицы $\hat {D}$ из леммы можно применить теорему о чередовании сингулярных чисел симметричной матрицы [9] и получить, что ${{\sigma }_{{u - \ell }}}(\hat {D}) \geqslant 1{\text{/}}2$. Отсюда и из равенства (7) вытекает

Рассмотрим теперь произвольный тензор $B$ со свойством ${{\left\| {A - B} \right\|}_{F}} \leqslant \tfrac{1}{2}{{b}^{{(d - k)/2}}}$. Аналогичное неравенство верно и для матриц развертки ${{A}_{k}}$ и ${{B}_{k}}$. По теореме Эккарта–Юнга [10] наилучшее приближение в норме Фробениуса ранга $u - \ell - 1$ имеет погрешность как минимум

где $N = \min \{ {{b}^{k}},{{b}^{{d - k}}}\} $ – меньший из размеров матрицы ${{A}_{k}}$. Поэтому верно

Рассмотрим произвольное ТТ-разложение тензора $B$ вида (1). Для $k$-й матрицы развертки можно написать

откуда следует, что ${{r}_{k}} \geqslant rank{{B}_{k}} \geqslant \tfrac{1}{{16}}{{b}^{{\tfrac{{d - k}}{2}}}} - 2$, а в силу произвольности $B$ и

Чтобы наглядно связать верхнюю оценку из данного раздела и нижние оценки из предыдущего, имеет смысл зафиксировать некоторые величины и перейти к асимптотической нотации. Именно, зафиксируем натуральное $b \geqslant 2$, произвольно малое $\varepsilon > 0$ и отрезок $[L,R]$ на вещественной прямой. Определим функцию

Здесь максимум берется по всем аналитическим в круге $U$ с диаметром $[L,R]$ функциям $f(z)$, имеющим вещественный след на $[L,R]$.

Следствие 1 гарантирует оценку ${{\mathcal{R}}_{{b,\varepsilon ,[L,R]}}}(M,d) = O(lnM + d)$ при $M,d \to \infty $. С другой стороны, для функции $f(z)$ из данного раздела несложно оценить максимум модуля на единичном круге:

Пусть $k = \left\lceil {d{\text{/}}3} \right\rceil $, тогда по теореме 3 максимальный ТТ-ранг есть как минимум: В последнем равенстве через $M(d)$ обозначено число ${{e}^{{2\pi {{b}^{{2d/3}}}}}}$. Получается, что

5. ПРИМЕНЕНИЕ К ПОЛИНОМАМ

В работе [5] рассматривались ТТ-ранги приближений к тензоризациям полиномов. В данном разделе мы применим результаты предыдущих разделов к полиномам, существенно улучшив верхние оценки из указанной работы. Также мы получим нижние оценки ТТ-рангов $\varepsilon $-приближений для этого класса функций.

Утверждение 1. Пусть $p(x) = {{p}_{0}} + {{p}_{1}}x + \ldots + {{p}_{n}}{{x}^{n}}$ – полином с вещественными коэффициентами. Пусть $A = {{T}_{{b,d,[0,1]}}}(f)$ и $M = \sum\nolimits_{i = 0}^n {\left| {{{p}_{i}}} \right|} $. Зафиксируем произвольное $\varepsilon > 0$.

Тогда для каждой матрицы развертки ${{A}_{k}}$ тензора $A$, $k = 1, \ldots ,d - 1$, и натурального $\mu \in [1,{{b}^{k}} - 1]$ существует матрица ${{B}_{k}}$ такая, что

где

Доказательство. Достаточно заметить, что на единичном круге на комплексной плоскости (а тем более, в круге с диаметром $[0,1]$) аналитическое продолжение $p(z)$ полинома $p(x)$ ограничено по модулю суммой $\sum\nolimits_i {\left| {{{p}_{i}}} \right|} $, и применить теорему 1.

Замечание. Если в духе работы [5] ограничить коэффициенты ${{p}_{i}}$ по модулю фиксированной константой и поинтересоваться асимптотическим поведением $\varepsilon $-рангов матриц развертки при стремлении $n$ к бесконечности, то доказанное утверждение даст оценку вида $O(lnn)$ в отличиe от оценки $O(\sqrt[3]{n})$, полученной в [5].

Утверждение 2. Пусть $b \geqslant 2$, $d \geqslant 2$ и $k \geqslant d{\text{/}}3$ – натуральные числа, удовлетворяющие условию ${{b}^{{d - k}}} \geqslant {{2}^{{10}}}$.

Тогда для любого $n \geqslant \left\lfloor {lo{{g}_{2}}(1 + 14{{b}^{{k/2}}}{{e}^{{10{{b}^{{2k}}}}}})} \right\rfloor $ существует полином ${{P}_{n}}(x) = {{p}_{0}} + \ldots + {{p}_{n}}{{x}^{n}}$ такой, что верно следующее:

1. $\sum\limits_{i = 0}^n \,{\text{|}}{{p}_{i}}{\kern 1pt} {\text{|}} \leqslant {{2}^{{2n}}}{{(n + 1)}^{2}}$;

2. ${{\mathcal{R}}_{\varepsilon }}({{T}_{{b,d,[0,1]}}}({{P}_{n}})) \geqslant \tfrac{1}{{16}}{{b}^{{\tfrac{{d - k}}{2}}}} - 2$, где $\varepsilon = \tfrac{1}{4}{{b}^{{\tfrac{{d - k}}{2}}}}$.

Доказательство. Возьмем функцию $f(x)$ из теоремы 3. Обозначим через ${{P}_{n}}(x)$ полином Лагранжа степени $n$, интерполирующий $f(x)$ на чебышёвской сетке с $n + 1$ узлом на $[ - 1,1]$.

Сначала оценим коэффициенты $p(x)$. Полином Лагранжа можно записать в следующем виде [9]:

где ${{x}_{j}}$ суть корни полинома Чебышёва степени $n + 1$, т.е. Оценим снизу модуль $\omega {\kern 1pt} '({{x}_{j}})$: Поэтому ${\text{|}}\omega {\kern 1pt} '({{x}_{j}}){\kern 1pt} {\text{|}} \geqslant {{2}^{{ - n}}}(n + 1)$. Коэффициент при ${{x}^{m}}$ многочлена $\omega (x){\text{/}}(x - {{x}_{j}})$ есть, очевидно, т.е. по модулю не превосходит $C_{n}^{{n - m}}$. Итого получаем

Применим лемму 1 для оценки отклонения $f(x)$ от ${{P}_{n}}(x)$ на $[ - 1,1]$:

Положим $\rho = 2$ и оценим величину $M$, исходя из рассуждения, аналогичного (8): Таким образом, с учетом неравенства для $n$ (из условия утверждения) имеем для всех $x \in [ - 1,1]$: Это означает, что

Теперь возьмем произвольный тензор $B$, приближающий ${{T}_{{b,d,[0,1]}}}({{P}_{n}})$ с ошибкой не более $\varepsilon $. Заметим, что по неравенству треугольника для нормы он дает приближение ${{T}_{{b,d,[0,1]}}}(f)$ с ошибкой не более $2\varepsilon $. Из теоремы 3 сразу получаем неравенство

а в силу произвольности $B$ и свойство из условия.

Автор выражает благодарность Виктории Владимировне Высоцкой за помощь в оформлении статьи.