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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Розділена різниця — узагальнення поняття похідної. Розділена різниця нульового порядку функції 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(x), де \omega_i(x)=(x-x_1)(x-x_2)\cdots(x-x_i).

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