\documentclass[12pt,draft]{amsart}
\usepackage{amsmath,amsthm}
%\usepackage[T2A]{fontenc}
%\usepackage[cp1251]{inputenc}
%\usepackage[english,russian]{babel}
\usepackage{amsfonts}
\usepackage{latexsym}
%\documentclass[12pt,draft,a4paper]{amsart}
%\usepackage{amsmath,amsthm,russcorr}
%\usepackage{srctex}
\tolerance 1800
%\renewcommand{\thesubsection}{\arabic{subsection}}
%\renewcommand*{\proofname}{��������������}
%\newtheorem{lemma}{�����}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newcommand*{\Hn}{H^2(\Bn)}
\newcommand*{\Bn}{\mathbb B^n}
\newcommand*{\Ls}{L_2(\sigma)}
\newcommand*{\Sn}{\mathbb S^{n-1}}
\newcommand*{\wm}{\widehat\varphi}
\newcommand*{\wl}{\lambda}
\newcommand*{\lt}{L_2(\mathbb T)}
\newcommand*{\ld}{L_2(\mathbb R^d)}
\newcommand*{\li}{L_\infty(\mathbb R)}
\newcommand*{\lis}{L_\infty(\Ds)}
\newcommand*{\Ds}{\Delta_\sigma}
\newcommand*{\Ld}{L_2(\Ds)}
\DeclareMathOperator*{\infp}{inf\vphantom p}
\DeclareMathOperator*{\co}{co}
\DeclareMathOperator*{\bco}{bco}
\DeclareMathOperator*{\sign}{sign}
\DeclareMathOperator*{\card}{card}
\DeclareMathOperator*{\grad}{grad}
\DeclareMathOperator*{\vraisup}{ess\,sup}
\DeclareMathOperator*{\gr}{gr}

\newcommand*{\Wrt}{W_2^r(\mathbb T)}

\newcommand*{\ws}{\widehat\sigma}
\newcommand*{\wa}{\widehat\alpha}
\newcommand*{\cp}{\mathcal P}
\newcommand*{\cm}{\mathcal M}

\newcommand*{\wmu}{\widehat\mu}
\newcommand*{\wh}{\widehat h}
\newcommand*{\wt}{\widehat\tau}
\newcommand*{\wx}{\widehat x}
\newcommand*{\wf}{\widehat x}
\newcommand*{\ci}{\mathcal I}
\newcommand*{\wy}{\widehat y}
\newcommand*{\Wi}{W_\infty^1}
\newcommand*{\bt}{\bar t}
\newcommand*{\It}{I_{\bt}}
\newcommand*{\ta}{\widetilde a}
\newcommand*{\wA}{\widetilde A}
\newcommand*{\tb}{\widetilde b}
\newcommand*{\WR}{\mathcal W_2^r(\mathbb T)}
\newcommand*{\Wt}{W_2^n(\mathbb T)}
\newcommand*{\lT}{L_2(\mathbb T)}
\newcommand*{\la}{\langle}
\newcommand*{\ra}{\rangle}

\newcommand*{\iR}{\int_{\mathbb R}}
%\newcommand*{\wmu}{\widehat\mu}
%\newcommand*{\Lia}{L_\infty(\mathbb R_+)}
%\newcommand*{\Li}{L_\infty(\mathbb R)}
\newcommand*{\WP}{\mathcal W_r^n(T)}
\newcommand*{\FF}{\mathcal F_{rp}^n}
\newcommand*{\wu}{\widehat u}
\newcommand*{\yj}{Y_j^{(k)}}
\newcommand*{\tx}{\tilde x}
\newcommand*{\Bs}{B_\sigma(\mathbb R^d)}
\newcommand*{\Bsp}{B_\sigma(\mathbb R^d)^\perp}
\newcommand*{\Ws}{W_{2,\sigma'}^r}
\newcommand*{\lf}{L_2^\psi(\mathbb R^d)}
\newcommand*{\id}{\int_{\mathbb R^d}}
\newcommand*{\mL}{\mathcal L}
%\newcommand*{\lt}{L_2(\mathbb R)}
\newcommand*{\zs}{Z_{skj}}
\newcommand*{\Wr}{W_\infty^r([-1,1])}
\newcommand*{\cd}{(\cdot)}
\newcommand*{\sjn}{\sum_{j=1}^n}
\newcommand*{\Lia}{L_\infty(\mathbb R_+)}
\newcommand*{\Li}{L_\infty(\mathbb R)}
\newcommand*{\ha}{\widehat a}
\newcommand*{\hb}{\widehat b}
\newcommand*{\lN}{l_2^{2N+1}}


\begin{document}
\title{Optimal Recovery of Linear Functionals and Operators}
\author{K.~Yu.~Osipenko}
\thanks{This research was carried out with the financial support of the Russian Foundation for Basic Research (grant nos.\ 14-01-00456, 14-01-00744).}
\address{Moscow Aviation Institute (National Research University)}
\address{Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow}
\maketitle

\section{Introduction}

In this paper we give a short history of optimal recovery problems and some general results. There are several surveys and monographs devoted to the theory of optimal recovery \cite{MR}--\cite{MT}. Here we try to pay special attention to the construction of optimal recovery methods.

One of the first example of optimal recovery problem is the problem of the best quadrature. Let $W$ be some class of functions integrable on the interval $[a,b]$. The problem is to find
$$Lf=\int_a^bf(x)\,dx,$$
knowing the information about function values at the system of knots $a\le x_1<\ldots<x_n\le b$. Thus, using the vector
$$If=(f(x_1),\ldots,f(x_n))$$
we have to give an approximate value of $Lf$. Any linear method of approximation
$$\varphi(If)=\sum_{j=1}^np_jf(x_j)$$
is called quadrature formula.

The quadrature formula
$$\widehat\varphi(If)=\sum_{j=1}^n\widehat p_jf(x_j)$$
is called the best quadrature formula if
\begin{equation}\label{Q}
\sup_{f\in W}|Lf-\widehat\varphi(If)|=\infp_{p_1,\ldots,p_n\in\mathbb R}
\sup_{f\in W}\biggl|Lf-\sum_{j=1}^np_jf(x_j)\biggr|.
\end{equation}

The first setting of such problems were given by A.~Sard \cite{S} and S.~M.~Nikolskii \cite{N}. The development of these problems may be found in \cite{N1}.

S.~A.~Smolyak \cite{Sm} considered the following generalization of \eqref{Q}. Let $X$ be a linear space and $L$ be a linear functional on $X$. Put
$$Ix=(l_1x,\ldots,l_nx),\quad x\in X,$$
where $l_j$, $j=1,\ldots,n$, are linear functionals on $X$.
For $W\subset X$ we consider the problem of optimal recovery of $L$ on $W$ by the information operator $I$. Any method of recovery is a mapping $\varphi\colon\mathbb R^n\to\mathbb R$. For a given method $\varphi$ we define the error of this method by
$$e(L,W,I,\varphi)=\sup_{x\in W}\left|Lx-\varphi(Ix)\right|.$$
We want to find the optimal error of recovery
$$E(L,W,I)=\infp_{\varphi\colon\mathbb R^n\to\mathbb R}e(L,W,I,\varphi)$$
and an optimal method $\widehat\varphi$ for which
$$e(L,W,I,\widehat\varphi)=E(L,W,I).$$

\begin{theorem}[\cite{Sm}]
If $W$ is a convex and centrally-symmetric set, then among all optimal methods there exists a linear optimal method and
\begin{equation}\label{du}
E(L,W,I)=\sup_{\substack{x\in W\\Ix=0}}|Lx|.
\end{equation}
\end{theorem}

Thus, if $W$ is a convex and centrally-symmetric set, then there exist $\widehat p_1,\ldots,\widehat p_n$ such that the method
$$\widehat\varphi(Ix)=\sum_{j=1}^n\widehat p_jl_jx$$
is optimal method of recovery.

Any element $x_0\in W$ for which $Ix_0=0$ and
$$|Lx_0|=\sup_{\substack{x\in W\\Ix=0}}|Lx|$$
we call {\it extremal}. The problem of finding an extremal element often
turns out more simple than the problem of finding an optimal recovery
method.

Let us consider a simple example. Let $\mathcal H_\infty^\mathbb R$ be the space of functions analytic in the unit disk
$$D:=\{\,z\in\mathbb C:|z|<1\,\},$$
bounded, and real in the interval $(-1,1)$. As the set $W$ we consider $H_\infty^\mathbb R$ which is the set of functions from $\mathcal H_\infty^\mathbb R$ satisfying the condition
$$\sup_{z\in D}|f(z)|\le1.$$

For the problem of optimal recovery of functions from $H_\infty^\mathbb R$
at the point $\tau\in(-1,1)$ by their values at zero the dual problem \eqref{du} may be solved immediately using the Schwarz lemma:
$$\sup_{\substack{f\in H_\infty^\mathbb R\\f(0)=0}}|f(\tau)|=|\tau|.$$
Thus the function $f_0(z)=z$ is extremal for the considered problem. However the problem of finding an optimal method of recovery is not so evident.

\section{Method of parametrization}

In \cite{Os} we offer an approach allowing to
obtain an optimal method of recovery using some parametrization of extremal element.

\begin{theorem}[\cite{Os}]\label2
Let $X$ be a real linear space, $W$ a convex centrally symmetric set from
$X$, and $x_0$ an extremal element in the problem of optimal recovery of
a linear functional $L$ on the set $W$ by the values of linear functionals
$l_1x,\ldots,l_nx$. Assume that for all $M=(t_1,\ldots,t_n)\in\mathbb R
^n$ from some neighborhood of $M_0\in\mathbb R^n$ there exist $x(M)\in W$ such that $x(M_0)=x_0$. Then if the functions $\omega(M)=Lx(M)$, $\omega_j(M)=l_jx(M)$, $j=1,\ldots,n$, have continuous partial derivatives with respect to all variables in a neighborhood of $M_0$ and the determinant of the matrix
$$J(M)=\begin{pmatrix}
\dfrac{\partial\omega_1}{\partial t_1}&\ldots&\dfrac{\partial\omega_n}{
\partial t_1}\\
\hdotsfor{3}\\
\dfrac{\partial\omega_1}{\partial t_n}&\ldots&\dfrac{\partial\omega_n
}{\partial t_n}
\end{pmatrix}$$
does not vanish at $M_0$, then the method
\begin{equation}\label{opt}
\wm(Ix)=\sum_{j=1}^nC_jl_jx,
\end{equation}
where $C_1,\ldots,C_n$ are solutions of the system
$$J(M_0)\begin{pmatrix}
C_1\\
\vdots\\
C_n\end{pmatrix}=\begin{pmatrix}
\dfrac{\partial\omega}{\partial t_1}(M_0)\\
\vdots\\
\dfrac{\partial\omega}{\partial t_n}(M_0)\end{pmatrix},$$
is the unique linear optimal method of recovery.
\end{theorem}

It is sometimes convenient to use another form of optimal method of recovery.

\begin{corollary}\label{C1}
Let conditions of Theorem~$\ref2$ are fulfielled. Then the unique linear optimal method of recovery is
$$\wm(Ix)=\sum_{j=1}^ny_j\dfrac{\partial\omega}{\partial t_j}(M_0),$$
where $y_1,\ldots,y_n$ are the solutions of the system
\begin{equation}\label{s}
\sum_{j=1}^ny_j\dfrac{\partial\omega_k}{\partial t_j}(M_0)=l_kx,\quad k=1,\ldots,n.
\end{equation}
\end{corollary}

\begin{proof}
For
$$a=\begin{pmatrix}
a_1\\
\vdots\\
a_n\end{pmatrix},\quad b=\begin{pmatrix}
b_1\\
\vdots\\
b_n\end{pmatrix}$$
put
$$(a,b)=\sum_{j=1}^na_jb_j.$$
Set
$$\widehat\omega=\begin{pmatrix}
\dfrac{\partial\omega}{\partial t_1}(M_0)\\
\vdots\\
\dfrac{\partial\omega}{\partial t_n}(M_0)\end{pmatrix},\quad z=\begin{pmatrix}
l_1x\\
\vdots\\
l_nx\end{pmatrix}.$$
Then optimal method \eqref{opt} has the form
$$\wm(Ix)=(J^{-1}(M_0)\widehat\omega,z)=(\widehat\omega,(J^T(M_0))^{-1}z).$$
Put $y=(J^T(M_0))^{-1}z$. Then the coordinates of $y=(y_1,\ldots,y_n)^T$ satisfy system \eqref{s}.
\end{proof}

Now let us construct the optimal recovery method of functions from $H_\infty^\mathbb R$
at the point $\tau\in(-1,1)$ by their values at zero. Put
$$f_1(z,t)=\frac{z+t}{1+tz}.$$
It is easy to see that $f_1(z,t)\in H_\infty^\mathbb R$ for all $t\in(-1,1)$. Moreover, $f_1(z,0)=f_0(z)=z$ and $f_1(0,t)=t$.

Thus, here $M=t\in\mathbb R$, $M_0=0$, $x(t)=f_1(z,t)$, $\omega(t)=f_1(\tau,t)$, $\omega_1(t)=f_1(0,t)=t$.

From Corollary~\ref{C1} we obtain that the unique linear optimal method of recovery has the form $\wm(f(0))=y_1\varphi'(0)$, where $y_1$ satisfies the equality $y_1\omega_1'(0)=f(0)$. Consequently, it has the form
$$\wm(f(0))=\left(\frac{\partial f_1}{\partial t}(0,0)\right)^{-1}\frac{
\partial f_1}{\partial t}(\tau,0)f(0)=(1-\tau^2)f(0).$$
More general results concerning the considered problem may be found in
\cite{Os1} and \cite{FM} (they also can be obtained by the proposed method).

\section{Optimal interpolation of smooth functions}

Denote by $\Wr$, $r\in\mathbb N$, the Sobolev class of functions $x(t)$, $t\in[-1,1]$, for which $x^{(r-1)}$ is absolutely continuous on $[-1,1]$ and
$$\vraisup_{t\in[-1,1]}|x^{(r)}(t)|\le1.$$
Let
\begin{equation}\label{us}
\begin{gathered}
-1\le t_1<\ldots<t_n\le1,\quad\nu_j\in\mathbb N,\quad1
\le\nu_j\le r,\quad j=1,\ldots,n,\\
m=\nu_1+\ldots+\nu_n\ge r.
\end{gathered}
\end{equation}
Assume that for any $x\in\Wr$ we know
\begin{equation}\label{3In}
Fx=(x(t_1),\ldots,x^{(\nu_1-1)}(t_1),\ldots,x(t_n),\ldots,x^{
(\nu_n-1)}(t_n)).
\end{equation}

Consider the problem of optimal recovery of $x(\tau)$, $\tau\in[-1,1]$, $x\in\Wr$, by the information $Fx$. In other words, we would like to interpolate a function $x\in\Wr$ at the point $\tau$ using values of $x$ and its derivatives at some system of points $t_1,\ldots,t_n$. In this case we put
$$E(\tau,\Wr,F)=\infp_{\varphi\colon\mathbb R^N\to\mathbb R}\,\sup_{x\in\Wr}|x(\tau)-
\varphi(Fx)|.$$

To obtain the solution of this optimal recovery problem we recall some definitions and results about splines.

A perfect spline of degree $r\in\mathbb N$ with knots $s_1<\ldots<s_N$ is a function of the form
$$s(t)=p_{r-1}(t)+\frac\alpha{r!}\biggl(t^r+2\sum_{j=1}^N(-1)^j
(t-s_j)^r_+\biggr),$$
where $p_{r-1}$ is a polynomial of degree $r-1$, $\alpha=-1$ or $\alpha=1$, and
$$t_+=\begin{cases}t,&t\ge0,\\
0,&t<0.\end{cases}$$

A polynomial spline of degree $r-1$, $r\in\mathbb N$, with $N$ knots $s_1<\ldots<s_N$ is a function of the form
$$S(t)=\sum_{j=0}^{r-1}a_jt^j+\sum_{j=1}^Nb_j(t-s_j)_+^{r-1}.$$

Suppose that conditions \eqref{us} are fulfilled. Then, it is known (see, for example, \cite{Ko}) that there exists a perfect spline $s$ of degree $r$ with $m-r$ knots
\begin{equation}\label{kn}
-1<s_1<\ldots<s_{m-r}<1
\end{equation}
such that
$$s^{(\nu)}(t_j)=0,\quad\nu=0,1,\ldots,\nu_j-1,\quad j=1,\ldots,n.$$
Moreover, for any $x_{j\nu}$, $\nu=0,1,\ldots,\nu_j-1$, $j=1,\ldots,n$, there exists the unique polynomial spline $S$ of order $r-1$ with knots \eqref{kn} for which
$$S^{(\nu)}(t_j)=x_{j\nu},\quad \nu=0,1,\ldots,\nu_j-1,\quad j=1,\ldots,n.$$



\begin{theorem}[\cite{MRW},\cite{GP}]\label{3_1}
Assume that conditions \eqref{us} are fulfilled and $s_1<\ldots<s
_{m-r}$ are the knots of a perfect spline $s$ such that
$$s^{(\nu)}(t_j)=0,\quad \nu=0,1,\ldots,\nu_j-1,\quad j=1,\ldots,n.$$
Then for any $\tau\in[-1,1]$
\begin{equation}\label{31}
E(\tau,\Wr,F)=|s(\tau)|,
\end{equation}
and the unique linear optimal recovery method is the polynomial spline
$S$ of order $r-1$ with knots $s_1,\ldots,s_{m-r}$ satisfying conditions
\begin{equation}\label{3int}
S^{(\nu)}(t_j)=x^{(\nu)}(t_j),\quad \nu=0,1,\ldots,\nu_j-1,\quad j=1,
\ldots,n.
\end{equation}
\end{theorem}

We give a simple proof of this theorem using the method of parametrization which was described in the previous section. Moreover, using this method we can prove the uniqueness of linear optimal method (which was not done in \cite{MRW} and \cite{GP}).

\begin{proof}
It follows from \eqref{du} that
$$E(\tau,\Wr,F)=\sup_{\substack{x\in\Wr\\Fx=0}}|x(\tau)|.$$
Assume that there exists $\wx\in\Wr$ such that $F\wx=0$ and $|\wx(\tau)|>|s(\tau)|$.
Put
$$y=s-\rho\wx,\quad\rho=\frac{s(\tau)}{\wx(\tau)}.$$
Then $y$ has $m+1$ zeros with multiplicities and consequently $y^{(r)}$ has at least $m-r+1$ sign changes. On the other hand, taking into account that $|\rho|<1$ on every interval $(-1,s_1),(s_1,s_2),\ldots,(s_{m-r},1)$ the function $y^{(r)}$ has the same sign as $s^{(r)}\cd$. Thus, $y^{(r)}$ has exactly $m-r$ sign changes. The obtained contradiction proves \eqref{31}.

Assume that the perfect spline $s$ has the form
$$s(t)=\sum_{j=0}^{r-1}a_jt^j+\frac\alpha{r!}\biggl(t^r+2\sum_{j=1}^{m-r}(-
1)^j(t-s_j)_+^r\biggr).$$
For points $M=(b_0,\ldots,b_{r-1},u_1,\ldots,u_{m-r})\in\mathbb R^m$
sufficiently close to the point $M_0=(a_0,\ldots,a_{r-1},s_1,\ldots,s_{m-r})\in
\mathbb R^m$ consider functions
$$s_M(t)=\sum_{j=0}^{r-1}b_jt^j+\frac\alpha{r!}\biggl(t^r+2\sum_{j=1}^{m-r}
(-1)^j(t-u_j)_+^r\biggr).$$
It is clear that $s_M\in\Wr$ for all $M$ from sufficiently small neiborhood of
$M_0$. Moreover, $s_{M_0}=s$. We have
\begin{align*}
\frac{\partial s_M(t)}{\partial b_j}_{\big|M_0}&=t^j,\quad j=0,\ldots,r-1,
\\
\frac{\partial s_M(t)}{\partial u_j}_{\big|M_0}&=\frac{2\alpha(-1)^{j+1}}{(
r-1)!}(t-s_j)^{r-1}_+,\quad j=1,\ldots,m-r.
\end{align*}
Putting
$$S(t)=\sum_{j=0}^{r-1}y_jt^j+\sum_{j=1}^{m-r}y_j(t-s_j)_+^{r-1},$$
we obtain that system \eqref{s} has the same form as \eqref{3int}. Thus, by Corollary~\ref{C1} the value of interpolation spline $S$ at the point $\tau$ is the unique linear optimal method of recovery.
\end{proof}

\section{Optimal recovery of linear functionals from inaccurate information}

Let $X$ be a linear space, $L$ be a linear functional on $X$, $Ix=(l_1x,\ldots,l_nx)$, $x\in X$, where $l_j$, $j=1,\ldots,n$, are linear functionals on $X$, and $W\subset X$. Now assume that for all $x\in W$ instead of exact values of $Ix$ we know approximate values $y\in\mathbb R^n$ such that $\|Ix-y\|\le\delta$, where $\|\cdot\|$ is any norm in $\mathbb R^n$ and $\delta\ge0$ is the error of approximate values. In this case the error of a recovery method $\varphi$ is defined as follows
$$e(L,W,I,\delta,\varphi)=\sup_{\substack{x\in W,\ y\in\mathbb R^n\\\|Ix-y\|\le\delta}}\left|Lx-\varphi(y)\right|.$$
Again, we are interested in the optimal error of recovery
$$E(L,W,I,\delta)=\infp_{\varphi\colon\mathbb R^n\to\mathbb R}e(L,W,I,\delta,\varphi)$$
and in an optimal method $\widehat\varphi$ for which
$$e(L,W,I,\delta,\widehat\varphi)=E(L,W,I,\delta).$$

It was proved in \cite{MO} an analog of Smolyak's result.

\begin{theorem}[\cite{MO}]\label{MrO}
If $W$ is a convex and centrally-symmetric set, then among all optimal methods there exists a linear optimal method and
%\begin{equation}\label{du1}
$$E(L,W,I,\delta)=\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|.$$
%\end{equation}
\end{theorem}

We consider a more general problem of optimal recovery. Let $X$ and $Y$ be linear spaces, $L$ be a linear functional on $X$, and $W\subset X$. Let $F\colon W\to Y$ be a multi-valued mapping. It means that for any $x\in W$ \ $F(x)$ is a subset of $Y$. The problem is to recover $Lx$, $x\in W$ by the information $F(x)$. The multi-valued mapping $F$ is modeling inaccurate information. Usually $F$ has the form
\begin{equation}\label{FF}
F(x)=\{\,y\in Y:\|Ix-y\|\le\delta\,\},
\end{equation}
where $I\colon X\to Y$ is a linear operator, $Y$ is a normed linear space, and $\delta\ge0$. In this case we speak about optimal recovery of $L$ on $W$ by inaccurate values of operator $I$.

For any recovery method $\varphi\colon Y\to\mathbb R$ we define the error of the method $\varphi$ by
\begin{equation}\label{ee}
e(L,F,\varphi)=\sup_{(x,y)\in\gr F}|Lx-\varphi(y)|,
\end{equation}
where
$$\gr F=\{\,(x,y):x\in W,\ y\in F(x)\,\}.$$
The optimal error of recovery is defined as follows
\begin{equation}\label{rec}
E(L,F)=\inf_{\varphi\colon Y\to\mathbb R}e(L,F,\varphi).
\end{equation}

Let $A\subset X$. Denote by $\bco A$ the convex centrally-symmetric hull of $A$
$$\bco A=\biggl\{\,x:x=\sjn\lambda_jx_j,\quad x_j\in A,\quad\sjn|\lambda_j|
\le1,\quad n\in\mathbb N\,\biggr\}.$$
For any multi-valued mapping $F\colon W\to Y$ we define the convex centrally-symmetric multi-valued mapping
$\bco F\colon\bco W\to Y$ by
$$\bco F(x)=\{\,y\in Y:(x,y)\in\bco\gr F\,\}.$$

Let $y\in F(W)$. The value
$$r(L,F,y)=\infp_{c\in\mathbb R}\,\sup_{x\in F^{-1}(y)}|Lx-c|$$
is called the Chebyshev radius of the set $L(F^{-1}(y))$. The value
$$R(L,F)=\sup_{y\in F(W)}r(L,F,y)$$
is called the radius of information in problem \eqref{rec}.

\begin{theorem}[\cite{MO1}]\label{MaO}
For the existence of linear optimal recovery method in \eqref{rec} it is necessary and sufficient that
$$R(L,F)=R(L,\bco F).$$
Moreover, in this case
$$E(L,F)=\sup_{x\in(\bco F)^{-1}(0)}|Lx|.$$
\end{theorem}

For $F$ defined by \eqref{FF} we put
$$e(L,F,\varphi)=e(L,W,I,\delta,\varphi),\quad E(L,F)=E(L,W,I,\delta).$$
If $W$ is a convex and centrally-symmetric set, then $\bco F=F$. Consequently, from Theorem~\ref{MaO} we immediately obtain that Theorem~\ref{MrO} holds in this general multi-dimensional case.

\section{Optimal recovery methods for inaccurate information}

Consider problem \eqref{rec} for $F$ defined by \eqref{FF}.

\begin{theorem}\label{T6}
Let $W$ be a convex and centrally-symmetric set and $Y$ be a normed linear space. Assume that there exist such linear continuous functional $\wm$ and $\wx\in W$ that
\begin{enumerate}
\renewcommand{\labelenumi}{$(\roman{enumi})$}
\item$\displaystyle\sup_{x\in W}|Lx-\wm(Ix)|=L\wx-\wm(I\wx)$,
\item$\displaystyle\wm(I\wx)=\delta\|\wm\|$,
\item$\|I\wx\|\le\delta$.
\end{enumerate}
Then $\wm$ is an optimal method of recovery and
\begin{equation}\label{EE}
E(L,W,I,\delta)=L\wx.
\end{equation}
\end{theorem}

\begin{proof}
It follows from generalization of Theorem~\ref{MrO} that
$$E(L,W,I,\delta)=\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|\ge|L\wx|=L\wx.$$
On the other hand, using conditions $(i)$--$(iii)$, for all $x\in W$ and $y\in Y$ such that $\|Ix-y\|\le\delta$ we have
\begin{multline*}
|Lx-\wm(y)|=|Lx-\wm(Ix)+\wm(Ix-y)|\le|Lx-\wm(Ix)|+|\wm(Ix-y)|\\
\le L\wx-\wm(I\wx)+\|\wm\|\delta=L\wx\le E(L,W,I,\delta).
\end{multline*}
Thus,
$$e(L,W,I,\delta,\wm)\le L\wx\le E(L,W,I,\delta)\le e(L,W,I,\delta,\wm).$$
Consequently, $\wm$ is an optimal method of recovery and \eqref{EE} holds.
\end{proof}

We apply this result to optimal recovery of function values from their Fourier coefficients. Let $\lt$ be the space of $2\pi$ periodic functions defined on the interval $\mathbb T=[-\pi,\pi]$ with identified endpoints with the norm
$$\|x\|=\left(\frac1{\pi}\int_{\mathbb T}|x(t)|^2\,dt\right)^{1/2}.$$
Denote by $\Wrt$ the Sobolev class of $2\pi$ periodic functions defined on $\mathbb T$ with absolutely continuous $x^{(r-1)}$ and $\|x^{(r)}\|\le1$. For any $x\in\Wrt$ and all $t\in\mathbb T$ we have
$$x(t)=\frac{a_0}2+\sum_{k=1}^\infty(a_k\cos kt+b_k\sin kt).$$

We consider the problem of optimal recovery of $x(\tau)$, $\tau\in\mathbb T$, on the class $\Wrt$ from the information about inaccurate values of Fourier coefficients $a_k$, $k\in A$, and $b_k$, $k\in B$, where $A$ and $B$ some finite subsets of $\mathbb Z_+=\{0,1,\ldots\}$. More precisely, instead of $a_k$, $k\in A$, and $b_k$, $k\in B$, we know $\ta_k,\tb_k$, such that
$$|a_k-\ta_k|\le\delta,\quad k\in A,\quad|b_k-\tb_k|\le\delta,\quad k\in B,$$

Set $N=\card A+\card B$ and
$$F_{A,B}x=(\{a_k\}_{k\in A},\{b_k\}_{k\in B}).$$
Denote by $l_\infty^N$ the space of vectors $y=(y_1,\ldots,y_N)$ with the norm
$$\|y\|_{l_\infty^N}=\max_{1\le k\le N}|y_k|.$$
Thus, for every $x\in\Wrt$ we know the vector
$$y=(\{\ta_k\}_{k\in A},\{\tb_k\}_{k\in B})$$
such that
$$\|F_{A,B}x-y\|_{l_\infty^N}\le\delta.$$

In accordance with \eqref{ee} and \eqref{rec} we put
\begin{gather*}
e(\Wrt,F_{A,B},\delta,\varphi)=\sup_{\substack{x\cd\in\Wrt,\ y\in l_\infty^N\\
\|F_{A,B}x-y\|_{l_\infty^N}\le\delta}}|x(\tau)-\varphi(y)|,\\
E(\Wrt,F_{A,B},\delta)=
\inf_{\varphi\colon l_\infty^N\to\mathbb R}e(\Wrt,F_{A,B},\delta,\varphi).
\end{gather*}
We say that $\wm$ is optimal method of recovery if
$$E(\Wrt,F_{A,B},\delta)=e(\Wrt,F_{A,B},\delta,\widehat\varphi).$$

It is easy to show that if $0\notin A$, then $E(\Wrt,F_{A,B},\delta)=\infty$ (for the proof it suffices to consider only constant functions from $\Wrt$). Therefore, in what follows, we assume that $0\in A$. Set $\wA=A\setminus\{0\}$ and consider the vector
$$\left(\left\{\frac{\cos k\tau}{k^{2r}}\right\}_{k\in\wA}, \ \left\{\frac{\sin k\tau}
{k^{2r}}\right\}_{k\in B}\right).$$

Let
\begin{equation}\label{cj}
|\gamma_2|\ge\ldots\ge |\gamma_N|
\end{equation}
be the modules of the elements of this vector, sorted in descending order. If $\gamma_s=k_s^{-2r}\cos k_s\tau$, then the corresponding index will be denoted by $k_s(A)$, and if $\gamma_s=k_s^{-2r}\sin k_s\tau$, then the corresponding index will be denoted by $k_s(B)$. For every $2\le s\le N$ we denote by $A_s$ and $B_s$ the subsets of indexes $k_2(C),\ldots,k_s(C)$ for $C=A$ and $C=B$ respectively. For convenience we put $A_1=B_1=\emptyset$. We also assume that the sum over the empty set equals $0$.

Put
\begin{multline*}
p=p(\delta)=\max\biggl\{\,s:\gamma^2_s\biggl(1-\delta^2\sum_{k\in A_s\cup B_s}k^{2r}\biggr)\\
>\delta^2\sum_{k\in\mathbb N\setminus A_s}\dfrac{\cos^2k\tau}{k^{2r}}+\delta^2\sum_{k\in\mathbb N\setminus B_s}
\dfrac{\sin^2k\tau}{k^{2r}},\ 2\le s\le N\,\biggr\}
\end{multline*}
(we assume that $p=1$, if the set of such $s$ is empty),
\begin{equation*}
\lambda=\left(\dfrac{\displaystyle\sum_{k\in\mathbb N\setminus A_p}
\dfrac{\cos^2k\tau}{k^{2r}}+\sum_{k\in\mathbb N\setminus B_p}\dfrac{\sin^2k\tau}{k^{2r}}}
{\displaystyle1-\delta^2\sum_{k\in A_p\cup B_p}k^{2r}}\right)^{1/2},
\end{equation*}
and
$$\lambda_s=k^{2r}_s(C)(|\gamma_s|-\lambda\delta),\quad \widetilde c_s=
\begin{cases}\sign\gamma_s\,\ta_{k_s(C)},&C=A,\\
\sign\gamma_s\,\tb_{k_s(C)},&C=B.\end{cases}$$

\begin{theorem}\label{T7}
For all $\delta>0$
$$E(\Wrt,F_{A,B},\delta)=\frac\delta2+\delta\sum_{s=2}^p\lambda_s+\lambda$$
and the method
\begin{equation}\label{m1}
\wm(y)=\frac{\ta_0}2+\sum_{s=2}^p\lambda_s\widetilde c_s
\end{equation}
is optimal method of recovery.
\end{theorem}


\begin{proof}
We define the sequences $\ha_k$ and $\hb_k$ as follows
$$\ha_k=\begin{cases}\delta\sign\cos k\tau,&
k\in A_p\cup{0}\,;\\[5pt]
\dfrac{\cos k\tau}{\lambda k^{2r}},& k\notin A_p\cup{0}\,.
\end{cases}\quad\hb_k=\begin{cases}\delta\sign\sin k\tau,&
k\in B_p\,;\\[5pt]
\dfrac{\sin k\tau}{\lambda k^{2r}},& k\notin B_p\,.
\end{cases}$$
It is easy to check that the following equality
\begin{equation}\label{ww}
\sum_{k=1}^\infty k^{2r}(\ha_k^2+\hb_k^2)=1
\end{equation}
holds.

Put
$$\wx(t)=\frac{\ha_0}2+\sum_{k=1}^\infty(\ha_k\cos kt+\hb_k\sin kt).$$
It follows from \eqref{ww} that $\|\wx^{(r)}\|=1$. Thus, $\wx\in\Wrt$.

We will apply Theorem~\ref{T6}. It suffices to check conditions $(i)$--$(iii)$. We begin with condition $(iii)$. Let us show that $\|F_{A,B}\wx\|_{l_\infty^N}\le\delta$. In other words, we should show that $|\ha_k|\le\delta$ for all $k\in A$ and $|\hb_k|\le\delta$ for all $k\in B$.
If $p=N$ then it is obvious. Let $p<N$. If for some $k>0$ and $k\in A\setminus A_p$
the inequality $|\ha_k|>\delta$ holds or for some $k\in B\setminus B_p$ the inequality
$|\hb_k|>\delta$ holds, then there exists $\gamma_s$, $2\le
s\le N$, for which
$$\gamma^2_s>\delta^2\lambda^2.$$
In view of \eqref{cj} it implies that
\begin{equation}\label{p1}
\gamma^2_{p+1}>\delta^2\lambda^2.
\end{equation}
Assume that
$$\gamma^2_{p+1}=\frac{\cos^2k_{p+1}(A)\tau}{k_{p+1}^{4r}(A)}\,.$$
Then \eqref{p1} may be written in the form
\begin{multline*}
\frac{\cos^2k_{p+1}(A)\tau}{k_{p+1}^{4r}(A)}\biggl(1-\delta^2\sum_{k\in A_p\cup B_p}k^{2r}\biggr)\\
>\delta^2\sum_{k\in\mathbb N\setminus A_p}\dfrac{\cos^2k\tau}{k^{2r}}+\delta^2
\sum_{k\in\mathbb N\setminus B_p}\dfrac{\sin^2k\tau}{k^{2r}}.
\end{multline*}
Since $A_{p+1}=A_p\cup\{k_{p+1}\}$, and $B_{p+1}=B_p$, the last inequality may be rewritten in the form
\begin{multline*}
\frac{\cos^2k_{p+1}(A)\tau}{k_{p+1}^{4r}(A)}\biggl(1-\delta^2\sum_{k\in A_{p+1}\cup B_{p+1}}k^{2r}\biggr)\\
>\delta^2\sum_{k\in\mathbb N\setminus A_{p+1}}\dfrac{\cos^2k\tau}{k^{2r}}+\delta^2\sum_{k\in\mathbb N
\setminus B_{p+1}}\dfrac{\sin^2k\tau}{k^{2r}}.
\end{multline*}
But this contradicts the definition of $p$. The case when
$$\gamma^2_{p+1}=\frac{\sin^2k_{p+1}(B)\tau}{k_{p+1}^{4r}(B)}\,,$$
may be considered analogously.

Let us prove that for all sequences $\{a_k\}$, $k=0,1,\ldots$, and $\{b_k\}$,
$k=1,2,\ldots$, such that
$$\sum_{k=1}^\infty k^{2r}(a_k^2+b_k^2)<\infty,$$
the equality
\begin{equation}\label{tozh}
\sum_{k=1}^\infty(a_k\cos k\tau+b_k\sin k\tau)=\sum_{s=2}^p\lambda_s c_s+
\lambda\sum_{k=1}^\infty k^{2r}(\ha_ka_k+\hb_kb_k)
\end{equation}
holds, where
$$c_s=\begin{cases}\sign\gamma_s\,a_{k_s(C)},&C=A,\\
\sign\gamma_s\,b_{k_s(C)},&C=B.\end{cases}$$
Indeed, we have
\begin{multline*}
\sum_{s=2}^p\lambda_s c_s+\lambda\sum_{k=1}^\infty k^{2r}(\ha_ka_k+\hb_kb_k)
=\sum_{s=2}^pk^{2r}_s|\gamma_{k_s}|c_s
-\lambda\delta\sum_{s=2}^pk^{2r}_s c_s\\
+\lambda\delta\sum_{s=2}^pk^{2r}_s c_s+ \lambda\sum_{k\in\mathbb N\setminus
A_p}k^{2r}\dfrac{\cos k\tau}{\lambda k^{2r}}a_k +\lambda\sum_{k\in\mathbb N\setminus
B_p}k^{2r}\dfrac{\sin k\tau}{\lambda k^{2r}}b_k\\= \sum_{k=1}^\infty(a_k\cos k\tau+b_k\sin
k\tau).
\end{multline*}

It follows from \eqref{tozh} that for any $x\in\Wrt$
$$x(\tau)-\wm(F_{A,B}x)=\lambda\sum_{k=1}^\infty k^{2r}(\ha_ka_k+\hb_kb_k).$$
Using the Cauchy--Schwarz inequality we obtain
$$|x(\tau)-\wm(F_{A,B}x)|\le\lambda\biggl(\sum_{k=1}^\infty k^{2r}(\ha_k^2+\hb_k^2)\biggr)^{1/2}\biggl(\sum_{k=1}^\infty k^{2r}(a_k^2+b_k^2)\biggr)^{1/2}\le\lambda.$$
On the other hand,
$$|\wx(\tau)-\wm(F_{A,B}\wx)|=\lambda\sum_{k=1}^\infty k^{2r}(\ha_k^2+\hb_k^2)=\lambda.$$
Consequently, condition $(i)$ holds.

It follows from the definition of $p$ that $\lambda_p>0$. In view of \eqref{cj} we obtain that $\lambda_s>0$ for all $s=2,\ldots,p-1$. We have
$$\wm(F_{A,B}\wx)=\delta\biggl(\frac12+\sum_{s=2}^p\lambda_s\biggr)=\delta\|\wm\|.$$
It means that condition $(ii)$ is fulfilled. Now the assertion of the theorem follows from Theorem~\ref{T6}.
\end{proof}
The case when Fourier coefficients are known with different errors, that is,
$$|a_k-\ta_k|\le\delta_k,\quad k\in A,\quad|b_k-\tb_k|\le\delta_k,\quad k\in B,$$
may be considered in a similar way (see \cite{Os96}).

\section{Optimal recovery of linear operators}

Let $Y_0,Y_1,\ldots,Y_n$ be normed linear spaces and $I_j\colon X\to Y_j$, $j=0,1,\ldots,n$, be linear operators. We consider the problem of optimal recovery of the operator $I_0$ on the set
$$W=\{\,x\in X:\|I_jx\|_{Y_j}\le\delta_j,\ \delta_j\ge0,\ j=1,\ldots,k,\,\}$$
where $0\le k<n$, from inaccurate values of $I_{k+1},\ldots,I_n$ (if $k=0$ we set $W=X$). More precisely, we assume that for every $x\in W$ we know a vector $y=(y_{k+1},\ldots,y_n)\in Y_{k+1}\times\ldots\times Y_n$ such that $\|I_jx-y_j\|_{Y_j}\le\delta_j$, $\delta_j\ge0$, $j=k+1,\ldots,n$.

By the analogy with the previous setting we define the error of a recovery method $\varphi\colon Y_{k+1}\times\ldots\times Y_n\to Y_0$ as follows
$$e(I,\delta,\varphi)=\sup_{\substack{x\in W,\ y\in Y_{k+1}\times\ldots\times Y_n\\
\|I_jx-y_j\|_{Y_j}\le\delta_j,\ j=k+1,\ldots,n}}\|I_0x-\varphi(y)\|_{Y_0}.$$
The value
\begin{equation}\label{e221}
E(I,\delta)=\infp_{\varphi\colon Y_{k+1}\times\ldots\times Y_n\to Y_0}
e(I,\delta,\varphi)
\end{equation}
is called the optimal error of recovery (here $I=(I_0,I_1\ldots,I_n)$, $\delta=(\delta_1,\ldots,\delta_n)$).
Methods for which the lower bound in \eqref{e221} is attained we call optimal methods of recovery.

For the problem of optimal recovery of linear operators there are no such general results similar to Theorem~\ref{MrO} or Theorem~\ref{MaO}. Moreover, sometimes there is no linear optimal method even for the problem of optimal recovery from exact information and with Hilbert spaces $Y_0,Y_1,\ldots,Y_n$. Let us consider the corresponding example.

Let $X=\mathbb R^3$, $Y_0=l_2^2$ ($l_2^n$ is the space $\mathbb
R^n$ with the usual Euclidean metric), $Y_1=Y_2=Y_3=Y_4=l_2^1$. For $x=(x_1,x_2,x_3)\in\mathbb R^3$ we set
\begin{multline*}
I_0x=(x_1,x_2),\quad I_1x=x_1+2x_2,\quad I_2x=x_1-2x_2,\\
I_3x=x_3,\quad I_4x=x_1+x_3.
\end{multline*}
Let $k=3$, $\delta_1=\delta_2=1$, $\delta_3=2/15$, $\delta_4=0$. Thus, we consider the problem of optimal recovery of $I_0$ on the set
$$W=\{\,x\in\mathbb R^3:|I_1x|\le1,\ |I_2x|\le1,\ |I_3x|\le2/15\,\}$$
from exact values of the functional $I_4$. It is easy to see that the set $W$ is the parallelepiped
$$W=\{\,x\in\mathbb R^3:|x_1|+2|x_2|\le1,\ |x_3|\le2/15\,\}.$$
Consider the method
$$\varphi_0(y)=\begin{cases}0,&|y|\le4/15,\\
(y,0),&|y|>4/15.\end{cases}$$
If $|x_1+x_3|\le4/15$, then
$$\sup_{\substack{(x_1,x_2,x_3)\in W\\|x_1+x_3|\le4/15}}||(x_1,x_2)-
\varphi_0(x_1+x_3)||_{l_2^2}=\sup_{\substack{(x_1,x_2,x_3)\in
W\\|x_1+x_3|\le4/15}}||(x_1,x_2)||_{l_2^2}.$$
Since
$$|x_1|=|x_1+x_3-x_3|\le|x_1+x_3|+|x_3|\le\frac25,$$
we have
$$\sup_{\substack{(x_1,x_2,x_3)\in W\\|x_1+x_3|\le4/15}}||(x_1,x_2)-
\varphi_0(x_1+x_3)||_{l_2^2}\le\sup_{\substack{(x_1,x_2,x_3)\in
W\\|x_1|\le2/5}}||(x_1,x_2)||_{l_2^2}=\frac12.$$
If $(x_1,x_2,x_3)\in W$ and $|x_1+x_3|>4/15$, then $|x_1|\ge|x_1+x_3|-|x_3|>2/15$. Consequently, $|x_2|<13/30$. Therefore
\begin{multline*}
\sup_{\substack{(x_1,x_2,x_3)\in W\\|x_1+x_3|>4/15}}||(x_1,x_2)-
\varphi_0(x_1+x_3)||_{l_2^2}\le\sup_{\substack{(x_1,x_2,x_3)\in W\\|x_2|<13/30}}
||(-x_3,x_2)||_{l_2^2}\\
<\sqrt{\frac4{225}+\frac{169}{900}}<\frac12.
\end{multline*}
Thus,
$$E(I,\delta)\le e(I,\delta,\varphi_0)\le\frac12.$$
On the other hand, for any linear method $\varphi(y)=(c_1y,c_2y)$, $c_1,c_2\in\mathbb R$, we have
$$e(I,\delta,\varphi)=\sup_{(x_1,x_2,x_3)\in W}\sqrt{(x_1-c_1(x_1+x_3))^2+
(x_2-c_2(x_1+x_3))^2}.$$
If $c_1\le0$, considering the point $(1,0,0)\in W$, we obtain
$$e(I,\delta,\varphi)\ge\sqrt{(1-c_1)^2+c_2^2}\ge1.$$
If $c_1>0$, considering the point $(0,1/2,2/15\sign c_2)\in W$, we obtain
$$e(I,\delta,\varphi)\ge\sqrt{c_1^2\frac4{15}+\left(\frac12+|c_2|\frac2{15}\right)^2}>\frac12.$$
Consequently, for any linear method $\varphi$
$$e(I,\delta,\varphi)>\frac12\ge E(I,\delta).$$

Nevertheless we prove a result which sometimes helps to construct a family of linear optimal methods.

\begin{theorem}\label{T22g}
Assume that there exist such $\wl_j\ge0$, $j=1,\ldots,n$, and an element
$\wx\in W$, for which
$\|I_j\wx\|_{Y_j}\le\delta_j$, $j=1,\ldots,n$, and
$$\|I_0\wx\|_{Y_0}\ge\biggl(\sum_{j=1}^n\wl_j\delta_j^2\biggr)^{1/2}.$$
Moreover, assume that linear operators $S_j\colon Y_j\to Y_0$ satisfy the conditions
\begin{align*}
(a)\quad&I_0=\sum_{j=1}^nS_jI_j,\\
(b)\quad&\biggl\|\sum_{j=1}^nS_jz_j\biggl\|_{Y_0}^2\le
\sum_{j=1}^n\wl_j\|z_j\|_{Y_j}^2,\ \mbox{for all}\ z_j\in Y_j,\ j=1,\ldots,n.
\end{align*}
Then for any such operators the method
$$\wm(y)=S_{k+1}y_{k+1}+\ldots+S_ny_n,\quad y\in Y_{k+1}\times\ldots\times Y_k,$$
is optimal and
$$E(I,\delta)=\biggl(\sum_{j=1}^n\wl_j\delta_j^2\biggr)^{1/2}.$$
\end{theorem}

\begin{proof}
Let $\varphi\colon Y_{k+1}\times\ldots\times Y_n\to Y_0$ be an arbitrary method of recovery. Then
\begin{multline*}
2\|I_0\wx\|_{Y_0}=\|I_0\wx-\varphi(0)-(I_0(-\wx)-\varphi(0))\|_{Y_0}\\
\le\|I_0\wx-
\varphi(0)\|_{Y_0}+\|I_0(-\wx)-\varphi(0)\|_{Y_0}\le2e(I,\delta,\varphi).
\end{multline*}
In view of the arbitrariness $\varphi$ we have
\begin{equation}\label{e22e4}
E(I,\delta)\ge\|I_0\wx\|_{Y_0}\ge\biggl(\sum_{j=1}^n\wl_j\delta_j^2\biggr)^{1/2}.
\end{equation}

To estimate the error of the method $\wm\cd$ consider the following extremal problem
\begin{multline*}
\biggl\|I_0x-\sum_{j=k+1}^nS_jy_j\biggr\|_{Y_0}^2\to\max,\quad
\|I_jx\|_{Y_j}^2\le\delta_j^2,\ j=1,\ldots,k,\\
\|I_jx-y_j\|_{Y_j}^2\le\delta_j^2,\
j=k+1,\ldots,n,\quad x\in X.
\end{multline*}
Set $z_j=I_jx$, $j=1,\ldots,k$, $z_j=I_jx-y_j$, $j=k+1,\ldots,n$. Then, taking into account $(a)$, this problem may be rewritten in the form
\begin{equation}\label{e22e3}
\biggl\|\sum_{j=1}^nS_jz_j\biggr\|_{Y_0}^2\to\max,
\quad\|z_j\|_{Y_j}^2\le\delta_j^2,\
j=1,\ldots,n,\quad x\in X.
\end{equation}
In view of $(b)$ we obtain
$$\biggl\|\sum_{j=1}^nS_jz_j\biggr\|_{Y_0}^2\le\sum_{j=1}^n\wl_j\|z_j\|_{Y_j}^2\le
\sum_{j=1}^n\wl_j\delta_j^2.$$
Thus,
$$E(I,\delta)\le e(I,\delta,\wm)\le\biggl(\sum_{j=1}^n\wl_j\delta_j^2\biggr)^{1/2}.$$
These inequalities together with \eqref{e22e4} prove the theorem.
\end{proof}

We apply this theorem to construct a family of optimal recovery methods of the $k$-th derivative, $1\le k<r$, for functions from the Sobolev class $\Wrt$ knowing a finite number of their Fourier coefficients given inaccurately. To simplify calculations we will consider the complex case.

Assume that we have the Fourier series for some $2\pi$-periodic function
$x$:
$$x(t)=\sum_{j=-\infty}^{+\infty}x_je^{ijt}.$$
Suppose that we know only a finite number of Fourier coefficients which
are given with an error. That is, we know $\tx=(\tx_{-N},\ldots,\tx_N)$ such that
\begin{equation}\label{del}
\sum_{|j|\le N}|x_j-\tx_j|^2\le\delta.
\end{equation}
Using the information $\tx$ we want to recover the $k$-th derivative of $x$.

One of the simplest methods of recovery is the following
$$x^{(k)}(t)\approx\sum_{|j|\le N}(ij)^k\tx_je^{ijt}.$$
But it is not very good because the error of terms $(ij)^k\tx_j$ in $|j|^k$ times larger than the error of $\tx_j$.

In practice this effect are known very well. Those who deal with such
problems simply cut the terms with high frequencies and smooth other terms by some
filter. Such filter was constructed in a similar problem in Theorem~\ref{T7}.

The problem which we would like to pose is: what is a best method of
recovery? In other words, what is a best possible filter? Now we give the exact setting of the problem.

Define $\lt$ as the space of square integrable real-valued or complex-valued functions $x$ on $\mathbb T$ with the norm
$$\|x\|=\left(\frac1{2\pi}\int_{\mathbb T}|x(t)|^2\,dt\right)^{1/2
}.$$
The Sobolev space $\WR$ is the set of all $2\pi$-periodic real-valued or complex-valued functions $x$ for which the $(r-1)$-st derivative is absolutely continuous and $\|x^{(r)}\|<\infty$.
The Sobolev class $\Wrt$ is the set of all functions $x\in\WR$ for which $\|x^{(r)}\|\le1$.

Denote by $\lN$, $N\in\mathbb Z_+$, the space of vectors $y=(y_{-N},\ldots,y_{N})$ with the norm
$$\|y\|_{\lN}=\biggl(\sum_{j=-N}^N|y_j|^2\biggr)^{1/2}.$$
We consider problem \eqref{e221} for $X=\WR$, $Y_0=Y_1=\lt$, $Y_2=\lN$, $I_0x=x^{(k)}$, $I_1x=x^{(r)}$, $I_2x=\{x_j\}_{j=-N}^N$,
$$x_j=\frac1{2\pi}\int_{\mathbb T}x(t)e^{-ijt}\,dt,$$
$\delta_1=1$, and $\delta_2=\delta>0$. The appropriate error of optimal recovery we denote by $E(D^k,\Wrt,\delta)$.

Set
\begin{equation}\label{s0}
s_0=\min\left\{\,s\in\mathbb Z_+:\frac{(s+1)^{2k}-s^{2k}}{(s+1)^{2r}-s^{2r}}\le\frac1{(N+1)^{2(r-k)}}\,\right\}.
\end{equation}
It is easy to prove that $s_0\le N$. We will consider three cases:
\begin{itemize}
\item[1.]$$s_0>1,\quad\dfrac1{(s+1)^r}\le\delta<\dfrac1{s^r},\quad1\le s\le s_0-1.$$
\item[2.]$$s_0>0,\quad0<\delta<\dfrac1{s_0^r}.$$
\item[3.]$s_0=0$ or $\delta\ge1$.
\end{itemize}
In case 1 we put
$$\wl_1=\frac{(s+1)^{2k}-s^{2k}}{(s+1)^{2r}-s^{2r}},\quad\wl_2=\frac{(s+1)^{2r}s^{2k}-
s^{2r}(s+1)^{2k}}{(s+1)^{2r}-s^{2r}},$$
in case 2 we put
$$\wl_1=\frac1{(N+1)^{2(r-k)}},\quad\wl_2=s_0^{2k}-\frac{s_0^{2r}}{(N+1)^{2(r-k)}},$$
and in case 3 we put $\lambda_1=1$, $\lambda_2=0$.

\begin{theorem}\label{kr}
For all $\delta>0$
$$E(D^k,\Wrt,\delta)=\sqrt{\lambda_1+\lambda_2\delta^2}.$$
If $s_0>0$ and $\delta<1$, then for all $\theta_j$, $|\theta_j|\le1$, $0<|j|\le N$, the methods
\begin{equation}\label{meth}
\wm(\tx)(t)=\sum_{0<|j|\le N}(ij)^k\alpha_j\tx_je^{ijt},
\end{equation}
where
\begin{equation}\label{al1}
\alpha_j=\frac{\lambda_2+\theta_jj^{r-k}\sqrt{\lambda_1\lambda_2(\lambda_2+
\lambda_1j^{2r}-j^{2k})}}{\lambda_2+\lambda_1j^{2r}},
\end{equation}
are optimal.

If $s_0=0$ or $\delta\ge1$, then the method $\wm(\tx)(t)=0$ is optimal.
\end{theorem}

\begin{proof}
In case 1 put
\begin{gather*}
\wx_s=\left(\frac{\delta^2(s+1)^{2r}-1}{(s+1)^{2r}-s^{2r}}\right)^{1/2},\quad
\wx_{s+1}=\left(\frac{1-\delta^2s^{2r}}{(s+1)^{2r}-s^{2r}}\right)^{1/2},\\
\wx(t)=\wx_se^{ist}+\wx_{s+1}e^{i(s+1)t}.
\end{gather*}
We have
\begin{gather*}
\|\wx^{(r)}\|^2=s^{2r}|\wx_s|^2+(s+1)^{2r}|\wx_{s+1}|^2=1,\\
\|I_2\wx\|_{\lN}^2=|\wx_s|^2+|\wx_{s+1}|^2=\delta^2.
\end{gather*}
Moreover,
$$\|I_0\wx\|^2=\|\wx^{(k)}\|^2=s^{2k}|\wx_s|^2+(s+1)^{2k}|\wx_{s+1}|^2=\lambda_1+\lambda_2\delta^2.$$

In case 2 we put
\begin{gather*}
\wx_{s_0}=\delta,\quad\wx_{N+1}=\frac{\sqrt{1-\delta^2s_0^{2r}}}{(N+1)^r},\quad
\wx(t)=\wx_{s_0}e^{is_0t}+\wx_{N+1}e^{i(N+1)t}.
\end{gather*}
We have
%\begin{gather*}
$$\|\wx^{(r)}\|^2=s_0^{2r}|\wx_{s_0}|^2+(N+1)^{2r}|\wx_{N+1}|^2=1,\quad
\|I_2\wx\|_{\lN}^2=|\wx_{s_0}|^2=\delta^2,$$
%\end{gather*}
and
$$\|I_0\wx\|^2=\|\wx^{(k)}\|^2=s_0^{2k}|\wx_{s_0}|^2+(N+1)^{2k}|\wx_{N+1}|^2=
\lambda_1+\lambda_2\delta^2.$$

In case 3 we consider $\wx(t)=e^{it}$. Then
$$\|\wx^{(r)}\|=1,\quad\|I_2\wx\|_{\lN}=\begin{cases}1,&N>0,\\
0,&N=0,\end{cases}$$
and
$$\|I_0\wx\|^2=\|\wx^{(k)}\|^2=1=\lambda_1+\lambda_2\delta^2.$$

Now to apply Theorem~\ref{T22g} we will construct operators $S_1$ and $S_2$. Let $u\in\lt$
$$u(t)=\sum_{j=-\infty}^{+\infty}u_je^{ijt}$$
and $v=(v_{-N},\ldots,v_N)\in\lN$.
We will search operators $S_1$ and $S_2$ in the forms
$$S_1u=\sum_{\substack{j=-\infty\\j\ne0}}^{+\infty}\beta_ju_je^{ijt},\quad
S_2v=\sum_{|j|\le N}(ij)^k\alpha_jv_je^{ijt}.$$
From condition $(a)$ of Theorem~\ref{T22g} we obtain
$$\beta_j=\begin{cases}(ij)^{k-r}(1-\alpha_j),&0<|j|\le N,\\
(ij)^{k-r},&|j|>N.\end{cases}$$

First we consider case 3 ($\lambda_1=1$, $\lambda_2=0$). Put $\alpha_j=0$ for all
$j=-N,\ldots,N$. Then by virtue of the Parseval equality we have
\begin{multline*}
\|S_1u+S_2v\|^2=\|S_1u\|^2=\sum_{\substack{j=-\infty\\j\ne0}}^{+\infty}j^{2(k-r)}|u_j|^2\le
\sum_{\substack{j=-\infty\\j\ne0}}^{+\infty}|u_j|^2\\
\le\|u\|^2=\lambda_1\|u\|^2+\lambda_2\|v\|_{\lN}^2.
\end{multline*}

Now consider cases 1 and 2. We have
\begin{equation}\label{eq0}
\|S_1u+S_2v\|^2=\sum_{0<|j|\le N}|\beta_ju_j+(ij)^k\alpha_jv_j|^2+\sum_{|j|>N}|\beta_j|^2|u_j|^2.
\end{equation}
Using the Cauchy--Schwarz inequality we obtain
\begin{equation}\label{eq1}
|\beta_ju_j+(ij)^k\alpha_jv_j|^2\le A_j(\lambda_1|u_j|^2+\lambda_2|v_j|^2),
\end{equation}
where
$$A_j=\frac{|\beta_j|^2}{\lambda_1}+\frac{j^{2k}|\alpha_j|^2}{\lambda_2}=
\frac{|1-\alpha_j|^2}{j^{2(r-k)}\lambda_1}+\frac{j^{2k}|\alpha_j|^2}{\lambda_2}.$$

Assume that we find $\alpha_j$ such that $A_j\le1$ for all $0<|j|\le N$. Then from \eqref{eq0}, \eqref{eq1}, taking into account that $\lambda_1\ge(N+1)^{-2(r-k)}$, we obtain
\begin{multline*}
\|S_1u+S_2v\|^2\le\lambda_1\sum_{0<|j|\le N}|u_j|^2+\sum_{|j|>N}j^{2(k-r)}|u_j|^2+\lambda_2\sum_{|j|\le N}|v_j|^2\\
\le\lambda_1\sum_{j=-\infty}^{+\infty}|u_j|^2+\lambda_2\sum_{|j|\le N}|v_j|^2=\lambda_1\|u\|^2+\lambda_2\|v\|_{\lN}^2.
\end{multline*}

It remains to show that there exist $\alpha_j$ such that
\begin{equation}\label{aj}
\frac{|1-\alpha_j|^2}{j^{2(r-k)}\lambda_1}+\frac{j^{2k}|\alpha_j|^2}{\lambda_2}\le1
\end{equation}
for all $0<|j|\le N$. This inequality may be rewritten in the form
\begin{equation}\label{al}
\left|\alpha_j-\frac{\lambda_2}{\lambda_2+\lambda_1j^{2r}}\right|^2\le
\frac{\lambda_1\lambda_2j^{2(r-k)}(\lambda_2+\lambda_1j^{2r}-j^{2k})}{(\lambda_2+
\lambda_1j^{2r})^2}.
\end{equation}
It suffices to prove that
\begin{equation}\label{ine}
\lambda_2+\lambda_1j^{2r}-j^{2k}\ge0
\end{equation}
for all $j=1,\ldots,N$. Consider the set of points on the plane $\mathbb R^2$
\begin{equation}\label{po}
\begin{cases}
x_j=j^{2r},&\\
y_j=j^{2k},&
\end{cases}j=0,1,\ldots\,\,.
\end{equation}
If we plot the function
\begin{equation}\label{fpo}
\begin{cases}
x=t^{2r},&\\
y=t^{2k},&
\end{cases}t\in[0,+\infty),
\end{equation}
then points \eqref{po} belong to the plot of this function. The function defined by \eqref{fpo} can be written in the form
$$y=x^{k/r},\quad0<\frac kr<1.$$
It is a concave function. In case 1 the line $y=\lambda_2+\lambda_1x$ passes through the points $(s^{2r},s^{2k})$ and $((s+1)^{2r},(s+1)^{2k}))$. In view of concavity inequality \eqref{ine} holds for all $j\ge0$.

In case 2 the line $y=\lambda_2+\lambda_1x$ passes through the point $(s_0^{2r},s_0^{2k})$ and
$$\frac{(s_0+1)^{2k}-s_0^{2k}}{(s_0+1)^{2r}-s_0^{2r}}\le\lambda_1.$$
It means that inequality \eqref{ine} holds for all $j\ge s_0$. On the other hand, in view of definition of $s_0$
$$\frac{s_0^{2k}-(s_0-1)^{2k}}{s_0^{2r}-(s_0-1)^{2r}}>\lambda_1.$$
Consequently, inequality \eqref{ine} holds for all $0\le j\le s_0$.

Now it remains to note that the set of all $\alpha_j$ satisfying \eqref{al} may be written in the form \eqref{al1} with $|\theta_j|\le1$.
\end{proof}

Among the family of optimal methods \eqref{meth} we find the ones that use minimal information about the input data. If in \eqref{meth} $\alpha_j=0$ for some $j$, then the information about $\tx_j$ is not used. So we would like to find all such $j$. It follows from \eqref{aj} that if $\alpha_j=0$, then $|j|\ge\lambda_1^{\frac1{2(k-r)}}$. It is interesting to find also those $j$ for which $\alpha_j=1$ (that is, for such $j$ we don't smooth the information). From \eqref{aj} we see that we may take $\alpha_j=1$ for $|j|\le\lambda_2^{\frac1{2k}}$. Thus we obtain the following result.

\begin{corollary}
If $s_0>0$ and $\delta<1$, then for all $\theta_j$, $|\theta_j|\le1$, $0<|j|\le N$, the methods
%\begin{equation}\label{meth}
$$\wm(\tx)(t)=\sum_{0<|j|\le\lambda_2^{\frac1{2k}}}(ij)^k\tx_je^{ijt}+
\sum_{\lambda_2^{\frac1{2k}}<|j|<\lambda_1^{\frac1{2(k-r)}}}(ij)^k
\alpha_j\tx_je^{ijt},$$
%\end{equation}
where $\alpha_j$ are defined by \eqref{al1} are optimal.
\end{corollary}

More results on optimal recovery of functions and their derivatives in the periodic case and in the case when functions defined on the real line may be found in \cite{MaO1}--\cite{MaO5}.

\vspace{15pt}

\begin{thebibliography}{11}

\bibitem{MR} Micchelli~C.~A., Rivlin~T.~J. A survey of optimal recovery, Optimal
estimation in approximation theory, Proc. Internat. Sympos. (Freudenstadt 1976),
Plenum, New York 1977, 1--54.

\bibitem{TW} Traub~J.~F., Wo\'zniakowski~H. A general theory of optimal algorithms, ACM
Monograph Series, Academic Press, New York--London 1980.

\bibitem{MR1} Micchelli~C.~A., Rivlin~T.~J. Lectures on optimal recovery, Numerical
analysis, Lancaster 1984 (Lancaster 1984), Lecture Notes in Math., 1129, Springer-Verlag, Berlin 1984, 21--93.

\bibitem{Ar} Arestov~V.~V. Optimal recovery of operators and related problems, Trudy Mat. Inst.
Steklov., 189, Nauka, Moscow 1989, 3--20; English transl., Proc. Steklov Inst. Math. 189:4 (1990), 1--20.

\bibitem{OsB} Osipenko~K.~Yu. Optimal recovery of analytic functions, Nova Science Publ., Inc.,
Huntington, New York 2000.

\bibitem{MT} Magaril-Il'yaev~G.~G., Tikhomirov~V.~M. Convex analysis: theory and
applications, Transl. Math. Monogr., 222, Amer. Math. Soc., Providence, RI 2003.

\bibitem{S} Sard~A. Best approximate integration formulas; best approximation formulas, Amer. J. Math. {\bf71}:1 (1949), 80--91.

\bibitem{N} Nikol'skii~S.~M. On the question of estimates for approximation by quadrature formulae, Uspekhi Mat. Nauk {\bf5}:2 (1950), 165--177 (in Russian).

\bibitem{N1} Nikol'skii~S.~M. Quadrature Formulas, Nauka, Moscow, 1988 (in Russian).

\bibitem{Sm} Smolyak~S.~A. On optimal recovery of functions and functionals of them, Diss. \ldots Cand. Phys.-Math. Sci., Moscow State Univ., Moscow 1965 (in Russian).

\bibitem{Os} Osipenko~K.~Yu. On optimal methods of recovery in Hardy-Sobolev spaces, Mat. Sb., 192 (2001), 67--86; English transl. in Sbornic: Mathematics, 192 (2001), 225--244.

\bibitem{Os1} Osipenko~K.~Yu. Best approximation of analytic functions
from their values at a finite number of points, Mat. Zametki, 19 (1976), 29--40; English transl. in Math. Notes, 19 (1976), 17--23.

\bibitem{FM} Fisher~S.~D., Micchelli~C.~A. The $n$-width of sets of
analytic functions, Duke Math. J., 47:4 (1980), 789--801.

\bibitem{Ko} Korneichuk~N.~P. Splines in Approximation Theory, Nauka, Moscow, 1984 (in Russian).

\bibitem{MRW} Micchelli~C.~A., Rivlin~T.~J., Winograd~S. The optimal recovery of smooth functions, Numer. Math., 26 (1976), 191--200.

\bibitem{GP} Gaffney~P.~W., Powell~M.~J.~D. Optimal interpolation, Lecture NNotes in Math., 506 (1976), 90--99.

\bibitem{MO} Marchuk~A.~G., Osipenko~K.~Yu. Best approximation of functions specified with an error at finite number of points, Mat. Zametki, 17 (1975), 359--368; English
transl. in Math. Notes, 17 (1975), 207--212.

\bibitem{MO1} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu. Optimal recovery of functionals based on inaccurate data, Mat.
Zametki, 50 (1991), 85--93; English transl. in Math. Notes, 50 (1991), 1274--1279.

\bibitem{Os96} Osipenko~K.~Yu. Optimal recovery of periodic functions from Fourier coefficients
given with an error, J. Complexity, 12 (1996), 35--46.

\bibitem{MaO1} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu. Optimal recovery of functions and their derivatives from Fourier coefficients prescribed with an error, Mat. Sb., 193 (2002),
79--100; English transl. in Sbornic: Mathematics, 193 (2002), 387--407.

\bibitem{MaO2} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu. Optimal recovery of functions and their derivatives from inaccurate information about a spectrum and inequalities for derivatives, Funkc. analiz i ego prilozh., 37 (2003), 51--64; English transl. in Funct. Anal and Its Appl., 37 (2003), 203--214.

\bibitem{MaO3} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu.   On optimal harmonic synthesis from inaccurate spectral data, Funkc. analiz i ego prilozh., 44 (2010), 76--79; English transl. in Funct. Anal and Its Appl., 44 (2010), 223--225.

\bibitem{MaO4} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu.  How best to recover a function from its inaccurately given spectrum? Mat. Zametki, 92, 1 (2012), 59--67; English transl. in Math. Notes, 92 (2012), 51--58.

\bibitem{MaO5} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu.    Exactness and optimality of methods for recovering functions from their spectrum, Trudy Mat. Inst. Steklov, 293 (2016), 201--216; English transl. in Proceedings of the Steklov Institute of Mathematics, 293 (2016), 194--208.
\end{thebibliography}
\end{document} 