\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}{Теорема}
\newtheorem{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 m}
\newcommand*{\wl}{\lambda}
\newcommand*{\lt}{L_2(\mathbb R)}
\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*{\sign}{sign}
\DeclareMathOperator*{\card}{card}

\newcommand*{\WR}{W_2^n(\mathbb R)}
\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 f}
\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*{\tb}{\widetilde b}
\newcommand*{\WWt}{\mathcal W_2^n(\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*{\Lia}{L_\infty(\mathbb R_+)}
\newcommand*{\Li}{L_\infty(\mathbb R)}


\begin{document}
\title[Optimal Recovery of Linear Operators]{Optimal Recovery of Linear Operators from Inaccurate Information}
\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{MATI --- Russian State Technological University\\
Institute for Information Transmission Problems,
Russian Academy of Sciences\\
South Mathematical Institute of the Vladikavkaz Scientific Center, Russian Academy of Sciences}
\maketitle

\section{Introduction}

What does it mean to solve a problem in an optimal way? Assume that we have a problem $p$ to be solved. Usually we have some information abut this problem. This information as a rule is incomplete and/or inaccurate. We denote it by $I(p)$. Suppose we have a method (algorithm) $m$ to solve this problem. The method $m$ uses the information $I(p)$. To compare the quality of different methods with each method $m$ we have to associate a number indicating the error of the solution of the problem. We denote this number by $e(p,I,m)$.

Usually we want to have a method that can be applied to several problems of the same type. Assume that we have a set of problems $\cp$. Then for the set $\cp$ the error of the given method $m$ may be defined as follows
$$e(\cp,I,m)=\sup_{p\in\cp}e(p,I,m).$$

If we want to find a good method for problems $\cp$ we have to find a method for which the value $e(\cp,I,m)$ as small as possible. Denote by $\cm$ the set of admissible methods. Then we want to find a method $\wm$ such that
$$e(\cp,I,\wm)=\inf_{m\in\cm}e(\cp,I,m)=:E(\cp,I,\cm).$$
We call the method $\wm$ an {\it optimal method\/} and the value $E(\cp,I,\cm)$ is called an {\it optimal error}.

It may appears that $E(\cp,I,\cm)$ is not sufficiently small. Then we may try to find another type of information about problems from $\cp$ that can provide a better error of solutions. In other words, we can consider the following problem
$$\inf_{I\in\ci}E(\cp,I,\cm),$$
where $\ci$ is some set of information.

Let us consider some examples.

\section{Optimal interpolation}

Let $W$ be some class of functions defined on a domain $D$. Denote by $p_f$ the problem of finding $f(t)$, $t\in D$, for a function $f\in W$. Put
$$I(p_f)=I(f)=(f(t_1),\ldots,f(t_n)),\quad t_j\in D,\ j=1,\ldots,n.$$
Let $\cm$ be the set of all mappings $m\colon\mathbb R^n\to\mathbb R$.
We put
$$e(p_f,I,m)=|f(t)-m(I(f))|.$$
Here $\cp=\{p_f:f\in W\}$. Thus,
$$e(\cp,I,m)=\sup_{f\in W}|f(t)-m(I(f))|=:e(t,W,I,m).$$

To find an optimal method we have to consider the following problem
$$E(t,W,I,\cm)=\inf_{m\colon\mathbb R^n\to\mathbb R}e(t,W,I,m).$$
This problem is called the problem of optimal recovery of a function $f\in W$ at a fixed point $t$ from the information about the values $f(t_1),\ldots,f(t_n)$.

\section{Optimal integration}

Let $p_f$ be the problem of finding the integral
$$Lf=\int_a^bf(t)\,dt$$
for a function $f\in W$. With the same $I(f)$, $\cp$, and $\cm$ we obtain the problem of optimal integration on the class $W$ from the information about values of $f$ at a fixed system of nodes
$$E(L,W,I,\cm)=\infp_{m\colon\mathbb R^n\to\mathbb R}\,\sup_{f\in W}\left|\int_a^bf(t)\,dt-m(I(f))\right|.$$

Note that if instead of $\cm$ we consider the set $\cm_0$ containing only linear functions $m$, that is,
$$m(I(f))=\sum_{j=1}^na_jf(t_j),\ a_j\in\mathbb R,\ j=1,\ldots,n,$$
then we obtain the well-known problem of finding optimal quadrature formula for the class $W$ and a fixed system of nodes.

One may ask how to choose such points $a\le t_1<\ldots<t_n\le b$ for which the optimal error will be minimal. In this case we obtain the following problem
$$E(L,W,\ci,\cm)=\inf_{I\in\ci}E(L,W,I,\cm),$$
where
$$\ci=\{\ I:a\le t_1<\ldots<t_n\le b\ \}.$$

\section{Optimal  numerical differentiation}

In notation of the first example this is the following problem
$$E'(t,W,I,\cm)=\infp_{m\colon\mathbb R^n\to\mathbb R}\,\sup_{f\in W}|f'(t)-m(I(f))|.$$

\section{Optimal interpolation for $\Wi$}
We consider complete solutions of some previous problems for simple classes.

Denote by $\Wi$ the class of real functions $f$ defined on the interval $[-1,1]$, absolutely continuous, and satisfying the condition
$$|f'(t)|\le1\quad\text{almost everywhere on $[-1,1]$}.$$
Following the first example we put
\begin{gather*}
e(t,\Wi,\It,m)=\sup_{f\in\Wi}|f(t)-m(\It(f))|,\\
E(t,\Wi,\It)=\inf_{m\colon\mathbb R^n\to\mathbb R}e(t,\Wi,\It,m),
\end{gather*}
$$\It(f)=(f(t_1),\ldots,f(t_n)),\quad\bt=(t_1,\ldots,t_n),\quad-1\le t_1<\ldots<t_n\le1.$$



Denote by $\alpha(t)$ the nearest point to $t$ from the set of nodes $\{t_1,\ldots,t_n\}$ (in the case when $t$ is in the middle between $t_j$ and $t_{j+1}$ we set for definiteness $\alpha(t)=t_j$). Thus,
$$\alpha(t)=\begin{cases}
t_1,&-1\le t\le\dfrac{t_1+t_2}2,\\[8pt]
t_j,&\dfrac{t_{j-1}+t_j}2<t\le\dfrac{t_j+t_{j+1}}2,\ j=2,\ldots,n-1,\\[8pt]
t_n,&\dfrac{t_{n-1}+t_n}2<t\le1.
\end{cases}$$

Put
$$\wx(t)=|t-\alpha(t)|$$
(see Fig.~\ref{f1}).

\begin{figure}[h]
$$\begin{picture}(250,100)
\put(0,10){\vector(1,0){240}}
\put(120,0){\vector(0,1){100}}
\put(245,0){$t$}
\put(20,10){\circle*{2}}
\put(12,-2){$-1$}
\put(50,10){\circle*{2}}
\put(100,10){\circle*{2}}
\put(175,10){\circle*{2}}
\put(200,10){\circle*{2}}
\put(50,10){\line(-1,1){30}}
\put(50,10){\line(1,1){25}}
\put(100,10){\line(-1,1){25}}
\put(100,10){\line(1,1){37.5}}
\put(175,10){\line(-1,1){37.5}}
\put(175,10){\line(1,1){25}}
\put(160,70){$\wx(t)$}
\put(48,-2){$t_1$}
\put(98,-2){$t_2$}
\put(173,-2){$t_n$}
\put(198,-2){$1$}
\end{picture}$$
\caption{1}\label{f1}
\end{figure}

It is obvious that $\wx\in\Wi$ and $-\wx\in\Wi$. Moreover, $\It(\wx)=\It(-\wx)=0$. For any method $m$ we have
\begin{multline*}
2\wx(t)=|\wx(t)-m(0)-(-\wx(t)-m(0))|\\
\le|\wx(t)-m(0)|+|-\wx(t)-m(0)|\le2e(t,\Wi,\It,m).
\end{multline*}
Consequently, for all $m$
$$e(t,\Wi,\It,m)\ge\wx(t).$$
Hence
\begin{equation}\label{lb}
E(t,\Wi,\It)\ge\wx(t).
\end{equation}
We obtain the lower bound. Now let us obtain the upper bound.

Define the method $\wm$ by the equality
$$\wm(\It(f))=f(\alpha(t)).$$
Then
$$f(t)-f(\alpha(t))=\int_{\alpha(t)}^tf'(\tau)\,d\tau.$$
Since $|f'(\tau)|\le1$ we have
$$|f(t)-f(\alpha(t))|\le|t-\alpha(t)|=\wx(t).$$
Thus, for all $f\in\Wi$
$$|f(t)-\wm(\It(f))|\le\wx(t).$$
We have
$$E(t,\Wi,\It)\le e(t,\Wi,\It,\wm)\le\wx(t).$$

Taking into account the lower bound \eqref{lb}, we obtain that
$$E(t,\Wi,\It)=\wx(t)$$
and $\wm$ ia an optimal method. Consequently, if we have function values $f(t_1),\ldots,f(t_n)$, then an optimal method of recovery of $f(t)$ on the class $\Wi$ is the following
$$f(t)\approx f(\alpha(t))$$
(see Fig.~\ref{f2}).


\begin{figure}[h]
$$\begin{picture}(250,100)
\put(0,40){\vector(1,0){240}}
\put(120,0){\vector(0,1){100}}
\put(245,30){$t$}
\put(20,40){\circle*{2}}
\put(12,28){$-1$}
\put(50,40){\circle*{2}}
\put(20,50){\line(1,0){55}}
\put(100,40){\circle*{2}}
\put(175,40){\circle*{2}}
\put(200,40){\circle*{2}}
\put(137.5,20){\vector(-1,0){62.5}}
\put(200,70){\vector(-1,0){62.5}}
\put(38,60){$f(t_1)$}
\put(90,7){$f(t_2)$}
\put(166,76){$f(t_n)$}
\put(78,80){$f(\alpha(t))$}
\put(48,28){$t_1$}
\put(98,28){$t_2$}
\put(173,28){$t_n$}
\put(198,28){$1$}
\end{picture}$$
\caption{2}\label{f2}
\end{figure}

There may be several optimal methods. Among them there is one which has good properties. It is called the {\it central method}. We construct the central method for the above problem. Let $y=(y_1,\ldots,y_n)\in\mathbb R^n$. Put
$$W_y=\{\,f\in\Wi:I_{\bar t}f=y\,\}.$$
Consider the set
$$A_y=\{\,f(t):f\in W_y\,\}.$$
For the fixed $t$ the set $A_y$ is an interval on $\mathbb R$ and
$$c_y=\frac{\sup_{f\in W_y}f(t)+\inf_{f\in W_y}f(t)}2$$
is the middle of it.


For any $y$, such that $W_y\ne\emptyset$ and for all $f\in W_y$ we have
$$\inf_{c\in\mathbb R}\sup_{f\in W_y}|f(t)-c|=\sup_{f\in W_y}|f(t)-c_y|.$$
Thus for any method $m$ and for any $y$, $W_y\ne\emptyset$,
$$\sup_{f\in W_y}|f(t)-m(y)|\ge\sup_{f\in W_y}|f(t)-c_y|.$$
Consequently, the method $\wm_c(I_{\bar t}f)=c_{I_{\bar t}f}$ is the optimal method which is the best for any fixed information $I_{\bar t}f$. Such methods are called central methods.

The explicit form for the method $\wm_c$ may be found using the following picture

\begin{figure}[h]
$$\begin{picture}(250,150)
\put(0,10){\vector(1,0){240}}
%\put(245,0){$t$}
\put(75,10){\circle*{2}}
\put(175,10){\circle*{2}}
\put(75,50){\line(1,1){75}}
\put(70,-2){$t_j$}
\put(173,-2){$t_{j+1}$}
\put(75,10){\line(0,1){40}}
\put(75,50){\circle*{2}}
\put(175,10){\line(0,1){90}}
\put(175,100){\circle*{2}}
\put(75,50){\line(1,-1){25}}
\put(175,100){\line(-1,1){25}}
\put(175,100){\line(-1,-1){75}}
\put(100,10){\circle*{2}}
\put(95,-2){$t_j^*$}
\put(100,10){\line(0,1){65}}
\put(150,10){\circle*{2}}
\put(145,-2){$t_j^{**}$}
\put(150,10){\line(0,1){115}}
{\thicklines
\put(75,50){\line(1,0){25}}
\put(100,50){\line(1,1){50}}
\put(150,100){\line(1,0){25}}
}
\put(62,45){$y_j$}
\put(178,93){$y_{j+1}$}
\put(112,-2){$t$}
\put(115,10){\circle*{2}}
\put(115,10){\line(0,1){55}}
\put(115,65){\circle*{2}}
\put(117,60){$c_y$}
\end{picture}$$
\caption{3}\label{f3}
\end{figure}



$$\wm_c(I_{\bar t}f)(t)=\begin{cases}
y_1,&-1\le t\le t_1,\\
y_j,&t_j\le t\le t_j^*,\\
&j=1,\ldots,n-1,\\
\dfrac{y_j+y_{j+1}}2&\\
\hspace{1pt}+\sign(y_{j+1}-y_j)\left(t-\dfrac{t_j+t_{j+1}}2\right),&t_j^*
\le t\le t_j^{**},\\
&j=1,\ldots,n-1,\\
y_{j+1},&t_j^{**}\le t<t_{j+1},\\
&j=1,\ldots,n-1,\\
y_n,&t_n\le t\le1.
\end{cases}$$
$$t_j^*=\frac{t_j+t_{j+1}}2-\frac{|y_{j+1}-y_j|}2,\quad
t_j^{**}=\frac{t_j+t_{j+1}}2+\frac{|y_{j+1}-y_j|}2.$$

\section{Optimal recovery of the minimum}

Now for the same class $\Wi$ and the same information $I_{\bar t}$ we consider the problem of optimal recovery of the (nonlinear!) functional
$$Lf=\min_{t\in[-1,1]}f(t).$$

The error of any method $m\colon\mathbb R^n\to\mathbb R$ is
$$e(L,\Wi,I_{\bar t},m)=\sup_{\vphantom{\Wi}f\in\Wi}\left|Lf-m(I_{\bar t}f)
\right|,$$
The problem is to find
$$E(L,\Wi,I_{\bar t})=\infp_{\vphantom{\Wi}m\colon\mathbb R^n\to\mathbb R}
e(L,\Wi,I_{\bar t},m)$$
and an optimal recovery method.


We construct the central method in this problem. For the fixed $y\in\mathbb R^n$ we again deal with the set $W_y=\{f\in\Wi:I_{\bar t}f=y\}\ne\emptyset$. All functions from $W_y$ are between two piecewise linear functions. The upper function we denote by $Z_y(t)$ and the lower function by $z_y(t)$.

\begin{figure}[h]
$$\begin{picture}(250,120)
\put(0,10){\vector(1,0){240}}
\put(245,0){$t$}
\put(75,10){\circle*{2}}
\put(175,10){\circle*{2}}
\put(75,50){\line(1,1){75}}
\put(75,50){\line(-1,-1){25}}
\put(75,50){\line(-1,1){35}}
\put(70,-2){$t_j$}
\put(173,-2){$t_{j+1}$}
\put(75,10){\line(0,1){40}}
\put(75,50){\circle*{2}}
\put(175,10){\line(0,1){90}}
\put(175,100){\circle*{2}}
\put(75,50){\line(1,-1){25}}
\put(175,100){\line(-1,1){25}}
\put(175,100){\line(-1,-1){75}}
\put(175,100){\line(1,1){25}}
\put(175,100){\line(1,-1){35}}
\put(58,47){$y_j$}
\put(94,98){$Z_y(t)$}
\put(56,70){$Z_y(t)$}
\put(164,116){$Z_y(t)$}
\put(120,38){$z_y(t)$}
\put(51,20){$z_y(t)$}
\put(177,66){$z_y(t)$}
\put(182,97){$y_{j+1}$}
\end{picture}$$
%\caption{}\label{f2}
\end{figure}

Thus for all $f\in W_y$
$$\min_{t\in[-1,1]}Z_y(t)\le\min_{t\in[-1,1]}f(t)\le\min_{t\in[-1,1]}z_y(t).$$
It is clear that
$$\min_{t\in[-1,1]}Z_y(t)=\min_{1\le j\le n}y_j.$$
It may be shown that
$$\min_{t\in[t_j,t_{j+1}]}z_y(t)=\frac{y_{j+1}+y_j}2-\frac{t_{j+1}-t_j}2.$$


Taking into account intervals $[-1,t_1]$ and $[t_n,1]$ we obtain
\begin{multline*}
\min_{t\in[-1,1]}z_y(t)\\=\min\left\{y_1-h_0,\frac{y_2+y_1}2-h_1/2,
\ldots,\frac{y_n+y_{n-1}}2-h_{n-1}/2,y_n-h_n\right\},
\end{multline*}
where $h_0=t_1+1$, $h_j=t_{j+1}-t_j$, $j=1,\ldots,n-1$, $h_n=1-t_n$.

Thus the method
\begin{multline*}
\wm_L(I_{\bar t}f)=\frac12\left(\min_{t\in[-1,1]}Z_y(t)+\min_{t\in[-1,1]}z_y(t)\right)\\
=\frac12\min_{1\le j\le n}y_j\\
+\frac12\min\left\{y_1-h_0,\frac{y_2+y_1}2-h_1/2,
\ldots,\frac{y_n+y_{n-1}}2-h_{n-1}/2,y_n-h_n\right\}
\end{multline*}
is the central method for recovery of minimum. It may be shown that
$$E(L,\Wi,I_{\bar t})=\frac12\min\left\{h_0,h_1/2,
\ldots,h_{n-1}/2,h_n\right\}.$$

For the equidistant system of points
$$\widehat t_j=-1+\frac{2j-1}n,\quad j=1,\ldots,n,$$
We have
\begin{multline*}
\wm_L(I_{\bar t}f)\\=
\frac12\min_{1\le j\le n}y_j+\frac12\min\left\{y_1,\frac{y_2+y_1}2,\ldots,\frac{y_n+y_{n-1}}2,y_n
\right\}-\frac1{2n}.
\end{multline*}

\section{Optimal recovery from Fourier coefficients}

Let $f$ be a periodic function on $\mathbb T=[-\pi,\pi]$ and the Fourier series
$$f(t)=\frac{a_0}2+\sum_{k=1}^\infty(a_k\cos kt+ b_k\sin kt),$$
where
\begin{align*}
a_k&=\frac1\pi\int_{\mathbb T}f(t)\cos kt\,dt,\quad k=0,1,2,\ldots,\\
b_k&=\frac1\pi\int_{\mathbb T}f(t)\sin kt\,dt,\quad k=1,2,\ldots,
\end{align*}
converges uniformly to $f$.

Suppose that instead of precise values of the Fourier coefficients of $f$ we know their inaccurate values $\ta_k$, $\tb_k$ such that
$$\frac{(a_0-\ta_0)^2}2+\sum_{k=1}^\infty((a_k-\ta_k)^2+(b_k-\tb_k)^2)\le\delta^2,$$
where $\delta>0$. The problem is to recover $f$ at some point $\tau$.

We cannot take as approximation the series
$$\frac{\ta_0}2+\sum_{k=1}^\infty(\ta_k\cos k\tau+\tb_k\sin k\tau)$$
since it may differ from $f(\tau)$ as much as desired or even be nonconvergent.

A.~N.~Tikhonov proposed to take the following series
$$\widetilde f(t)=\frac{\ta_0}2+\sum_{k=1}^\infty\frac1{1+\alpha k^2}(\ta_k\cos k\tau+\tb_k\sin k\tau),$$
where $\alpha$ has the same order of smallness as $\delta$ (in particular, it is possible to put $\alpha=\delta$). He proved that if $f\in L_2(\mathbb T)$ and $f$ is continuous at $\tau$, then $\widetilde f(\tau)\to f(\tau)$ as $\delta\to0$.

$L_2(\mathbb T)$ is the linear space of functions for which
$$\int_{\mathbb T}|f(t)|^2\,dt<\infty.$$

This method are known as Tikhonov regularization.

There are several questions to this method.

1. Are there any better method? How to compare various methods?

2. What is the error of approximation when $\delta$ is fixed?

3. Do we need to know all inaccurate values $\ta_k$ and $\tb_k$?

We try to answer these questions and construct a family of optimal methods for this problem. We call the approach that we use Kolmogorov regularization since it based on ideas of A.~N.~Kolmogorov.

We begin with the setting of the problem in terms of optimal recovery theory.

Let $\WWt$ be the space of $2\pi$-periodic functions with absolutely continuous $x^{(n-1)}$ and $x^{(n)}\in\lT$. Set
$$\Wt=\{\,x\in\WWt:\|x^{(n)}\|_{\lT}\le1.$$
Suppose that for every $x\in\Wt$ we know the Fourier coefficients
\begin{align*}
a_j(x)&=\frac1\pi\int_{\mathbb T}x(t)\cos jt\,dt,\quad j=0,1,2,\ldots,\\
b_j(x)&=\frac1\pi\int_{\mathbb T}x(t)\sin jt\,dt,\quad j=1,2,\ldots,
\end{align*}
given inaccurately.

Suppose that we know
$$y=(\ta_0,\ta_1,\tb_1\ldots)$$
such that
$$\|Ix-y\|_{l_2}\le\delta,$$
where
$$Ix=(a_0(x),a_1(x),b_1(x),\ldots).$$
Here the norm in $l_2$ is defined by the inner product
\begin{multline*}
\la u,v\ra_{l_2}=\frac{a_0c_0}2+\sum_{k=1}^n(a_kc_k+b_kd_k),\quad u=(a_0,a_1,b_1,\ldots),\\
v=(c_0,d_1,c_1,\ldots).
\end{multline*}

Using this information we would like to find the best method of recovery of $x(\tau)$ at some point $\tau\in\mathbb T$.
For every method of recovery $m\colon l_2\to\mathbb R$ we define the error of the method by
$$e(\Wt,I,\delta,m)=\sup_{\substack{x\in\Wt,\ y\in l_2\\
\|Ix-y\|_{l_2}\le\delta}}|x(\tau)-m(y)|.$$
We are interested in the optimal error of recovery
$$E(\Wt,I,\delta)=\inf_{m\colon l_2\to\mathbb R}e(\Wt,I,\delta,m),$$
and the method for which this value ia attained.

Let $a$ be the solution of the equation
$$\frac{\dfrac12+\sum_{k=1}^\infty\dfrac1{(1+ak^{2n})^2}}
{\sum_{k=1}^\infty\dfrac{k^{2n}}{(1+ak^{2n})^2}}=\delta^2$$
(it may be shown that for every $\delta>0$ there exists the unique  solution of this equation).

\begin{theorem}
The method
$$\wm(y)=\frac{\ta_0}2+\sum_{k=1}^\infty\frac1{1+ak^{2n}}(\ta_k\cos k\tau+\tb_k\sin k\tau)$$
is optimal and
$$E(\Wt,I,\delta)=\wl_1(a+\delta^2),$$
where
$$\wl_1=\biggl(\sum_{k=1}^\infty\frac{k^{2n}}{(1+ak^{2n})^2}\biggr)^{1/2}.$$
\end{theorem}

\section{Optimal recovery by finite number of Fourier coefficients}

We begin with the case when we know exact values of Fourier coefficients.
Let $A\subset\mathbb Z_+=\{0,1,2,\ldots\}$ and $B\subset\mathbb N=\{1,2,\ldots\}$ be finite sets and for every $x\in\Wt$ we know the Fourier coefficients $\{a_k\}_{k\in A}$ and $\{b_k\}_{k\in B}$. That is for every $x$ we know the vector $F_{A,B}x=(\{a_k\}_{k\in
A},\{b_k\}_{b\in B})$ from $\mathbb R^N$, $N=\card A+\card B$.

Using the information $F_{A,B}x$ we want to find a function which approximate $x^{(r)}$, $0\le r\le n-1$, in $\lT$ in the best way. Now the error of method $m\colon\mathbb R^N\to\lT$ is defined as follows
$$e_r(\Wt,F_{A,B},m)=\sup_{x\in\Wt}\|x^{(r)}-m(F_{A,B}x)\|_{\lT}.$$

The error of optimal recovery is defined by
$$E_r(\Wt,F_{A,B})=\inf_{m\colon\mathbb R^N\to\lT}e_r(\Wt,F_{A,B},m).$$

Since for every $c\in\mathbb R$ \ $x=c\in\Wt$, it is easy to show that in the case when $0\notin A$ \ $E_0(\Wt,F_{A,B})=\infty$.

Put
$$k_0=k_0(A,B)=\min\{\min_{\,k\in\mathbb N\setminus A}k, \ \min_{k\in\mathbb N\setminus B}k\,\}.$$
It means that $\{0,1,\ldots,k_0-1\}\in A$, $\{1,\ldots,k_0-1\}\in B$, and $k_0\notin A$ or $k_0\notin B$.

Put $\chi_0=1$ and $\chi_r=0$ for $r\ge1$.

\begin{theorem}
Let $1\le r\le n-1$ or $r=0$ and $0\in A$. Then $E_r(\Wt,F_{A,B})=k_0^{-(n-r)}$ and for all $\alpha=\{\alpha_k\}_{k\in A}$ and $\beta=\{\beta_k\}_{k\in B}$ such that
$$|\alpha_k-1|\le\left(\frac{k}{k_0}\right)^{n-r},\ k\in A,\quad
|\beta_k-1|\le\left(\frac{k}{k_0}\right)^{n-r},\ k\in B,$$
the method
\begin{multline*}
\widehat m(F_{A,B}x)(t)=\frac{a_0}2\chi_r+\sum_{k\in A\setminus\{0\}}k^r\alpha_ka_k\cos(kt+\pi r/2)\\
+\sum_{k\in B}k^r\beta_kb_k\sin(kt+\pi r/2)
\end{multline*}
is optimal
\end{theorem}


Let us consider the case when $r=0$. Note that we may take as an optimal method the method
$$\widehat m(F_{A,B}x)(t)=\frac{a_0}2+\sum_{k\in A\setminus\{0\}}a_k\cos kt
+\sum_{k\in B}b_k\sin kt.$$

But the method
$$\widehat m(F_{A,B}x)(t)=\frac{a_0}2+\sum_{k=1}^{k_0-1}(a_k\cos kt
+b_k\sin kt)$$
is also optimal and it does not use coefficients $a_k$ and $b_k$ if $k\ge k_0$.

\section{Optimal recovery by finite number of inaccurate Fourier coefficients}
Now we consider the case when for every $x\in\Wt$ we know $y\in\mathbb R^N$ such that $\|F_{A,B}x-y\|_{\infty}\le\delta$, where
$\|y\|_{\infty}=\max_{0\le j\le N-1}|y_j|$, $y=(y_0,y_1,\ldots,y_{N-1})$.

It means that instead of exact values of Fourier coefficients we know $\{\ta_k\}_{k\in A}$ and $\{\tb_k\}_{k\in B}$ such that
$$|a_k-\ta_k|\le\delta,\ k\in A,\quad|b_k-\tb_k|\le\delta,\ k\in B.$$
Again we want to recover $x^{(r)}$ in $\lT$-metric.

Here we define the error of $m$ by
$$e_r(\Wt,F_{A,B},\delta,m)=\sup_{\substack{x\in\Wt,\ y\in l_\infty^N\\
\|F_{A,B}x-y\|_{\infty}\le\delta}}\|x^{(r)}-m(y)\|_{\lT}.$$

The error of optimal recovery is
$$E_r(\Wt,F_{A,B},\delta)=\inf_{m\colon l_\infty^N\to\lT}e_r(\Wt,F_{A,B},\delta,m).$$
Set
$$\widehat p=\max\biggl\{p\in\mathbb Z_+ :
2\delta^2\sum_{k=0}^pk^{2n}<1\biggr\},\quad p_0=\min\{\widehat p,k_0-1\}.$$

\begin{theorem}
If $1\le r\le n-1$ or $r=0$ and $0\in A$, then
\begin{multline*}
E_r(\Wt,F_{A,B},\delta)\\=\sqrt{\frac
1{(p_0+1)^{2(n-r)}}+\frac{\delta^2}2\chi_r+2\delta^2\sum_{k=1}^{p_0}k^{2r}
\left(1-\left(\frac{k}{p_0+1}\right)^{2(n-r)}\right)}
\end{multline*}
and the method \ $\widehat m(\{\ta_k\}_{k\in A},\{\tb_k\}_{k\in B})(t)=\dfrac{\ta_0}2\chi_r$
\begin{multline*}
+\sum_{k=1}^{p_0}\left(1-\left(\frac{k}{p_0+1}\right)^{2(n-r)}\right)\\ \times k^r(\ta_k\cos
(kt+\pi r/2)+\tb_k\sin(kt+\pi r/2))\quad\mbox{is optimal.}
\end{multline*}
\end{theorem}

\section{Hadamard three-circle theorem and inequalities for derivatives}
We begin with one extremal problem which is known as the Hadamard
three-circle theorem. Let $f(z)$ be a holomorphic function on the
annulus
$$r_1\le|z|\le r_2.$$
Put
$$M(r)=\max_{|z|=r}|f(z)|.$$
Then $\log M(r)$ is a convex function of the $\log r$. The conclusion of the theorem can be restated as
$$M(r)\le M(r_1)^{\frac{\log r_2/r}{\log r_2/r_1}}M(r_2)^{\frac{\log r/r_1}{\log r_2/r_1}}.$$
for any three concentric circles of radii $r_1<r<r_2$.

The history of this theorem is the following. A statement and proof for the theorem was given by J.E. Littlewood in 1912, but he attributes it to no one in particular, stating it as a known theorem. H. Bohr and E. Landau claim the theorem was first given by J. Hadamard in 1896, although Hadamard had published no proof.

The Hadamard three-circle theorem gives an estimate in the following extremal problem
$$M(r)\to\max,\quad M(r_1)\le\delta_1,\quad M(r_2)\le\delta_2.$$
The exact solution of this problem which is expressed in terms of elliptic functions was given by R.~M. Robinson in 1943.


In 1913 E.~Landau considered a very similar problem. He took derivatives instead of circles. He proved that for all functions $x\in
\Lia$ with the first derivative locally absolutely continuous on $\mathbb
R_+$ and $x''\in\Lia$ the following exact inequality
$$\|x'\|_{\Lia}\le2\|x\|_{\Lia}^{1/2}\|x''\|_{\Lia}^{1/2}$$
holds (the exactness means that the constant $2$ could not be replaced by some other constant which is less than $2$). That is he found the exact solution of the extremal problem
$$\|x'\|_{\Lia}\to\max,\quad\|x\|_{\Lia}\le\delta_1,\quad\|x''\|_{\Lia}\le \delta_2.$$

Then in 1914 Hadamard solved the analogous problem for $\mathbb R$.

In 1939 A.~N.~Kolmogorov obtained the general result in this field. He found the exact solution of the problem
$$\|x^{(k)}\|_{\Li}\to\max,\quad\|x\|_{\Li}\le\delta_1,\quad
\|x^{(r)}\|_{\Li}\le\delta_2.$$
The value of this problem is
$$\frac{K_{r-k}}{K_r^{1-\frac kr}}\delta_1^{1-
k/r}\delta_2^{k/r},$$
where
$$K_m=\frac4\pi\sum_{s=0}^\infty\frac{(-1)^{s(m+1)}}{(2s+1)^{m+1}}$$
are the Favard constants.

These types of extremal problems are known as Landau--Kolmogorov
inequalities for derivatives and they all are similar to the initial extremal problem formulated by Hadamard.

\section{Hardy--Littlewood--P\'olya inequality and optimal recovery of derivatives}

One more example of Landau--Kolmogorov type inequalities is the Hardy--Littlewood--P\'olya inequality.

In 1939 Hardy, Littlewood, and P\'olya proved that for all integer
$0<k<r$ and all $x\in\lt\cap W_2^r(\mathbb R)$
$$\|x^{(k)}\|_{\lt}\le\|x\|_{\lt}^{1-\frac kr}\|x^{(r)}\|_{\lt}^{
\frac kr},$$

This result may be formulated in the same form as Hadamard's theorem.
\begin{theorem}
$\log\|x^{(k)}\|_{\lt}$ is a convex function of $k$.
\end{theorem}

It is possible to define fractional derivatives then $k$ will be continuous argument.

We may consider more than three circles in Hadamar's theorem and more than three derivatives in the Hardy--Littlewood--P\'olya inequality. The more values of convex function we know the more precise we can estimate the function.

Let $k_1<\ldots<k_n$ and $k_1\le k\le k_n$. Consider the following extremal problem
\begin{multline*}
\|x^{(k)}\|_{\lt}\to\max,\quad\|x^{(k_j)}\|_{\lt}\le\delta_j,\ j=1,\ldots,n,\\
x\in\mathcal W_2^{k_n}(\mathbb R).
\end{multline*}

Let
$$M=\co\{\,(k_j,\log\delta_j),\ j=1,\ldots,n\,\}.$$
be a set in $\mathbb R^2$
Put
$$\theta(x)=\min\{\,y:(x,y)\in M\,\}.$$

\begin{figure}[h]
$$\begin{picture}(290,230)
\put(2,150){$0$}
\put(0,160){\vector(1,0){300}}
\put(10,25){\vector(0,1){215}}
\put(290,150){$x$}
\put(110,40){$\theta(x)$}
{\thicklines
\put(20,140){\line(1,-2){30}}
\put(50,80){\line(4,-1){60}}
\put(110,65){\line(4,1){60}}
\put(170,80){\line(3,2){90}}
}
\put(22,140){$\log\delta_{j_1}$}
\put(45,66){$\log\delta_{j_2}$}
\put(112,55){$\log\delta_{j_3}$}
\put(160,66){$\log\delta_{j_4}$}
\put(262,134){$\log\delta_{j_5}$}
\put(20,140){\circle*{2}}
\put(16,166){$k_{j_1}$}
\put(20,160){\line(0,-1){20}}
\put(50,160){\line(0,-1){80}}
\put(46,166){$k_{j_2}$}
\put(50,80){\circle*{2}}
\put(110,65){\circle*{2}}
\put(106,166){$k_{j_3}$}
\put(110,160){\line(0,-1){95}}
\put(166,166){$k_{j_4}$}
\put(170,160){\line(0,-1){80}}
\put(170,80){\circle*{2}}
\put(256,166){$k_{j_5}$}
\put(260,160){\line(0,-1){20}}
\put(260,140){\circle*{2}}
\put(100,150){\circle*{2}}
\put(80,90){\circle*{2}}
\put(140,120){\circle*{2}}
\put(198,148){\circle*{2}}
\end{picture}$$
%\caption{}
\end{figure}

\begin{theorem}
$$\sup_{\substack{x\in\mathcal W_2^{k_n}(\mathbb R)\\\|x^{(k_j)}\|_{\lt}\le\delta_j,\ j=1,\ldots,n}}\|x^{(k)}\|_{\lt}=e^{\theta(k)}.$$
\end{theorem}


\section{Optimal recover of derivatives}

Suppose that we know functions $y_1,\ldots,y_n\in\lt$ such that
$$\|x^{(k_j)}-y_j\|_{\lt}\le\delta_j,\quad j=1,\ldots,n.$$
We want to recover $x^{(k)}$.

Any recovery method is a map $m\colon(\lt)^n\to\lt$.

The error of method $m$ is defined as
$$e(D^k,K,\delta,m)=\sup_{\substack{x\in\mathcal W_2^{k_n}(\mathbb R)\\\|x^{(k_j)}-y_j\|_{\lt}\le\delta_j,\ j=1,\ldots,n}}\|x^{(k)}-m(y)\|_{\lt},$$
here $K=(k_1,\ldots,k_n)$, $\delta=(\delta_1,\ldots,\delta_n)$ and $y=(y_1,\ldots,y_n)$.

The error of optimal recovery is defined by
$$E(D^k,K,\delta)=\inf_{m\colon(\lt)^n\to\lt}e(D^k,K,\delta,m).$$

The method for which the lower bound is attained is called optimal method of recovery.

Let $k_{j_1},\ldots,k_{j_r}$ be the points of break of polygonal line $\theta$. Denote by $Fx$ the Fourier transform of $x$.

\begin{theorem}
For all $k_1\le k\le k_n$
$$E(D^k,K,\delta)=e^{\theta(k)}.$$
If $k_{j_s}<k<k_{j_{s+1}}$, $1\le s\le r-1$, Then the metod $\wm(y)=(L_s*y_{j_s})+(R_{s+1}*y_{j_{s+1}})$, where
\begin{gather*}
FL_s(\tau)=(i\tau)^k\frac{(k_{j_{s+1}}-k)\delta_{j_{s+1}}^2(-i\tau)^{k_{j_s}}}
{(k_{j_{s+1}}-k)\delta_{j_{s+1}}^2\tau^{2k_{j_s}}+
(k-k_{j_s})\delta_{j_s}^2\tau^{2k_{j_{s+1}}}},\\
FR_{s+1}(\tau)=(i\tau)^k\frac{(k-k_{j_s})\delta_{j_s}^2(-i\tau)^{k_{j_{s+1}}}}
{(k_{j_{s+1}}-k)\delta_{j_{s+1}}^2\tau^{2k_{j_s}}+
(k-k_{j_s})\delta_{j_s}^2\tau^{2k_{j_{s+1}}}},
\end{gather*}
is optimal. For $k=k_{j_s}$, $1\le s\le r-1$, the metod $\wm(y)=y_{j_s}$ is optimal.
\end{theorem}

\section{Analog of the Hadamard theorem for the heat equation}
For the heat equation we will consider the problem which is analogous to the Hadamard three-circle theorem.



Let $u$ be the solution of the heat equation in $\mathbb R^d$
%\begin{equation}\label{rex}
$$\begin{aligned}
&u_t=\Delta u,\\
&u_{\big|t=0}=f(x),\quad f\in\ld.
\end{aligned}$$

\begin{theorem}
Let $u(t,x)$ be the solution of the heat equation.
Then $\log\|u(t,\cdot)\|_{\ld}$ is a convex function of $t$.
\end{theorem}

In other words, for all $t_1<\tau<t_2$
$$\|u(\tau,\cdot)\|_{\ld}\le\|u(t_1,\cdot)\|_{\ld}^{\frac{t_2-\tau}{t_2-t_1}}
\|u(t_2,\cdot)\|_{\ld}^{\frac{\tau-t_1}{t_2-t_1}}.$$



Now we consider the similar problem with $n+1$ ``circles''. Namely, we want to solve the following extremal problem
\begin{multline*}
\|u(\tau,\cdot)\|_{\ld}\to\max,\quad\|u(t_j,\cdot)\|_{\ld}\le\delta_j,\quad j=1,2,\ldots,n,\\
f\in\ld,
\end{multline*}
where $0\le t_1<\ldots<t_n$ and $\delta_j>0$, $j=1,2,\ldots,n$.


To formulate the result we consider the set
$$M=\co\{\,(t_j,\log\delta_j),\,\,1\le j\le n\,\}+\{\,(t,0)\mid\,\,t\ge0\,\},$$
where $\co A$ is a convex hull of $A$. Define the function
$\theta(t)$, $t\in[t_1,\infty)$ as follows
$$\theta(t)=\min\{\,y:(t,y)\in M\,\}.$$
It is clear that $\theta$ is a polygonal line on $[t_1,\infty)$.


\begin{figure}[h]
$$\begin{picture}(290,230)
\put(2,150){$0$}
\put(0,160){\vector(1,0){300}}
\put(10,25){\vector(0,1){215}}
\put(290,150){$t$}
\put(110,40){$\theta(t)$}
{\thicklines
\put(20,140){\line(1,-2){30}}
\put(50,80){\line(4,-1){60}}
\put(110,65){\line(1,0){168}}
}
\put(110,65){\line(4,1){60}}
\put(170,80){\line(3,2){90}}
\put(20,140){\circle*{2}}
\put(16,166){$t_{j_1}$}
\put(20,160){\line(0,-1){20}}
\put(50,160){\line(0,-1){80}}
\put(46,166){$t_{j_2}$}
\put(50,80){\circle*{2}}
\put(110,65){\circle*{2}}
\put(106,166){$t_{j_3}$}
\put(110,160){\line(0,-1){95}}
\put(170,80){\circle*{2}}
\put(260,140){\circle*{2}}
\put(100,150){\circle*{2}}
\put(80,90){\circle*{2}}
\put(140,120){\circle*{2}}
\put(198,148){\circle*{2}}
\end{picture}$$
%\caption{}
\end{figure}



\begin{theorem}
For all $\tau\ge t_1$
$$\sup_{\substack{f\in\ld\\\|u(t_j,\cdot)\|_{\ld}\le\delta_j,\ j=1,2,\ldots,n}}\|u(\tau,\cdot)\|_{\ld}=e^{\theta(\tau)}.$$
\end{theorem}

\section{Optimal recovery of the solution of the heat equation}
The considered extremal problem is closely connected with the problem of optimal recovery of the solution of the heat equation from inaccurate observations of the solution at time moments $t_1,\ldots,t_n$.



Assume that we know functions $y_j\in\ld$, $j=1,\ldots,n$, such
that
$$\|u(t_j,\cdot)-y_j(\cdot)\|_{\ld}\le\delta_j,\quad j=1,\ldots,n.$$



What is the best way to use this information to recover the
temperature distribution at the time $\tau\ne t_j$, $1\le
j\le n$, that is to recover the function $u(\tau,\cdot)$?


We admit as recovery methods arbitrary maps $m\colon(\ld)^n\to\ld$. For a fixed method $m$ the quantity
\begin{multline*}
e_\tau(\ld,\delta,m)\\
=\sup_{\substack{f,y_1,\ldots,y_n\in\ld\\
\|u(t_j,\cdot)-y_j(\cdot)\|_{\ld}\le\delta_j,\ j=1,\ldots,n}}
\|u(\tau,\cdot)-m(y)(\cdot)\|_{\ld},
\end{multline*}
where $u$ is the solution of the heat equation with the initial function $f$, $\delta=(\delta_1,\ldots,\delta_n)$, and $y=(y_1,\ldots,y_n)$, is called the error of the method $m$.

We are interested in the value
$$E_\tau(\ld,\delta)=\inf_{m\colon(\ld)^n\to\ld}e_\tau(\ld,\delta,m),$$
which is called the error of optimal recovery and in the
method $\wm$, for which the infinum is attained that is in
the method $\widehat m$ for which
$$E_\tau(\ld,\delta)=e_\tau(\ld,\delta,\wm).$$
We call this method the optimal recovery method.


Let $t_{s_j}$, $j=1,\ldots,r$, be points of break of $\theta$. For $\tau\in(t_{s_j},t_{s_{j+1}})$ put
\begin{align*}
\wl_{s_j}&=\frac{t_{s_{j+1}}-\tau}{t_{s_{j+1}}-t_{s_j}}\left(\frac{
\delta_{s_{j+1}}}{\delta_{s_j}}\right)^{\frac{2(\tau-t_{s_j})}
{t_{s_{j+1}}-t_{s_j}}},\\
\wl_{s_{j+1}}&=\frac{\tau-t_{s_j}}{t_{s_{j+1}}-t_{s_j}}\left(\frac{
\delta_{s_j}}{\delta_{s_{j+1}}}\right)^{\frac{2(t_{s_{j+1}}-\tau)}
{t_{s_{j+1}}-t_{s_j}}
}.
\end{align*}

\begin{theorem}
For all $\tau\ge t_1$ \ $E_\tau(\ld,\delta)=e^{\theta(\tau)}$.
If $\tau\in(t_{s_j},t_{s_{j+1}})$, then for all $\gamma_j$ such that
$$\wl_{s_{j+1}}|\gamma_j(\xi)|^2e^{2|\xi|^2(t_{s_j}-\tau)}+\wl_{s_j}
|1-\gamma_j(\xi)|^2e^{2|\xi|^2(t_{s_{j+1}}-\tau)}\le\wl_{s_j}\wl_{s_{j+1}},$$
all methods
$$m(y)(t)=(K_j*y_{s_j})(t)+(L_{j+1}*y_{s_{j+1}})(t),$$
where
$$FK_j(\xi)=\gamma_j(\xi)e^{|\xi|^2(t_{s_j}-\tau)},\quad FL_{j+1}(\xi)=(1-\gamma_j(\xi))e^{|\xi|^2(t_{s_{j+1}}-\tau)},$$
are optimal.
For $\tau=t_{s_j}$, $j=1,\ldots,r$, methods $m(y)(t)=y_{s_j}(t)$ are optimal and for $\tau>t_{s_r}$ the method
$$m(y)=F^{-1}(e^{-|\xi|^2(\tau-t_{s_r})}Fy_{s_r}(\xi))(x)$$
is optimal.
\end{theorem}

The condition
$$\wl_{s_{j+1}}|\gamma_j(\xi)|^2e^{2|\xi|^2(t_{s_j}-\tau)}+\wl_{s_j}
|1-\gamma_j(\xi)|^2e^{2|\xi|^2(t_{s_{j+1}}-\tau)}\le\wl_{s_j}\wl_{s_{j+1}}$$
may be rewritten in the form
$$\left|\gamma_j(\xi)-\frac{\mu_1}{\mu_1+\mu_2}\right|\le
\frac{\sqrt{\mu_1\mu_2}\sqrt{\mu_1+\mu_2-1}}{\mu_1+\mu_2},$$
where
$$\mu_1=\wl_{s_j}e^{-2|\xi|^2(t_{s_j}-\tau)},\quad\mu_2=\wl_{s_{j+1}}
e^{-2|\xi|^2(t_{s_{j+1}}-\tau)}.$$


It can be shown that $\mu_1+\mu_2\ge1$ for all $\xi\in\mathbb R^d$. Thus, $\gamma_j(\xi)$ may be chosen from the interval
$$\left[\frac{\mu_1}{\mu_1+\mu_2}-\frac{\sqrt{\mu_1\mu_2}\sqrt{\mu_1+\mu_2-1}}
{\mu_1+\mu_2},\frac{\mu_1}{\mu_1+\mu_2}+\frac{\sqrt{\mu_1\mu_2}\sqrt{\mu_1+\mu_2-1}}
{\mu_1+\mu_2}\right].$$

Note that optimal method of recovery uses not more than two observations. To find these observation we have to construct the set $M$ and the polygonal line $\theta$. Then we have to find the nearest points of break of $\theta$ to the point $\tau$. The observations at these points are those that use in optimal method of recovery.



Note also that we can make more precise points of observation which are not on the polygonal line. Suppose that for some $t_m$, $t_{s_j}<t_m<t_{s_{j+1}}$ and
$$\theta(t_m)<\log\delta_m.$$

Then optimal recovery method gives the error less than $\delta_m$. Indeed
$$\|u(t_m,\cdot)-\wm(y)(\cdot)\|_{\ld}\le e^{\theta(t_m)}<\delta_m.$$

\begin{figure}[h]
$$\begin{picture}(290,230)
\put(2,150){$0$}
\put(0,160){\vector(1,0){300}}
\put(10,25){\vector(0,1){215}}
\put(290,150){$t$}
\put(110,40){$\theta(t)$}
{\thicklines
\put(20,140){\line(1,-2){30}}
\put(50,80){\line(3,-1){60}}
\put(110,60){\line(5,-1){80}}}
\put(50,160){\line(0,-1){80}}
\put(46,166){$t_{j_s}$}
\put(50,80){\circle*{2}}
\put(110,60){\circle*{2}}
\put(106,166){$t_{j_{s+1}}$}
\put(110,160){\line(0,-1){100}}
\put(170,80){\circle*{2}}
\put(80,160){\line(0,-1){70}}
\put(76,166){$t_j$}
\put(100,150){\circle*{2}}
\put(80,90){\circle*{2}}
\put(140,120){\circle*{2}}
\end{picture}$$
%\caption{}
\end{figure}

\section{Optimal recovery of signals}


The Hardy--Littlewood--P\'olya inequality may be considered as the solution of the following extremal problem
$$\|x^{(k)}\|_{\lt}\to\max,\quad\|x\|_{\lt}\le\delta_1,\quad
\|x^{(n)}\|_{\lt}\le\delta_2.$$


We will consider a slightly different extremal problem which closely connected with problems of signal reconstruction
$$\|x^{(k)}\|_{\lt}\to\max,\quad\|Fx\|_{\Ld}\le\delta,\quad
\|x^{(n)}\|_{\lt}\le1,$$
where $Fx$ is the Fourier transform of $x$ and $\Ds=[-\sigma,\sigma]$, $\sigma>0$.


We consider the problem of optimal recovery of $x^{(k)}$ knowing the Fourier transform of $x$ giving with some error on $\Ds$.


We assume that $x\in\WR$,
$$\WR=\{x\in\lt:x^{(n-1)}\mbox{ is loc. abs. cont. },\ \|x^{(n)}\|_{\lt}\le1\}.$$

Moreover, we assume that for any $x\in\WR$ we know a function $y\in\Ld$ such that
$$\|Fx-y\|_{\Ld}\le\delta.$$


The problem is to recover $x^{(k)}$ knowing $y$.


Any method of recovery is a map $m\colon\Ld\to\lt$. The error of such method is defined as follows
$$e_\sigma(m)=\sup_{\substack {x\in\WR,\ y\in\Ld\\\|Fx-y\|_{\Ld}\le\delta}}
\|x^{(k)}-m(y)\|_{\lt}.$$

We are interested in the value
$$E_\sigma=\inf_{m\colon\Ld\to\lt}e_\sigma(m),$$
which is called the error of optimal recovery and in the
method $\wm$, for which the infinum is attained that is in
the method $\widehat m$ for which
$$E_\sigma=e_\sigma(\wm).$$
We call this method the optimal recovery method.


Set
\begin{gather*}
\ws=\left(\dfrac
nk\right)^{\frac1{2(n-k)}}\left(\dfrac{2\pi}{\delta^2}\right)^{\frac1{2n}},\quad
\sigma_0=\min\{\sigma,\ws\},\\
\wa(\xi)=\left(1+\dfrac
n{n-k} \left(\dfrac nk\right)^{\frac
k{n-k}}\left(\dfrac\xi{\sigma_0}\right)^{2n} \right)^{-1}.
\end{gather*}

\begin{theorem}
%\begin{equation}\label{e1}
$$E=\sigma_0^k\sqrt{\dfrac{n-k}{2 \pi n}\left(\dfrac kn\right)^{\frac
k{n-k}}\delta^2+\sigma_0^{2(k-n)}}.$$
%\end{equation}
For all $\alpha$ such that
%\begin{equation}\label{ea}
$$|\alpha(\xi)-\wa(\xi)|\le\sqrt{\wa^2(\xi)+\wa(\xi)
\left(\left(\frac\xi{\sigma_0}\right)^{2(n-k)}-1\right)},$$
%\end{equation}
methods
%\begin{equation}\label{am}
$$m(y)(t)=\frac1{2\pi}\int_{\Ds}(i\xi)^k\alpha(\xi)y(\xi)e^{i\xi t}\,d\xi$$
%\end{equation}
are optimal.
\end{theorem}

For a fixed error of input data consider the error of optimal recovery
$E_\sigma$ as a function of $\sigma$. The larger interval $(-\sigma,\sigma)$ we take the less error we have. But beginning with $\ws$ the error $E_\sigma$ does
not change.

\begin{figure}
$$\begin{picture}(300,150)
\put(0,10){\vector(1,0){200}}
\put(10,0){\vector(0,1){160}}
\put(188,0){$\sigma$}
\put(-4,140){$E_\sigma$}
\put(116,-2){$\ws$}
\qbezier(20,150)(40,50)(120,50)
\put(120,50){\line(1,0){60}}
\put(120,10){\line(0,1){40}}
\end{picture}$$
\caption{}\label{A}
\end{figure}


Consequently, for $\sigma>\ws$ the observed information becomes partially redundant. To avoid this case the following condition
$$\delta^2\sigma^{2n}\le2\pi\left(\frac nk\right)^{\frac n{n-k}}$$
should hold. This inequality may be considered as some ``uncertain
principle''.


Now consider the set of optimal filters $\alpha$ obtained in the previous theorem. Let $n=2$ and $k=1$. Then this set is defined as follows
$$\left|\alpha(\sigma_0t)-\frac1{1+4t^2}\right|\le\frac{t|2t^2-1|}{1+4t^2}.$$


\begin{corollary}
For all
$$0\le\sigma'\le\left(\frac{n-k}n\right)^{\frac1{2k}}
\left(\frac kn\right)^{\frac1{2(n-k)}}\sigma_0,$$
methods
\begin{multline*}
m(y)(t)=\frac1{2\pi}\int_{|\xi|\le\sigma'}(i\xi)^ky(\xi)
e^{i\xi t}\,d\xi\\
+\frac1{2\pi}\int_{\sigma'\le|\xi|\le\sigma_0}(i\xi)^k\alpha(\xi)
y(\xi)e^{i\xi t}\,d\xi
\end{multline*}
%\end{equation}
are optimal.
\end{corollary}


Note that obtained methods do not smooth the input data on the interval $[-\sigma',\sigma']$.

\section{Scheme of proof}

It can be easily obtained the lower bound
$$E_\sigma\ge\sup_{\substack{x\in\WR\\\|Fx\|_{\Ld}\le\delta}}
\|x^{(k)}\|_{\lt}.$$


Passing to the Fourier transform and using the Plancherel theorem we obtain the extended extremal problem with measures
\begin{multline*}
\iR\xi^{2k}\,d\mu(\xi)\to\max,\quad\int_{\Ds}\,d\mu(\xi)\le\frac{\delta^2}{2\pi},
\\\iR\xi^{2n}\,d\mu(\xi)\le1,\quad d\mu(\xi)\ge0.
\end{multline*}


Using the Lagrange principle we obtain that $E_\sigma^2\ge\wl_1\delta^2/(2\pi)+\wl_2$,
where $\wl_1$ and $\wl_2$ are Lagrange multipliers.

To obtain the upper bound we have to consider methods
$$m(y)(t)=\frac1{2\pi}\int_{\Ds}(i\xi)^k\alpha(\xi)y(\xi)e^{i\xi t}\,d\xi$$
and to obtain the error of these methods.


For simplicity we consider the case $\sigma=\infty$. Passing to the Fourier transform we get the following extremal problem
\begin{multline*}
\frac1{2\pi}\iR|(i\xi)^kFx(\xi)-(i\xi)^k\alpha(\xi)y(\xi)|^2\,d\xi\to\max,\\
\iR|Fx(\xi)-y(\xi)|^2\,d\xi\le\delta^2,\quad\frac1{2\pi}\iR\xi^{2n}|Fx(\xi)|^2\,d\xi
\le1.
\end{multline*}

Put $z=Fx-y$. Then the extremal problem has the form
\begin{multline*}
\frac1{2\pi}\iR\xi^{2k}|\alpha(\xi)z(\xi)+(1-\alpha(\xi))Fx(\xi)|^2\,d\xi\to\max,\\
\iR|z(\xi)|^2\,d\xi\le\delta^2,\quad\frac1{2\pi}\iR\xi^{2n}|Fx(\xi)|^2\,d\xi
\le1.
\end{multline*}


By the Caushy--Schwarz inequality we have
\begin{multline*}
|\alpha(\xi)z(\xi)+(1-\alpha(\xi))Fx(\xi)|^2\\
\le\left(\frac{\alpha^2(\xi)}{\wl_1}+
\frac{(1-\alpha(\xi))^2}{\wl_2\xi^{2n}}\right)(\wl_1|z(\xi)|^2+
\wl_2\xi^{2n}|Fx(\xi)|^2).
\end{multline*}

Using this inequality we obtain that
$$E^2_\sigma\le S(\alpha)\left(\wl_1\frac{\delta^2}{2\pi}+\wl_2\right),$$
where
$$S(\alpha)=\sup_{\xi\in\mathbb R}\left(\xi^{2k}\left(\frac{\alpha^2(\xi)}{\wl_1}+
\frac{(1-\alpha(\xi))^2}{\wl_2\xi^{2n}}\right)\right).$$



For all $\alpha$ such that
\begin{equation}\label{i}
\xi^{2k}\left(\frac{\alpha^2(\xi)}{\wl_1}+
\frac{(1-\alpha(\xi))^2}{\wl_2\xi^{2n}}\right)\le1
\end{equation}
$S(\alpha)\le1$ and the upper bound coincides with the lower bound.
It is easy to show that inequality \eqref{i} is equivalent to the inequality from the theorem.

\begin{thebibliography}{11}

\bibitem{MOs2} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu. Optimal recovery of functionals based on inaccurate data, Math. Notes {\bf50}:6 (1991) 1274--1279.
\bibitem{MOs} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu. Optimal recovery of values of functions and their derivatives from inaccurate data on the Fourier transform, Sbornic: Mathematics {\bf195} (2004) 1413--1459.

\bibitem{MO1} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu. How best to recover a function from
its inaccurately given spectrum? Math. Notes {\bf92}:1 (2012) 51--58.

\bibitem{MOT} Magaril-Il'yaev~G.~G., Osipenko~K.~Yu., Tikhomirov~V.~M. Indefinite knowledge about an object and accuracy of its recovery
methods, Probl. of Inform. Transm. {\bf39} (2003) 104--118.

\bibitem{MO} Marchuk~A.~G., Osipenko~K.~Yu. Best approximation of functions specified
with an error at a finite number of points, Math. Notes {\bf17}:3 (1975) 207--212.

\bibitem{MR} Micchelli~C.~A., Rivlin~T.~J. A survey of optimal
recovery. In: Optimal Estimation in Approximation Theory
(C.~A.~Micchelli and T.~J.~Rivlin, eds.). Plenum Press, New York,
1977, 1--54.

\bibitem{Os} Osipenko~K.~Yu. {\it Optimal Recovery of Analytic Functions},
Nova Science Publ., Inc., Huntington, New York 2000.

\bibitem{Os1} Osipenko~K.~Yu. Optimal recovery of linear operators in non-Euclidean metrics, Sbornic: Mathematics {\bf205}:10 (2014) 1442--1472.


\bibitem{TWW} Traub~J.~F., Wasilkowski~G.~W., Wo\'zniakowski~H. {\it Information-Based Complexity}, Academic Press, New York 1988.

\bibitem{TW} Traub J.~F., Wo\'zniakowski H. {\it A General Theory of
Optimal Algorithms}, New York: Academic Press, 1980.


\end{thebibliography}

\end{document}