Our 3D CAD supplier models have been moved to 3Dfindit.com, the new visual search engine for 3D CAD, CAE & BIM models.
You can log in there with your existing account of this site.
The content remains free of charge.
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
(Learn how and when to remove this template message)

In mathematics, divided differences is an algorithm, historically used for computing tables of logarithms and trigonometric functions.^{[citation needed]} Charles Babbage's difference engine, an early mechanical calculator, was designed to use this algorithm in its operation.^{[1]}
Divided differences is a recursive division process. The method can be used to calculate the coefficients in the interpolation polynomial in the Newton form.
Given k+1 data points
The forward divided differences are defined as:
The backward divided differences are defined as:
If the data points are given as a function ƒ,
one sometimes writes
Several notations for the divided difference of the function ƒ on the nodes x_{0}, ..., x_{n} are used:
etc.
Divided differences for $\nu =0$ and the first few values of $j$:
To make the recursive process more clear, the divided differences can be put in a tabular form:
The divided difference scheme can be put into an upper triangular matrix. Let $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}]\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\ldots &f[x_{n}]\end{pmatrix}}$.
Then it holds
${\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})}}+{\frac {f(x_{2})}{(x_{2}x_{0})\cdot (x_{2}x_{1})\cdot (x_{2}x_{3})}}+\\&\quad \quad {\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}}$
With the help of a polynomial function $q$ with $q(\xi )=(\xi x_{0})\cdots (\xi x_{n})$ this can be written as
Alternatively, we can allow counting backwards from the start of the sequence by defining $x_{k}=x_{k+n+1}=x_{k(n+1)}$ whenever $k<0$ or $n<k$. This definition allows $x_{1}$ to be interpreted as $x_{n}$, $x_{2}$ to be interpreted as $x_{n1}$, $x_{n}$ to be interpreted as $x_{0}$, etc. The expanded form of the divided difference thus becomes
$f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod \limits _{k=jn}^{j1}(x_{j}x_{k})}}+\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod \limits _{k=j+1}^{j+n}(x_{j}x_{k})}}$
Yet another characterization utilizes limits:
$f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}\lim _{x\rightarrow x_{j}}\left[{\frac {f(x_{j})(xx_{j})}{\prod \limits _{k=0}^{n}(xx_{k})}}\right]$
You can represent partial fractions using the expanded form of divided differences. (This does not simplify computation, but is interesting in itself.) If $p$ and $q$ are polynomial functions, where $\mathrm {deg} \ p<\mathrm {deg} \ q$ and $q$ is given in terms of linear factors by $q(\xi )=(\xi x_{1})\cdot \dots \cdot (\xi x_{n})$, then it follows from partial fraction decomposition that
If limits of the divided differences are accepted, then this connection does also hold, if some of the $x_{j}$ coincide.
If $f$ is a polynomial function with arbitrary degree and it is decomposed by $f(x)=p(x)+q(x)\cdot d(x)$ using polynomial division of $f$ by $q$, then
The divided differences can be expressed as
where $B_{n1}$ is a Bspline of degree $n1$ for the data points $x_{0},\dots ,x_{n}$ and $f^{(n)}$ is the $n$th derivative of the function $f$.
This is called the Peano form of the divided differences and $B_{n1}$ is called the Peano kernel for the divided differences, both named after Giuseppe Peano.
If nodes are cumulated, then the numerical computation of the divided differences is inaccurate, because you divide almost two zeros, each of which with a high relative error due to differences of similar values. However we know, that difference quotients approximate the derivative and vice versa:
This approximation can be turned into an identity whenever Taylor's theorem applies.
You can eliminate the odd powers of $yx$ by expanding the Taylor series at the center between $x$ and $y$:
The Taylor series or any other representation with function series can in principle be used to approximate divided differences. Taylor series are infinite sums of power functions. The mapping from a function $f$ to a divided difference $f[x_{0},\dots ,x_{n}]$ is a linear functional. We can as well apply this functional to the function summands.
Express power notation with an ordinary function: $p_{n}(x)=x^{n}.$
Regular Taylor series is a weighted sum of power functions: $f=f(0)\cdot p_{0}+f'(0)\cdot p_{1}+{\frac {f''(0)}{2!}}\cdot p_{2}+{\frac {f'''(0)}{3!}}\cdot p_{3}+\dots$
Taylor series for divided differences: $f[x_{0},\dots ,x_{n}]=f(0)\cdot p_{0}[x_{0},\dots ,x_{n}]+f'(0)\cdot p_{1}[x_{0},\dots ,x_{n}]+{\frac {f''(0)}{2!}}\cdot p_{2}[x_{0},\dots ,x_{n}]+{\frac {f'''(0)}{3!}}\cdot p_{3}[x_{0},\dots ,x_{n}]+\dots$
We know that the first $n$ terms vanish, because we have a higher difference order than polynomial order, and in the following term the divided difference is one:
It follows that the Taylor series for the divided difference essentially starts with ${\frac {f^{(n)}(0)}{n!}}$ which is also a simple approximation of the divided difference, according to the mean value theorem for divided differences.
If we would have to compute the divided differences for the power functions in the usual way, we would encounter the same numerical problems that we had when computing the divided difference of $f$. The nice thing is, that there is a simpler way. It holds
Consequently, we can compute the divided differences of $p_{n}$ by a division of formal power series. See how this reduces to the successive computation of powers when we compute $p_{n}[h]$ for several $n$.
If you need to compute a whole divided difference scheme with respect to a Taylor series, see the section about divided differences of power series.
Divided differences of polynomials are particularly interesting, because they can benefit from the Leibniz rule. The matrix $J$ with
contains the divided difference scheme for the identity function with respect to the nodes $x_{0},\dots ,x_{n}$, thus $J^{n}$ contains the divided differences for the power function with exponent $n$. Consequently, you can obtain the divided differences for a polynomial function $\varphi (p)$ with respect to the polynomial $p$ by applying $p$ (more precisely: its corresponding matrix polynomial function $\varphi _{\mathrm {M} }(p)$) to the matrix $J$.
This is known as Opitz' formula.^{[2]} ^{[3]}
Now consider increasing the degree of $p$ to infinity, i.e. turn the Taylor polynomial to a Taylor series. Let $f$ be a function which corresponds to a power series. You can compute a divided difference scheme by computing the according matrix series applied to $J$. If the nodes $x_{0},\dots ,x_{n}$ are all equal, then $J$ is a Jordan block and computation boils down to generalizing a scalar function to a matrix function using Jordan decomposition.
When the data points are equidistantly distributed we get the special case called forward differences. They are easier to calculate than the more general divided differences.
Note that the "divided portion" from forward divided difference must still be computed, to recover the forward divided difference from the forward difference.
Given n data points
with
the divided differences can be calculated via forward differences defined as
The relationship between divided differences and forward differences is^{[4]}
This article uses material from the Wikipedia article "Divided differences", which is released under the Creative Commons AttributionShareAlike License 3.0. There is a list of all authors in Wikipedia
3d,cad,model,library,download,drawing,step,cad blocks,basics,university,highschool,college,grammer school,statistics,3dprinted