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

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

Определение

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

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

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

$f(x_0;\;x_1;\;\ldots;\;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}f(x_1;\;\ldots;\;x_i)\omega_{i-1}(x),$

где $\omega_i(x)=(x-x_1)(x-x_2)\cdot\ldots\cdot(x-x_i)$, $\omega_0(x)=1$^[1].

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

История

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

См. также

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

Ссылки

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

Примечания

1. ↑ Интерполяционная формула Ньютона с разделенными разностями.
2. ↑ Конечные разности. в энциклопедии Кругосвет

Для улучшения этой статьи по математике желательно?: Поставить правильное ударение.