\documentclass[12pt,draft,a4paper]{amsart}
\usepackage{amsmath,amsthm}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{cite}
%\usepackage{abstract}
%\usepackage{srctex}
\tolerance 1000

\newtheorem{theorem}{Теорема}
\newtheorem*{lemma}{Лемма}
\newtheorem{proposition}{Предложение}
\newtheorem*{corollary}{Следствие}
\renewcommand{\thesection}{\S \arabic{section}}
\newtheorem*{theorem1}{Теорема~$\mathbf1'$}

\DeclareMathOperator*{\infp}{inf\vphantom p}
\DeclareMathOperator*{\vraisup}{vraisup}
\DeclareMathOperator*{\IM}{Im}
\DeclareMathOperator*{\RE}{Re}
\DeclareMathOperator*{\gr}{gr}
\DeclareMathOperator{\sn}{sn}
\DeclareMathOperator*{\spann}{span}
\DeclareMathOperator{\cn}{cn}
\DeclareMathOperator{\ctn}{ctn}
\DeclareMathOperator{\dn}{dn}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\arth}{arth}
\DeclareMathOperator{\thh}{th}
\DeclareMathOperator{\Aff}{Aff}
\DeclareMathOperator{\co}{co}
\DeclareMathOperator{\bco}{bco}
\DeclareMathOperator*{\ulim}{\underline{\lim}}

\newcommand*{\ov}{\overline}
\newcommand*{\ei}{e^{i\theta}}
\newcommand*{\la}{\langle}
\newcommand*{\ra}{\rangle}
\newcommand*{\wt}{\widetilde\Theta}
\newcommand*{\wl}{\widetilde l}
\newcommand*{\pph}[1]{\Phi_{\lambda,#1,\beta}}


\begin{document}
\pagestyle{plain}




\begin{flushright}
УДК 517.5
\end{flushright}

\bigskip

\title{НАИЛУЧШЕЕ ПРИБЛИЖЕНИЕ ФУНКЦИЙ, ЗАДАННЫХ С ПОГРЕШНОСТЬЮ В КОНЕЧНОМ ЧИСЛЕ ТОЧЕК}


\author{А.~Г.~Марчук, К.~Ю.~Осипенко}




\maketitle

\begin{center}
\parbox{10.2cm}{\footnotesize
\hspace{20pt}Доказывается, что для выпуклых и центрально-сим\-мет\-рич\-ных классов функций среди наилучших в определенном смысле методов приближения по значениям, заданным с погрешностью в конечном числе точек, существует линейный метод. Для некоторых простейших классов строятся линейные наилучшие методы и оценивается их погрешность. Библ. 3 назв.}
\end{center}

\bigskip

{\bf1.} Рассмотрим задачу приближения функции $f(x)$, $x\in[a, b]$ из некоторого класса $W$ по ее приближенным значениям $f_k=f(x_k)+\rho_k$, $x_k\in[a, b]$, $k=1,\ldots,n$, при условии $\|\rho\|\le\delta$; здесь $\|\cdot\|$ --- какая-либо норма в пространстве векторов $\rho=(\rho_1,\ldots,\rho_n)$. Всякий метод приближения функции $f(x)$, использующий информацию только о значениях $f_1,\ldots,f_n$, может быть представлен в виде некоторой функции $f(x)\approx S(x,\delta,f_1,\ldots,f_n)$. Погрешностью данного метода в точке $x\in[a,b]$ на классе $W$ назовем величину
$$r_S(x,\delta,x_1,\ldots,x_n)=\sup_{\substack{f\in W\\\|\rho\|\le\delta}}|f(x)-S(x,\delta,f_1,\ldots,f_n)|.$$
Величину
$$r(x,\delta,x_1,\ldots,x_n)=\inf_Sr_S(x,\delta,x_1,\ldots,x_n)$$
будем называть наилучшей оценкой погрешности в точке $x$, а метод $S_0(x,\delta,f_1,\ldots,f_n)$ --- наилучшим методом, если при всех $x\in[a,b]$ имеет место равенство
$$r(x,\delta,x_1,\ldots,x_n)=r_{S_0}(x,\delta,x_1,\ldots,x_n).$$

Интересно рассмотреть задачу минимизации наилучшей оценки погрешности в точках $x\in[a,b]$ за счет выбора точек $x_1,\ldots,x_n$. Назовем величину
$$r_n(\delta)=\inf_{\{x_k\}}\|r(x,\delta,x_1,\ldots,x_n)\|_{C[a, b]}$$
наилучшей оценкой погрешности приближения на $[a,b]$, а точки $x_1^0,\ldots,x_n^0$ --- оптимальными узлами, если имеет место равенство
$$r_n(\delta)=\|r(x,\delta,x_1^0,\ldots,x_n^0)\|_{C[a, b]}.$$

Для случая $\delta=0$ (приближение по точным значениям) соответствующие задачи для класса функций, аналитически продолжаемых в некоторую односвязную и симметричную относительно вещественной оси область и ограниченных в ней, рассматривались в работе \cite{1}.

{\bf2.} Задача построения наилучшего метода приближения функции по ее значениям, заданным с погрешностью, и нахождения его погрешности может быть сформулирована в более общем виде. Пусть $L,l_1,\ldots,l_n$ --- линейные функционалы на линейном пространстве $X$. Ставится задача приближения функционала $L(x)$ на некотором множестве $W \subset X$ на основании информации о значениях $\wl_k(x)=l_k(x)+\rho_k$, где $x\in W$, $\|\rho\|\le\delta$. Оказывается, что для довольно широкого класса множеств $W$ среди наилучших методов приближения (в смысле данного выше определения) существует линейный.

\begin{theorem}\label{T1}
Пусть $W$ --- выпуклое, центрально-симметричное подмножество линейного пространства $X$ с центром симметрии $0$. Тогда справедливо равенство
$$\infp_S\sup_{\substack{x\in W\\\|\rho\|\le\delta}}|L(x)-S(\delta,\wl_1(x),\ldots, \wl_n(x))|=\sup_{\substack{x\in W\\\|\ov l(x)\|\le\delta}}|L(x)|,$$
где $\ov l(x)=(l_1(x),\ldots,l_n(x))$; причем существуют числа $D_j(\delta)$ такие, что
$$\sup_{\substack{x\in W\\\|\rho\|\le\delta}}\biggl|L(x)-\sum_{j=1}^nD_j(\delta)\wl_j(x)\biggr|=
\sup_{\substack{x\in W\\\|\ov l(x)\|\le\delta}}|L(x)|.$$
\end{theorem}

\begin{proof}
Обозначим через $Y$ замыкание множества точек $(n+1)$-мерного пространства
$$(y_0,y_1,\ldots,y_n)=(L(x),\wl_1(x),\ldots,\wl_n(x)),$$
где $x\in W$, $\|\rho\|\le\delta$. Нетрудно показать, что множество $Y$ будет выпуклым и центрально-симметричным с центром симметрии в начале координат. Положим
$$D_0(\delta)=\sup_{(y_0,0,\ldots,0)\in Y}y_0.$$
Нетрудно показать, что
\begin{equation}\label{1}
D_0(\delta)=\sup_{\substack{x\in W\\\|\ov l(x)\|\le\delta}}|L(x)|.
\end{equation}
Действительно,
$$D_0(\delta)=\sup_{\substack{x\in W\\\wl_k(x)=0,\ k=1,\ldots,n\\\|\rho\|\le\delta}} L(x)=\sup_{\substack{x\in W\\\ov l(x)=-\rho\\\|\rho\|\le\delta}}L(x)=
\sup_{\substack{x\in W\\\|\ov l(x)\|\le\delta}}L(x).$$
Так как множество $W$ центрально-симметрично, то
$$\sup_{\substack{x\in W\\\|\ov l(x)\|\le\delta}}L(x)=
\sup_{\substack{x\in W\\\|\ov l(x)\|\le\delta}}|L(x)|.$$

Пусть $D_0(\delta)<\infty$. Вследствие выпуклости множества $Y$ через каждую его граничную точку можно провести опорную гиперплоскость. Уравнение опорной гиперплоскости, проходящей через точку $(D_0(\delta),0,\ldots,0)$, можно записать в виде
$$y_0=\sum_{j=1}^nD_j(\delta)y_j+D_0(\delta).$$
Плоскостью, симметричной этой плоскости относительно начала координат, будет плоскость
$$y_0=\sum_{j=1}^nD_j(\delta)y_j-D_0(\delta).$$
Из симметричности множества $Y$ относительно начала координат следует, что эта плоскость также будет опорной к множеству $Y$. Множество $Y$ находится между этими плоскостями и поэтому для всех точек $Y$
$$\biggl|y_0-\sum_{j=1}^nD_j(\delta)y_j\biggr|\le D_0(\delta);$$
вспоминая смысл координат $y_j$, перепишем это неравенство в виде
$$\biggl|L(x)-\sum_{j=1}^nD_j(\delta)\wl_j(x)\biggr|\le D_0(\delta)$$
при всех $x\in W$, $\|\rho\|\le\delta$. Таким образом,
\begin{equation}\label{2}
\sup_{\substack{x\in W\\\|\rho\|\le\delta}}\biggl|L(x)-\sum_{j=1}^nD_j(\delta)\wl_j(x)\biggr|\le D_0(\delta).
\end{equation}

Из равенства \eqref{1} следует, что для любого $\varepsilon >0$ существует элемент $x_\varepsilon\in W$ такой, что $|L(x_\varepsilon)|>D_0(\delta)-\varepsilon$ и $\wl_1(x_\varepsilon)=\ldots=\wl_n(x_\varepsilon)=0$. Теми же свойствами будет обладать элемент $-x_\varepsilon$. Пусть задан произвольный метод приближения, тогда для элементов $\pm x_\varepsilon$ приближенное значение функционала $L(\pm x_\varepsilon)$ равно $S(\delta,\wl_1(\pm x_\varepsilon),\ldots,\wl_n(\pm x_\varepsilon))=S(\delta,0,\ldots,0)=S^0.$
Из неравенств
\begin{multline*}
|L(x_\varepsilon)-S^0|+|L(-x_\varepsilon)-S^0|\ge|L(x_\varepsilon)-S^0+(S^0-
L(-x_\varepsilon))|\\
>2(D_0(\delta)-\varepsilon)
\end{multline*}
следует, что для одного из элементов $\pm x_\varepsilon$ ошибка приближенного значения больше $D_0(\delta)-\varepsilon$. В силу произвольности $\varepsilon$ и рассматриваемого метода получаем неравенство
$$\infp_S\sup_{\substack{x\in W\\\|\rho\|\le \delta}}|L(x)-S(\delta,\wl_1(x),\ldots,\wl_n(x))|\ge D_0(\delta).$$
Сравнивая последнее неравенство с неравенством \eqref{2} и замечая, что множество всевозможных методов содержит линейные, получаем утверждение теоремы.

В случае, когда $D_0(\delta)=\infty$, легко показать, что
$$\infp_S \sup_{\substack{x\in W\\\|\rho\|\le\delta}}|L(x) - S(\delta,\wl_1(x),\ldots,\wl_n(x))|=\infty.$$

Тогда всякий метод, в частности всякий линейный метод, будет наилучшим, и утверждение теоремы остается в силе.
\end{proof}

\begin{corollary}
Положим
$$\varphi_j^\delta(\varepsilon)=\sup_{\substack{x\in W\\\|\ov l(x)-\varepsilon e_j\|\le\delta}}L(x),$$
где $e_j=(\underbrace{0,\ldots,0}_{j-1},1,0,\ldots,0)$. Если функция $\varphi_j^\delta(\varepsilon)$ дифференцируема в нуле, то
$$D_j(\delta)=\frac{d\varphi_j^\delta(\varepsilon)}{d\varepsilon}\bigg|_{\varepsilon=0}.$$
\end{corollary}

Доказательство следствия непосредственно вытекает из доказательства теоремы при рассмотрении сечения множества точек $Y$ плоскостью $(y_0,y_j)$.

Доказательство теоремы~\ref{T1} является модификацией доказательства соответствующего утверждения для случая $\delta=0$ из работы \cite{2} (см. также \cite{3}).

Из теоремы~\ref{T1} и следствия вытекает

\begin{theorem1}
Пусть $W$ --- выпуклый и центрально-симметричный с центром симметрии $0$ класс функций. Тогда среди наилучших методов существует линейный
$$S_0(x,\delta,f_1,\ldots,f_n)=\sum_{j=1}^nD_j(\delta,x)f_j$$
с погрешностью
$$r(x,\delta,x_1,\ldots,x_n)=\sup_{\substack{f\in W\\\|\ov f\|\le\delta}}|f(x)|,$$
где $\ov f=(f(x_1),\ldots,f(x_n))$; причем если функция
$$\varphi_j^\delta(\varepsilon,x)=\sup_{\substack{f\in W\\\|\ov f-\varepsilon e_j\|\le\delta}}f(x)$$
дифференцируема в нуле по $\varepsilon$, то $D_j(\delta,x)=\dfrac{d\varphi_j^\delta(\varepsilon,x)}{d\varepsilon} \bigg|_{\varepsilon=0}$.
\end{theorem1}

Рассмотрим некоторые простейшие классы функций и построим для них линейные наилучшие методы приближения. В дальнейшем мы будем использовать следующие нормы в пространстве векторов:
$$\|\rho\|_p=\biggl(\sum_{j=1}^n|\rho_j|^p\biggr)^{1/p},\quad1\le p\le\infty,$$
а наилучшие оценки погрешности снабжать соответствующим индексом.

{\bf3.} Рассмотрим типичный для классической интерполяции класс $W^{(n)}(M;a,b)$ функций, имеющих непрерывную производную порядка $n$, ограниченную константой $M$, где $n$ --- число точек, в которых заданы приближенные значения.

\begin{theorem}\label{T2}
При измерении погрешности данных в $\|\cdot\|_p$ интерполяция Лагранжа
\begin{gather*}
S_0(x,\delta,f_1,\ldots,f_n)=\sum_{j=1}^nP_j(x)f_j,\\
P_j(x)=\prod_{i\ne j}\frac{x-x_i}{x_j-x_i},
\end{gather*}
является наилучшим методом приближения в классе $W^{(n)}(M;a,\linebreak b)$. При всех $1\le p\le\infty$. Для погрешности наилучшего метода имеет место равенство
\begin{equation}\label{3}
r_p(x,\delta,x_1,\ldots,x_n)=\frac{M|\omega_n(x)|}{n!}+\delta\|\ov P(x)\|_q;
\end{equation}
здесь $\omega_n(x)=\displaystyle\prod_{i=1}^n(x-x_i)$, $\ov P(x)=(P_1(x),\ldots,P_n(x))$ и $\dfrac1p+\dfrac1q=1$.
\end{theorem}

\begin{proof}
Очевидно, $W^{(n)}(M;a,b)$ удовлетворяет условиям теоремы~$1'$, следовательно,
$$r_p(x,\delta,x_1,\ldots,x_n)=\sup_{\substack{f\in W^{(n)}(M;a,b)\\\|\ov f\|_p\le\delta}}|f(x)|.$$
Оценим $r_p(x,\delta,x_1,\ldots,x_n)$ снизу. Рассмотрим функцию
$$f(y)=\frac{M|\omega_n(y)|}{n!}\sign\omega_n(x)+\sum_{j=1}^nP_j(y)\sign P_j(x);$$
здесь при $p=1$
$$\rho_j=\begin{cases}
0&\mbox{ при }|P_j(x)|\ne\displaystyle\max_k|P_k(x)|,\\
\delta&\mbox{ при }|P_j(x)|=\displaystyle\max_k|P_k(x)|;\end{cases}$$
при $1<p<\infty$ \ $\rho_j=\delta\dfrac{|P_j(x)|^{q-1}}{\|\ov P(x)\|_q^{q-1}}$; при $p=\infty$ \ $\rho_j=\delta$.

Нетрудно проверить, что $f(y)\in W^{(n)}(M,a,b)$ и $\|\ov f\|_p=\|\rho\|_p=\delta$. Таким образом,
\begin{equation}\label{4}
r_p(x,\delta,x_1,\ldots,x_n)\ge f(x)=\frac{M|\omega_n(x)|}{n!}+\delta\|\ov P(x)\|_q.
\end{equation}
Оценим погрешность интерполяционной формулы Лагранжа на классе $W^{(n)}(M,a,b)$:
\begin{multline}\label{5}
\biggl|f(x)-\sum_{j=1}^nP_j(x)f_j\biggr|\le\biggl|f(x)-\sum_{j=1}^nP_j(x)f(x_j)\biggr|
+\biggr|\sum_{j=1}^nP_j(x)\rho_j\biggr|\\
\le\frac{M|\omega_n(x)|}{n!}+\|\rho\|_p\|\ov P(x)\|_q\le\frac{M|\omega_n(x)|}{n!}+\delta\|\ov P(x)\|_q.
\end{multline}
Отсюда следует
$$r_p(x,\delta,x_1,\ldots,x_n)\le\frac{M|\omega_n(x)|}{n!}+\delta\|\ov P(x)\|_q,$$
что вместе с неравенством \eqref{4} доказывает равенство \eqref{3}. Оценка \eqref{5} показывает, что интерполяция Лагранжа является наилучшим методом приближения.
\end{proof}

{\bf4.} Обозначим через $H_\omega$ класс функций, модуль непрерывности которых не превосходит фиксированного модуля непрерывности $\omega(\varepsilon)$. Для этого класса можно построить целое множество линейных наилучших методов, если погрешность данных измеряется в $\|\rho\|_\infty=\displaystyle\max_{1\le j\le n}|\rho_j|$.

\begin{theorem}\label{T3}
Пусть $a\le x_1<x_2<\ldots<x_n\le b$. При измерении погрешности данных в $\|\cdot\|_\infty$ методы
\begin{multline}\label{6}
S_0^\lambda(x,\delta,f_1,\ldots,f_n)\\
=\begin{cases}
f_1&\mbox{ при }x\in\left[a,\dfrac{x_1+x_2}2\right),\\[10pt]
f_k&\mbox{ при }x\in\left(\dfrac{x_{k-1}+x_k}2,\dfrac{x_k+x_{k+1}}2\right),\\
&\hspace{125pt}k=2,\ldots,n-1,\\
f_n&\mbox{ при }x\in\left(\dfrac{x_{n-1}+x_n}2,b\right],\\[8pt]
\lambda_kf_k+(1-\lambda_k)f_{k+1}&\mbox{ при }x=\dfrac{x_k+x_{k+1}}2,\ k=1,\ldots,n-1,
\end{cases}
\end{multline}
являются наилучшими методами для класса $H_\omega$ при всех $\lambda=(\lambda_1,\ldots,\lambda_{n-1})$, $\lambda_k\in[0,1]$, $k=1,\ldots,n-1$; для
наилучшей оценки погрешности имеет место равенство
\begin{equation}\label{7}
r_\infty(x,\delta,x_1,\ldots,x_n)=\delta+\omega\left(\min_{1\le i\le n}|x-x_i|\right).
\end{equation}
\end{theorem}

\begin{proof}
Из теоремы~$1'$ следует, что для доказательства равенства \eqref{7} достаточно доказать
равенство
$$\sup_{\substack{f\in H_\omega\\\|\ov f\|_\infty\le\delta}}|f(x)|=\delta+\omega\left(\min_{1\le i\le n}|x-x_i|\right).$$
Пусть $f(x)\in H_\omega$ и $\|\ov f\|_\infty\le\delta$, тогда
$$|f(x)|\le|f(x)-f(x_k)|+|f(x_k)|\le\delta+\omega(|x - x_k|).$$
Выберем $x_k$ из условия $|x-x_k|=\displaystyle\min_{1\le i\le n}|x-x_i|$. Имеем
\begin{equation}\label{8}
\sup_{\substack{f\in H_\omega\\\|\ov f\|_\infty\le\delta}}|f(x)|\le\delta+\omega\left(\min_{1\le i\le n}|x-x_i|\right).
\end{equation}
Так как функция $f(x)=\delta+\omega\left(\displaystyle\min_{1\le i\le n}|x-x_i|\right)$ принадлежит классу $H_\omega$ и $\|\ov f\|_\infty=\delta$, неравенство \eqref{8} обращается в равенство, что и доказывает равенство \eqref{7}.

Пусть $x\in\left(\dfrac{x_{k-1}+x_k}2,\dfrac{x_k+x_{k+1}}2\right)$. Покажем, что приближение $f(x)\approx f_k$ будет наилучшим. Действительно,
$$|f(x)-f_k|\le\delta+|f(x)-f(x_k)|\le\delta+\omega(|x-x_k|)=r_\infty(x,\delta,x_1,\ldots,
x_n).$$
Аналогично рассматриваются случаи $x\in\left[a,\dfrac{x_1+x_2}2\right)$ и
$x\in\left(\dfrac{x_{n-1}+x_n}2,b\right]$. Пусть теперь $x=\dfrac{x_k+x_{k+1}}{2}$. Рассмотрим приближение $f\left(\dfrac{x_k+x_{k+1}}{2}\right)\approx\lambda_kf_k+(1-\lambda_k)f_{k+1}$, где $\lambda_k\in[0,1]$. Имеем
\begin{multline*}
\left|f\left(\dfrac{x_k+x_{k+1}}{2}\right)-\lambda_kf_k-(1-\lambda_k)f_{k+1}\right|\\
\le\left|\lambda_k\left[f\left(\dfrac{x_k+x_{k+1}}{2}\right)-f(x_k)\right]\right.\\
\left.+(1-\lambda_k)\left[f\left(\dfrac{x_k+x_{k+1}}{2}\right)-f(x_{k+1})\right]\right|+
\delta\le\omega\left(\dfrac{x_{k+1}-x_k}2\right)+\delta\\
=r_\infty\left(\dfrac{x_k+x_{k+1}}{2},\delta,x_1,\ldots,x_n\right).
\end{multline*}
Следовательно, рассматриваемый метод является наилучшим при любом $k\in[0,1]$. Теорема доказана.
\end{proof}

\begin{corollary}
Для наилучшей оценки погрешности на $[a,b]$ в классе $H_\omega$ имеет место равенство
\begin{equation}\label{9}
r_n(\delta)=\delta+\omega\left(\frac{b-a}{2n}\right),
\end{equation}
а оптимальными узлами являются узлы
$$x_j^0=a+(2j-1)\frac{b-a}{2n},\quad j=1,\ldots,n.$$
\end{corollary}

\begin{proof}
Так как функция $\omega(\varepsilon)$ не убывает, задача нахождения узлов, минимизирующих $\|r_\infty(x,\delta,x_1,\ldots,x_n)\|_{C[a,b]}$, сводится к задаче нахождения узлов, минимизирующих
$$\left\|\max_{1\le i\le n}|x-x_i|\right\|_{C[a,b]}.$$
Решением последней задачи являются узлы $x_j^0=a+(2j-1)\dfrac{b-a}{2n}$, $j=1,\ldots,n$. Следовательно,
$$r_n(\delta)=\|r_\infty(x,\delta,x_1^0,\ldots,x_n^0)\|_{C[a,b]}=\delta+
\omega\left(\dfrac{b-a}{2n}\right).$$
\end{proof}

Из равенства \eqref{9} следует, что число узлов $n$ при приближении на классе $H_\omega$ разумно выбирать из условия $\omega\left(\dfrac{b-a}{2n}\right)\sim\delta$ (например, для класса функций, удовлетворяющих условию Липшица с константой $K$: $n\sim K \dfrac{b-a}{2\delta}$), дальнейшее увеличение не дает существенного выигрыша в точности приближения.

\bigskip

\noindent Московский государственный \hfill Поступило\\
университет им.~М.~В.~Ломоносова\hfill 9.IV.1974

\bigskip

\renewcommand{\refname}{ЦИТИРОВАННАЯ ЛИТЕРАТУРА}
\begin{thebibliography}{11}

\bibitem{1} О с и п е н к о~К.~Ю., Оптимальная интерполяция аналитических функций, Матем. заметки, {\bf12}, \No~4 (1972), 465--476.

\bibitem{2} С м о л я к~С.~А., Об оптимальном восстановлении функций и функционалов от них, Кандид. дисс., МГУ, 1965.

\bibitem{3} Б а х в а л о в~Н.~С., Об оптимальности линейных методов приближения операторов на выпуклых классах функций, Ж. вычисл. матем. и матем. физ., {\bf11}, \No~4 (1971), 1014--1018.

\end{thebibliography}


\end{document}
