Русская Википедия:Разделённая разность

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Разделённая ра́зность — обобщение понятия производной для дискретного набора точек.

Определение

Пусть функция <math>f</math> задана на (связном) множестве <math>X,</math> и фиксированы попарно различные точки <math>x_0,\;\ldots,\;x_n \in X.</math>

Тогда разделённой разностью нулевого порядка функции <math>f</math> в точке <math>x_j</math> называют значение <math>f(x_j) ,</math> а разделённую разность порядка <math>k</math> для системы точек <math>(x_j, \; x_{j+1}, \; \ldots, \; x_{j+k})</math> определяют через разделённые разности порядка <math>(k-1)</math> по формуле

<math>f(x_j; \; x_{j+1}; \; \ldots; \; x_{j+k-1}; \; x_{j+k}) = \frac{f(x_{j+1}; \; \ldots; \; x_{j+k-1}; \; x_{j+k}) - f(x_{j}; \; x_{j+1};\;\ldots;\;x_{j+k-1})}{x_{j+k}-x_{j}} ,</math>

в частности,

<math>f(x_0;\;x_1)=\frac{f(x_1)-f(x_0)}{x_1-x_0} ,</math>

<math>f(x_0;\;x_1;\;x_2)=\frac{f(x_1;\;x_2)-f(x_0;\;x_1)}{x_2-x_0}=\dfrac{\dfrac{f(x_2)-f(x_1)}{x_2-x_1}-\dfrac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_0} ,</math>

<math>f(x_0;\;x_1;\;\ldots;\;x_{n-1};\;x_n) = \frac{f(x_1;\;\ldots;\;x_{n-1};\;x_n) - f(x_0;\;x_1;\;\ldots;\;x_{n-1})}{x_n-x_0} .</math>

Свойства

Для разделённой разности верна формула

<math>f(x_0;\;x_1;\;\ldots;\;x_n)=\sum_{j=0}^n\dfrac{f(x_j)}{\prod\limits_{i=0\atop i\neq j}^n(x_j-x_i)},</math>

в частности,

<math>f(x_0;\;x_1)=\frac{f(x_1)}{x_1-x_0}+\frac{f(x_0)}{x_0-x_1} ,</math>

<math>f(x_0;\;x_1;\;x_2) = \frac{f(x_2)}{(x_2-x_1)(x_2-x_0)}+\frac{f(x_1)}{(x_1-x_2)(x_1-x_0)}+\frac{f(x_0)}{(x_0-x_2)(x_0-x_1)} .</math>

Разделённая разность является симметрической функцией своих аргументов, то есть при любой их перестановке её значение не меняется, в частности,

<math>f(x_0;\;x_1)=f(x_1;\;x_0) ,</math>

<math>f(x_0;\;x_1;\;x_2)=f(x_1;\;x_0;\;x_2)=f(x_2;\;x_1;\;x_0) ,</math>

<math>f(x_0;\;x_1;\;\ldots;\;x_{n-1};\;x_n) = f(x_n;\;x_{n-1};\;\ldots;\;x_{1};\;x_{0}) .</math>

При фиксированной системе точек <math>(x_0,\;\ldots,\;x_n)</math> разделённая разность является линейным функционалом, то есть для функций <math>f</math> и <math>g</math> и скаляров <math>a</math> и <math>b</math>:

<math>(a\cdot f + b\cdot g)(x_0;\;\ldots;\;x_n) = a\cdot f(x_0;\;\ldots;\;x_n) + b\cdot g(x_0;\;\ldots;\;x_n) .</math>

Применение

С помощью разделённых разностей функции <math>f</math> для узлов <math>(x_0,\;\ldots,\;x_n)</math> можно записать как интерполяционный многочлен Ньютона «вперёд»:

<math>\begin{array}{rcl} L_n(x) &= &f(x_0)+f(x_0;\;x_1)\cdot(x-x_0)+f(x_0;\;x_1;\;x_2)\cdot(x-x_0)\cdot(x-x_1)+\ldots+f(x_0;\;\ldots;\;x_n)\cdot\prod_{k=0}^{n-1}(x-x_k)= \\

&= &f(x_0)+(x-x_0)\cdot\left(f(x_0;\;x_1)+(x-x_1)\cdot\left(f(x_0;\;x_1;\;x_2)+\ldots+(x-x_{n-1})\cdot f(x_0;\;\ldots;\;x_n) \ldots \right) \right), \end{array}</math>

так и интерполяционный многочлен Ньютона «назад»:

<math>\begin{array}{rcl} L_n(x) &= &f(x_n)+f(x_n;\;x_{n-1})\cdot(x-x_n)+f(x_n;\;x_{n-1};\;x_{n-2})\cdot(x-x_n)\cdot(x-x_{n-1})+\ldots+f(x_n;\;\ldots;\;x_0)\cdot\prod_{k=1}^{n}(x-x_k)= \\

&= &f(x_n)+(x-x_n)\cdot\left(f(x_n;\;x_{n-1})+(x-x_{n-1})\cdot\left(f(x_n;\;x_{n-1};\;x_{n-2})+\ldots+(x-x_{1})\cdot f(x_n;\;\ldots;\;x_0) \ldots \right) \right). \end{array}</math>

Преимущества:

• для вычислений разделённых разностей требуется <math>(n+2)(n+1)/2=O(n^2)</math> действий (деления), что меньше, чем в других алгоритмах;
• вычислять значения интерполяционного многочлена можно по схеме Горнера за <math>O(n)</math> действий (умножения);
• хранения требуют <math>(n+1)</math> узел и <math>(n+1)</math> разность, причём разности можно хранить (получить) в тех же ячейках, где были заданы значения <math>f(x_k) </math> ;
• по сравнению с интерполяционным многочленом Лагранжа упрощено добавление нового узла.

С использованием

<math>\left\{ \begin{array}{rcl}

\omega_j(x) &= &(x-x_0)\cdot\ldots\cdot(x-x_{j-1})=\prod\limits_{k=0}^{j-1}(x-x_k)=\omega_{j-1}(x)\cdot(x-x_{j-1}), \; j > 0, \\ \omega_0(x) &= &1 \end{array} \right. </math> первую из формул можно записать в виде

<math>L_n(x)=\sum_{j=0}^{n}f(x_0;\;\ldots;\;x_j)\cdot\omega_{j}(x).</math>

С помощью многочлена Ньютона можно также получить следующее представление разделённых разностей в виде отношения определителей:

<math> f(x_0;\ldots;x_n) = \frac{\left| \begin{array}{ccccc} 1 &x_0 &\ldots &x_0^{n-1} &f(x_0) \\ \vdots &\vdots &\ddots &\vdots &\vdots \\ 1 &x_n &\ldots &x_n^{n-1} &f(x_n) \end{array} \right|}{\left| \begin{array}{ccccc} 1 &x_0 &\ldots &x_0^{n-1} &x_0^n \\ \vdots &\vdots &\ddots &\vdots &\vdots \\ 1 &x_n &\ldots &x_n^{n-1} &x_n^n \end{array} \right|}. </math>

История

Ньютон использовал в своей общей формуле интерполяции (см. выше) разделённые разности, но термин, по-видимому, был введён О. де Морганом в 1848 году.

Пример

Файл:Разделённая разность.png

Пример для функции <math>f(x)=2x^3-2x^2+3x-1</math>

На приведённом изображении рассмотрен пример вычисления разделённых разностей для

<math> \begin{array}{rcl}

f(x) &= &2x^3 - 2x^2 + 3x - 1, \\ x_i &= &i, \; i = 0,\ldots,n,\\ n &= &5. \end{array} </math>

См. также

• Конечные разности
• Численное дифференцирование

Ссылки

• Интерполирование Эрмита с использованием разделенных разностей.

Литература

• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — 3-е изд., доп. и перераб. — Шаблон:М: БИНОМ. Лаборатория знаний, 2004. — 636 с., илл. — ISBN 5-94774-175-X.
• Корн Г. (Granino A. Korn, Ph.D.), Корн Т. (Theresa M. Korn, M.S.) Справочник по математике (для научных работников и инженеров) (Шаблон:Lang-en). — Шаблон:М: Наука, 1973. — 832 с., илл.