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

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

Разделенная разность — обобщение понятия производной. Разделенная разность нулевого порядка функции f(x) — сама функция f(x). Разделенная разность порядка n определяется через разделенную разность порядка n − 1 по формуле

$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}$.

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

$f(x_0;x_1;\dots;x_n)=\sum_{j=0}^n\frac{f(x_j)}{\prod\limits_{i=0\atop i\neq j}^n(x_j-x_i)}$.

Из этой формулы следует, что разделенная разность является симметрической функцией своих аргументов (то есть при любой их перестановке не меняется), а также то, что при фиксированных $x_0;\ldots;x_n$ разделенная разность — линейный функционал от функции f: $(a_0f_0+a_1f_1)(x_0;\ldots;x_n) = a_0f_0(x_0;\ldots;x_n) + a_1f_1(x_0;\ldots;x_n)$.

Через разделенные разности можно выразить многочлен Лагранжа:

$L_n(x)=\sum_{i=1}^{n-1}f(x_1;\dots;x_i)\omega_{i-1}(x)$, где $\omega_i(x)=(x-x_1)(x-x_2)\cdots(x-x_i)$.

Эта формула позволяет после предварительных вычислений разделенных разностей, требующих O(n²) действий (с меньшей, чем в других алгоритмах константой), вычислять многочлен Лагранжа в любой точке за O(n) действий.

См. также

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