%\documentstyle{report}
%\documentclass{report }

%\usepackage[cp866]{inputenc}
%\usepackage[cp1251]{inputenc}

%\usepackage[russian]{babel}
%\usepackage[LCY]{fontenc}
%\usepackage{graphicx,mybib,russian}
%\newcommand{\<<}{\lfq}
\documentclass[12pt,a4paper]{article}
%\usepackage[cp866]{inputenc}
\usepackage{pscyr}
\usepackage[cp1251]{inputenc}

\usepackage[russian]{babel}
%\usepackage[LCY]{fontenc}
%\usepackage{graphicx,mybib,russian}
%\newcommand{\<<}{\lfq}
\textheight 22cm \textwidth 16cm \topmargin 0cm \oddsidemargin 0cm \evensidemargin 0cm
%\twocolumn
%\oddsidemargin =-2cm
%\topmargin -3cm
%\textheight=27cm
%\textwidth=17cm
\pagestyle{empty}
\begin{document}

{\footnotesize

Лекция 9.
{\bf Дискретизация функциональных пространств}
Пусть $f\in H_{[a,b]}$, $H$- метрическое пространство с метрикой $\rho(x,y)=\|x-y\| $,
$f^n=(f_1^{(n)},f_2^{(n)},\cdots,f_n^{(n)})\in R_n $
Для представления элемента $f\in H_{[a,b]}$ элементом $f^n\in R_n$
метрическое пространство $H_{[a,b]}$ заменим последовательностью конечномерных
пространств $\{R_k\}_{k=1}^\infty$

{\bf Опр.} Оператор $T_n:H_{[a,b]}\to R_n, T_nH_{[a,b]}=R_n(T_nf=f^n)$ назовем
оператором проектирования. Элементы $f^n\in R_n$- будем называть элементами,
аппроксимирующими элементы $f$ пространства $H_{[a,b]}$

Таким образом поставленная задача называется задачей дискретизации прстрантсва
$H_{[a,b]}$

Близость элементов $f^n\in R_n$  к элементам $f\in H_{[a,b]}$ будем оценивать числом
$\rho(f^n,T_n f) =\| f^n-T_n f \|_{R_n} $


{\bf Опр.} Говорят, что последовательность $\{f^k\}_{k=1}^\infty$ $ T_n$ -
сходится к элементу $f\in H_{[a,b]}$, если

$ \rho(f^n,T_n f)=\| f^n-T_n f\|_{R_n} \to_ {n \to \infty}  0$
Вообще говоря, предел $T_nf$ последовательности не единствен.

{\bf Опр.}  Говорят, что норма в пространстве $R_n$ согласована с нормой в пространстве
$H_{[a,b]}$, если

$ \lim\limits_{n \to \infty } \|T_n x \|= \| x \|_{H_{[a,b]}}$

При согласованности норм предел последовательности единственный.

Пример:
1) $H_{[a,b]}=C_{[a,b]}$,

множество $\omega_n=\{ x_i^{(n)} : a \le x_0^{(n)} \le \cdots \le x_n^{(n)} \} $
-будем называть
сеткой интервала $[a,b]$  и писать $[a,b]\to \omega_n $, если
$x_i^{(n)}=a+ih, h=\frac{b-a}{n},i=\overline{0,n} $ сетку $\omega_n $ -будем
называть равномерной.

Вектор $ (f_0^{(n)}, f_1^{(n)}, \cdots , f_n^{(n)})$
-называют сеточной функцией
сетки $\omega_n$.


Оператор проектирования зададим формулой
$T_nf=\{f(x_k^{(n)}\}_{k=0}^n=f^n$- вектор пространства $R_n$

$\lim\limits{n\to\infty}\max\limits{0\le i\le n }|f(x_i^{(n)})|=\max\limits{a\le x\le b}|f(x)|$

Согласованность имеет место, если
$\max\limits_{i}|x_{i+1}-x_i|\to\lim\limits_{n\to \infty} 0$

$\{ f(x_k^{(n)} \}_{k=0}^\infty \to{T_n} f,\rho(T_n f,f^n)=
\max\limits_{0\le i \le n-1} |f_i-f(x_i^{(n)} | \to_{n\to \infty} 0
$

2) $H_{[a,b]}=L^2_{[a,b]} $

$T_mf=\{\frac{1}{2h}\int_{x_i-h}^{x_i+h} f(x)dx $

{\bf Задача интерполяции}: Пусть на отрезке $[a,b]$ задана сетка
$\omega_n=\{ x_i^{(n)}: a\le x_0^{(n)} \le \cdots\le x_n^{(n)}\}$ и определена
сеточная функция $ f^n=(f_0^{(n)},f_1^{(n)},\cdots,f_n^{(n)}) $
Пусть задан оператор проектирования
$T_IF^n=f^I\in H_{[a,b]} $т.е. поставлена задача обратная задаче дискретизации.
При этом  выполнены условия, что

$ f^I(x_i)=f_i, i=\overline{0,n}$

Тогда, поставленную таким образом задачу называют задачей интерполяции.

Заметим, что задача интерполяции имеет множество решений (если не оговорены
дополнительные условия) даже в заданном классе функций.
(поясняющий рисунок)

Пример: $H_{[a,b]}=C^m_{[a,b]}$

$f_k=f^I(x_k^{(n)},k=\overline{0,n}$

Оператор проектирования можно построить множеством способов

1)$ f^I(x)=\sum_{k=0}^nC_kF_k(x)$, где $F_1(x),F_2,\cdots,F_k$ система
линейно независимых функций на интервале $[a,b]$

а) $F_k(x)=x^k$

б) $F_k(x)=\{sin(kx),cos(k,x)\}$

С алгоритмической точки зрения наиболее удобны многочлены Лагранжа

$F_k(x)=l_k(x)^n=\prod\limits_{i=0,i\ne k}^n\frac{x-x_i}{x_k-x_i}=
$

$
\frac{(x-x_1)\cdots(x-x_{k-1})(x-x_{k+1})\cdots(x-x_n)}
{(x_k-x_0)\cdots(x_k-x_{k-1})(x_k-x_{k+1})\cdots(x_k-x_n)}
$

Многочлены Лагранжа обладают удобным свойством ортогональности

$$
l_k^n(x_i)=\left \{
\begin{array}{rr}
1&i=k\\
0&i\ne k\\
\end{array}
\right.
$$
которое помогает легко найти интерполянту Лагранжа

$\sum_{k=1}^nC_kl^n_k(x_i)=f_i, \to C_k=f_k $

$f^L(x)=\sum_{k=1}^nf_kl_k^n(x)$

Если класс функций где ищется интерполянта задан, то можно найти и меру отличия
полученной интерполянты от искомой функции.

Например: если $f\in C_{[a,b]}^{n+1}$ то $f(x)- f^L(x)=
\frac{f^{n=1}(\xi )}{(n+1)!}\prod_{i=1}^n (x-x_i), \xi \in [a,b] $

Заметим, что мера отличия - неустранимая есть погрешность при заданном n.

Рисунок

{\bf Сплайн-интерполяция} Сплайном называют интерполянту сеточной функции,
которая с несколькими своими производными непрерывна на интервале $[a,b]$
и на каждом частичном интервале $[x_i,x_{i+1}]\in [a,b]$ сетки $\omega_n$
является алгебраическим многочленом. Максимальную степень многочлена называют
степенью сплайна

$\{f_i\}_{i=0}^n\in R_n\to^T f^T\in C_{[a,b]}^m$

На практике наибольшее распространение получили линейные и кубические сплайны

{\bf Построение кубического сплайна $S_3(x)$}

$\{f_i\}_{i=0}^n\in R_n\to^T S_3(x)\in C_{[a,b]}^2$

$S_3(x)=a_i+b_ix+c_ix^2+d_ix^2,\forall x\in [x_i,x_{i+1}] $



Уравнения для нахождения коэффициентов $a_,b_i,c_i,d_i$ получаются из условий

1) $ S_3(x_i)=f_i,i=\overline{0,n}$ Всего $n+1-$ условие

2)$ S_3(x_i-0)=S_3(x_i+0) i=\overline{0,n-1}$ Всего $n-1-$ условие

3) $ S_3'(x_i-0)=S_3'(x_i+0) i=\overline{0,n-1}$ Всего $n-1-$ условие

4) $ S_3''(x_i-0)=S_3''(x_i+0) i=\overline{0,n-1}$ Всего $n-1-$ условие

5) $S_3{''}(a)=S_3''(b)=0$ два дополнительных условия, смысл которых обсудим
позднее. Таким образом для определения $4n$ неизвестных коэффициентов
$a_,b_i,c_i,d_i$ имеем $n+1+(n-1)+(n-1)+(n-1)+2=4n $- условий.

Покажем, что поставленная задача разрешима и хорошо обусловлена. Для построения
кубического сплайна видоизменим алгоритм его построения. Заметим, что

$S_3{''}(x)=m_{i-1}\frac{x_i-x}{h_i}+m_i\frac{x-x_{i-1}}{h_i}$

Здесь $m_i$-
коэффициенту подлежащие определению, а $h_i=x_i-x_{i-1}$, $m_k=S_3^{''}(x_k)$
Проинтегрируем два раза $S_3{''}(x)$.  В результате будем иметь

$S_3(x)=m_{i-1}\frac{(x_i-x)^3}{6h_i}+m_i\frac{(x-x_{i-1})^3}{6h_i}
+A_i\frac{x_i-x}{h_i}+B_i\frac{x-x_{i-1}}{h_i}$

где $A_i,B_i$ - постоянные интегрирования. Из условий

$S_3(x_{i})=f_{i}$ $\to m_{i}\frac{h_i^2}{6}+B_i=f_{i}$

$S_3(x_{i-1})=f_{i-1}$ $\to m_{i-1}\frac{h_i^2}{6}+A_i=f_{i-1}$


$S_3(x)=m_{i-1}\frac{(x_i-x)^3}{6h_i}+$
$m_i\frac{(x-x_{i-1})^3}{6h_i}$

$
+(f_{i-1}-\frac{m_{i-1}}{6}h_i^2)\frac{x_i-x}{h_i}
+(f_i-\frac{m_i}{6}h_i^2 )\frac{x-x_{i-1}}{h_i}$

Из последнего равенства следуют равенства, что

$S_3'(x)=-m_{i-1}\frac{(x_i-x)^2}{2h_i}+m_i\frac{(x-x_{i-1})^2}{2h_i}+
\frac{f_i-f_{i-1}}{h_i}-\frac{m_i-m_{i-1}}{6}h_i$

$S_3'(x_i-0)=\frac{h_i}{6}m_{i-1}+\frac{h_i}{3}m_i+\frac{f_{i}-f_{i-1}}{h_{i}}$


$S_3'(x_i+0)=-\frac{h_{i+1}}{3}m_{i}+\frac{h_{i+1}}{6}m_{i+1}+
\frac{f_{i+1}-f_i}{h_{i+1}}$

Из условий непрерывности первой производной $S_3'(x)$  в точках
$(x_1,\cdots,x_{n-1}$ получаем $n-1$- уравнение для определения коэффициентов
$m_i$

$\frac{h_i}{6}m_{i-1}+\frac{h_i+h_{i+1}}{3}m_i+\frac{h_{i+1}}{6}m_{i+1}=
\frac{f_{i+1}-f_{i}}{h_{i+1}}-\frac{f_i-f_{i-1}}{h_i}$

$i=\overline{1,n-1}$

Из условий равенства нулю в точках $a$ и $в$ второй производной, имеем

$m_0=0$  $m_n=0$

Таким образом, для определения $n+1$- коэффициентов $m_0,m_1,\cdots,m_n$ имеем
систему алгебраических уравнений с матрицей ленточного типа, причем
диагональный коэффициент преобладает над суммой под диагонального и над
диагонального и следовательно для решения этой системы может быть использован
метод прогонки.

{\bf Экстремальное свойство кубического сплайна }
 Рассмотрим задачу отыскания интерполянты сеточной функции из класса
$W_{2[a,b]}^2 $ минимизирующую функционал

$J[u]=\int_a^b[u{''}(x)]^2dx $

$W_2^2-$ класс функций суммируемых вместе со второй производной. Утверждается,
что функция минимизурующая  такой функционал - кубический сплайн.

Рассмотрим

$J[u(x)-S_3(x)]=\int_a^b[u{''}(x)-S_3{''}(x)]^2dx=
J[u]-J[S_3]-2\int_a^b (u^{''}(x)-S_3{''}(x))S_3{''}(x)dx= $
инт. по частям =
$J[u]-J[S_3]- 2[(u'-S_3')S_3{''}|_a^b -
   \int_a^b (u{'}(x)-S_3{'}(x))S_3{'''}(x)dx]=
\{S_3{''}(a)=S_3{''}(b)=0\}=$
$
J[u]-J[S_3]+2\sum_{k=1}^n\int_{x_{k-1}}^{x_k} (u{'}(x)-S_3{'}(x))S_3{'''}dx$

$S_3{'''}=C_k$- постоянные на интервале $[x_{k-1},x_k]$, и следовательно

$J[u-S_3]=J[u]-J[S_3]+2\sum_{k=1}^nC_k(u-S_3)|_{x_{k-1}}^{x_k}=
\hbox{\{ в узлах сетки т.к. u - интерполянта $u(x_k)=S_3(x_k)=y_k$\}}=
J[u]-J[S_3]$ $\to$

$ J[S_3]=J[u]-J[u-S_3]\le J[u] $ для любой функции
 $u\in W_2^2 ,
u(x_k)=y_k ,k=\overline{0,n} $.  Таким образом минимум функционала
$J[u]=\int_a^b[u{''}(x)]^2dx $ достигается на кубическом сплайне.

{\bf Второе определение кубического сплайна.}   Функцию из класса $W_2^2[a,b]$ которая
принимает в узлах сетки $\omega_n$ заданные значения и минимизирует
функционал $J[u]=\int_a^b[u{''}(x)]^2dx $ называют кубическим сплайном.

С физической точки зрения указанный функционал интерпретируется как аналог потенциальной
энергии упругого стержня закрепленного в точках $(x_i,y_i)$ и кубический сплайн
реализует минимум этой энергии.

Имеет место следующая теорема. Если функция $f(x)\in C^k_{[a,b]},
k=\overline{0,4}$ то имеет место оценка

$\max\limits_{a\le x\le b}|f^{(p)}(x)-S_3^{(p)}|\le Ch^{k-p}, k\ge p$

где $C>0$- постоянная не зависящая от $h=\max\limits_{1\le i\le n}|x_i-x_{i-1}|$

Иными словами, если имеется априорная информация о классе востанавливаемых
из сеточной функции функций, то  можно указать степень погрешности восстановленной функции.





}
\end{document}
