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

Розділена різниця — узагальнення поняття похідної. Розділена різниця нульового порядку функції $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 _{\genfrac{}{}{0ex}{}{i=0}{i\ne j}}^n(x_j-x_i)}$.

З цієї формули слідує, що розділена різниця є симетричною функцією від своїх аргументів (тобто при будь-якій їх перестановці не змінюється), а також те, що при фіксованих $x_0;\dots ;x_n$ розділена різниця — лінійний функціонал від функції $f$: $(a_0{f}_0+a_1{f}_1)(x_0;\dots ;x_n)=a_0{f}_0(x_0;\dots ;x_n)+a_1{f}_1(x_0;\dots ;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)$ кроків.

Джерела

• Шаблон:Фіхтенгольц.укр