\documentclass[12pt,draft,a4paper]{amsart}
\usepackage{amsmath,amsthm}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsfonts}
\usepackage{latexsym}
\tolerance 1900
\renewcommand*{\proofname}{Доказательство}
\DeclareMathOperator*{\cl}{cl}
\DeclareMathOperator*{\co}{co}
\DeclareMathOperator*{\spa}{span}
\DeclareMathOperator*{\aff}{aff}
\DeclareMathOperator*{\intt}{int}
\newcommand*{\Rn}{\mathbb R^n}
\newcommand*{\sj}{\sum_{j=1}^n}
\newcommand*{\sk}{\sum_{j=1}^k}
\newcommand*{\sm}{\sum_{j=1}^m}
\newcommand*{\wx}{\widehat x}
\newcommand*{\wa}{\widetilde a}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{proposition}{Предложение}
\newtheorem{corollary}{Следствие}
\begin{document}
\bigskip

\begin{center}\bf \Large Федеральное агентство по образованию
\smallskip
\large

Государственное образовательное учреждение высшего
профессионального образования
``МАТИ'' - Российский государственный технологический
университет\\
 им. К.Э.Циолковского


\vskip50pt
\rm
Кафедра "Высшая математика"


\vskip 70pt

\bf К.~Ю.~Осипенко

\vskip20pt

Теоремы отделимости в $\Rn$\\
и оптимальное восстановление


\vskip 270pt
Москва  2006 г.
\end{center}

\thispagestyle{empty}
\newpage


\section{Выпуклые множества}

Пусть $x,y\in\Rn$. {\it Отрезком $($соединяющим $x$ и $y)$} называется множество
$$[x,y]=\{\,z\in\Rn: z=(1-\alpha)x+\alpha y,\ 0\le\alpha\le1\,\}.$$
Непустое множество $A\subset\Rn$ называется {\it выпуклым}, если
вместе с любыми двумя своими точками $x$, $y$ оно содержит отрезок
$[x,y]$. Пустое множество считается выпуклым.

Пусть $x_1,\ldots,x_k\in\Rn$. Вектор
$$x=\sk\alpha_jx_j,$$
где
$$\sj\alpha_j=1,\quad\alpha_j\ge0,\ j=1,\ldots,k,$$
называется {\it выпуклой комбинацией\/} векторов $x_1,\ldots,x_k$.

\begin{proposition}
Непустое выпуклое множество $A\subset\Rn$ содержит все выпуклые комбинации векторов из $A$.
\end{proposition}

\begin{proof}
Будем доказывать это утверждение индукцией по числу слагаемых в
выпуклой комбинации. Для двух слагаемых утверждение очевидно.
Предположим, что утверждение доказано для $k$ слагаемых. Пусть
$x_1,\ldots,x_{k+1}\in A$ и
$$\sum_{j=1}^{k+1}\alpha_j=1,\quad\alpha_j\ge0,\ j=1,\ldots,k+1.$$
Имеем
$$x=\sum_{j=1}^{k+1}\alpha_jx_j=\alpha_1x_1+(1-\alpha_1)y,$$
где
$$y=\sum_{j=2}^{k+1}\frac{\alpha_j}{1-\alpha_1}x_j.$$
Поскольку
$$\sum_{j=2}^{k+1}\frac{\alpha_j}{1-\alpha_1}=1,$$
то по предположению индукции $y\in A$. Следовательно, $x\in A$.
\end{proof}

Из доказанного утверждения вытекает, что наименьшим выпуклым
множеством, содержащим произвольное непустое множество $A$, является
множество всех выпуклых комбинаций векторов из $A$. Это множество
называется {\it выпуклой оболочкой} $A$ и обозначается $\co A$.

\section{Аффинные многообразия}

Пусть $x_1,\ldots,x_k\in\Rn$. Вектор
$$x=\sk\alpha_jx_j,\quad\alpha_j\in\mathbb R,\ j=1,\ldots,k,$$
называется {\it линейной комбинацией\/} векторов $x_1,\ldots,x_k$. Множество всех линейных комбинаций векторов из $A\subset\Rn$ называется {\it линейной оболочкой} $A$ и обозначается через $\spa A$. Вектор
\begin{equation}\label{1}
x=\sk\alpha_jx_j,\quad\sk\alpha_j=1,\quad\alpha_j\in\mathbb R,\ j=1,\ldots,k,
\end{equation}
называется {\it аффинной комбинацией\/} векторов $x_1,\ldots,x_k$. Множество всех аффинных комбинаций векторов из $A\subset\Rn$ называется {\it аффинной оболочкой} $A$ и обозначается через $\aff A$.


{\it Аффинным многообразием\/} в $\Rn$ называется множество вида $x+L$, где $x\in\Rn$, а $L$ --- линейное подпространство $\Rn$. {\it Размерностью аффинного многообразия\/} называется размерность линейного подпространства $L$.

\begin{proposition}
Пусть $A\subset\Rn$. Тогда аффинная оболочка $A$ является аффинным многообразием, причем
$$\aff A=x_0+\spa(A-x_0),\quad x_0\in A.$$
\end{proposition}

\begin{proof}
Пусть $x\in\aff A$ имеет вид \eqref1. Тогда
$$x=x_0+\sum_{j=1}^k\alpha_j(x_j-x_0)\in x_0+\spa(A-x_0).$$

Обратно, пусть $x\in x_0+\spa(A-x_0)$. Тогда
$$x=x_0+\sum_{j=1}^k\lambda_j(x_j-x_0)=(1-\lambda_1-\ldots-\lambda_k)x_0+
\sum_{j=1}^k\lambda_jx_j,$$
что является аффинной комбинацией векторов $x_0,x_1,\ldots,x_k$.
\end{proof}

Если $A\subset\Rn$ --- выпуклое множество, то его размерностью называется размерность аффинной оболочки $A$
\begin{equation}\label{Dim}
\dim A=\dim\aff A=\dim\spa(A-x_0),
\end{equation}
где $x_0$ --- произвольный вектор из $A$.

Векторы $x_1,\ldots,x_{k+1}$ называются {\it аффинно независимыми}, если из того, что
\begin{equation}\label{11}
\sum_{j=1}^{k+1}\lambda_jx_j=0\quad\text{и}\quad\sum_{j=1}^{k+1}\lambda_j=0,
\end{equation}
следует, что $\lambda_1=\ldots=\lambda_{k+1}=0$.

\begin{proposition}\label{pr}
Векторы $x_1,\ldots,x_{k+1}$ аффинно независимы в том и только в том случае, если векторы $x_j-x_1$, $2\le j\le k+1$, --- линейно независимы.
\end{proposition}

\begin{proof}
Пусть $x_1,\ldots,x_{k+1}$ аффинно независимы и
\begin{equation}\label{12}
\sum_{j=2}^{k+1}\lambda_j(x_j-x_1)=0.
\end{equation}
Тогда
\begin{equation}\label{2}
\sum_{j=2}^{k+1}\lambda_jx_j-\biggl(\sum_{j=2}^{k+1}\lambda_j\biggr)x_1=0.
\end{equation}
Из аффинной независимости $x_1,\ldots,x_{k+1}$ вытекает, что $\lambda_2=
\ldots=\lambda_{k+1}=0$.

Пусть теперь векторы $x_j-x_1$, $2\le j\le k+1$, --- линейно независимы и выполняются условия \eqref{11}. Тогда имеет место равенство \eqref2, которое эквивалентно равенству \eqref{12}. Из линейной независимости векторов $x_j-x_1$, $2\le j\le k+1$, получаем, что $\lambda_2=
\ldots=\lambda_{k+1}=0$. Кроме того,
$$\lambda_1=-\sum_{j=2}^{k+1}\lambda_j=0.$$
\end{proof}

Выпуклая оболочка аффинно независимых векторов $x_1,\ldots,x_{k+1}$ называется {\it$k$-мерным симплексом}, а векторы $x_1,\ldots,x_{k+1}$ --- {\it вершинами симплекса}. Любой вектор из этого симплекса единственным образом представим в виде
$$x=\sum_{j=1}^{k+1}\lambda_jx_j,\quad\sum_{j=1}^{k+1}\lambda_j=1,\quad
\lambda_j\ge0,\ j=1,\ldots,k+1.$$
Числа $\lambda_1,\ldots,\lambda_{k+1}$ называются {барицентрическими координатами\/} вектора $x$.

Одномерные симплексы --- это отрезки, двумерные --- треугольники, трехмерные --- тетраэдры.

Если $A\subset\Rn$ --- выпуклое множество размерности $k\le n$, то оно содержит $k$-мерный симплекс. Действительно, в силу равенства \eqref{Dim} найдутся линейно независимые векторы $x_1-x_0,\ldots,x_k-x_0$, $x_0,x_1,\ldots,x_k\in A$. Тогда из предложения~\ref{pr} вытекает, что векторы $x_0,x_1,\ldots,x_k$ --- аффинно независимы. Следовательно, симплекс с вершинами в этих точках содержится в $A$.

\section{Внутренние точки}

Точка $a\in A\subset\Rn$ называется {\it внутренней точкой\/} множества $A$, если существует такая окрестность этой точки, что она целиком лежит в $A$. Множество внутренних точек $A$ обозначается через $\intt A$.

\begin{proposition}\label{P4}
Если $A\subset\Rn$ --- выпуклое множество размерности $n$, то $\intt A\ne\emptyset$.
\end{proposition}

\begin{proof}
Так как $A$ содержит $n$-мерный симплекс, достаточно доказать, что $n$-мерный симплекс в $\Rn$ содержит внутреннюю точку. Пусть $a_0,a_1,\ldots,a_n$ --- вершины $n$-мерного симплекса. Без ограничения общности можно считать, что $a_0=0$. Покажем, что любая точка вида
$$x=\sj\lambda_ja_j,\quad\sj\lambda_j<1,\quad\lambda_j>0,\ j=1,\ldots,n,$$
является внутренней. Пусть $x_0$ принадлежит открытому шару радиуса $\varepsilon>0$
$$B_\varepsilon(0)=\{\,y\in\Rn:|y|<\varepsilon\,\}.$$
Тогда
$$x_0=\sum_{k=1}^nx_ke_k,$$
где $e_k$ --- стандартный базис в $\Rn$, причем $|x_k|<\varepsilon$, $k=1,\ldots,n$. В силу того, что $a_1,\ldots,a_n$ --- линейно независимы, каждый из векторов стандартного базиса может быть представлен в виде
$$e_k=\sj\alpha_{jk}a_k,\quad k=1,\ldots,n.$$
Имеем
$$x+x_0=\sj\gamma_ja_j,$$
где
$$\gamma_j=\lambda_j+\sum_{k=1}^n\alpha_{jk}x_k,\quad j=1,\ldots,n.$$
В силу оценки
$$\biggl|\sum_{k=1}^n\alpha_{jk}x_k\biggr|\le\varepsilon\sum_{k=1}^n|\alpha_{jk}|$$
для достаточно малых $\varepsilon>0$ при всех $x_0\in B_\varepsilon(0)$ \ $\gamma_j>0$, $j=1,\ldots,n$, и
$$\sj\gamma_j<1.$$
тем самым все точки $x+x_0$ принадлежат симплексу.
\end{proof}

Обозначим через $\partial A$ --- граничные точки множества $A$. Через $\cl A$ будем обозначать замыкание множества $A$, т.е.\ множество всех предельных точек $A$.

\begin{proposition}\label{P5}
Пусть $A\subset\Rn$ --- выпуклое множество, $x\in\intt A$ и $\wx\in\partial A$. Тогда $\lambda(\wx-x)\notin\cl A$ для всех $\lambda>1$.
\end{proposition}

\begin{proof}
Без ограничения общности можно считать, что внутренняя точка множества $A$ совпадает с началом координат, т.е., что $x=0$. Это означает, что существует такое число $r>0$, что все точки, для которых $|a|<r$, принадлежат $A$. Предположим противное, т.е., что $\lambda\wx\in\cl A$ при некотором $\lambda>1$. Тогда в любой окрестности точки $\lambda\wx$ должна найтись точка из $A$. Пусть $\xi\in A$ и
$$|\lambda\wx-\xi|<(\lambda-1)\frac r2.$$
Докажем, что любая точка из окрестности точки $\wx$ радиуса $(\lambda-1)\lambda^{-1}r/2$ лежит в $A$ (тем самым $\wx$ не является граничной точкой). Пусть $y$ --- произвольная точка, для которой
$$|y-\wx|<\frac{\lambda-1}\lambda\frac r2.$$
Положим
$$a_0=\frac\lambda{\lambda-1}y-\frac1{\lambda-1}\xi.$$
Имеем
$$|a_0|\le\frac\lambda{\lambda-1}|y-\wx|+\frac1{\lambda-1}|\lambda\wx-\xi|<r,$$
Поэтому $a_0\in A$. С другой стороны,
$$y=(1-\lambda^{-1})a_0+\lambda^{-1}\xi\in A.$$
\end{proof}


\section{Теоремы отделимости}

Пусть $x'=(x_1',\ldots,x_n')\in\Rn$ и $x=(x_1,\ldots,x_n)\in\Rn$. Через $x'\cdot x$ будем обозначать стандартное скалярное произведение в $\Rn$
$$x'\cdot x=\sj x_j'x_j.$$

{\it Гиперплоскостью\/} $H$ в $\Rn$ называется множество точек $x\in\Rn$, для которых $x'\cdot x=\gamma$, где $x'\in\Rn$, $x'\ne0$, а $\gamma\in\mathbb R$. Каждая гиперплоскость $H$ порождает два полупространства
$$H_+=\{\,x\in\Rn:x'\cdot x\ge\gamma\,\},\quad H_-=\{\,x\in\Rn:x'\cdot x\le\gamma\,\}.$$

Говорят, что точка $b\in\Rn$ {\it отделима\/} от множества $A\subset\Rn$, если существует такая гиперплоскость $H$, что $b$ и $A$ лежат в разных полупространствах. Иными словами, точка $b$ отделима от $A$, если существует такой элемент $x'\in\Rn$, $x'\ne0$, что при всех $a\in A$
$$x'\cdot a\le x'\cdot b.$$

\begin{figure}[h]
$$\begin{picture}(300,95)
\put(140,70){\circle*{2}}
\put(140,80){$b$}
\put(80,25){\line(2,1){130}}
\qbezier(105,15)(105,30)(145,45)
\qbezier(145,45)(185,60)(185,40)
\qbezier(105,15)(105,0)(121,6)
\qbezier(121,6)(185,30)(185,40)
\put(186,86){$H$}
\put(140,30){$A$}
\end{picture}$$
\caption{}
\end{figure}


\begin{theorem}\label{T1}
Пусть $A$ --- выпуклое множество и $b\notin\cl A$. Тогда точка $b$ отделима от $A$.
\end{theorem}

\begin{proof}
Положим
$$B_r(b)=\{\,x\in\Rn:|x-b|\le r\,\}.$$
Существует $r$, при котором $A_1=\cl A\cap B_r(b)\ne\emptyset$. Функция $f(x)=|x-b|$ является непрерывной на ограниченном замкнутом множестве $A_1$ и, следовательно, по теореме Вейерштрасса достигает своего минимума в некоторой точке $\wx$. Иными словами, точка $\wx$ --- ближайшая к $b$ из множества $A_1$, а значит и из множества $\cl A$. Положим $x'=\wx-b$ и рассмотрим гиперплоскость $x'\cdot x=x'\cdot\wx$. Докажем, что эта гиперплоскость отделяет $b$ от $A$. Имеем
$$x'\cdot b=x'\cdot(\wx-x')=x'\cdot\wx-|x'|^2<x'\cdot\wx.$$
Остается доказать, что $x'\cdot a\ge x'\cdot\wx$ для всех $a\in A$. Предположим, что нашлась точка $a_0\in A$, для которой $x'\cdot a_0<x'\cdot\wx$. Так как $\cl A$ --- тоже выпуклое множество, $(1-t)\wx+ta_0\in\cl A$ при всех $t\in[0,1]$. Имеем
$$|(1-t)\wx+ta_0-b|^2=|x'+t(a_0-\wx)|^2=|x'|^2+2t\alpha+t^2|a_0-\wx|^2,$$
где $\alpha=x'\cdot(a_0-\wx)<0$. Поэтому при достаточно малых $t$
$$|(1-t)\wx+ta_0-b|^2<|x'|^2=|\wx-b|^2,$$
что противоречит тому, что $\wx$ --- ближайшая точка к $b$ из точек множества $\cl A$.
\end{proof}

\begin{lemma}\label{L}
Если $A\subset\Rn$ --- выпуклое множество и $\dim A<n$, то существует гиперплоскость $H$ такая, что $A\subset H$.
\end{lemma}

\begin{proof}
Пусть $\aff A=x_0+\spa(x_1,\ldots,x_k)$, $k<n$. Тогда существует $x'\in\Rn$ такой, что $x'\ne0$ и $x'\cdot x_j=0$, $j=1,\ldots,k$. Гиперплоскость $x'\cdot x=x'\cdot x_0$ содержит множество $A$.
\end{proof}

\begin{theorem}\label{T2}
Пусть $A$ --- выпуклое множество и $b\in\partial A$. Тогда точка $b$ отделима от $A$.
\end{theorem}

\begin{proof}
Если $\dim A<n$, то по лемме~\ref{L} существует гиперплоскость $x'\cdot x=\gamma$, содержащая $A$. Очевидно, что $x'\cdot b=\gamma$. Поэтому эта гиперплоскость отделяет $b$ от $A$.

Предположим , что $\dim A=n$. Тогда по предложению~\ref{P4} у $A$ есть внутренняя точка, а из предложения~\ref{P4} следует, что существует последовательность точек $b_k\notin\cl A$ такая, что $b_k\to b$ при $k\to\infty$ (достаточно положить $b_k=(1+1/k)(b-x_0)$, $k=1,2,\ldots$, где $x_0$ --- внутренняя точка $A$). Из теоремы~\ref{T1} вытекает, что точки $b_k$ можно отделить от $A$, т.е. существуют $x_k'\in\Rn$, $x_k'\ne0$, $k=1,2,\ldots$, такие, что для всех $a\in A$
\begin{equation}\label{aa}
x_k'\cdot a\le x_k'\cdot b_k.
\end{equation}
Разделив на $|x_k'|$, можно считать, что $|x_k'|=1$. Поскольку сфера
$$\mathbb S^{n-1}=\{\,y\in\Rn:|y|=1\,\}$$
ограничена и замкнута, найдется подпоследовательность $x'_{k_s}\to x'$ при $s\to\infty$, причем $|x'|=1$ (т.е. $x'\ne0$). Переходя к пределу по этой подпоследовательности в неравенстве \eqref{aa}, получим
$$x'\cdot a\le x'\cdot b$$
для всех $a\in A$.
\end{proof}

Множество $A\subset\Rn$ называется {\it центрально-симметричным}, если из того, что $x\in A$, следует, что $-x\in A$.

\begin{theorem}\label{T3}
Пусть $A$ --- выпуклое центрально симметричное множество из $\mathbb R^{n+1}$ и
\begin{equation}\label{B}
b=\sup_{(0,\ldots,0,a_{n+1})\in A}a_{n+1}<\infty.
\end{equation}
Тогда существуют такие числа $\alpha_1,\ldots,\alpha_n\in\mathbb R$, что для всех $(a_1,\ldots,a_{n+1})\in A$ имеет место неравенство
\begin{equation}\label{AA}
\alpha_1a_1+\ldots+\alpha_na_n+a_{n+1}\le b.
\end{equation}
\end{theorem}

\begin{figure}[h]
$$\begin{picture}(300,160)

\qbezier(90,30)(90,70)(150,110)
\qbezier(150,110)(210,150)(210,110)
\qbezier(150,30)(210,70)(210,110)
\qbezier(90,30)(90,-10)(150,30)
\put(180,110){$A$}
\put(154,104){$b$}
\put(80,70){\vector(1,0){150}}
\put(150,0){\vector(0,1){150}}
\put(220,60){$a_1$}
\put(122,144){$a_{n+1}$}
\put(150,70){\circle*{2}}
\put(150,110){\circle*{2}}
\put(60,50){\line(3,2){162}}
\put(152,60){$O$}
\end{picture}$$
\caption{}
\end{figure}

\begin{proof}
Будем доказывать эту теорему индукцией по $n$. Пусть сначала $n=1$. Так как точка $(0,b)\in\partial A$, то по теореме~\ref{T2} существует гиперплоскость (прямая), отделяющая эту точку от множества $A$, т.е.\ существует вектор $(x_1',x_2')\ne0$ такой, что
\begin{equation}\label{a1}
x_1'a_1+x_2'a_2\le x_2'b
\end{equation}
для всех $(a_1,a_2)\in A$. Если $x_2'>0$, то разделив на $x_2'$, мы придем к виду \eqref{AA}. Если $x_2'<0$, то разделив на $x_2'$, мы придем к виду
\begin{equation}\label{a2}
\alpha_1a_1+a_2\ge b.
\end{equation}
Поскольку $(0,0)\in A$, то из этого неравенства следует, что $b\le0$. Тем самым (см.\ \eqref{B}) $b=0$. Подставив в \eqref{a2} вместо $(a_1,a_2)$ точку $(-a_1,-a_2)$ и умножив полученное неравенство на $-1$, придем к виду $$-\alpha_1a_1+a_2\le0,$$
что соответствует \eqref{AA} при $b=0$. Предположим теперь, что $x_2'=0$. Тогда из \eqref{a1} вытекает, что
$$x_1'a_1\le0.$$
В силу центральной симметрии множества $A$ это означает, что $a_1=0$ для точек $(a_1,a_2)\in A$. Следовательно, неравенство \eqref{AA} выполнено для любого $\alpha_1$.

Пусть утверждение теоремы доказано для всех $k\le n-1$. Докажем его для $k=n$. Поскольку точка $(0,\ldots,0,b)\in\partial A$, по теореме~\ref{T2} найдется вектор $x'=(x_1',\ldots,x_{n+1}')\ne0$ такой, что для всех $a\in A$
\begin{equation}\label{a3}
x'\cdot a\le x_{n+1}'b.
\end{equation}
Если $x_{n+1}'\ne0$, то рассуждения, аналогичные проведенным для $n=2$, сразу приводят к неравенству \eqref{AA}. Предположим, что $x_{n+1}'=0$. Тогда из неравенства \eqref{a3} с учетом центральной симметрии следует, что множество $A$ лежит в подпространстве $x'\cdot x=0$. Выберем в этом подпространстве ортонормированный базис $f_1,\ldots,f_n$, взяв в качестве $f_n=e_{n+1}=(0,\ldots,0,1)$ (в силу того, что $x_{n+1}'=0$, $e_{n+1}$ принадлежит этому подпространству). Из предположения индукции следует, что в этом подпространстве (размерность которого $n-1$) найдутся $\alpha_1,\ldots,\alpha_{n-1}\in\mathbb R$ такие, что для точек $\wa_1f_1+\ldots+\wa_nf_n\in A$ имеет место неравенство
$$\alpha_1\wa_1+\ldots+\alpha_{n-1}\wa_{n-1}+\wa_n\le b.$$
Выразив координаты $\wa_1,\ldots,\wa_n$ через координаты $a_1,\ldots,a_{n+1}$, учитывая, что $\wa_n=a_{n+1}$, а $\wa_j$, $j=1,\ldots,n-1$, линейно выражаются через $a_1,\ldots,a_n$, приходим к виду \eqref{AA}.
\end{proof}

\section{Оптимальное восстановление линейного функционала}

Пусть $X$ --- линейное пространство, $W\subset X$, $L,l_1,\ldots,l_n$ --- линейные функционалы на $X$. Ставится задача восстановления функционала $L$ на множестве $W$ по значениям функционалов $l_1,\ldots,l_n$, заданным с некоторой погрешностью. Будем считать, что для каждого $x\in W$ известен вектор $y=(y_1,\ldots,y_n)$ такой, что
$$\|Ix-y\|\le\delta,$$
где $Ix=(l_1x,\ldots,l_nx)$, $\|\cdot\|$ --- некоторая норма в $\Rn$, а $\delta>0$ --- погрешность задания исходных данных.

В качестве {\it методов восстановления\/} рассматриваются всевозможные отображения $\varphi\colon\Rn\to\mathbb R$. Для данного метода $\varphi$ его {\it погрешностью\/} называется величина
$$e(W,L,I,\delta,\varphi)=\sup_{\substack{x\in W,\ y\in\Rn\\\|Ix-y\|\le\delta}}|Lx-\varphi(y)|.$$
{\it Погрешностью оптимального восстановления\/} называется величина
$$E(W,L,I,\delta)=\inf_{\varphi\colon\Rn\to\mathbb R}e(W,L,I,\delta,\varphi),$$
а метод, на котором достигается нижняя грань называется {\it оптимальным методом восстановления}.

\begin{theorem}
Пусть $W$ --- выпуклое центрально-симметричное множество. Тогда
\begin{equation}\label{Sm}
E(W,L,I,\delta)=\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|,
\end{equation}
а среди оптимальных методов восстановления существует линейный, т.е. метод вида
$$\varphi(y)=\sj c_jy_j.$$
\end{theorem}

\begin{proof}
1. Оценка снизу. Пусть $\varphi\colon\Rn\to\mathbb R$ --- произвольный метод восстановления. Для всех $x\in W$ таких, что $\|Ix\|\le\delta$, имеем
\begin{multline*}
2|Lx|=|Lx-\varphi(0)-(L(-x)-\varphi(0)|\\
\le|Lx-\varphi(0)|+|(L(-x)-\varphi
(0)|\le2e(W,L,I,\delta,\varphi).
\end{multline*}
Отсюда
$$e(W,L,I,\delta,\varphi)\ge\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|.$$
Следовательно,
$$E(W,L,I,\delta)\ge\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|.$$

2. Оценка сверху. Рассмотрим в $\mathbb R^{n+1}$ множество точек
\begin{multline*}
A=\{\,(y_1,\ldots,y_{n+1}):\|Ix-y\|\le\delta.\ y_{n+1}=Lx,\\
x\in W,\ y=(y_1,\ldots,y_n)\,\}.
\end{multline*}
Легко убедиться, что $A$ --- выпуклое центрально-симметричное множество. Положим
$$b=\sup_{(0,\ldots,0,y_{n+1})\in A}y_{n+1}=\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|.$$
Из теоремы~\ref{T3} следует, что существуют такие числа $\alpha_1,\ldots,\alpha_n\in\mathbb R$, что для всех $(y_1,\ldots,y_{n+1})\in A$ имеет место неравенство
\begin{equation}\label{RA}
\alpha_1y_1+\ldots+\alpha_ny_n+y_{n+1}\le b.
\end{equation}
Так как $(-y_1,\ldots,-y_{n+1})\in A$, то имеет место также неравенство
\begin{equation}\label{RB}
-\alpha_1y_1-\ldots-\alpha_ny_n-y_{n+1}\le b.
\end{equation}
Из \eqref{RA} и \eqref{RB} следует, что
$$|y_{n+1}+\alpha_1y_1+\ldots+\alpha_ny_n|\le b$$
для всех $(y_1,\ldots,y_{n+1})\in A$. Это означает, что для всех $x\in W$ и $y\in\Rn$ таких, что $\|Ix-y\|\le\delta$ справедливо неравенство
$$|Lx-\varphi(y)\|\le b,$$
где
$$\varphi(y)=-\alpha_1y_1-\ldots-\alpha_ny_n.$$
Тем самым
$$E(W,L,I,\delta)\le e(W,L,I,\delta,\varphi)\le b,$$
что доказывает равенство \eqref{Sm} и оптимальность метода $\varphi$.
\end{proof}
\end{document}
