Розділена різниця

Розділена різниця — узагальнення поняття похідної. Розділена різниця нульового порядку функції $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_{0}f_{0}+a_{1}f_{1})(x_{0};\ldots ;x_{n})=a_{0}f_{0}(x_{0};\ldots ;x_{n})+a_{1}f_{1}(x_{0};\ldots ;x_{n})$.

Через розділені різниці можна виразити многочлен Лагранжа:

$L_{n}(x)=\sum _{i=1}^{n-1}f(x_{1};\dots ;x_{i})\omega _{i}(x)$, де $\omega _{i}(x)=(x-x_{1})(x-x_{2})\cdots (x-x_{i})$.

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