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

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

Определение

Пусть функция [math]\displaystyle{ f }[/math] задана на (связном) множестве [math]\displaystyle{ X, }[/math] и фиксированы попарно различные точки [math]\displaystyle{ x_0,\;\ldots,\;x_n \in X. }[/math]

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

[math]\displaystyle{ f(x_j; \; x_{j+1}; \; \ldots; \; x_{j+k-1}; \; x_{j+k}) = \frac{f(x_{j+1}; \; \ldots; \; x_{j+k-1}; \; x_{j+k}) - f(x_{j}; \; x_{j+1};\;\ldots;\;x_{j+k-1})}{x_{j+k}-x_{j}} , }[/math]

в частности,

[math]\displaystyle{ f(x_0;\;x_1)=\frac{f(x_1)-f(x_0)}{x_1-x_0} , }[/math]

[math]\displaystyle{ f(x_0;\;x_1;\;x_2)=\frac{f(x_1;\;x_2)-f(x_0;\;x_1)}{x_2-x_0}=\dfrac{\dfrac{f(x_2)-f(x_1)}{x_2-x_1}-\dfrac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_0} , }[/math]

[math]\displaystyle{ f(x_0;\;x_1;\;\ldots;\;x_{n-1};\;x_n) = \frac{f(x_1;\;\ldots;\;x_{n-1};\;x_n) - f(x_0;\;x_1;\;\ldots;\;x_{n-1})}{x_n-x_0} . }[/math]

Свойства

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

[math]\displaystyle{ f(x_0;\;x_1;\;\ldots;\;x_n)=\sum_{j=0}^n\dfrac{f(x_j)}{\prod\limits_{i=0\atop i\neq j}^n(x_j-x_i)}, }[/math]

в частности,

[math]\displaystyle{ f(x_0;\;x_1)=\frac{f(x_1)}{x_1-x_0}+\frac{f(x_0)}{x_0-x_1} , }[/math]

[math]\displaystyle{ 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)} . }[/math]

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

[math]\displaystyle{ f(x_0;\;x_1)=f(x_1;\;x_0) , }[/math]

[math]\displaystyle{ f(x_0;\;x_1;\;x_2)=f(x_1;\;x_0;\;x_2)=f(x_2;\;x_1;\;x_0) , }[/math]

[math]\displaystyle{ f(x_0;\;x_1;\;\ldots;\;x_{n-1};\;x_n) = f(x_n;\;x_{n-1};\;\ldots;\;x_{1};\;x_{0}) . }[/math]

При фиксированной системе точек [math]\displaystyle{ (x_0,\;\ldots,\;x_n) }[/math] разделённая разность является линейным функционалом, то есть для функций [math]\displaystyle{ f }[/math] и [math]\displaystyle{ g }[/math] и скаляров [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math]:

[math]\displaystyle{ (a\cdot f + b\cdot g)(x_0;\;\ldots;\;x_n) = a\cdot f(x_0;\;\ldots;\;x_n) + b\cdot g(x_0;\;\ldots;\;x_n) . }[/math]

Применение

С помощью разделённых разностей функции [math]\displaystyle{ f }[/math] для узлов [math]\displaystyle{ (x_0,\;\ldots,\;x_n) }[/math] можно записать как интерполяционный многочлен Ньютона «вперёд»:

[math]\displaystyle{ \begin{array}{rcl} 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)+\ldots+f(x_0;\;\ldots;\;x_n)\cdot\prod_{k=0}^{n-1}(x-x_k)= \\ &= &f(x_0)+(x-x_0)\cdot\left(f(x_0;\;x_1)+(x-x_1)\cdot\left(f(x_0;\;x_1;\;x_2)+\ldots+(x-x_{n-1})\cdot f(x_0;\;\ldots;\;x_n) \ldots \right) \right), \end{array} }[/math]

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

[math]\displaystyle{ \begin{array}{rcl} 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})+\ldots+f(x_n;\;\ldots;\;x_0)\cdot\prod_{k=1}^{n}(x-x_k)= \\ &= &f(x_n)+(x-x_n)\cdot\left(f(x_n;\;x_{n-1})+(x-x_{n-1})\cdot\left(f(x_n;\;x_{n-1};\;x_{n-2})+\ldots+(x-x_{1})\cdot f(x_n;\;\ldots;\;x_0) \ldots \right) \right). \end{array} }[/math]

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

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

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

[math]\displaystyle{ \left\{ \begin{array}{rcl} \omega_j(x) &= &(x-x_0)\cdot\ldots\cdot(x-x_{j-1})=\prod\limits_{k=0}^{j-1}(x-x_k)=\omega_{j-1}(x)\cdot(x-x_{j-1}), \; j \gt 0, \\ \omega_0(x) &= &1 \end{array} \right. }[/math]

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

[math]\displaystyle{ L_n(x)=\sum_{j=0}^{n}f(x_0;\;\ldots;\;x_j)\cdot\omega_{j}(x). }[/math]

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

[math]\displaystyle{ f(x_0;\ldots;x_n) = \frac{\left| \begin{array}{ccccc} 1 &x_0 &\ldots &x_0^{n-1} &f(x_0) \\ \vdots &\vdots &\ddots &\vdots &\vdots \\ 1 &x_n &\ldots &x_n^{n-1} &f(x_n) \end{array} \right|}{\left| \begin{array}{ccccc} 1 &x_0 &\ldots &x_0^{n-1} &x_0^n \\ \vdots &\vdots &\ddots &\vdots &\vdots \\ 1 &x_n &\ldots &x_n^{n-1} &x_n^n \end{array} \right|}. }[/math]

История

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

Пример

Пример для функции [math]\displaystyle{ f(x)=2x^3-2x^2+3x-1 }[/math]

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

[math]\displaystyle{ \begin{array}{rcl} f(x) &= &2x^3 - 2x^2 + 3x - 1, \\ x_i &= &i, \; i = 0,\ldots,n,\\ n &= &5. \end{array} }[/math]

См. также

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

Ссылки

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

Литература

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