Divided differences

In mathematics, divided differences is an algorithm, historically used for computing tables of logarithms and trigonometric functions. Charles Babbage's difference engine, an early mechanical calculator, was designed to use this algorithm in its operation. Divided differences is a recursive division process. Given a sequence of data points ( x 0 , y 0 ) , … , ( x n , y n ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})} , the method calculates the coefficients of the interpolation polynomial of these points in the Newton form. It is sometimes denoted by a delta with a bar: △ | {\displaystyle {\text{△}}\!\!\!|\,\,} or ◿ ◺ {\displaystyle {\text{◿}}\!{\text{◺}}} . Given n + 1 data points ( x 0 , y 0 ) , … , ( x n , y n ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})} where the x k {\displaystyle x_{k}} are assumed to be pairwise distinct, the forward divided differences are defined as: [ y k ] := y k , k ∈ { 0 , … , n } [ y k , … , y j ] := [ y k + 1 , … , y j ] − [ y k , … , y j − 1 ] x j − x k , k ∈ { 0 , … , n − 1 } , j ∈ { k + 1 , … , n } . {\displaystyle {\begin{aligned}{\mathopen {[}}y_{k}]&:=y_{k},&&k\in \{0,\ldots ,n\}\\{\mathopen {[}}y_{k},\ldots ,y_{j}]&:={\frac {[y_{k+1},\ldots ,y_{j}]-[y_{k},\ldots ,y_{j-1}]}{x_{j}-x_{k}}},&&k\in \{0,\ldots ,n-1\},\ j\in \{k+1,\ldots ,n\}.\end{aligned}}} To make the recursive process of computation clearer, the divided differences can be put in tabular form, where the columns correspond to the value of j above, and each entry in the table is computed from the difference of the entries to its immediate lower left and to its immediate upper left, divided by a difference of corresponding x-values: 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 ] {\displaystyle {\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}}} Note that the divided difference [ y k , … , y k + j ] {\displaystyle [y_{k},\ldots ,y_{k+j}]} depends on the values x k , … , x k + j {\displaystyle x_{k},\ldots ,x_{k+j}} and y k , … , y k + j {\displaystyle y_{k},\ldots ,y_{k+j}} , but the notation hides the dependency on the x-values. If the data points are given by a function f, ( x 0 , y 0 ) , … , ( x k , y n ) = ( x 0 , f ( x 0 ) ) , … , ( x n , f ( x n ) ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{n})=(x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n}))} one sometimes writes the divided difference in the notation f [ x k , … , x k + j ] = def [ f ( x k ) , … , f ( x k + j ) ] = [ y k , … , y k + j ] . {\displaystyle f[x_{k},\ldots ,x_{k+j}]\ {\stackrel {\text{def}}{=}}\ [f(x_{k}),\ldots ,f(x_{k+j})]=[y_{k},\ldots ,y_{k+j}].} Other notations for the divided difference of the function ƒ on the nodes x0, ..., xn are: f [ x k , … , x k + j ] = [ x 0 , … , x n ] f = [ x 0 , … , x n ; f ] = D [ x 0 , … , x n ] f . {\displaystyle 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.} Divided differences for k = 0 {\displaystyle k=0} and the first few values of j {\displaystyle j} : [ y 0 ] = y 0 [ y 0 , y 1 ] = y 1 − y 0 x 1 − x 0 [ y 0 , y 1 , y 2 ] = [ y 1 , y 2 ] − [ y 0 , y 1 ] x 2 − x 0 = y 2 − y 1 x 2 − x 1 − y 1 − y 0 x 1 − x 0 x 2 − x 0 = y 2 − y 1 ( x 2 − x 1 ) ( x 2 − x 0 ) − y 1 − y 0 ( x 1 − x 0 ) ( x 2 − x 0 ) [ y 0 , y 1 , y 2 , y 3 ] = [ y 1 , y 2 , y 3 ] − [ y 0 , y 1 , y 2 ] x 3 − x 0 {\displaystyle {\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}}}