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

Розділена різниця — узагальнення поняття похідної. Розділена різниця нульового порядку функції ${\displaystyle f(x)}$ — сама функція ${\displaystyle f(x)}$. Розділена різниця порядку ${\displaystyle n}$ визначається через розділену різницю порядку ${\displaystyle n-1}$ за формулою

${\displaystyle 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}}}}$.

Для розділеної різниці також справедлива формула

${\displaystyle 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})}}}$.

З цієї формули слідує, що розділена різниця є симетричною функцією від своїх аргументів (тобто при будь-якій їх перестановці не змінюється), а також те, що при фіксованих ${\displaystyle x_{0};\ldots ;x_{n}}$ розділена різниця — лінійний функціонал від функції ${\displaystyle f}$: ${\displaystyle (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})}$.

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

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

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