Разделённая разность

Разделённая ра́зность — обобщение понятия производной для дискретного набора точек.

Определение

Пусть функция $f$ задана на (связном) множестве $X,$ и фиксированы попарно различные точки $x_0,\dots ,x_n\in X.$

Тогда разделённой разностью нулевого порядка функции $f$ в точке $x_j$ называют значение $f(x_j),$ а разделённую разность порядка $k$ для системы точек $(x_j,x_{j+1},\dots ,x_{j+k})$ определяют через разделённые разности порядка $(k-1)$ по формуле

$f(x_j;x_{j+1};\dots ;x_{j+k-1};x_{j+k})=\frac{f(x_{j+1};\dots ;x_{j+k-1};x_{j+k})-f(x_j;x_{j+1};\dots ;x_{j+k-1})}{x_{j+k}-x_j},$

в частности,

$f(x_0;x_1)=\frac{f(x_1)-f(x_0)}{x_1-x_0},$

$f(x_0;x_1;x_2)=\frac{f(x_1;x_2)-f(x_0;x_1)}{x_2-x_0}=\frac{\frac{f(x_2)-f(x_1)}{x_2-x_1}-\frac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_0},$

$f(x_0;x_1;\dots ;x_{n-1};x_n)=\frac{f(x_1;\dots ;x_{n-1};x_n)-f(x_0;x_1;\dots ;x_{n-1})}{x_n-x_0}.$

Свойства

Для разделённой разности верна формула

$f(x_0;x_1;\dots ;x_n)=\sum _{j=0}^n\frac{f(x_j)}{\prod _{\genfrac{}{}{0ex}{}{i=0}{i\ne j}}^n(x_j-x_i)},$

в частности,

$f(x_0;x_1)=\frac{f(x_1)}{x_1-x_0}+\frac{f(x_0)}{x_0-x_1},$

$f(x_0;x_1;x_2)=\frac{f(x_2)}{(x_2-x_1)(x_2-x_0)}+\frac{f(x_1)}{(x_1-x_2)(x_1-x_0)}+\frac{f(x_0)}{(x_0-x_2)(x_0-x_1)}.$

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

$f(x_0;x_1)=f(x_1;x_0),$

$f(x_0;x_1;x_2)=f(x_1;x_0;x_2)=f(x_2;x_1;x_0),$

$f(x_0;x_1;\dots ;x_{n-1};x_n)=f(x_n;x_{n-1};\dots ;x_1;x_0).$

При фиксированной системе точек $(x_0,\dots ,x_n)$ разделённая разность является линейным функционалом, то есть для функций $f$ и $g$ и скаляров $a$ и $b$:

$(a\cdot f+b\cdot g)(x_0;\dots ;x_n)=a\cdot f(x_0;\dots ;x_n)+b\cdot g(x_0;\dots ;x_n).$

Применение

С помощью разделённых разностей функции $f$ для узлов $(x_0,\dots ,x_n)$ можно записать как интерполяционный многочлен Ньютона «вперёд»:

$\begin{array}{ccc}{L}_n(x)& =& f(x_0)+f(x_0;x_1)\cdot (x-x_0)+f(x_0;x_1;x_2)\cdot (x-x_0)\cdot (x-x_1)+\dots +f(x_0;\dots ;x_n)\cdot \prod _{k=0}^{n-1}(x-x_k)=\\ & =& f(x_0)+(x-x_0)\cdot (f(x_0;x_1)+(x-x_1)\cdot (f(x_0;x_1;x_2)+\dots +(x-x_{n-1})\cdot f(x_0;\dots ;x_n)\dots )),\end{array}$

так и интерполяционный многочлен Ньютона «назад»:

$\begin{array}{ccc}{L}_n(x)& =& f(x_n)+f(x_n;x_{n-1})\cdot (x-x_n)+f(x_n;x_{n-1};x_{n-2})\cdot (x-x_n)\cdot (x-x_{n-1})+\dots +f(x_n;\dots ;x_0)\cdot \prod _{k=1}^n(x-x_k)=\\ & =& f(x_n)+(x-x_n)\cdot (f(x_n;x_{n-1})+(x-x_{n-1})\cdot (f(x_n;x_{n-1};x_{n-2})+\dots +(x-x_1)\cdot f(x_n;\dots ;x_0)\dots )).\end{array}$

Преимущества:

• для вычислений разделённых разностей требуется $(n+2)(n+1)/2=O(n^2)$ действий (деления), что меньше, чем в других алгоритмах;
• вычислять значения интерполяционного многочлена можно по схеме Горнера за $O(n)$ действий (умножения);
• хранения требуют $(n+1)$ узел и $(n+1)$ разность, причём разности можно хранить (получить) в тех же ячейках, где были заданы значения $f(x_k)$ ;
• по сравнению с интерполяционным многочленом Лагранжа упрощено добавление нового узла.

С использованием

$\{\begin{array}{ccc}{\omega }_j(x)& =& (x-x_0)\cdot \dots \cdot (x-x_{j-1})=\prod _{k=0}^{j-1}(x-x_k)={\omega }_{j-1}(x)\cdot (x-x_{j-1}),j>0,\\ {\omega }_0(x)& =& 1\end{array}$

первую из формул можно записать в виде

$L_n(x)=\sum _{j=0}^{n}f(x_0;\dots ;x_j)\cdot {\omega }_j(x).$

С помощью многочлена Ньютона можно также получить следующее представление разделённых разностей в виде отношения определителей:

$f(x_0;\dots ;x_n)=\frac{\left|\begin{array}{ccccc}1& x_0& \dots & x_0^{n-1}& f(x_0)\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& x_n& \dots & x_n^{n-1}& f(x_n)\end{array}\right|}{\left|\begin{array}{ccccc}1& x_0& \dots & x_0^{n-1}& x_0^n\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& x_n& \dots & x_n^{n-1}& x_n^n\end{array}\right|}.$

История

Ньютон использовал в своей общей формуле интерполяции (см. выше) разделённые разности, но термин, по-видимому, был введён О. де Морганом в 1848 году.

Пример

Пример для функции $f(x)=2x^3-2x^2+3x-1$

На приведённом изображении рассмотрен пример вычисления разделённых разностей для

$\begin{array}{ccc}f(x)& =& 2x^3-2x^2+3x-1,\\ x_i& =& i,i=0,\dots ,n,\\ n& =& 5.\end{array}$

См. также

• Конечные разности
• Численное дифференцирование

Ссылки

• Интерполирование Эрмита с использованием разделенных разностей.

Литература

• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — 3-е изд., доп. и перераб. — Шаблон:М: БИНОМ. Лаборатория знаний, 2004. — 636 с., илл. — ISBN 5-94774-175-X.
• Корн Г. (Granino A. Korn, Ph.D.), Корн Т. (Theresa M. Korn, M.S.) Справочник по математике (для научных работников и инженеров) (Шаблон:Lang-en). — Шаблон:М: Наука, 1973. — 832 с., илл.