| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Краткие сообщения О минимальной норме проектора при линейной интерполяции на М. В. Невский Ярославский государственный университет им. П. Г. Демидова
Англоязычная версия:
Mathematical Notes, 2023, Volume 114, Issue 3, Pages DOI: https://doi.org/10.1134/S0001434623090146 
Реферативные базы данных:
  1. ВведениеДоказывается, что при линейной интерполяции на $n$-мерном евклидовом шаре интерполяционный проектор, узлы которого совпадают с вершинами правильного симплекса, вписанного в граничную сферу, имеет наименьшую норму. Ниже $n\in{\mathbb N}$. Элемент $x\in {\mathbb R}^n$ будем записывать в виде $x=(x_1,\dots,x_n)$. Пусть $K$ – выпуклое тело в ${\mathbb R}^n$. Обозначим через $C(K)$ пространство непрерывных функций $f\colon K\to{\mathbb R}$ с равномерной нормой $\|f\|_{C(K)}:=\max_{x\in K}|f(x)|$. Под $\Pi_1({\mathbb R}^n)$ будем понимать совокупность многочленов от $n$ переменных степени $\leqslant 1$, или линейных функций на ${\mathbb R}^n$. Для $x^{(0)}\in {\mathbb R}^n$, $R>0$ через $B(x^{(0)};R)$ обозначим $n$-мерный евклидов шар, задаваемый неравенством $\|x-x^{(0)}\|\leqslant R$. Здесь
$$
\begin{equation*}
\|x\|:=\sqrt{\langle x,x\rangle}= \biggl(\,\sum_{i=1}^n x_i^2\biggr)^{1/2}.
\end{equation*}
\notag
$$
Положим $B_n:=B(0;1)$. Пусть $S$ – невырожденный симплекс в ${\mathbb R}^n$ с вершинами $x^{(j)}=(x_1^{(j)},\dots,x_n^{(j)})$, $1\leqslant j\leqslant n+1$. Введем в рассмотрение матрицу вершин этого симплекса:
$$
\begin{equation*}
{\mathbf S}:=\begin{pmatrix} x_1^{(1)}&\dots&x_n^{(1)}&1 \\ x_1^{(2)}&\dots&x_n^{(2)}&1 \\ \vdots&\vdots&\vdots&\vdots \\ x_1^{(n+1)}&\dots&x_n^{(n+1)}&1 \end{pmatrix}.
\end{equation*}
\notag
$$
Считаем ${\mathbf S}^{-1}=(l_{ij})$. Линейные многочлены $\lambda_j(x)=l_{1j}x_1+\cdots+l_{nj}x_n+l_{n+1,j}$, коэффициенты которых записаны по столбцам матрицы ${\mathbf S}^{-1}$, обладают свойствами $\lambda_j(x^{(k)})=\delta_j^k$. Для точки $x\in{\mathbb R}^n$ числа $\lambda_j(x)$ являются ее барицентрическими координатами (см., например, [1]). Мы называем $\lambda_j$ базисными многочленами Лагранжа симплекса $S$. Будем говорить, что интерполяционный проектор $P\colon C(K)\to \Pi_1({\mathbb R}^n)$ соответствует симплексу $S\subset K$, если его узлы совпадают с вершинами этого симплекса. Проектор $P$ определяется равенствами $Pf(x^{(j)})=f(x^{(j)})$. Справедлив следующий аналог интерполяционной формулы Лагранжа: Под $\|P\|_K$ будем понимать норму $P$ как оператора из $C(K)$ в $C(K)$. Из (1) следует, что
$$
\begin{equation*}
\|P\|_K=\max_{x\in K}\,\sum_{j=1}^{n+1}|\lambda_j(x)|.
\end{equation*}
\notag
$$
Через $\theta_n(K)$ обозначим минимальную норму интерполяционного проектора $P\colon C(K)\to\Pi_1({\mathbb R}^n)$, узлы которого принадлежат $K$. Пусть $K=B:=B(x^{(0)};R)$. Как доказано в [2],
$$
\begin{equation}
\|P\|_B=\max_{f_j=\pm 1}\biggl[R\biggl(\,\sum_{i=1}^n \biggl(\,\sum_{j=1}^{n+1} f_jl_{ij}\biggr)^2\biggr)^{1/2}+ \biggl|\,\sum_{j=1}^{n+1}f_j\lambda_j(x^{(0)})\biggr|\biggr].
\end{equation}
\tag{2}
$$
Если $S$ – правильный симплекс, вписанный в шар, то $\|P\|_B$ не зависит ни от центра $x^{(0)}$, ни от радиуса $R$ шара, ни от выбора такого симплекса. В этом случае справедливо равенство $\|P\|_B=\max\{\psi(a_n),\psi(a_n+1)\}$ (см. [2; теорема 2]). Здесь
$$
\begin{equation}
\psi(t):=\frac{2\sqrt{n}}{n+1}(t(n+1-t))^{1/2}+ \biggl|1-\frac{2t}{n+1}\biggr|, \qquad 0\leqslant t\leqslant n+1,
\end{equation}
\tag{3}
$$
$$
\begin{equation}
a_n:=\biggl\lfloor\frac{n+1}{2}- \frac{\sqrt{n+1}}{2}\biggr\rfloor.
\end{equation}
\tag{4}
$$
2. Теорема о симплексе и минимальном эллипсоидеПусть $S$ – невырожденный $n$-мерный симплекс, $E$ – эллипсоид минимального объема, содержащий $S$, $m$ – натуральное, $1\leqslant m\leqslant n$. Каждому набору из $m$ вершин симплекса поставим в соответствие точку $y\in E$, определяемую следующим образом. Пусть $g$ есть центр тяжести $(m-1)$-мерной грани $S$, содержащей выделенные вершины, $h$ – центр тяжести $(n-m)$-мерной грани, содержащей остальные $n+1-m$ вершин. Тогда $y$ есть точка пересечения прямой $(gh)$ с границей эллипсоида в направлении от $g$ к $h$. Теорема 1. Для любого невырожденного симплекса $S\subset B_n$ и всякого $m\in\{1,\dots,n\}$ найдется такой набор из $m$ вершин симплекса, для которого $y\in B_n$. Доказательство. Пусть $x^{(j)}$ – вершины симплекса. Центр тяжести $S$ и центр минимального эллипсоида $E$ находятся в точке Обозначим через $r$ отношение расстояния от центра тяжести правильного симплекса до центра тяжести $(m-1)$-мерной грани к радиусу описанной сферы. Нетрудно показать, что Через $N$ обозначим число $(m-1)$-мерных граней симплекса: $N=\binom{n+1}{m}$.
Рассмотрим произвольный набор $J$ из $m$ индексов $j$. Центр тяжести $(m-1)$-мерной грани с вершинами $x^{(j)}$, $j\in J$, есть точка Пусть $y_J$ совпадает с точкой $y$ для этого набора вершин. Тогда т.e. $y_J=(1/r)((r+1)c-g_J)$. Суммируя по всем наборам $J$, имеем
$$
\begin{equation}
\begin{aligned} \, \nonumber \sum_{J}\|y_J\|^2&=\sum_{J}\langle y_J, y_J\rangle= \frac{1}{r^2}\biggl(N\|c\|^2(r+1)^2+\sum_J\|g_J\|^2-2(r+1) \biggl\langle\sum_J g_J,c\biggr\rangle\biggr) \\ &=\frac{1}{r^2}\biggl(N\|c\|^2(r^2-1)+\sum_J\|g_J\|^2\biggr). \end{aligned}
\end{equation}
\tag{5}
$$
Мы учли, что $\sum g_J=Nc$. Далее, справедливо равенство
$$
\begin{equation}
\sum_J\|g_J\|^2=\frac{1}{mn}\begin{pmatrix} n \\ m\end{pmatrix} \sum_{j=1}^{n+1}\|x^{(j)}\|^2+\frac{(m-1)(n+1)}{mn} \begin{pmatrix} n+1 \\ m \end{pmatrix}\|c\|^2.
\end{equation}
\tag{6}
$$
Оно доказывается следующим образом. Выражение $\sum \|g_J\|^2$ содержит для каждого $j$ чисел $\|x^{(j)}\|^2$, взятых с коэффициентом $1/m^2$, ровно $\binom{n}{m-1}$, и чисел $2\langle x^{(i)},x^{(j)}\rangle$ для каждых $i\ne j$, взятых с тем же коэффициентом $1/m^2$, ровно $\binom{n-1}{m-2}$. (Последнее – при $m\geqslant 2$; если $m=1$, попарные произведения отсутствуют.) Выражение $\|c\|^2$ содержит все числа $\|x^{(j)}\|^2$ для каждого $j$ и $2\langle x^{(i)},x^{(j)}\rangle$ для $i\ne j$ с множителем $1/(n+1)^2$. Коэффициент при $\|c\|^2$ в правой части (6) обеспечивает равенство выражений с попарными произведениями $\langle x^{(i)},x^{(j)}\rangle$; коэффициент при $\sum \|x^{(j)}\|^2$ выбран так, чтобы разность левой части (6) и второго слагаемого в правой части равнялась первому слагаемому. Поскольку
$$
\begin{equation*}
N(r^2-1)=-\frac{(m-1)(n+1)}{mn} \begin{pmatrix} n+1 \\ m\end{pmatrix},
\end{equation*}
\notag
$$
при подстановке в (5) вместо $\sum \|g_J\|^2$ правой части (6) члены c $\|c\|^2$ компенсируются. После преобразований мы приходим к равенству Так как $S\subset B_n$, то $\|x^{(j)}\|\leqslant 1$. Поэтому среднее значение чисел $\|y_J\|^2$ также $\leqslant 1$. Тем самым, для некоторого набора $J$ выполняется $\|y_J\|\leqslant 1$. Это означает, что эта точка $y_J$ принадлежит шару $B_n$. Теорема доказана. В качестве гипотезы теорема 1 была сформулирована в [3]. Там же с помощью другого подхода показано, что утверждение теоремы 1 верно для $m=1$. 3. Величина $\theta_n(B_n)$Основной результат статьи касается минимальной возможной нормы интерполяционного проектора на $n$-мерном шаре. Теорема 2. Пусть функция $\psi(t)$ и число $a_n$ определяются равенствами (3), (4). При любом $n\in{\mathbb N}$ справедливо равенство Для интерполяционного проектора $P\colon C(B_n)\to \Pi_1({\mathbb R}^n)$ равенство $\|P\|_{B_n}=\theta_n(B_n)$ выполняется тогда и только тогда, когда узлы интерполяции совпадают с вершинами правильного симплекса, вписанного в граничную сферу. Доказательство. Пусть сначала $P$ – интерполяционный проектор, соответствующий правильному вписанному симплексу $S$, $\lambda_j(x)$ – базисные многочлены для этого симплекса, $p_n:=\|P\|_{B_n}$. В [2] доказано, что $p_n=\max\{\psi(a_n),\psi(a_n+1)\}$. В [3] найдены точки $y\in B_n$, для которых Именно, пусть $k_n$ совпадает с тем из чисел $a_n$ и $a_n+1$, на котором $\psi(t)$ принимает большее значение. Возьмем $m=k_n$. Тогда равенство (9) имеет место для каждой из $N=\binom{n+1}{m}$ точек $y$, которые строятся так, как перед формулировкой теоремы 1 в ситуации $E=B_n$.
Пусть теперь $P\colon C(B_n)\to \Pi_1({\mathbb R}^n)$ – произвольный проектор с узлами $x^{(j)}\in B_n$, $S$ – симплекс с вершинами $x^{(j)}$, $E$ – эллипсоид минимального объема, содержащий $S$. Можно рассматривать $P$ как проектор на пространстве $C(E)$. При этом для $m=k_n$ и каждой из точек $y$, указанных перед формулировкой теоремы 1 уже для минимального эллипсоида $E$. По теореме 1, некоторая из этих точек $y^*$ принадлежит $B_n$. Тем самым,
$$
\begin{equation*}
\|P\|_{B_n}=\max_{x\in B_n}\,\sum_{j=1}^{n+1}|\lambda_j(x)|\geqslant \sum_{j=1}^{n+1}|\lambda_j(y^*)|=p_n.
\end{equation*}
\notag
$$
Следовательно, $\theta_n(B_n)=p_n=\max\{\psi(a_n),\psi(a_n+1)\}$.
Остается показать, что если $\|P\|_{B_n}=\theta_n(B_n)$, то симплекс с вершинами в узлах интерполяции является правильным и вписанным в $B_n$. Для симплекса $S$ некоторая из точек $y\in E$, построенная для $m=k_n$, попадает на граничную сферу – иначе $\|P\|_{B_n}>p_n$. Это связано с тем, что $\sum|\lambda_j(x)|$ возрастает при движении $x$ по прямой в направлении от $c$ к $y$. Поскольку $\|y\|=1$, то среднее значение $\|y_J\|$ для оставшихся $y_J$ будет также $\leqslant 1$ (см. (7)). Значит, другая такая точка также попадает на границу шара. Таким образом получаем, что $\|y_J\|=1$ для всех наборов $J$ из $m=k_n$ индексов $j$. Из (7) теперь следует, что $\|x^{(j)}\|=1$, т.e. симплекс $S$ вписан в шар. Поскольку все точки $y_J$ принадлежат граничной сфере, то функция $\sum |\lambda_j(x)|$ достигает максимума на шаре в $N=\binom{n+1}{m}$ различных точках. Поэтому симплекс $S$ является правильным. Теорема доказана. Отметим, что для $1\leqslant n\leqslant 4$ равенство (8) и характеризация минимальных проекторов другими способами доказаны в [2] и [3]. Следствие 1. Справедливы соотношения $\sqrt{n}\leqslant \theta_n(B_n)\leqslant \sqrt{n+1}$ . При этом $\theta_n(B_n)=\sqrt{n}$ лишь в случае $n=1$, а равенство $\theta_n(B_n)=\sqrt{n+1}$ выполняется тогда и только тогда, когда $\sqrt{n+1}$ – целое число. Доказательство. Как показано в [2], указанным соотношениям удовлетворяет величина $\max\{\psi(a_n),\psi(a_n+1)\}$. Остается привлечь теорему 2. Заметим, что числа $k_n$ из доказательства теоремы 2 растут с ростом $n$, но не строго монотонно. Если $n\geqslant 2$, то $k_n\leqslant n/2$. Для примера приведем числа $k_n$ для $1\leqslant n\leqslant 15$, $n=50$, $n=100$ и $n=1000$ ([2]):
$$
\begin{equation*}
\begin{gathered} \, k_1=k_2=k_3=k_4=1, \qquad k_5=k_6=2, \qquad k_7=k_8=k_9=3, \qquad k_{10}=k_{11}=4, \\ k_{12}=k_{13}=5, \qquad k_{14}=k_{15}=6, \qquad k_{50}=22, \qquad k_{100}=45, \qquad k_{1000}=485. \end{gathered}
\end{equation*}
\notag
$$
В заключение автор выражает благодарность А. В. Акопяну за помощь при доказательстве теоремы 1. 
Цитирование в формате AMSBIB
\RBibitem{Nev23} |
|
||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|