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

Разделенная разность нулевого порядка функции f(x) — сама функция f(x). Разделенная разность n порядка определяется через разделенную разность n − 1 порядка по формуле f(x_1;x_2;\dots;x_n)=\frac{f(x_1;\dots;x_{n-1})-f(x_2;\dots;x_n)}{x_1-x_n}. Для разделенной разности также верна формула f(x_1;\dots;x_n)=\sum_{j=1}^n\frac{f(x_j)}{\prod_{i\neq j}(x_j-x_i)}. Из этой формулы следует, что разделенная разность является симметрической функцией.

Через разделенные разности можно выразить многочлен Лагранжа: 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(n2) действий (с меньшей, чем в других алгоритмах константой), вычислять многочлен Лагранжа в любой точке за O(n) действий.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home