\documentclass[12pt,a4paper,oneside,reqno,draft]{amsbook}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsfonts}
\usepackage{latexsym}


\tolerance 3750


\renewcommand{\labelenumi}{\theenumi.}
\renewcommand*{\proofname}{Доказательство}
\DeclareMathOperator*{\grad}{grad}
\DeclareMathOperator*{\Div}{div}
\DeclareMathOperator*{\const}{const}
\newcommand*{\Rd}{\mathbb R^d}
\newcommand*{\sk}{\sum_{|\alpha|=k}}
\newcommand*{\Pc}{\mathcal P}
\newcommand*{\Ac}{\mathcal A}
\newcommand*{\Hc}{\mathcal H}
\newcommand*{\la}{\langle}
\newcommand*{\ra}{\rangle}
\newcommand*{\Sd}{\mathbb S^{d-1}}
\newcommand*{\Bd}{\mathbb B^d}
\newcommand*{\ov}{\overline}


\newtheorem{lemma}{Лемма}[section]
%\newtheorem{theorem}{Теорема}
\newtheorem{theorem}{Теорема}[section]

\newtheorem{proposition}{Предложение}[section]
\newtheorem{corollary}{Следствие}[section]
%\textwidth=160mm
%\usepackage{remreset}
%\makeatletter
%\@removefromreset{section}{chapter}
%\makeatother



\makeatletter
\@addtoreset{equation}{section}
%\renewcommand{\section}{\@startsection{section}{1}{0pt}{3.5ex plus 1ex minus .2ex}%
%%{2.3ex plus .2ex}{\S}}
\makeatother
%\renewcommand{\thesection}{\arabic{chapter}.\arabic{section}}
%\newcounter{section}
\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\renewcommand{\thetheorem}{\arabic{section}.\arabic{theorem}}

%\renewcommand*{\thesection}{\S\arabic{section}}
%\renewcommand*{\theequation}{\arabic{section}.\arabic{equation}}

\newcounter{exam}[section]
\renewcommand{\theexam}{\arabic{section}.\arabic{exam}}
\newcommand*{\ex}{\par\refstepcounter{exam}%
{\bf Пример \theexam.}\ }
\renewcommand*{\thefigure}{}
\pagestyle{plain}

\begin{document}
\renewcommand{\figurename}{}

\bigskip

\begin{center}\bf Государственный комитет Российской Федерации\\
по высшему образованию
\vskip20pt

Московский государственный авиационный\\
технологический университет им.\ К.~Э.~Циолковского
\large


\vskip50pt
\bf
Кафедра ``Высшая математика''



\vskip70pt
\Large\rm
 АППРОКСИМАЦИЯ ФУНКЦИЙ МНОГОЧЛЕНАМИ\\
И ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ

\vskip50pt

\rm Методические указания\\ по курсу ``Численные методы''

\vskip70pt

\begin{flushright}
Составитель Осипенко К.Ю.
\end{flushright}

\vskip 140pt
Москва  1994 г.
\end{center}

\thispagestyle{empty}
\newpage

\section*{ВВЕДЕНИЕ}

В настоящем пособии излагаются основные классические методы аппроксимации
функций многочленами и применение этих методов для задач численного
дифференцирования. Функция --- центральное понятие в математике. При
практическом вычислении даже довольно простых функций (таких, например,
как $\sin x$, $\cos x$, $e^x$) уже возникает вопрос: как их вычислять?
Часто на практике значения функций бывают известны лишь в некотором числе
точек. Как получить значения таких функций в промежуточных точках? В этих
и других подобных задачах используется аппроксимация (приближение) изучаемых
функций более простыми, как правило, многочленами.

Распространенной задачей является также задача приближенного вычисления
производной функции, если она известна в некотором наборе точек.
Соответствующие методы приближения, называемые формулами численного
дифференцирования, могут быть получены с помощью многочленов,
аппроксимирующих функцию.

\section*{АППРОКСИМАЦИЯ ФУНКЦИЙ МНОГОЧЛЕНАМИ}

\section{Многочлен Тейлора}

Обозначим через $C[a,b]$ множество всех непрерывных на отрезке $[a,b]$ функций. Через $C^n[a,b]$ будем обозначать множество функций, для которых $f^{(n)}\in C[a,b]$, т.е.\ функция $f$ $n$ раз дифференцируема и ее $n$-ая производная непрерывна на отрезке $[a,b]$.

\medskip

{\sc Определение.} Пусть $f\in C[a,b]$. {\it Многочленом Тейлора\/} функции $f$ в точке $x_0\in[a,b]$ степени $n$ называется многочлен
$$P_n(x)=\sum_{k=o}^n\frac{f^{(k)}(x_0)}{k!}(x-x_0)^k.$$

\medskip

{\sc Пример 1.1.} Найти многочлен Тейлора степени $n$ для функции $f(x)=\sin x$ в нуле.

\medskip

{\sc Решение.} Нетрудно убедиться, что
$$f^{(2k-1)}(x)=(-1)^{k-1}\cos x,\qquad f^{(2k)}=(-1)^k\sin x,\quad k=1,2,
\dots\,\,.$$
Поэтому для $n=2k-1$ имеем
$$P_{2k-1}(x)=x-\frac{x^3}{3!}+\dots+\frac{(-1)^{k-1}}{(2k-1)!}x^{2k-1}.$$
Этот же многочлен является многочленом Тейлора и для $n=2k$, так как $f^{(2
k)}(0)=0$.

\medskip


Многочлен Тейлора степени $n$ обладает тем замечательным свойством, что все его производные до порядка $n$ включительно в точке $x_0$ совпадают с соответствующими производными функции $f$, т.е.\
$$P_n^{(k)}(x_0)=f^{(k)}(x_0),\quad k=0,1,\dots,n.$$
Это свойство легко проверить непосредственным дифференцированием $P_n(x)$.

Положим
$$R_n(x)=f(x)-P_n(x).$$
Величина $R_n(x)$ равна погрешности, возникающей при замене функции на ее многочлен Тейлора в точке $x$.

Из курса математического анализа известно, что, если $f\in C^{n+1}[a,b]$, то при всех $x\in[a,b]$ справедливо представление погрешности $R_n(x)$ в форме Лагранжа
$$R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)^{n+1},$$
где $\xi$ некоторая точка, лежащая строго между $x$ и $x_0$, если $x\ne x_0$.

Так как $f^{(n+1)}$ непрерывна на $[a,b]$, то она ограничена на этом отрезке. Положим
$$M_{n+1}=\max_{x\in[a,b]}|f^{(n+1)}(x)|.$$
Тогда имеем для всех $x\in[a,b]$
\begin{equation}\label{11}
|f(x)-P_n(x)|\le\frac{M_{n+1}}{(n+1)!}|x-x_0|^{n+1}.
\end{equation}

Аппроксимация многочленами Тейлора (или, что то же, отрезками рядов Тейлора) используется, когда у функции легко вычисляются производные высших порядков, а остаточный член стремится к нулю при $n\to\infty$. Это прежде всего относится к элементарным функциям $\sin x$, $\cos x$, $e^x$, $\ln(1+x)$ и $\arctg x$. Напомним ряды Тейлора для этих функций:
\begin{align*}
\sin x&=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\dots,\\
\cos x&=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\dots,\\
e^x&=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots,\\
\ln(1+x)&=x-\frac{x^2}2+\frac{x^3}3-\frac{x^4}4+\dots,\\
\arctg x&=x-\frac{x^3}3+\frac{x^5}5-\frac{x^7}7+\dots\,\,.
\end{align*}
Первые три ряда сходятся на всей числовой оси, а последние два имеют радиус сходимости, равный единице.

\medskip

{\sc Пример 1.2.} Найти аппроксимацию функции $\sin x$ многочленом Тейлора, позволяющую вычислять эту функцию с погрешностью, не превосходящей $10^{-6}$.

\medskip

{\sc Решение.} С помощью формул приведения задача сводится к вычислению $\sin x$ для $0\le x<\dfrac\pi2$. Более того, в силу равенства
$$\sin x=\cos\left(\frac\pi2-x\right)$$
можно ограничиться отрезком $0\le x\le\dfrac\pi4$, если с той же точностью построить аппроксимацию на этом же отрезке для функции $\cos x$.

Имеем (см.\ пример 1.1)
\begin{align*}
\sin x&=x-\frac{x^3}{3!}+\dots+\frac{(-1)^{k-1}}{(2k-1)!}x^{2k-1}+R_
{2k}^s,\\
\cos x&=1-\frac{x^2}{2!}+\dots+\frac{(-1)^k}{(2k)!}x^{2k}+R_{2k+1}^c.
\end{align*}
В силу того, что
$$\max_{x\in\left[0,\tfrac\pi4\right]}|\sin^{(2k+1)}x|=\max_{x\in\left[0,\tfrac\pi4\right]}
|\cos^{(2k+2)}x|=\max_{x\in\left[0,\tfrac\pi4\right]}|\cos x|=1,$$
получаем (см.~\eqref{11})
\begin{equation}\label{12}
\begin{aligned}
|R_{2k}^s(x)|&\le\frac1{(2k+1)!}|x|^{2k+1}&&\le\frac1{(2k+1)!}
\left(\frac\pi4\right)^{2k+1},\\
|R_{2k+1}^c(x)|&\le\frac1{(2k+2)!}|x|^{2k+2}&&\le\frac1{(2k+2)!}\left(\frac
\pi4\right)^{2k+2}.
\end{aligned}
\end{equation}
Обозначив через $r_s$ и $r_c$ правые части в \eqref{12}, будем иметь:
$$\begin{matrix}k&0&1&2&3&4\\
r_s&7,85\cdot10^{-1}&8,07\cdot10^{-2}&2,49\cdot10^{-3}&3,66\cdot10^{-5}&3,13
\cdot10^{-7}\\
r_c&3,08\cdot10^{-1}&1,59\cdot10^{-2}&3,26\cdot10^{-4}&3,59\cdot10^{-6}&2,46
\cdot10^{-8}\end{matrix}$$

Таким образом, для $x\in\left[0,\dfrac\pi4\right]$ получаем следующие
аппроксимации
\begin{equation}\label{13}
\begin{aligned}
\sin x&\approx x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!},&
\quad|R_8^s(x)|&\le3,13\cdot10^{-7},\\
\cos x&\approx1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\frac{x^8}{8!},
&\quad|R_9^c(x)|&\le2,46\cdot10^{-8}.
\end{aligned}
\end{equation}

\section{Вычисление значений многочлена. Схема Горнера}

Рассмотрим многочлен степени $n$
$$P_n(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1}+a_nx^n.$$
Чтобы вычислить значения этого многочлена в точке $a$ можно сначала найти с помощью $(n-1)$-го умножения $a,a^2,\dots,a^n$, а затем выполнить еще $n$ умножений и $n$ сложений. Общее число арифметических действий при таком алгоритме будет равно $3n-1$.

Однако существует более экономный способ вычисления многочлена, основанный
на его представлении в виде
$$P_n(x)=a_0+x(a_1+x(a_2+\dots x(a_{n-2}+x(a_{n-1}+xa_n))\dots)).$$
Тогда вычисление $P_n(a)$ сводится к последовательному нахождению следующих
величин
\begin{align*}
b_n&=a_n,\\
b_{n-1}&=a_{n-1}+ab_n,\\
b_{n-2}&=a_{n-2}+ab_{n-1},\\
\multispan2\dotfill\\
b_1&=a_1+ab_2,\\
b_0&=a_0+ab_1=P_n(a).
\end{align*}
Этот способ называется {\it схемой Горнера}. Для реализации этого алгоритма
требуется $n$ умножений и $n$ сложений, т.е. всего $2n$ арифметических
действий. Можно доказать, что в общем случае не существует способа вычисления
алгебраического многочлена $n$-ой степени менее, чем за $2n$ арифметических
действий.

Отметим, что при вычислении на компьютере многочленов с большими коэффициентами по схеме Горнера может произойти значительная потеря точности за счет вычитания больших округленных чисел. Для некоторых специальных многочленов, рассматриваемых далее, предпочтительнее в смысле точности является применение рекуррентных соотношений, связывающих значения многочленов разных порядков.

\medskip

{\sc Замечание.} Если многочлен есть четная функция, т.е.
$$P_{2k}(x)=a_0+a_2x^2+\dots+a_{2k}x^{2k},$$
то его удобно вычислять по формуле
$$P_{2k}(x)=a_0+x^2(a_2+\dots+x^2(a_{2k-2}+x^2a_{2k})\dots).$$
Аналогично для многочлена нечетной степени
$$P_{2k+1}(x)=a_1x+a_3x^3+\dots+a_{2k+1}x^{2k+1}$$
удобно пользоваться представлением
$$P_{2k+1}(x)=x(a_1+x^2(a_3+\dots+x^2(a_{2k-1}+x^2a_{2k+1})\dots)).$$
Например, для аппроксимаций \eqref{13} имеем
\begin{align*}
\sin x&\approx x\left(1+x^2\left(-\frac1{3!}+x^2\left(\frac1{5!}-x^2
\frac1{7!}\right)\right)\right),\\
\cos x&\approx1+x^2\left(-\frac1{2!}+x^2\left(\frac1{4!}+x^2\left(-\frac1{6!
}+x^2\frac1{8!}\right)\right)\right).    
\end{align*}

\section{Интерполяционный многочлен Лагранжа}

Одной из распространенных задач на практике является следующая задача. Функция $f(x)$ известна в некоторой системе точек $x_0,x_1,\dots,x_n$, т.е. известны значения $f(x_i)$, $i=0,1,\dots,n$. Требуется найти приближенные значения функции в промежуточных точках.

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

\begin{theorem}\label{T31}
Существует единственный многочлен $n$-ой степени, удовлетворяющий условиям
\begin{equation}\label{31}
L_n(x_i)=f(x_i),\quad i=0,1,\dots,n.
\end{equation}
\end{theorem}

\begin{proof}
Существование. Рассмотрим многочлены степени $n$
\begin{multline*}
l_{nj}(x)=\frac{(x-x_0)\dots(x-x_{j-1})(x-x_{j+1})\dots(x-x_n)}{(x_j-x_0)
\dots(x_j-x_{j-1})(x_j-x_{j+1})\dots(x_j-x_n)},\\ 
j=0,1,\dots,n.
\end{multline*}
Имеем
\begin{equation}\label{32}
l_{nj}(x_j)=1,\qquad l_{nj}(x_i)=0,\quad i\ne j.
\end{equation}
Положим
\begin{equation}\label{33}
L_n(x)=\sum_{j=0}^nl_{nj}(x)f(x_j).
\end{equation}
В силу равенств \eqref{32} убеждаемся в справедливости \eqref{31}.

Единственность. Пусть многочлен $\widetilde L_n(x)$ также удовлетворяет равенствам \eqref{31}. Рассмотрим многочлен степени $n$
$$P_n(x)=L_n(x)-\widetilde L_n(x).$$
Имеем
$$P_n(x_i)=L_n(x_i)-\widetilde L_n(x_i)=0,\quad i=0,1,\dots,n.$$
В силу основной теоремы алгебры число нулей всякого многочлена, отличного от тождественного нуля, не превосходит его степени. Следовательно, $P_n(x)\equiv0$, т.е. $\widetilde L_n(x)\equiv L_n(x)$. Теорема доказана.
\end{proof}

\medskip

{\sc Определение.} Многочлен, удовлетворяющий равенствам \eqref{31} называется {\it интерполяционным многочленом}.

\medskip

{\sc Определение.} Интерполяционный многочлен, записанный в виде \eqref{33} называется {\it интерполяционным многочленом Лагранжа}.

\medskip

Многочлены $l_{nj}$ могут быть записаны в несколько ином виде. Положим
$$\omega_n(x)=(x-x_0)\dots(x-x_n).$$
Тогда
$$(x-x_0)\dots(x-x_{j-1})(x-x_{j+1})\dots(x-x_n)=\frac{\omega_n(x)}{x-x_j}.$$
Поскольку
$$\omega'_n(x_j)=(x_j-x_0)\dots(x_j-x_{j-1})(x_j-x_{j+1})\dots(x_j-x_n),$$
то
$$l_{nj}(x)=\frac{\omega_n(x)}{(x-x_j)\omega'_n(x_j)}.$$
Тем самым интерполяционный многочлен Лагранжа может быть представлен в виде
\begin{equation}\label{34}
L_n(x)=\sum_{j=0}^n\frac{\omega_n(x)}{(x-x_j)\omega'_n(x_j)}f(x_j)=\omega_n(x)
\sum_{j=0}^n\frac{f(x_j)}{(x-x_j)\omega'_n(x_j)}.
\end{equation}

\medskip

{\sc Пример 3.1.} Построить интерполяционный многочлен Лагранжа по данным
$$\begin{array}{crrrr}
 x_i&-1&0&1&3\\
f(x_i)&1&2&1&0\end{array}$$
и вычислить его значение при $x=2$.

\medskip

{\sc Решение.} Из равенства \eqref{33}
\begin{multline*}
L_3(x)=\frac{x(x-1)(x-3)}{-8}+\frac{(x+1)(x-1)(x-3)}32+\frac{(x+
1)x(x-3)}{-4}\\
=\frac7{24}x^3-x^2-\frac7{24}x+2.
\end{multline*}
Следовательно, $L_3(2)=-\dfrac14$.

\section{Погрешность при интерполяции многочленом Лагранжа}

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

\begin{theorem}\label{T41} 
Пусть $f\in C^{n+1}[a,b]$. Тогда при всех $x\in[a,b]$ имеет место равенство
\begin{equation}\label{41}
f(x)-L_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_n(x),
\end{equation}
где $\xi\in(a,b)$.
\end{theorem}

\begin{proof}
При $x=x_i$, $i=0,1,\dots,n$, равенство \eqref{41} очевидно. Предположим, что $x\ne x_i$, $i=0,1,\dots,n$. Рассмотрим функцию
$$\varphi(t)=f(t)-L_n(t)-K\omega_n(t),$$
где
$$K=\frac{f(x)-L_n(x)}{\omega_n(x)}.$$
Легко убедиться, что при таком выборе $K$ \ $\varphi(x)=0$. Кроме того, $\varphi(x_i)=0$, $i=0,1,\dots,n$. Тем самым $\varphi$ обращается в нуль в $n+2$ различных точках. По теореме Ролля $\varphi'$ обращается в нуль по крайней мере в $n+1$ различной точке из интервала $(a,b)$.
Последовательно применяя теорему Ролля, получаем, что существует точка $\xi\in(a,b)$, для которой $\varphi^{(n+1)}(\xi)=0$. Таким образом,
\begin{equation}\label{42}
\varphi^{(n+1)}(\xi)=f^{(n+1)}(\xi)-K\omega^{(n+1)}(\xi)=0
\end{equation}
(мы используем здесь тот факт, что $n+1$ производная от многочлена степени
$n$ тождественно равна нулю). Поскольку
$$\omega^{(n+1)}(t)\equiv(n+1)!,$$
то из \eqref{42} получаем
$$f^{(n+1)}(\xi)=K(n+1)!.$$
Выражая отсюда $K$, находим
$$\varphi(t)=f(t)-L_n(t)-\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_n(t).$$
Подставляя в последнее равенство $t=x$ и учитывая, что $\varphi(x)=0$, получаем \eqref{41}. Теорема доказана.
\end{proof}

\begin{corollary}\label{C41}
Пусть $f\in C^{n+1}[a,b]$ и
\begin{equation}\label{43}
M_{n+1}=\max_{x\in[a,b]}|f^{(n+1)}(x)|.
\end{equation}
Тогда для всех $x\in[a,b]$
$$|f(x)-L_n(x)|\le\frac{M_{n+1}}{(n+1)!}|\omega_n(x)|.$$
\end{corollary}

Отсюда сразу же следует оценка
\begin{equation}\label{44}
\max_{x\in[a,b]}|f(x)-L_n(x)|\le\frac{M_{n+1}}{(n+1)!}\max_{x\in[a,b]}|
\omega_n(x)|.
\end{equation}

\medskip

{\sc Пример 4.1.} В предположении, что $f\in C^4[-1,3]$, оценить погрешность приближения $f(2)\approx-\dfrac14$ из примера 3.1 через максимум модуля четвертой производной $M_4$. 

\medskip

{\sc Решение.} Из следствия~\ref{C41} получаем
$$|f(x)-L_3(x)|\le\frac{M_4}{4!}|(x+1)x(x-1)(x-3)|.$$
Таким образом, подставляя $x=2$, имеем
$$\left|f(2)+\frac14\right|=|f(2)-L_3(2)|\le\frac{M_4}4.$$

\section{Интерполяция с равноотстоящими узлами}

Пусть $x_i=x_0+ih$, $i=0,1,\dots,n$, --- узлы интерполяции и $h>0$. Такие узлы называются {\it равноотстоящими узлами\/} или {\it равномерной сеткой}. При этом число $h$ называется {\it шагом\/} сетки. При интерполяции по равномерной сетке удобно ввести новую переменную
$$q=\frac{x-x_0}h.$$
Тогда $x=x_0+qh$ и, кроме того,
\begin{align*}
x-x_i&=x_0+qh-(x_0+ih)=h(q-i),\\
x_j-x_i&=h(j-i).
\end{align*}
Таким образом,
\begin{multline*}
l_{nj}(x_0+qh)=\prod_{i\ne j}\frac{x-x_i}{x_j-x_i}=\prod_{i\ne j}
\frac{q-i}{j-i}\\
=\frac{q(q-1)\dots(q-j+1)(q-j-1)\dots(q-n)}{j(j-1)\dots2\cdot1\cdot(-1)\cdot
(-2)\dots(j-n)}\\
=(-1)^{n-j}\frac{q(q-1)\dots(q-j+1)(q-j-1)\dots(q-n)}{j!(n-j)!}.
\end{multline*}

Следовательно, многочлен Лагранжа для равноотстоящих узлов может быть
записан в виде
\begin{multline}\label{51}
L_n(x_0+qh)\\
=\sum_{j=0}^n(-1)^{n-j}\frac{q(q-1)\dots(q-j+1)(q-j-1)\dots(q-n)
}{j!(n-j)!}f(x_j).
\end{multline}

\medskip

{\sc Пример 5.1.} Написать многочлен Лагранжа второй степени для равноотстоящих узлов с шагом $h$.

\medskip

{\sc Решение.}  При $n=2$ из \eqref{51} находим
$$L_2(x_0+qh)=\frac{(q-1)(q-2)}2f(x_0)-q(q-2)f(x_1)+\frac{q(q-1)}2f(x_2).$$

\medskip

Оценим теперь погрешность, возникающую при замене функции на ее интерполяционный многочлен Лагранжа, когда значения функции заданы в равноотстоящих узлах. Для функции $\omega_n(x)$ имеем
$$\omega_n(x_0+qh)=h^{n+1}q(q-1)\dots(q-n).$$
Если $x\in[x_0,x_n]$, то $q\in[0,n]$. Положим
$$\Omega_n=\max_{q\in[0,n]}|q(q-1)\dots(q-n)|.$$
Тогда из \eqref{44} получаем
\begin{equation}\label{52}
\max_{x\in[x_0,x_n]}|f(x)-L_n(x)|\le\frac{M_{n+1}}{(n+1)!}h^{n+1}\Omega_n.
\end{equation}

Значения $\Omega_n$ при $n=1,2,3$ могут быть легко посчитаны:
\begin{equation}\label{53}
\Omega_1=\frac14,\quad\Omega_2=\frac{2\sqrt3}9,\quad\Omega_3=1.
\end{equation}

\medskip

{\sc Пример 5.2.} С каким шагом надо затабулировать функцию $\sin x$, чтобы при использовании интерполяционного многочлена второй степени по ближайшим точкам погрешность аппроксимации не превосходила $0,5\cdot10^{-6}$?

\medskip

{\sc Решение.} Для $f(x)=\sin x$ \ $f'''(x)=-\cos x$. Поэтому $M_3\le1$. Из \eqref{52} и \eqref{53} имеем
$$|f(x)-L_2(x)|\le\frac1{3!}\frac{2\sqrt3}9h^3.$$
Таким образом, достаточно, чтобы шаг $h$ удовлетворял неравенству
$$\frac1{3!}\frac{2\sqrt3}9h^3\le0,5\cdot10^{-6}.$$
Отсюда
$$h\le\root3\of{\frac{3\sqrt3}2}\cdot10^{-2}\approx1,37\cdot10^{-2}.$$

\section{Минимизация оценки погрешности интерполяции. Многочлены Чебышева}

Пусть имеется функция $f\in C^{n+1}[a,b]$ и известна величина $M_{n+1}$ (см.~\eqref{43}) или оценка этой величины. Как выбрать узлы на отрезке $[a,b]$, чтобы значение
$$\max_{x\in[a.b]}|\omega_n(x)|$$
было минимальным?

Рассмотрим для простоты случай, когда $[a,b]=[-1,1]$. Для этой задачи нам потребуются некоторые специальные многочлены.
{\sc Определение.} {\it Многочленами Чебышева\/} называются многочлены, задаваемые на отрезке $[-1,1]$ равенством
\begin{equation}\label{61}
T_n(x)=\cos(n\arccos x).
\end{equation}

\medskip

Легко найти многочлены Чебышева для $n=0,1$ и 2. Действительно,
\begin{align*}
T_0(x)&=1,\\
T_1(x)&=\cos(\arccos x)=x,\\
T_2(x)&=\cos(2\arccos x)=2\cos^2(\arccos x)-1=2x^2-1.
\end{align*}

Проверим, что функции, задаваемые формулой \eqref{61}, действительно являются многочленами степени $n$. Из известных тригонометрических равенств находим
$$\cos(n+1)\varphi+\cos(n-1)\varphi=2\cos\varphi\cos n\varphi.$$
Отсюда
$$\cos(n+1)\varphi=2\cos\varphi\cos n\varphi-\cos(n-1)\varphi.$$
Полагая $\varphi=\arccos x$, получаем
\begin{equation}\label{62}
T_{n+1}(x)=2xT_n(x)-T_{n-1}(x),\quad n=1,2,\dots\,\,.
\end{equation}
Следовательно,
\begin{align*}
T_3(x)&=2xT_2(x)-T_1(x)=2x(2x^2-1)-x=4x^3-3x,\\
T_4(x)&=2xT_3(x)-T_2(x)=2x(4x^3-3x)-(2x^2-1)=8x^4-8x^2+1
\end{align*}
и т.д. Рекуррентная формула \eqref{62} является удобным и эффективным способом вычисления значений многочленов Чебышева.

Отметим ряд свойств многочленов Чебышева.
\begin{enumerate}
\item Если $n$ --- четное, то $T_n(x)$ --- четная функция, если $n$ --- нечетное, то $T_n(x)$ --- нечетная функция.
\item Для старшего коэффициента многочлена $T_n(x)$ справедливо равенство
$$a_n=2^{n-1}.$$
\item $T_n(x)$ имеет $n$ различных действительных корней, лежащих в интервале $(-1,1)$
$$x_i=\cos\frac{(2i-1)}{2n}\pi,\quad i=1,2,\dots,n.$$
\item
$$\max_{x\in[-1,1]}|T_n(x)|=1,$$
причем максимум достигается в $n+1$ точке
\begin{equation}\label{63}
x_i=\cos\frac{i\pi}n,\quad i=0,1,\dots,n.
\end{equation}
\end{enumerate}

\medskip

{\sc Определение.} Многочлен
$$\overline T_n(x)=\frac1{2^{n-1}}T_n(x)$$
называется {\it нормированным многочленом Чебышева\/} (у него старший коэффициент равен единице).

\medskip

\begin{theorem}\label{T61}
Для любого многочлена $P_n(x)$ степени $n$ со старшим коэффициентом, равным единице, справедливо неравенство
$$\max_{x\in[-1,1]}|P_n(x)|\ge\max_{x\in[-1,1]}|\overline T_n(x)|=\frac1{2^{n-1}}.$$
\end{theorem}

\begin{proof}
Предположим, что нашелся многочлен $P_n(x)$ со старшим коэффициентом, равным единице, для которого
$$\max_{x\in[-1,1]}|P_n(x)|<\frac1{2^{n-1}}.$$
Рассмотрим многочлен
$$R(x)=\overline T_n(x)-P_n(x).$$
В силу того, что у $\overline T_n(x)$ и $P_n(x)$ старшие коэффициенты равны единице, многочлен $R(x)$ имеет степень $n-1$. Для точек $x_i$, определенных равенствами \eqref{63}, имеем
$$R(x_i)=\frac{(-1)^i}{2^{n-1}}-P_n(x_i)=(-1)^i\left(\frac1{2^{n-1}}-(-1)^iP_n(x_i)\right)=
(-1)^i\varepsilon_i,$$
где $\varepsilon_i>0$, $i=0,1,\dots,n$. Таким образом, у многочлена $R(x)$ на каждом из интервалов $(x_{i-1},x_i)$, $i=1,\dots,n$, имеется хотя бы один нуль. Следовательно, у $R(x)$ по крайней мере $n$ нулей, что невозможно, так как $R(x)$ многочлен степени $n-1$. Теорема доказана. 
\end{proof}

Благодаря свойству, доказанному в теореме~\ref{T61}, многочлены Чебышева называют {\it многочленами, наименее уклоняющимися от нуля}.

По доказанной теореме для любых точек $x_0,\dots,x_n$ из отрезка $[-1,1]$ имеем
$$\max_{x\in[-1,1]}|\omega_n(x)|\ge\frac1{2^n}$$
(напомним, что $\omega_n(x)$ --- многочлен степени $n+1$). С другой стороны, положив
\begin{equation}\label{64}
x_i=\cos\frac{(2i+1)}{2(n+1)}\pi,\quad i=0,1,\dots,n,
\end{equation}
будем иметь
$$\omega_n(x)=\overline T_{n+1}(x)$$
и, следовательно,
$$\max_{x\in[-1,1]}|\omega_n(x)|=\frac1{2^n}.$$
Таким образом, оценка \eqref{44} достигает своего минимума, когда в качестве узлов интерполяции выбраны нули многочлена Чебышева ({\it чебышевские узлы}). При этом она имеет вид
\begin{equation}\label{65}
\max_{x\in[-1,1]}|f(x)-L_n(x)|\le\frac{M_{n+1}}{(n+1)!2^n}.
\end{equation}
В силу этого свойства узлы \eqref{64} называются {\it оптимальными узлами
интерполяции}.

В случае интерполяции по чебышевским узлам многочлен Лагранжа можно упростить. Так как
$$\omega_n(x)=\overline T_{n+1}(x)=\frac1{2^n}T_{n+1}(x),$$
то
$$\omega_n'(x)=\frac1{2^n}T'_{n+1}(x)=\frac{(n+1)\sin((n+1)\arccos x)}{2^n
\sqrt{1-x^2}}.$$
Поэтому
$$\omega_n'(x_i)=\frac{(n+1)\sin \dfrac{2i+1}2\pi}{2^n\sin\dfrac{(2i+1)}{2(n
+1)}\pi}=(-1)^i\frac{n+1}{2^n\sin\dfrac{(2i+1)}{2(n+1)}\pi}.$$
Таким образом, из \eqref{34} получаем
$$L_n(x)=\frac{T_{n+1}(x)}{n+1}\sum_{i=0}^n(-1)^i\frac{\sin\dfrac{(2i+1)}{2(n
+1)}\pi}{x-x_i}f(x_i).$$

Случай интерполяции на произвольном отрезке $[a,b]$ можно свести к отрезку $[-1,1]$ с помощью замены переменной
$$t=\frac{b-a}2x+\frac{b+a}2.$$
При этом оптимальные узлы интерполяции переходят в оптимальные узлы на отрезке $[a,b]$
$$t_i=\frac{b-a}2\cos\frac{2i+1}{2(n+1)}\pi+\frac{b+a}2,\quad i=0,1,\dots,n,$$
а оценка \eqref{44} будет иметь вид
$$\max_{t\in[a,b]}|f(t)-L_n(t)|\le\frac{M_{n+1}}{(n+1)!}\frac{(b-a)^{n+1}}{2^{2n+1}}.$$

Для произвольного отрезка $[a,b]$ интерполяционный многочлен Лагранжа по оптимальным узлам запишется в виде
$$L_n(t)=\frac{b-a}2\frac{T_{n+1}\left(\dfrac{2t-a-b}{b-a}\right)}{n+1}\sum_
{i=0}^n(-1)^i\frac{\sin\dfrac{(2i+1)}{2(n+1)}\pi}{t-t_i}f(t_i).$$

\section{Интерполяционный многочлен Ньютона}

Пусть $x_0,x_1,\dots,x_n,\dots$ --- произвольные различные точки.

\medskip

{\sc Определение.} Число
$$f(x_i;x_{i+1})=\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}$$
называется {\it разделенной разностью первого порядка}.

\medskip

Очевидно, что $f(x_i;x_{i+1})=f(x_{i+1};x_i)$.

\medskip

{\sc Определение.} {\it Разделенной разностью $n$-го порядка\/} называется величина
$$f(x_i;x_{i+1};\dots;x_{i+n})=\frac{f(x_{i+1};\dots;x_{i+n})-f(x_i;x_{i+1};
\dots;x_{i+n-1})}{x_{i+n}-x_i}.$$

\medskip

При вычислении разделенные разности удобно записывать в виде следующей
таблицы
$$\begin{aligned}&\mathstrut x_0\\&\mathstrut x_1\\&\mathstrut x_2\\&\mathstrut x_3
\\&\mathstrut x_4\end{aligned}\
\begin{aligned}&f(x_0)\\&f(x_1)\\&f(x_2)\\&f(x_3)\\&f(x_4)\end{aligned}\
\begin{aligned}&f(x_0;x_1)\\&f(x_1;x_2)\\&f(x_2;x_3)\\&f(x_3;x_4)\end{aligned}\
\begin{aligned}&f(x_0;x_1;x_2)\\&f(x_1;x_2;x_3)\\&f(x_2;x_3;x_4)\end{aligned}\
\begin{aligned}&f(x_0;x_1;x_2;x_3)\\&f(x_1;x_2;x_3;x_4)\end{aligned}\
f(x_0;x_1;x_2;x_3;x_4)$$

\begin{lemma}\label{L71}
Имеет место равенство
\begin{equation}\label{71}
f(x_0;\dots;x_k)=\sum_{j=0}^k\frac{f(x_j)}{\prod_{i\ne j}(x_j-x_i)}.
\end{equation}
\end{lemma}

\begin{proof}
Легко проверить, что при $k=1$ это равенство совпадает с определениемmвеличины $f(x_0;x_1)$. Воспользуемся методом математической индукции. Предположим, что \eqref{71} доказано для всех $k\le l$. Тогда
\begin{multline*}
f(x_0;\dots;x_{l+1})=\frac{f(x_1;\dots;x_{l+1})-f(x_0;\dots;x_l)
}{x_{l+1}-x_0}\\
=\frac1{x_{l+1}-x_0}\left(\sum_{j=1}^{l+1}\frac{f(x_j)}{\prod\limits_{\substack{i=1\\i\ne j}}^{l+1}(x_j-x_i)}-\sum_{j=0}^l\frac{f(x_j)}{\prod\limits_{\substack{i=0\\i\ne j}}^l(x_j-x_i)}\right).
\end{multline*}
Пусть $j\ne0,l+1$. Тогда коэффициент при $f(x_j)$ в правой части последнего равенства есть
\begin{multline*}
\frac1{x_{l+1}-x_0}\left(\frac1{\prod\limits_{\substack{i=1\\i\ne j}}^{l+1}(x_j-x_i)}-\frac1{
\prod\limits_{\substack{i=0\\i\ne j}}^l(x_j-x_i)}\right)\\
=\frac{(x_j-x_0)-(x_j-x_{l+1})}{(x_{l+1}-x_0)\prod\limits_{\substack{i=0\\i\ne j}}
^{l+1}(x_j-x_i)}=\frac1{\prod\limits_{\substack{i=0\\i\ne j}}^{l+1}(x_j-x_i)},
\end{multline*}
т.е.\ имеет требуемый вид. При $j=0$ или $l+1$ \ $f(x_j)$ входит только
в одно слагаемое и нетрудно убедиться, что коэффициент при нем имеет также
требуемый вид. Лемма доказана.
\end{proof}

Из доказанной леммы вытекает, что разделенная разность есть симметрическая функция своих аргументов $x_0,\dots,x_k$, т.е.\ не меняется при любой их перестановке.

При помощи разделенных разностей можно получить другую форму записи интерполяционного многочлена.

\begin{theorem}\label{T71}
Для интерполяционного многочлена справедливо представление
\begin{multline}\label{72}
L_n(x)=f(x_0)+f(x_0;x_1)(x-x_0)+\dots\\
+f(x_0;x_1;\dots;x_n)(x-x_0)\dots(x-x_{n-1}).
\end{multline}
\end{theorem}

\begin{proof}
Из равенств \eqref{34} и \eqref{71} имеем
\begin{multline}\label{73}
f(x)-L_n(x)=f(x)-\omega_n(x)\sum_{j=0}^n\frac{f(x_j)}{(x-x_j)
\prod_{i\ne j}(x_j-x_i)}\\
=\omega_n(x)\left(\frac{f(x)}{\omega_n(x)}+\sum_{j=0}^n\frac{f(x_j)}{(x_j-x)
\prod_{i\ne j}(x_j-x_i)}\right).
\end{multline}
Из леммы~\ref{L71} следует, что выражение в скобках есть $f(x;x_0;\dots;x_n)$. Таким образом,
$$f(x)-L_n(x)=f(x;x_0;\dots;x_n)\omega_n(x).$$
Интерполяционный многочлен $L_n(x)$ можно представить в виде
\begin{equation}\label{74}
L_n(x)=L_0(x)+(L_1(x)-L_0(x))+\dots+(L_n(x)-L_{n-1}(x)).
\end{equation}
Разность $L_k(x)-L_{k-1}(x)$ есть многочлен степени $k$, который обращается в нуль в точках $x_0,\dots,x_{k-1}$, так как
$$f(x_j)=L_k(x_j)=L_{k-1}(x_j),\quad j=0,1,\dots,k-1.$$
Следовательно,
\begin{equation}\label{75}
L_k(x)-L_{k-1}(x_k)=A_k(x-x_0)\dots(x-x_{k-1})=A_k\omega_{k-1}(x).
\end{equation}
Подставим в это равенство $x=x_k$ и воспользуемся тем, что $L_k(x_k)=f(x_k)$. Будем иметь
$$f(x_k)-L_{k-1}(x_k)=A_k\omega_{k-1}(x_k).$$
С другой стороны, подставим в \eqref{73} $x=x_k$ при $n=k-1$, получаем
$$f(x_k)-L_{k-1}(x_k)=f(x_k;x_0;\dots;x_{k-1})\omega_{k-1}(x_k).$$
Тем самым, учитывая свойство симметрии разделенных разностей, находим
$$A_k=f(x_0;x_1;\dots;x_k).$$
Теперь утверждение теоремы вытекает из представления \eqref{74} и равенства
\eqref{75}. Теорема доказана.
\end{proof}

\medskip

{\sc Определение.} Интерполяционный многочлен, записанный в виде \eqref{72} называется {\it интерполяционным многочленом Ньютона}.

\medskip

Интерполяционный многочлен Ньютона имеет одно важное преимущество по сравнению с интерполяционным многочленом Лагранжа. Если к узлам интерполяции добавить еще одну точку $x_{n+1}$, то интерполяционный многочлен Лагранжа надо строить заново, а к интерполяционному многочлену Ньютона в силу равенства (см.~\eqref{75})
$$L_{n+1}(x)=L_n(x)+f(x_0;x_1;\dots;x_{n+1})(x-x_0)\dots(x-x_n)$$
следует добавить лишь одно слагаемое. Тем не менее, ряд вычислений все же надо провести, чтобы найти разделенную разность $f(x_0;x_1;\dots;x_{n+1})$.

\section{Интерполяционный многочлен Ньютона для равноотстоящих узлов}

Пусть $x_i=x_0+ih$ --- равномерная сетка с шагом $h$ и $f_i=f(x_i)$. 

\medskip

{\sc Определение.}  {\it Конечной разностью первого порядка\/} функции $f$ в точке $x_i$ называется величина
$$\Delta f_i=f(x_i+h)-f(x_i)=f_{i+1}-f_i.$$
{\it Конечной разностью $n$-го порядка\/} функции $f$ в точке $x_i$ называется величина
$$\Delta^nf_i=\Delta(\Delta^{n-1}f_i)=\Delta^{n-1}f_{i+1}-\Delta^{n-1}f_i.$$

\medskip

Например,
$$\Delta^2f_i=\Delta f_{i+1}-\Delta f_i=f_{i+2}-2f_{i+1}+f_i.$$

При вычислении конечные разности удобно располагать в таблицу
$$\begin{aligned}&\mathstrut x_0\\&\mathstrut x_1\\&\mathstrut x_2\\&\mathstrut x_3
\\&\mathstrut x_4\end{aligned}\quad
\begin{aligned}&f_0\\&f_1\\&f_2\\&f_3\\&f_4\end{aligned}\quad
\begin{aligned}&\Delta f_0\\&\Delta f_1\\&\Delta f_2\\&\Delta f_3\end{aligned}\quad
\begin{aligned}&\Delta^2f_0\\&\Delta^2f_1\\&\Delta^2f_2\end{aligned}\quad
\begin{aligned}&\Delta^3f_0\\&\Delta^3f_1\end{aligned}\quad
\Delta^4f_0$$

\begin{lemma}\label{L81} 
Для равномерной сетки $x_i=x_0+ih$ имеет место равенство
\begin{equation}\label{81}
f(x_0;x_1;\dots;x_n)=\frac{\Delta^nf_0}{n!h^n}.
\end{equation}
\end{lemma}

\begin{proof}
Будем доказывать это равенство по индукции. При ${n=1}$ получаем
$$f(x_0;x_1)=\frac{f(x_1)-f(x_0)}{x_1-x_0}=\frac{f_1-f_0}h=\frac{\Delta f_0}h.$$
Пусть равенство \eqref{81} доказано для $n-1$. Докажем его для $n$. Имеем
\begin{multline*}
f(x_0;x_1;\dots;x_n)=\frac{f(x_1;\dots;x_n)-f(x_0;\dots;x_{n-1})
}{x_n-x_0}\\
=\frac1{nh}\left(\frac{\Delta^{n-1}f_1}{(n-1)!h^{n-1}}-\frac{\Delta^{n-1}f_0
}{(n-1)!h^{n-1}}\right)=\frac{\Delta^nf_0}{n!h^n}.
\end{multline*}
Лемма доказана.
\end{proof}

Пусть имеется равномерная сетка $x_i=x_0+ih$, $i=0,1,\dots,n$. Введем переменную
$$q=\frac{x-x_0}h.$$
Тогда $x-x_i=h(q-i)$ и в силу леммы~\ref{L81} для интерполяционного многочлена Ньютона 
(см.~\eqref{72}) получаем представление
\begin{equation}\label{82}
L_n(x_0+qh)=f_0+q\Delta f_0+q(q-1)\frac{\Delta^2f_0}{2!}+\dots+q(q-1)
\dots(q-n+1)\frac{\Delta^nf_0}{n!}.
\end{equation}
Этот многочлен называется интерполяционным многочленом Ньютона для {\it интерполяции вперед}. Им удобно пользоваться для $x$ близких к $x_0$.

Можно рассматривать сетку, идущую влево от точки $x_0$
$$x_{-i}=x_0-ih,\quad i=0,1,\dots,n.$$
Тогда аналогично равенству \eqref{81} получаем
$$f(x_0;x_{-1};\dots;x_{-k})=\frac{\Delta^kf_{-k}}{k!h^k},\quad k=1,\dots,n.$$
Следовательно, для интерполяционного многочлена Ньютона
\begin{multline*}
L_n(x)=f(x_0)+f(x_0;x_{-1})(x-x_0)+\dots\\
+f(x_0;x_{-1};\dots;x_{-n})(x-x_0)(x-x_{-1})\dots(x-x_{-n+1})
\end{multline*}
имеем представление
\begin{multline}\label{83}
L_n(x_0+qh)=f_0+q\Delta f_{-1}+q(q+1)\frac{\Delta^2f_{-2}}{2!}+\dots\\+q(q+1)
\dots(q+n-1)\frac{\Delta^nf_{-n}}{n!}.
\end{multline}
Этот многочлен называется интерполяционным многочленом Ньютона для {\it интерполяции назад}. Он используется для интерполяции в конце таблицы. При этом конечные разности удобно получать, пользуясь таблицей
$$\begin{aligned}&\mathstrut x_{-4}\\&\mathstrut x_{-3}\\&\mathstrut x_{-2}\\&\mathstrut x_{-1}
\\&\mathstrut x_0\end{aligned}\quad
\begin{aligned}&f_{-4}\\&f_{-3}\\&f_{-2}\\&f_{-1}\\&f_0\end{aligned}\quad
\begin{aligned}&\Delta f_{-4}\\&\Delta f_{-3}\\&\Delta f_{-2}\\&\Delta f_{-1}\end{aligned}\quad
\begin{aligned}&\Delta^2f_{-4}\\&\Delta^2f_{-3}\\&\Delta^2f_{-2}\end{aligned}\quad
\begin{aligned}&\Delta^3f_{-4}\\&\Delta^3f_{-3}\end{aligned}\quad
\Delta^4f_{-4}$$

\medskip

{\sc Пример 8.1.} Пусть задана таблица для функции $f(x)=\sin x$ и ее конечных разностей
$$\begin{matrix} x&f(x)&\Delta f&\Delta^2f&\Delta^3f&\Delta^4f\\[10pt]
\begin{array}{r}
5^\circ\\
10^\circ\\
15^\circ\\
20^\circ\\
25^\circ\end{array}&\begin{matrix}0,08716\\
0,17365\\
0,25882\\
0,34202\\
0,42262\end{matrix}&\begin{matrix}8649\\
8517\\
8320\\
8060\end{matrix}&\begin{matrix}-132\\
-197\\
-260\end{matrix}&\begin{matrix}-65\\
-63\end{matrix}&2\end{matrix}$$
Найти приближенные значения $\sin8^\circ$ и $\sin22^\circ$ с помощью интерполяционных многочленов Ньютона $1$, $2$, $3$ и $4$-ой степеней.

\medskip

{\sc Решение.} Найдем сначала приближенное значение $\sin8^\circ$. У нас заданы значения синуса в равномерной сетке $x_i=x_0+ih$, где $x_0=h=5^\circ$. Поскольку
$$q=\frac{x-x_0}h=\frac{8^\circ-5^\circ}{5^\circ}=0,6,$$
то
\begin{align*}
L_1(x_0+qh)&=f_0+q\Delta f_0=0,139054,\\
L_2(x_0+qh)&=L_1(x_0+qh)+q(q-1)\frac{\Delta^2f_0}{2!}=0,139212,\\
L_3(x_0+qh)&=L_2(x_0+qh)+q(q-1)(q-2)\frac{\Delta^3f_0}{3!}=0,139176,\\
L_4(x_0+qh)&=L_3(x_0+qh)+q(q-1)(q-2)(q-3)\frac{\Delta^4f_0}{4!}=0,139175.
\end{align*}
В силу того, что $\sin8^\circ=0,13917309\dots$, для погрешностей полученных приближений справедливы равенства
\begin{align*}
\varepsilon_1&=1,19\cdot10^{-4},\\
\varepsilon_2&=3,89\cdot10^{-5},\\
\varepsilon_3&=2,91\cdot10^{-6},\\
\varepsilon_4&=1,91\cdot10^{-6}.
\end{align*}
Найдем теперь приближенное значение $\sin22^\circ$. Для этого воспользуемся интерполяционным многочленом Ньютона для интерполяции назад. Положим $x_0=25^\circ$, $h=5^\circ$ и $x_{-i}=x_0-ih$, $i=0,1,\dots,4$. Тогда
$$q=\frac{x-x_0}h=-0,6.$$
Аналогично предыдущему случаю получаем
\begin{align*}
L_1(x_0+qh)&=f_0+q\Delta f_{-1}=0,374260,\\
L_2(x_0+qh)&=L_1(x_0+qh)+q(q+1)\frac{\Delta^2f_{-1}}{2!}=0,37745772,\\
L_3(x_0+qh)&=L_2(x_0+qh)+q(q+1)(q+2)\frac{\Delta^3f_{-1}}{3!}=0,37460728,\\
L_4(x_0+qh)&=L_3(x_0+qh)+q(q+1)(q+2)(q+3)\frac{\Delta^4f_{-1}}{4!}\\
&\hspace{217pt}=0,374606608.
\end{align*}
Для сравнения приведем значение $\sin22^\circ$ с точностью до девяти знаков
$$\sin22^\circ=0,374606593.$$
Тем самым для погрешности полученных приближений справедливы равенства
\begin{align*}
\varepsilon_1&=3,47\cdot10^{-4},\\
\varepsilon_2&=3,46\cdot10^{-5},\\
\varepsilon_3&=6,87\cdot10^{-7},\\
\varepsilon_4&=1,46\cdot10^{-8}.
\end{align*}

\bigskip

\section*{ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ}

\section{Формулы численного дифференцирования, получаемые с помощью формулы Тейлора}

Напомним, что производной функции $f(x)$ в точке $x$ называется величина
$$f'(x)=\lim_{\Delta x\to x}\frac{f(x+\Delta x)-f(x)}{\Delta x}.$$
Если производную не удается вычислить точно или это слишком сложно сделать, то пользуются приближенными формулами, использующими значения функции в некоторых точках. Эти формулы называются {\it формулами численного дифференцирования}. Например,
$$f'(x)\approx\frac{f(x+\Delta x)-f(x)}{\Delta x}.$$

Оценим погрешность этой простейшей формулы численного дифференцирования. Обычно для оценки погрешности предполагается существование у функции некоторых производных более высокого порядка, чем искомая производная. Рассмотрим равномерную сетку с шагом $h>0$ \ $x_i=x_0+ih$, $i=0,\pm1,\dots\,\,$. Положим $f_i=f(x_i)$ и $f'_i=f'(x_i)$. Если $f\in C^2[x_0,x_1]$, то по формуле Тейлора
$$f_1=f_0+f'_0(x_1-x_0)+\frac{f''(\xi)}{2!}(x_1-x_0)^2,$$
где $\xi\in(x_0,x_1)$. Отсюда, учитывая, что $x_1-x_0=h$, находим
$$f'_0=\frac{f_1-f_0}h-\frac{f''(\xi)}2h.$$
Таким образом,
\begin{equation}\label{91}
\left|f'_0-\frac{f_1-f_0}h\right|\le\frac{M_2}2h.
\end{equation}
Итак, мы получили одну из простейших формул численного дифференцирования
\begin{equation}\label{92}
f'_0\approx\frac{f_1-f_0}h
\end{equation}
с оценкой погрешности \eqref{91}.

Пусть теперь $f\in C^2[x_{-1},x_1]$. Тогда по формуле Тейлора
\begin{align*}
f_1&=f_0+f'_0h+\frac{f''_0}{2!}h^2+\frac{f'''(\xi_1)}{3!}h^3,\\
f_{-1}&=f_0-f'_0h+\frac{f''_0}{2!}h^2-\frac{f'''(\xi_2)}{3!}h^3,
\end{align*}
где $\xi_1,\xi_2\in(x_{-1},x_1)$. Вычитая из первого равенства второе,
находим
$$f_1-f_{-1}=2f'_0h+\frac{h^3}6(f'''(\xi_1)+f'''(\xi_2)).$$
Отсюда
$$f'_0=\frac{f_1-f_{-1}}{2h}-\frac{h^2}{12}(f'''(\xi_1)+f'''(\xi_2)).$$
Следовательно,
\begin{equation}\label{93}
\left|f'_0-\frac{f_1-f_{-1}}{2h}\right|\le\frac{h^2}6M_3.
\end{equation}
Тем самым получена еще одна формула численного дифференцирования
\begin{equation}\label{94}
f'_0\approx\frac{f_1-f_{-1}}{2h}
\end{equation}
с оценкой погрешности \eqref{93}.

Пусть, наконец, $f\in C^4[x_{-1},x_1]$. Тогда
\begin{align*}
f_1&=f_0+f'_0h+\frac{f''_0}{2!}h^2+\frac{f'''_0}{3!}h^3+\frac{f^{(4
)}(\xi_1)}{4!}h^4,\\
f_{-1}&=f_0-f'_0h+\frac{f''_0}{2!}h^2-\frac{f'''_0}{3!}h^3+\frac{f^{(4)}(\xi_2)
}{4!}h^4.
\end{align*}
Сложив эти равенства, находим
$$f_1-2f_0+f_{-1}=f_0''h^2+\frac{h^4}{4!}(f^{(4)}(\xi_1)+f^{(4)}(\xi_2)).$$
Отсюда
$$f_0''=\frac{f_1-2f_0+f_{-1}}{h^2}-\frac{h^2}{24}(f^{(4)}(\xi_1)+f^{(4)}(\xi_2)).$$
Следовательно,
\begin{equation}\label{95}
f_0''\approx\frac{f_1-2f_0+f_{-1}}{h^2}.
\end{equation}
При этом для погрешности этой формулы численного дифференцирования справедлива оценка
\begin{equation}\label{96}
\left|f_0''-\frac{f_1-2f_0+f_{-1}}{h^2}\right|\le\frac{h^2}{12}M_4.
\end{equation}

\section{Оптимальный выбор шага}

Из оценок погрешностей \eqref{91}, \eqref{93} и \eqref{96} вытекает, что выбирая достаточно малое значение шага $h$, можно сколь угодно точно вычислить значение производных. Однако при практическом вычислении производных с помощью формул численного дифференцирования шаг не берется слишком маленьким. Связано это с тем, что реально значения функций всегда известны с некоторой
погрешностью.

Рассмотрим для примера вычисление производной по формуле \eqref{92}, в которой вместо точных значений $f_0$ и $f_1$ используются приближенные значения
$$\widetilde f_0=f_0+\delta_0,\qquad\widetilde f_1=f_1+\delta_1.$$
Предположим, что $|\delta_0|\le\delta$ и $|\delta_1|\le\delta$ (в этом случае говорят, что значения функции {\it вычислены с погрешностью $\delta$}). Тогда в качестве приближения к $f_0'$ мы вычисляем
$$f_0'\approx\frac{\widetilde f_1-\widetilde f_0}h=\frac{f_1-f_0}h+\frac{\delta_1-\delta_0}h.$$
Для погрешности такого приближения имеем оценку
$$\left|f_0'-\frac{\widetilde f_1-\widetilde f_0}h\right|\le\left|f_0'-
\frac{f_1-f_0}h\right|+\left|\frac{\delta_1-\delta_0}h\right|\le\frac{M_2}2
h+\frac{2\delta}h=\varphi(h).$$

При каком шаге $h$ оценка такого приближения будет минимальной? Поскольку
$$\varphi'(h)=\frac{M_2}2-\frac{2\delta}{h^2},$$
то легко убедиться, что функция $\varphi(h)$ при $h>0$ имеет единственный минимум
$$h_0=2\sqrt{\frac\delta{M_2}}.$$
Этот шаг является оптимальным для формулы \eqref{91} при вычислении функции с погрешностью $\delta$.

\medskip

{\sc Задача.} Найти оптимальный шаг для формул \eqref{94} и \eqref{95}.

\section{Формулы численного дифференцирования, получаемые с помощью интерполяционного многочлена Лагранжа}

Один из универсальных способов построения формул численного дифференцирования состоит в том, что по значениям функции $f$ в некоторых узлах $x_0,x_1,\dots,x_n$ строят интерполяционный многочлен Лагранжа $L_n(x)$ и приближенно полагают
$$f^{(m)}(x)\approx L^{(m)}_n(x).$$

Наиболее часто встречается случай, когда узлы распределены равномерно: $x_i=x_0+ih$, $h>0$. Будем по-прежнему пользоваться обозначением $f_i=f(x_i)$. Тогда (см.~\eqref{51})
\begin{gather*}
L_n(x)=\sum_{i=0}^n(-1)^{n-i}\frac{q(q-1)\dots(q-i+1)(q-i-1)\dots
(q-n)}{i!(n-i)!}f_i,\\
f(x)-L_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}h^{n+1}\Omega_n(q),
\end{gather*}
где
$$x=x_0+qh,\qquad\Omega_n(q)=q(q-1)\dots(q-n).$$
Поскольку $\dfrac{dq}{dx}=\dfrac1h$, то $\dfrac d{dx}=\dfrac1h\dfrac d{dq}$ и
\begin{multline*}
f'(x)\approx L'_n(x)=\frac1h\sum_{i=0}^n\frac{(-1)^{n-i}}{i!(n-i)!}\\
\times\frac d{dq}\left(q(q-1)\dots(q-i+1)(q-i-1)\dots(q-n)\right)f_i.
\end{multline*}

Оценим погрешность такого приближения. Имеем
$$f'(x)-L_n'(x)=\frac{h^{n+1}}{(n+1)!}\left(\Omega_n(q)\frac d{dx}f^{(n+1)}(
\xi)+f^{(n+1)}(\xi)\frac1h\frac d{dq}\Omega_n(q)\right).$$
В случае, когда оценивается погрешность приближенного вычисления производной в узле $x_i$, $q=i$ и $\Omega_n(q)=0$. Следовательно,
$$f'(x_i)-L_n'(x_i)=\frac{h^n}{(n+1)!}f^{(n+1)}(\xi)\frac d{dq}\Omega_n(q)
_{\big|_{q=i}}.$$
Отсюда, положив $f'_i=f'(x_i)$, получаем
\begin{equation}\label{111}
|f'_i-L_n'(x_i)|\le\frac{M_{n+1}h^n}{(n+1)!}\frac d{dq}\Omega_n(q)_{\big|
_{q=i}}.
\end{equation}

\medskip

{\sc Примеры.} При $n=2$ (см.~пример 5.1) имеем
$$L_2(x_0+qh)=\frac{(q-1)(q-2)}2f_0-q(q-2)f_1+\frac{q(q-1)}2f_2.$$
Тем самым
$$f'(x_0+qh)\approx L_2'(x_0+qh)=\frac{(2q-3)f_0-4(q-1)f_1+(2q-1)f_2}{2h}.$$
Учитывая \eqref{111} и то, что $\Omega_2(q)=q(q-1)(q-2)$, получаем:

\begin{enumerate}
\item $q=0$
$$\left|f_0'-\frac{-3f_0+4f_1-f_2}{2h}\right|\le\frac{h^2}3M_3.$$
\item $q=1$
$$\left|f_1'-\frac{f_2-f_0}{2h}\right|\le\frac{h^2}6M_3.$$
Отметим, что эта формула численного дифференцирования уже была получена с помощью формулы Тейлора (см.~\eqref{93}).
\item $q=2$
$$\left|f_2'-\frac{f_0-4f_1+3f_2}{2h}\right|\le\frac{h^2}3M_3.$$ 
\end{enumerate}

\medskip

Для второй производной имеем
$$f''(x_0+qh)\approx L_2''(x_0+qh)=\frac{f_0-2f_1+f_2}{h^2}.$$
Эта формула численного дифференцирования (и ее оценка) была также получена с помощью формулы Тейлора (см.~\eqref{95}).

Пусть теперь $n=3$. Тогда
\begin{multline*}
L_3(x_0+qh)=-\frac{(q-1)(q-2)(q-3)}6f_0+\frac{q(q-2)(q-3)}2f_1\\
-\frac{q(q-1)(q-3)}2f_2+\frac{q(q-1)(q-2)}6f_3.
\end{multline*}
Таким образом,
\begin{multline*}
f'(x_0+qh)\approx L_3'(x_0+qh)=-\frac{3q^2-12q+11}{6h}f_0+\frac{3q^2-10q+6}{2h}f_1\\
-\frac{3q^2-8q+3}{2h}f_2+\frac{3q^2-6q+2}{6h}f_3.
\end{multline*}
Отсюда получаем следующие формулы численного дифференцирования: 

\begin{enumerate}
\item $q=0$
$$f_0'\approx\frac{-11f_0+18f_1-9f_2+2f_3}{6h};$$
\item $q=1$
$$f_1'\approx\frac{-2f_0-3f_1+6f_2-f_3}{6h};$$
\item $q=2$
$$f_2'\approx\frac{f_0-6f_1+3f_2+2f_3}{6h};$$
\item $q=3$
$$f_3'\approx\frac{-2f_0+9f_1-18f_2+11f_3}{6h}.$$ 
\end{enumerate}

\medskip

{\sc Задача.} Для случаев $1$--$4$ оценить погрешность формул численного дифференцирования.

\section{Применение интерполяционного многочлена Ньютона для построения
формул численного дифференцирования} 

В п.7 мы говорили об удобствах, связанных с применением интерполяционного многочлена Ньютона. Пользуясь этим многочленом, можно получать формулы численного дифференцирования, содержащие разделенные разности или конечные разности.
 
Пусть имеется равномерная сетка $x_i=x_0+ih$, $i=0,1,\dots\,\,$. Тогда (см.~\eqref{82})
$$L_n(x_0+qh)=f_0+q\Delta f_0+q(q-1)\frac{\Delta^2f_0}{2!}+\dots+q(q-1)
\dots(q-n+1)\frac{\Delta^nf_0}{n!}.$$
Так как $\dfrac d{dx}=\dfrac1h\dfrac d{dq}$, то
\begin{multline*}
f'(x_0+qh)\approx L_n'(x_0+qh)=\frac1h\left(\Delta f_0+(2q-1)\frac
{\Delta^2f_0}{2!}\right.\\
\left.+(3q^2-6q+2)\frac{\Delta^3f_0}{3!}+\dots+\frac d{dq}(q(q-1)\dots(q-n+1))
\frac{\Delta^nf_0}{n!}\right).
\end{multline*}
Этой формулой удобно пользоваться при малых $q$, т.е.\ в начале таблицы. Аналогичную формулу можно получить, исходя из интерполяционного многочлена Ньютона для интерполяции назад (см.~\eqref{83})
\begin{multline*}
f'(x_0+qh)\approx L_n'(x_0+qh)=\frac1h\left(\Delta f_{-1}+(2q+1)
\frac{\Delta^2f_{-2}}{2!}\right.\\
\left.+(3q^2+6q+2)\frac{\Delta^3f_{-3}}{3!}+\dots+\frac d{dq}(q(q+1)\dots(q+
n-1))\frac{\Delta^nf_{-n}}{n!}\right),
\end{multline*}
которой удобно пользоваться в конце таблицы.

Таким же образом можно получать формулы численного дифференцирования и для старших производных. Например,
\begin{multline*}
f''(x_0+qh)\approx L_n''(x_0+qh)=\frac1{h^2}\left(\Delta^2f_0+(q
-1)\Delta^3f_0+\dots\right.\\
\left.+\frac {d^2}{dq^2}(q(q-1)\dots(q-n+1))\frac{\Delta^nf_0}{n!}\right).
\end{multline*}

%\renewcommand{\refname}{СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ}
\begin{thebibliography}{11}
\bibitem{1} Бахвалов Н.С. {\it Численные методы}. М.: Наука, 1973.
\bibitem{2} Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. {\it Численные методы}.
М.: Наука, 1987.
\bibitem{3} Березин И.С., Жидков Н.П. {\it Методы вычислений}. М.: Наука, 1966.
Т.1; Физматгиз, 1962. Т.2.
\bibitem{4} Волков Е.А. {\it Численные методы}. М.: Наука, 1982.
\bibitem{5} Демидович Б.П., Марон И.А. {\it Основы вычислительной математики}.
М.: Наука, 1966.
\bibitem{6} Калиткин Н.Н. {\it Численные методы}. М.: Наука, 1978.
\end{thebibliography}

\tableofcontents

\end{document}