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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править вики-текст]

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

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

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}} ,

в частности,

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}=\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} ,
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} .

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

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)},

в частности,

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;\;\ldots;\;x_{n-1};\;x_n) = f(x_n;\;x_{n-1};\;\ldots;\;x_{1};\;x_{0}) .

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

(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) .

Применение[править | править вики-текст]

С помощью разделённых разностей функции f для узлов (x_0,\;\ldots,\;x_n) можно записать

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

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) ,

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

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) .

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

1) для вычислений разделённых разностей требуется \frac{(n+2)(n+1)}{2}=O(n^2) действий (деления), что меньше, чем в других алгоритмах;

2) вычислять значения интерполяционного многочлена можно по схеме Горнера за O(n) действий (умножения);

3) хранения требуют (n+1) узел и (n+1) разность, причём разности можно хранить (получить) в тех же ячейках, где были заданы значения f(x_k)  ;

4) по сравнению с интерполяционным многочленом Лагранжа упрощено добавление нового узла.

С помощью

\begin{cases}
\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 > 0, \\
\omega_0(x)=1  & {}
\end{cases}

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

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

История[править | править вики-текст]

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

Пример[править | править вики-текст]

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

Составить таблицу конечных разностей функции y=2x^3-2x^2+3x-1 от начального значения x_0=0, приняв шаг h=1 (см. рисунок).

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

Примечания[править | править вики-текст]