\documentclass[12pt,draft,a4paper]{amsart} \usepackage{amsmath,amsthm} \usepackage[T2A]{fontenc} \usepackage[cp1251]{inputenc} \usepackage[english,russian]{babel} \usepackage{amsfonts} \usepackage{latexsym} \tolerance 1900 \renewcommand*{\proofname}{Доказательство} \DeclareMathOperator*{\cl}{cl} \DeclareMathOperator*{\co}{co} \DeclareMathOperator*{\spa}{span} \DeclareMathOperator*{\aff}{aff} \DeclareMathOperator*{\intt}{int} \newcommand*{\Rn}{\mathbb R^n} \newcommand*{\sj}{\sum_{j=1}^n} \newcommand*{\sk}{\sum_{j=1}^k} \newcommand*{\sm}{\sum_{j=1}^m} \newcommand*{\wx}{\widehat x} \newcommand*{\wa}{\widetilde a} \newtheorem{lemma}{Лемма} \newtheorem{theorem}{Теорема} \newtheorem{proposition}{Предложение} \newtheorem{corollary}{Следствие} \begin{document} \bigskip \begin{center}\bf \Large Федеральное агентство по образованию \smallskip \large Государственное образовательное учреждение высшего профессионального образования ``МАТИ'' - Российский государственный технологический университет\\ им. К.Э.Циолковского \vskip50pt \rm Кафедра "Высшая математика" \vskip 70pt \bf К.~Ю.~Осипенко \vskip20pt Теоремы отделимости в $\Rn$\\ и оптимальное восстановление \vskip 270pt Москва 2006 г. \end{center} \thispagestyle{empty} \newpage \section{Выпуклые множества} Пусть $x,y\in\Rn$. {\it Отрезком $($соединяющим $x$ и $y)$} называется множество $$[x,y]=\{\,z\in\Rn: z=(1-\alpha)x+\alpha y,\ 0\le\alpha\le1\,\}.$$ Непустое множество $A\subset\Rn$ называется {\it выпуклым}, если вместе с любыми двумя своими точками $x$, $y$ оно содержит отрезок $[x,y]$. Пустое множество считается выпуклым. Пусть $x_1,\ldots,x_k\in\Rn$. Вектор $$x=\sk\alpha_jx_j,$$ где $$\sj\alpha_j=1,\quad\alpha_j\ge0,\ j=1,\ldots,k,$$ называется {\it выпуклой комбинацией\/} векторов $x_1,\ldots,x_k$. \begin{proposition} Непустое выпуклое множество $A\subset\Rn$ содержит все выпуклые комбинации векторов из $A$. \end{proposition} \begin{proof} Будем доказывать это утверждение индукцией по числу слагаемых в выпуклой комбинации. Для двух слагаемых утверждение очевидно. Предположим, что утверждение доказано для $k$ слагаемых. Пусть $x_1,\ldots,x_{k+1}\in A$ и $$\sum_{j=1}^{k+1}\alpha_j=1,\quad\alpha_j\ge0,\ j=1,\ldots,k+1.$$ Имеем $$x=\sum_{j=1}^{k+1}\alpha_jx_j=\alpha_1x_1+(1-\alpha_1)y,$$ где $$y=\sum_{j=2}^{k+1}\frac{\alpha_j}{1-\alpha_1}x_j.$$ Поскольку $$\sum_{j=2}^{k+1}\frac{\alpha_j}{1-\alpha_1}=1,$$ то по предположению индукции $y\in A$. Следовательно, $x\in A$. \end{proof} Из доказанного утверждения вытекает, что наименьшим выпуклым множеством, содержащим произвольное непустое множество $A$, является множество всех выпуклых комбинаций векторов из $A$. Это множество называется {\it выпуклой оболочкой} $A$ и обозначается $\co A$. \section{Аффинные многообразия} Пусть $x_1,\ldots,x_k\in\Rn$. Вектор $$x=\sk\alpha_jx_j,\quad\alpha_j\in\mathbb R,\ j=1,\ldots,k,$$ называется {\it линейной комбинацией\/} векторов $x_1,\ldots,x_k$. Множество всех линейных комбинаций векторов из $A\subset\Rn$ называется {\it линейной оболочкой} $A$ и обозначается через $\spa A$. Вектор \begin{equation}\label{1} x=\sk\alpha_jx_j,\quad\sk\alpha_j=1,\quad\alpha_j\in\mathbb R,\ j=1,\ldots,k, \end{equation} называется {\it аффинной комбинацией\/} векторов $x_1,\ldots,x_k$. Множество всех аффинных комбинаций векторов из $A\subset\Rn$ называется {\it аффинной оболочкой} $A$ и обозначается через $\aff A$. {\it Аффинным многообразием\/} в $\Rn$ называется множество вида $x+L$, где $x\in\Rn$, а $L$ --- линейное подпространство $\Rn$. {\it Размерностью аффинного многообразия\/} называется размерность линейного подпространства $L$. \begin{proposition} Пусть $A\subset\Rn$. Тогда аффинная оболочка $A$ является аффинным многообразием, причем $$\aff A=x_0+\spa(A-x_0),\quad x_0\in A.$$ \end{proposition} \begin{proof} Пусть $x\in\aff A$ имеет вид \eqref1. Тогда $$x=x_0+\sum_{j=1}^k\alpha_j(x_j-x_0)\in x_0+\spa(A-x_0).$$ Обратно, пусть $x\in x_0+\spa(A-x_0)$. Тогда $$x=x_0+\sum_{j=1}^k\lambda_j(x_j-x_0)=(1-\lambda_1-\ldots-\lambda_k)x_0+ \sum_{j=1}^k\lambda_jx_j,$$ что является аффинной комбинацией векторов $x_0,x_1,\ldots,x_k$. \end{proof} Если $A\subset\Rn$ --- выпуклое множество, то его размерностью называется размерность аффинной оболочки $A$ \begin{equation}\label{Dim} \dim A=\dim\aff A=\dim\spa(A-x_0), \end{equation} где $x_0$ --- произвольный вектор из $A$. Векторы $x_1,\ldots,x_{k+1}$ называются {\it аффинно независимыми}, если из того, что \begin{equation}\label{11} \sum_{j=1}^{k+1}\lambda_jx_j=0\quad\text{и}\quad\sum_{j=1}^{k+1}\lambda_j=0, \end{equation} следует, что $\lambda_1=\ldots=\lambda_{k+1}=0$. \begin{proposition}\label{pr} Векторы $x_1,\ldots,x_{k+1}$ аффинно независимы в том и только в том случае, если векторы $x_j-x_1$, $2\le j\le k+1$, --- линейно независимы. \end{proposition} \begin{proof} Пусть $x_1,\ldots,x_{k+1}$ аффинно независимы и \begin{equation}\label{12} \sum_{j=2}^{k+1}\lambda_j(x_j-x_1)=0. \end{equation} Тогда \begin{equation}\label{2} \sum_{j=2}^{k+1}\lambda_jx_j-\biggl(\sum_{j=2}^{k+1}\lambda_j\biggr)x_1=0. \end{equation} Из аффинной независимости $x_1,\ldots,x_{k+1}$ вытекает, что $\lambda_2= \ldots=\lambda_{k+1}=0$. Пусть теперь векторы $x_j-x_1$, $2\le j\le k+1$, --- линейно независимы и выполняются условия \eqref{11}. Тогда имеет место равенство \eqref2, которое эквивалентно равенству \eqref{12}. Из линейной независимости векторов $x_j-x_1$, $2\le j\le k+1$, получаем, что $\lambda_2= \ldots=\lambda_{k+1}=0$. Кроме того, $$\lambda_1=-\sum_{j=2}^{k+1}\lambda_j=0.$$ \end{proof} Выпуклая оболочка аффинно независимых векторов $x_1,\ldots,x_{k+1}$ называется {\it$k$-мерным симплексом}, а векторы $x_1,\ldots,x_{k+1}$ --- {\it вершинами симплекса}. Любой вектор из этого симплекса единственным образом представим в виде $$x=\sum_{j=1}^{k+1}\lambda_jx_j,\quad\sum_{j=1}^{k+1}\lambda_j=1,\quad \lambda_j\ge0,\ j=1,\ldots,k+1.$$ Числа $\lambda_1,\ldots,\lambda_{k+1}$ называются {барицентрическими координатами\/} вектора $x$. Одномерные симплексы --- это отрезки, двумерные --- треугольники, трехмерные --- тетраэдры. Если $A\subset\Rn$ --- выпуклое множество размерности $k\le n$, то оно содержит $k$-мерный симплекс. Действительно, в силу равенства \eqref{Dim} найдутся линейно независимые векторы $x_1-x_0,\ldots,x_k-x_0$, $x_0,x_1,\ldots,x_k\in A$. Тогда из предложения~\ref{pr} вытекает, что векторы $x_0,x_1,\ldots,x_k$ --- аффинно независимы. Следовательно, симплекс с вершинами в этих точках содержится в $A$. \section{Внутренние точки} Точка $a\in A\subset\Rn$ называется {\it внутренней точкой\/} множества $A$, если существует такая окрестность этой точки, что она целиком лежит в $A$. Множество внутренних точек $A$ обозначается через $\intt A$. \begin{proposition}\label{P4} Если $A\subset\Rn$ --- выпуклое множество размерности $n$, то $\intt A\ne\emptyset$. \end{proposition} \begin{proof} Так как $A$ содержит $n$-мерный симплекс, достаточно доказать, что $n$-мерный симплекс в $\Rn$ содержит внутреннюю точку. Пусть $a_0,a_1,\ldots,a_n$ --- вершины $n$-мерного симплекса. Без ограничения общности можно считать, что $a_0=0$. Покажем, что любая точка вида $$x=\sj\lambda_ja_j,\quad\sj\lambda_j<1,\quad\lambda_j>0,\ j=1,\ldots,n,$$ является внутренней. Пусть $x_0$ принадлежит открытому шару радиуса $\varepsilon>0$ $$B_\varepsilon(0)=\{\,y\in\Rn:|y|<\varepsilon\,\}.$$ Тогда $$x_0=\sum_{k=1}^nx_ke_k,$$ где $e_k$ --- стандартный базис в $\Rn$, причем $|x_k|<\varepsilon$, $k=1,\ldots,n$. В силу того, что $a_1,\ldots,a_n$ --- линейно независимы, каждый из векторов стандартного базиса может быть представлен в виде $$e_k=\sj\alpha_{jk}a_k,\quad k=1,\ldots,n.$$ Имеем $$x+x_0=\sj\gamma_ja_j,$$ где $$\gamma_j=\lambda_j+\sum_{k=1}^n\alpha_{jk}x_k,\quad j=1,\ldots,n.$$ В силу оценки $$\biggl|\sum_{k=1}^n\alpha_{jk}x_k\biggr|\le\varepsilon\sum_{k=1}^n|\alpha_{jk}|$$ для достаточно малых $\varepsilon>0$ при всех $x_0\in B_\varepsilon(0)$ \ $\gamma_j>0$, $j=1,\ldots,n$, и $$\sj\gamma_j<1.$$ тем самым все точки $x+x_0$ принадлежат симплексу. \end{proof} Обозначим через $\partial A$ --- граничные точки множества $A$. Через $\cl A$ будем обозначать замыкание множества $A$, т.е.\ множество всех предельных точек $A$. \begin{proposition}\label{P5} Пусть $A\subset\Rn$ --- выпуклое множество, $x\in\intt A$ и $\wx\in\partial A$. Тогда $\lambda(\wx-x)\notin\cl A$ для всех $\lambda>1$. \end{proposition} \begin{proof} Без ограничения общности можно считать, что внутренняя точка множества $A$ совпадает с началом координат, т.е., что $x=0$. Это означает, что существует такое число $r>0$, что все точки, для которых $|a|1$. Тогда в любой окрестности точки $\lambda\wx$ должна найтись точка из $A$. Пусть $\xi\in A$ и $$|\lambda\wx-\xi|<(\lambda-1)\frac r2.$$ Докажем, что любая точка из окрестности точки $\wx$ радиуса $(\lambda-1)\lambda^{-1}r/2$ лежит в $A$ (тем самым $\wx$ не является граничной точкой). Пусть $y$ --- произвольная точка, для которой $$|y-\wx|<\frac{\lambda-1}\lambda\frac r2.$$ Положим $$a_0=\frac\lambda{\lambda-1}y-\frac1{\lambda-1}\xi.$$ Имеем $$|a_0|\le\frac\lambda{\lambda-1}|y-\wx|+\frac1{\lambda-1}|\lambda\wx-\xi|0$, то разделив на $x_2'$, мы придем к виду \eqref{AA}. Если $x_2'<0$, то разделив на $x_2'$, мы придем к виду \begin{equation}\label{a2} \alpha_1a_1+a_2\ge b. \end{equation} Поскольку $(0,0)\in A$, то из этого неравенства следует, что $b\le0$. Тем самым (см.\ \eqref{B}) $b=0$. Подставив в \eqref{a2} вместо $(a_1,a_2)$ точку $(-a_1,-a_2)$ и умножив полученное неравенство на $-1$, придем к виду $$-\alpha_1a_1+a_2\le0,$$ что соответствует \eqref{AA} при $b=0$. Предположим теперь, что $x_2'=0$. Тогда из \eqref{a1} вытекает, что $$x_1'a_1\le0.$$ В силу центральной симметрии множества $A$ это означает, что $a_1=0$ для точек $(a_1,a_2)\in A$. Следовательно, неравенство \eqref{AA} выполнено для любого $\alpha_1$. Пусть утверждение теоремы доказано для всех $k\le n-1$. Докажем его для $k=n$. Поскольку точка $(0,\ldots,0,b)\in\partial A$, по теореме~\ref{T2} найдется вектор $x'=(x_1',\ldots,x_{n+1}')\ne0$ такой, что для всех $a\in A$ \begin{equation}\label{a3} x'\cdot a\le x_{n+1}'b. \end{equation} Если $x_{n+1}'\ne0$, то рассуждения, аналогичные проведенным для $n=2$, сразу приводят к неравенству \eqref{AA}. Предположим, что $x_{n+1}'=0$. Тогда из неравенства \eqref{a3} с учетом центральной симметрии следует, что множество $A$ лежит в подпространстве $x'\cdot x=0$. Выберем в этом подпространстве ортонормированный базис $f_1,\ldots,f_n$, взяв в качестве $f_n=e_{n+1}=(0,\ldots,0,1)$ (в силу того, что $x_{n+1}'=0$, $e_{n+1}$ принадлежит этому подпространству). Из предположения индукции следует, что в этом подпространстве (размерность которого $n-1$) найдутся $\alpha_1,\ldots,\alpha_{n-1}\in\mathbb R$ такие, что для точек $\wa_1f_1+\ldots+\wa_nf_n\in A$ имеет место неравенство $$\alpha_1\wa_1+\ldots+\alpha_{n-1}\wa_{n-1}+\wa_n\le b.$$ Выразив координаты $\wa_1,\ldots,\wa_n$ через координаты $a_1,\ldots,a_{n+1}$, учитывая, что $\wa_n=a_{n+1}$, а $\wa_j$, $j=1,\ldots,n-1$, линейно выражаются через $a_1,\ldots,a_n$, приходим к виду \eqref{AA}. \end{proof} \section{Оптимальное восстановление линейного функционала} Пусть $X$ --- линейное пространство, $W\subset X$, $L,l_1,\ldots,l_n$ --- линейные функционалы на $X$. Ставится задача восстановления функционала $L$ на множестве $W$ по значениям функционалов $l_1,\ldots,l_n$, заданным с некоторой погрешностью. Будем считать, что для каждого $x\in W$ известен вектор $y=(y_1,\ldots,y_n)$ такой, что $$\|Ix-y\|\le\delta,$$ где $Ix=(l_1x,\ldots,l_nx)$, $\|\cdot\|$ --- некоторая норма в $\Rn$, а $\delta>0$ --- погрешность задания исходных данных. В качестве {\it методов восстановления\/} рассматриваются всевозможные отображения $\varphi\colon\Rn\to\mathbb R$. Для данного метода $\varphi$ его {\it погрешностью\/} называется величина $$e(W,L,I,\delta,\varphi)=\sup_{\substack{x\in W,\ y\in\Rn\\\|Ix-y\|\le\delta}}|Lx-\varphi(y)|.$$ {\it Погрешностью оптимального восстановления\/} называется величина $$E(W,L,I,\delta)=\inf_{\varphi\colon\Rn\to\mathbb R}e(W,L,I,\delta,\varphi),$$ а метод, на котором достигается нижняя грань называется {\it оптимальным методом восстановления}. \begin{theorem} Пусть $W$ --- выпуклое центрально-симметричное множество. Тогда \begin{equation}\label{Sm} E(W,L,I,\delta)=\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|, \end{equation} а среди оптимальных методов восстановления существует линейный, т.е. метод вида $$\varphi(y)=\sj c_jy_j.$$ \end{theorem} \begin{proof} 1. Оценка снизу. Пусть $\varphi\colon\Rn\to\mathbb R$ --- произвольный метод восстановления. Для всех $x\in W$ таких, что $\|Ix\|\le\delta$, имеем \begin{multline*} 2|Lx|=|Lx-\varphi(0)-(L(-x)-\varphi(0)|\\ \le|Lx-\varphi(0)|+|(L(-x)-\varphi (0)|\le2e(W,L,I,\delta,\varphi). \end{multline*} Отсюда $$e(W,L,I,\delta,\varphi)\ge\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|.$$ Следовательно, $$E(W,L,I,\delta)\ge\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|.$$ 2. Оценка сверху. Рассмотрим в $\mathbb R^{n+1}$ множество точек \begin{multline*} A=\{\,(y_1,\ldots,y_{n+1}):\|Ix-y\|\le\delta.\ y_{n+1}=Lx,\\ x\in W,\ y=(y_1,\ldots,y_n)\,\}. \end{multline*} Легко убедиться, что $A$ --- выпуклое центрально-симметричное множество. Положим $$b=\sup_{(0,\ldots,0,y_{n+1})\in A}y_{n+1}=\sup_{\substack{x\in W\\\|Ix\|\le\delta}}|Lx|.$$ Из теоремы~\ref{T3} следует, что существуют такие числа $\alpha_1,\ldots,\alpha_n\in\mathbb R$, что для всех $(y_1,\ldots,y_{n+1})\in A$ имеет место неравенство \begin{equation}\label{RA} \alpha_1y_1+\ldots+\alpha_ny_n+y_{n+1}\le b. \end{equation} Так как $(-y_1,\ldots,-y_{n+1})\in A$, то имеет место также неравенство \begin{equation}\label{RB} -\alpha_1y_1-\ldots-\alpha_ny_n-y_{n+1}\le b. \end{equation} Из \eqref{RA} и \eqref{RB} следует, что $$|y_{n+1}+\alpha_1y_1+\ldots+\alpha_ny_n|\le b$$ для всех $(y_1,\ldots,y_{n+1})\in A$. Это означает, что для всех $x\in W$ и $y\in\Rn$ таких, что $\|Ix-y\|\le\delta$ справедливо неравенство $$|Lx-\varphi(y)\|\le b,$$ где $$\varphi(y)=-\alpha_1y_1-\ldots-\alpha_ny_n.$$ Тем самым $$E(W,L,I,\delta)\le e(W,L,I,\delta,\varphi)\le b,$$ что доказывает равенство \eqref{Sm} и оптимальность метода $\varphi$. \end{proof} \end{document}