Разделенные различия

В математике — разделенные разности это алгоритм , исторически использовавшийся для вычисления таблиц логарифмов и тригонометрических функций . Чарльза Бэббиджа , Разностная машина один из первых механических калькуляторов , была разработана для использования этого алгоритма в своей работе.

Разделенные разности — это рекурсивный процесс деления . Учитывая последовательность точек данных $(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$, метод вычисляет коэффициенты интерполяционного полинома этих точек в форме Ньютона .

Определение

Учитывая n + 1 точку данных $$(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$$где $x_{k}$ считаются попарно различными, то разделенные вперед разности определяются как: $${\begin{aligned}{\mathopen {[}}y_{k}]&:=y_{k},&&k\in \{0,\ldots ,n\}\\{\mathopen {[}}y_{k},\ldots ,y_{k+j}]&:={\frac {[y_{k+1},\ldots ,y_{k+j}]-[y_{k},\ldots ,y_{k+j-1}]}{x_{k+j}-x_{k}}},&&k\in \{0,\ldots ,n-j\},\ j\in \{1,\ldots ,n\}.\end{aligned}}$$

Чтобы сделать рекурсивный процесс вычислений более понятным, разделенные разности можно представить в табличной форме, где столбцы соответствуют значению j, указанному выше, и каждая запись в таблице вычисляется на основе разности записей, находящихся непосредственно в нижнем левом углу и до его ближайшего верхнего левого угла, разделенного на разность соответствующих значений x : $${\begin{matrix}x_{0}&y_{0}=[y_{0}]&&&\\&&[y_{0},y_{1}]&&\\x_{1}&y_{1}=[y_{1}]&&[y_{0},y_{1},y_{2}]&\\&&[y_{1},y_{2}]&&[y_{0},y_{1},y_{2},y_{3}]\\x_{2}&y_{2}=[y_{2}]&&[y_{1},y_{2},y_{3}]&\\&&[y_{2},y_{3}]&&\\x_{3}&y_{3}=[y_{3}]&&&\\\end{matrix}}$$

Обозначения

Обратите внимание, что разделенная разность $[y_{k},\ldots ,y_{k+j}]$ зависит от ценностей $x_{k},\ldots ,x_{k+j}$ и $y_{k},\ldots ,y_{k+j}$, но обозначение скрывает зависимость от значений x . Если точки данных заданы функцией f , $$(x_{0},y_{0}),\ldots ,(x_{k},y_{n})=(x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n}))$$иногда записывают разделенную разность в обозначениях $$f[x_{k},\ldots ,x_{k+j}]\ {\stackrel {\text{def}}{=}}\ [f(x_{k}),\ldots ,f(x_{k+j})]=[y_{k},\ldots ,y_{k+j}].$$Другие обозначения разделенной разности функции ƒ в узлах x ₀ , ..., x _n : $$f[x_{k},\ldots ,x_{k+j}]={\mathopen {[}}x_{0},\ldots ,x_{n}]f={\mathopen {[}}x_{0},\ldots ,x_{n};f]=D[x_{0},\ldots ,x_{n}]f.$$

Пример

Разделенные разницы для $k=0$ и первые несколько значений $j$: $${\begin{aligned}{\mathopen {[}}y_{0}]&=y_{0}\\{\mathopen {[}}y_{0},y_{1}]&={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\\{\mathopen {[}}y_{0},y_{1},y_{2}]&={\frac {{\mathopen {[}}y_{1},y_{2}]-{\mathopen {[}}y_{0},y_{1}]}{x_{2}-x_{0}}}={\frac {{\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}-{\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}}{x_{2}-x_{0}}}={\frac {y_{2}-y_{1}}{(x_{2}-x_{1})(x_{2}-x_{0})}}-{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})(x_{2}-x_{0})}}\\{\mathopen {[}}y_{0},y_{1},y_{2},y_{3}]&={\frac {{\mathopen {[}}y_{1},y_{2},y_{3}]-{\mathopen {[}}y_{0},y_{1},y_{2}]}{x_{3}-x_{0}}}\end{aligned}}$$

Таким образом, таблица, соответствующая этим терминам до двух столбцов, имеет следующий вид: $${\begin{matrix}x_{0}&y_{0}&&\\&&{y_{1}-y_{0} \over x_{1}-x_{0}}&\\x_{1}&y_{1}&&{{y_{2}-y_{1} \over x_{2}-x_{1}}-{y_{1}-y_{0} \over x_{1}-x_{0}} \over x_{2}-x_{0}}\\&&{y_{2}-y_{1} \over x_{2}-x_{1}}&\\x_{2}&y_{2}&&\vdots \\&&\vdots &\\\vdots &&&\vdots \\&&\vdots &\\x_{n}&y_{n}&&\\\end{matrix}}$$

Характеристики

• Линейность $${\begin{aligned}(f+g)[x_{0},\dots ,x_{n}]&=f[x_{0},\dots ,x_{n}]+g[x_{0},\dots ,x_{n}]\\(\lambda \cdot f)[x_{0},\dots ,x_{n}]&=\lambda \cdot f[x_{0},\dots ,x_{n}]\end{aligned}}$$
• Правило Лейбница $$(f\cdot g)[x_{0},\dots ,x_{n}]=f[x_{0}]\cdot g[x_{0},\dots ,x_{n}]+f[x_{0},x_{1}]\cdot g[x_{1},\dots ,x_{n}]+\dots +f[x_{0},\dots ,x_{n}]\cdot g[x_{n}]=\sum _{r=0}^{n}f[x_{0},\ldots ,x_{r}]\cdot g[x_{r},\ldots ,x_{n}]$$
• Разделенные разности симметричны: если $\sigma :\{0,\dots ,n\}\to \{0,\dots ,n\}$ тогда это перестановка $$f[x_{0},\dots ,x_{n}]=f[x_{\sigma (0)},\dots ,x_{\sigma (n)}]$$
• Полиномиальная интерполяция в форме Ньютона : если $P$ является полиномиальной функцией степени $\leq n$, и $p[x_{0},\dots ,x_{n}]$ разделенная разность, то $$P_{n-1}(x)=p[x_{0}]+p[x_{0},x_{1}](x-x_{0})+p[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})+\cdots +p[x_{0},\ldots ,x_{n}](x-x_{0})(x-x_{1})\cdots (x-x_{n-1})$$
• Если $p$ является полиномиальной функцией степени $<n$, затем $$p[x_{0},\dots ,x_{n}]=0.$$
• Теорема о среднем значении для разделенных разностей : если $f$ раз n дифференцируемо, то $$f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}$$ на номер $\xi$ в открытом интервале, определяемом наименьшим и наибольшим из $x_{k}$х.

Матричная форма

Разделенную разностную схему можно представить в виде верхней треугольной матрицы : $$T_{f}(x_{0},\dots ,x_{n})={\begin{pmatrix}f[x_{0}]&f[x_{0},x_{1}]&f[x_{0},x_{1},x_{2}]&\ldots &f[x_{0},\dots ,x_{n}]\\0&f[x_{1}]&f[x_{1},x_{2}]&\ldots &f[x_{1},\dots ,x_{n}]\\0&0&f[x_{2}]&\ldots &f[x_{2},\dots ,x_{n}]\\\vdots &\vdots &&\ddots &\vdots \\0&0&0&\ldots &f[x_{n}]\end{pmatrix}}.$$

Тогда оно держится

• $T_{f+g}(x)=T_{f}(x)+T_{g}(x)$
• $T_{\lambda f}(x)=\lambda T_{f}(x)$ если $\lambda$ является скаляром
• $T_{f\cdot g}(x)=T_{f}(x)\cdot T_{g}(x)$
  Это следует из правила Лейбница. Это означает, что умножение таких матриц коммутативно . В итоге матрицы разделенных разностных схем относительно одного и того же набора узлов x образуют коммутативное кольцо .
• С $T_{f}(x)$ — треугольная матрица, ее собственные значения , очевидно, равны $f(x_{0}),\dots ,f(x_{n})$.
• Позволять $\delta _{\xi }$ быть дельта -подобной функцией Кронекера, т.е. $$\delta _{\xi }(t)={\begin{cases}1&:t=\xi ,\\0&:{\mbox{else}}.\end{cases}}$$ Очевидно $f\cdot \delta _{\xi }=f(\xi )\cdot \delta _{\xi }$, таким образом $\delta _{\xi }$ является собственной функцией поточечного умножения функций. То есть $T_{\delta _{x_{i}}}(x)$ каким-то образом является « собственной матрицей » $T_{f}(x)$: $T_{f}(x)\cdot T_{\delta _{x_{i}}}(x)=f(x_{i})\cdot T_{\delta _{x_{i}}}(x)$. Однако все столбцы $T_{\delta _{x_{i}}}(x)$ кратны друг другу, матричный ранг $T_{\delta _{x_{i}}}(x)$ равно 1. Таким образом, вы можете составить матрицу всех собственных векторов $T_{f}(x)$ из $i$-й столбец каждого $T_{\delta _{x_{i}}}(x)$. Обозначим матрицу собственных векторов через $U(x)$. Пример $$U(x_{0},x_{1},x_{2},x_{3})={\begin{pmatrix}1&{\frac {1}{(x_{1}-x_{0})}}&{\frac {1}{(x_{2}-x_{0})(x_{2}-x_{1})}}&{\frac {1}{(x_{3}-x_{0})(x_{3}-x_{1})(x_{3}-x_{2})}}\\0&1&{\frac {1}{(x_{2}-x_{1})}}&{\frac {1}{(x_{3}-x_{1})(x_{3}-x_{2})}}\\0&0&1&{\frac {1}{(x_{3}-x_{2})}}\\0&0&0&1\end{pmatrix}}$$ Диагонализация ​ ​ $T_{f}(x)$ можно записать как $$U(x)\cdot \operatorname {diag} (f(x_{0}),\dots ,f(x_{n}))=T_{f}(x)\cdot U(x).$$

Полиномы и степенные ряды

Матрица $$J={\begin{pmatrix}x_{0}&1&0&0&\cdots &0\\0&x_{1}&1&0&\cdots &0\\0&0&x_{2}&1&&0\\\vdots &\vdots &&\ddots &\ddots &\\0&0&0&0&\;\ddots &1\\0&0&0&0&&x_{n}\end{pmatrix}}$$содержит схему разделенных разностей для тождественной функции по узлам $x_{0},\dots ,x_{n}$, таким образом $J^{m}$ содержит разделенные разности для степенной функции с показателем $m$.Следовательно, вы можете получить разделенные разности для полиномиальной функции $p$ применяя $p$ в матрицу $J$: Если $$p(\xi )=a_{0}+a_{1}\cdot \xi +\dots +a_{m}\cdot \xi ^{m}$$и $$p(J)=a_{0}+a_{1}\cdot J+\dots +a_{m}\cdot J^{m}$$затем $$T_{p}(x)=p(J).$$Это известно как формула Опитца .

Теперь рассмотрим увеличение степени $p$ до бесконечности, т.е. превратить полином Тейлора в ряд Тейлора .Позволять $f$ — функция, соответствующая степенному ряду .Вы можете вычислить схему разделенной разности для $f$ путем применения соответствующего матричного ряда к $J$:Если $$f(\xi )=\sum _{k=0}^{\infty }a_{k}\xi ^{k}$$и $$f(J)=\sum _{k=0}^{\infty }a_{k}J^{k}$$затем $$T_{f}(x)=f(J).$$

Альтернативные характеристики

Расширенная форма

$${\begin{aligned}f[x_{0}]&=f(x_{0})\\f[x_{0},x_{1}]&={\frac {f(x_{0})}{(x_{0}-x_{1})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})}}\\f[x_{0},x_{1},x_{2}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})}}+{\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})}}\\f[x_{0},x_{1},x_{2},x_{3}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})\cdot (x_{0}-x_{3})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})\cdot (x_{1}-x_{3})}}+\\&\quad \quad {\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})\cdot (x_{2}-x_{3})}}+{\frac {f(x_{3})}{(x_{3}-x_{0})\cdot (x_{3}-x_{1})\cdot (x_{3}-x_{2})}}\\f[x_{0},\dots ,x_{n}]&=\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod _{k\in \{0,\dots ,n\}\setminus \{j\}}(x_{j}-x_{k})}}\end{aligned}}$$

С помощью полиномиальной функции $\omega (\xi )=(\xi -x_{0})\cdots (\xi -x_{n})$ это можно записать как $$f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{\omega '(x_{j})}}.$$

Форма Пеано

Если $x_{0}<x_{1}<\cdots <x_{n}$ и $n\geq 1$разделенные разности можно выразить как $$f[x_{0},\ldots ,x_{n}]={\frac {1}{(n-1)!}}\int _{x_{0}}^{x_{n}}f^{(n)}(t)\;B_{n-1}(t)\,dt$$где $f^{(n)}$ это $n$-я производная функции $f$ и $B_{n-1}$ является неким B-сплайном степени $n-1$ для точек данных $x_{0},\dots ,x_{n}$, заданный формулой $$B_{n-1}(t)=\sum _{k=0}^{n}{\frac {(\max(0,x_{k}-t))^{n-1}}{\omega '(x_{k})}}$$

Это следствие теоремы о ядре Пеано ; это называется формой Пеано разделенных разностей и $B_{n-1}$ — это ядро ​​Пеано для разделенных различий, названных в честь Джузеппе Пеано .

Прямые и обратные различия

Дополнительная информация: Конечная разность.

Когда точки данных распределены эквидистантно, мы получаем особый случай, называемый прямыми разностями . Их легче вычислить, чем более общие разделенные разности.

Учитывая n +1 точек данных $$(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$$с $$x_{k}=x_{0}+kh,\ {\text{ for }}\ k=0,\ldots ,n{\text{ and fixed }}h>0$$форвардные разницы определяются как $${\begin{aligned}\Delta ^{(0)}y_{k}&:=y_{k},\qquad k=0,\ldots ,n\\\Delta ^{(j)}y_{k}&:=\Delta ^{(j-1)}y_{k+1}-\Delta ^{(j-1)}y_{k},\qquad k=0,\ldots ,n-j,\ j=1,\dots ,n.\end{aligned}}$$тогда как обратные разницы определяются как: $${\begin{aligned}\nabla ^{(0)}y_{k}&:=y_{k},\qquad k=0,\ldots ,n\\\nabla ^{(j)}y_{k}&:=\nabla ^{(j-1)}y_{k}-\nabla ^{(j-1)}y_{k-1},\qquad k=0,\ldots ,n-j,\ j=1,\dots ,n.\end{aligned}}$$Таким образом, таблица прямых разностей записывается как: $${\begin{matrix}y_{0}&&&\\&\Delta y_{0}&&\\y_{1}&&\Delta ^{2}y_{0}&\\&\Delta y_{1}&&\Delta ^{3}y_{0}\\y_{2}&&\Delta ^{2}y_{1}&\\&\Delta y_{2}&&\\y_{3}&&&\\\end{matrix}}$$тогда как таблица обратной разницы записывается как: $${\begin{matrix}y_{0}&&&\\&\nabla y_{1}&&\\y_{1}&&\nabla ^{2}y_{2}&\\&\nabla y_{2}&&\nabla ^{3}y_{3}\\y_{2}&&\nabla ^{2}y_{3}&\\&\nabla y_{3}&&\\y_{3}&&&\\\end{matrix}}$$

Отношения между разделенными разницами и прямыми разницами $$[y_{j},y_{j+1},\ldots ,y_{j+k}]={\frac {1}{k!h^{k}}}\Delta ^{(k)}y_{j},$$тогда как для обратных разностей: $$[{y}_{j},y_{j-1},\ldots ,{y}_{j-k}]={\frac {1}{k!h^{k}}}\nabla ^{(k)}y_{j}.$$

См. также

• Коэффициент разницы
• Алгоритм Невилла
• Полиномиальная интерполяция
• Теорема о среднем значении для разделенных разностей
• Интеграл Нёрлунда – Райса
• Треугольник Паскаля

Ссылки

• Луи Мелвилл Милн-Томсон (2000) [1933]. Исчисление конечных разностей . Американское математическое соц. Глава 1: Разделенные различия. ISBN  978-0-8218-2107-7 .
• Майрон Б. Аллен; Эли Л. Исааксон (1998). Численный анализ для прикладной науки . Джон Уайли и сыновья. Приложение А. ISBN  978-1-118-03027-1 .
• Рон Голдман (2002). Алгоритмы пирамид: подход к динамическому программированию кривых и поверхностей для геометрического моделирования . Морган Кауфманн. Глава 4: Интерполяция Ньютона и разностные треугольники. ISBN  978-0-08-051547-2 .

Внешние ссылки

• Реализация ​ на Haskell .