# Finite difference > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Finite_difference > Markdown URL: https://mediated.wiki/source/Finite_difference.md > Source: https://en.wikipedia.org/wiki/Finite_difference > Source revision: 1347435183 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Discrete analog of a derivative A **finite difference** is a mathematical expression of the form *f*(*x* + *b*) − *f*(*x* + *a*). Finite differences (or the associated [difference quotients](/source/Difference_quotient)) are often used as approximations of derivatives, such as in [numerical differentiation](/source/Numerical_differentiation). The [difference operator](/source/Difference_operator), commonly denoted Δ {\displaystyle \Delta } (uppercase [Delta](/source/Delta_(letter))), is the [operator](/source/Operator_(mathematics)) that maps a function f to the function Δ [ f ] {\displaystyle \Delta [f]} defined by Δ [ f ] ( x ) = f ( x + 1 ) − f ( x ) . {\displaystyle \Delta [f](x)=f(x+1)-f(x).} A [difference equation](/source/Difference_equation) is a [functional equation](/source/Functional_equation) that involves the finite difference operator in the same way as a [differential equation](/source/Differential_equation) involves [derivatives](/source/Derivative). There are many similarities between difference equations and differential equations. Certain [recurrence relations](/source/Recurrence_relation#Relationship_to_difference_equations_narrowly_defined) can be written as difference equations by replacing iteration notation with finite differences. In [numerical analysis](/source/Numerical_analysis), finite differences are widely used for [approximating derivatives](#Relation_with_derivatives), and the term "finite difference" is often used as an abbreviation of "finite difference approximation of derivatives".[1][2][3] Finite differences were introduced by [Brook Taylor](/source/Brook_Taylor) in 1715 and have also been studied as abstract self-standing mathematical objects in works by [George Boole](/source/George_Boole) (1860), [L. M. Milne-Thomson](/source/L._M._Milne-Thomson) (1933), and [Károly Jordan](https://en.wikipedia.org/w/index.php?title=K%C3%A1roly_Jordan&action=edit&redlink=1) [[de](https://de.wikipedia.org/wiki/K%C3%A1roly_Jordan)] (1939). Finite differences trace their origins back to one of [Jost Bürgi](/source/Jost_B%C3%BCrgi)'s algorithms (c. 1592) and work by others including [Isaac Newton](/source/Isaac_Newton). The formal calculus of finite differences can be viewed as an alternative to the [calculus](/source/Calculus) of [infinitesimals](/source/Infinitesimal).[4] ## Basic types The three types of the finite differences. The central difference about x gives the best approximation of the derivative of the function at x. Three basic types are commonly considered: *forward*, *backward*, and *central* finite differences.[1][2][3] A **forward difference**, denoted Δ h [ f ] {\displaystyle \Delta _{h}[f]} of a [function](/source/Function_(mathematics)) f is a function defined as Δ h [ f ] ( x ) = f ( x + h ) − f ( x ) . {\displaystyle \Delta _{h}[f](x)=f(x+h)-f(x).} Depending on the application, the spacing h may be variable or constant. When not specified, the default value for h is 1; that is, Δ [ f ] ( x ) = Δ 1 [ f ] ( x ) = f ( x + 1 ) − f ( x ) . {\displaystyle \Delta [f](x)=\Delta _{1}[f](x)=f(x+1)-f(x).} A **backward difference** uses the function values at x and *x* − *h*, instead of the values at *x* + *h* and x: ∇ h [ f ] ( x ) = f ( x ) − f ( x − h ) = Δ h [ f ] ( x − h ) . {\displaystyle \nabla _{h}[f](x)=f(x)-f(x-h)=\Delta _{h}[f](x-h).} Finally, the **central difference** is given by δ h [ f ] ( x ) = f ( x + h 2 ) − f ( x − h 2 ) = Δ h 2 [ f ] ( x ) + ∇ h 2 [ f ] ( x ) . {\displaystyle \delta _{h}[f](x)=f(x+{\tfrac {h}{2}})-f(x-{\tfrac {h}{2}})=\Delta _{\tfrac {h}{2}}[f](x)+\nabla _{\tfrac {h}{2}}[f](x).} ## Relation with derivatives Main article: [difference quotient](/source/Difference_quotient) The approximation of [derivatives](/source/Derivative) by finite differences plays a central role in [finite difference methods](/source/Finite_difference_method) for the [numerical](/source/Numerical_analysis) solution of [differential equations](/source/Differential_equation), especially [boundary value problems](/source/Boundary_value_problem). The [derivative](/source/Derivative) of a function f at a point x is defined by the [limit](/source/Limit_of_a_function) f ′ ( x ) = lim h → 0 f ( x + h ) − f ( x ) h . {\displaystyle f'(x)=\lim _{h\to 0}{\frac {f(x+h)-f(x)}{h}}.} If h has a fixed (non-zero) value instead of approaching zero, then the right-hand side of the above equation would be written f ( x + h ) − f ( x ) h = Δ h [ f ] ( x ) h . {\displaystyle {\frac {f(x+h)-f(x)}{h}}={\frac {\Delta _{h}[f](x)}{h}}.} Hence, the forward difference divided by h approximates the derivative when h is small. The error in this approximation can be derived from [Taylor's theorem](/source/Taylor's_theorem). Assuming that f is twice differentiable, we have Δ h [ f ] ( x ) h − f ′ ( x ) = o ( h ) → 0 as h → 0. {\displaystyle {\frac {\Delta _{h}[f](x)}{h}}-f'(x)=o(h)\to 0\quad {\text{as }}h\to 0.} The same formula holds for the backward difference: ∇ h [ f ] ( x ) h − f ′ ( x ) = o ( h ) → 0 as h → 0. {\displaystyle {\frac {\nabla _{h}[f](x)}{h}}-f'(x)=o(h)\to 0\quad {\text{as }}h\to 0.} However, the central (also called centered) difference yields a more accurate approximation. If f is three times differentiable, δ h [ f ] ( x ) h − f ′ ( x ) = o ( h 2 ) . {\displaystyle {\frac {\delta _{h}[f](x)}{h}}-f'(x)=o\left(h^{2}\right).} The main problem[*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*] with the central difference method, however, is that oscillating functions can yield zero derivative. If *f*(*nh*) = 1 for n odd, and *f*(*nh*) = 2 for n even, then *f*′(*nh*) = 0 if it is calculated with the [central difference scheme](/source/Central_difference_scheme). This is particularly troublesome if the domain of f is discrete. See also [Symmetric derivative](/source/Symmetric_derivative). Authors for whom finite differences mean finite difference approximations define the forward/backward/central differences as the quotients given in this section (instead of employing the definitions given in the previous section).[1][2][3] ## Higher-order differences This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "Finite difference" – news · newspapers · books · scholar · JSTOR (July 2018) (Learn how and when to remove this message) In an analogous way, one can obtain finite difference approximations to higher order derivatives and differential operators. For example, by using the above central difference formula for *f* ′(*x* + ⁠*h*/2⁠) and *f* ′(*x* − ⁠*h*/2⁠) and applying a central difference formula for the derivative of *f* ′ at x, we obtain the central difference approximation of the second derivative of f : **Second-order central** - f ″ ( x ) ≈ δ h 2 [ f ] ( x ) h 2 = f ( x + h ) − f ( x ) h − f ( x ) − f ( x − h ) h h = f ( x + h ) − 2 f ( x ) + f ( x − h ) h 2 . {\displaystyle f''(x)\approx {\frac {\delta _{h}^{2}[f](x)}{h^{2}}}={\frac {{\frac {f(x+h)-f(x)}{h}}-{\frac {f(x)-f(x-h)}{h}}}{h}}={\frac {f(x+h)-2f(x)+f(x-h)}{h^{2}}}~.} Similarly we can apply other differencing formulas in a recursive manner. **Second-order forward** - f ″ ( x ) ≈ Δ h 2 [ f ] ( x ) h 2 = f ( x + 2 h ) − f ( x + h ) h − f ( x + h ) − f ( x ) h h = f ( x + 2 h ) − 2 f ( x + h ) + f ( x ) h 2 . {\displaystyle f''(x)\approx {\frac {\Delta _{h}^{2}[f](x)}{h^{2}}}={\frac {{\frac {f(x+2h)-f(x+h)}{h}}-{\frac {f(x+h)-f(x)}{h}}}{h}}={\frac {f(x+2h)-2f(x+h)+f(x)}{h^{2}}}~.} **Second-order backward** - f ″ ( x ) ≈ ∇ h 2 [ f ] ( x ) h 2 = f ( x ) − f ( x − h ) h − f ( x − h ) − f ( x − 2 h ) h h = f ( x ) − 2 f ( x − h ) + f ( x − 2 h ) h 2 . {\displaystyle f''(x)\approx {\frac {\nabla _{h}^{2}[f](x)}{h^{2}}}={\frac {{\frac {f(x)-f(x-h)}{h}}-{\frac {f(x-h)-f(x-2h)}{h}}}{h}}={\frac {f(x)-2f(x-h)+f(x-2h)}{h^{2}}}~.} More generally, the **n-th order forward, backward, and central** differences are given by, respectively, **Forward** - Δ h n [ f ] ( x ) = ∑ j = 0 n ( − 1 ) n − j ( n j ) f ( x + j h ) , {\displaystyle \Delta _{h}^{n}[f](x)=\sum _{j=0}^{n}(-1)^{n-j}{\binom {n}{j}}f{\bigl (}x+jh{\bigr )},} **Backward** - ∇ h n [ f ] ( x ) = ∑ j = 0 n ( − 1 ) j ( n j ) f ( x − j h ) , {\displaystyle \nabla _{h}^{n}[f](x)=\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}f(x-jh),} **Central** - δ h n [ f ] ( x ) = ∑ j = 0 n ( − 1 ) j ( n j ) f ( x + ( n 2 − j ) h ) . {\displaystyle \delta _{h}^{n}[f](x)=\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}f\left(x+\left({\frac {n}{2}}-j\right)h\right)~.} These equations use [binomial coefficients](/source/Binomial_coefficient) after the summation sign shown as ( n j ) . {\textstyle \ {\binom {n}{j}}~.} Each row of [Pascal's triangle](/source/Pascal's_triangle) provides the coefficient for each value of j . Note that the central difference will, for odd n, have h multiplied by non-integers. This is often a problem because it amounts to changing the interval of discretization. The problem may be remedied substituting the average of δ n [ f ] ( x − h 2 ) {\textstyle \delta ^{n}[f](x-{\tfrac {h}{2}})} and δ n [ f ] ( x + h 2 ) . {\textstyle \delta ^{n}[f](x+{\tfrac {h}{2}}).} Forward differences applied to a [sequence](/source/Sequence) are sometimes called the [binomial transform](/source/Binomial_transform) of the sequence, and have a number of interesting combinatorial properties. Forward differences may be evaluated using the [Nörlund–Rice integral](/source/N%C3%B6rlund%E2%80%93Rice_integral). The integral representation for these types of series is interesting, because the integral can often be evaluated using [asymptotic expansion](/source/Asymptotic_expansion) or [saddle-point](/source/Saddle-point) techniques; by contrast, the forward difference series can be extremely hard to evaluate numerically, because the binomial coefficients grow rapidly for large n. The relationship of these higher-order differences with the respective derivatives is straightforward, d n f ( d x ) n ( x ) = Δ h n [ f ] ( x ) h n + o ( h ) = ∇ h n [ f ] ( x ) h n + o ( h ) = δ h n [ f ] ( x ) h n + o ( h 2 ) . {\displaystyle {\frac {\mathrm {d} ^{n}f}{(\mathrm {d} x)^{n}}}(x)={\frac {\Delta _{h}^{n}[f](x)}{h^{n}}}+{\mathcal {o}}(h)={\frac {\nabla _{h}^{n}[f](x)}{h^{n}}}+{\mathcal {o}}(h)={\frac {\delta _{h}^{n}[f](x)}{h^{n}}}+{\mathcal {o}}\!\left(h^{2}\right).} Higher-order differences can also be used to construct better approximations. As mentioned above, the first-order difference approximates the first-order derivative up to a term of order h. However, the combination Δ h [ f ] ( x ) − 1 2 Δ h 2 [ f ] ( x ) h = − f ( x + 2 h ) − 4 f ( x + h ) + 3 f ( x ) 2 h {\displaystyle {\frac {\Delta _{h}[f](x)-{\frac {1}{2}}\Delta _{h}^{2}[f](x)}{h}}=-{\frac {f(x+2h)-4f(x+h)+3f(x)}{2h}}} approximates *f* ′(*x*) up to a term of order *h*2. This can be proven by expanding the above expression in [Taylor series](/source/Taylor_series), or by using the calculus of finite differences, explained below. If necessary, the finite difference can be centered about any point by mixing forward, backward, and central differences. Sometimes, the low order derivatives of a function may be analytically known, but high order derivatives are not. In these cases, the high order derivatives can be approximated by finite difference of low order derivatives, which is often more accurate and numerically more stable than finite difference of the function *f* (*x*) itself. This is sometimes called seminumerical differentiation.[5] For example, when the first order derivative *f* ′(*x*) is available but the second order derivative *f* ′′(*x*) is not, the latter can be approximated by second-order central difference of *f* ′(*x*): f ″ ( x ) ≈ f ′ ( x + h ) − f ′ ( x − h ) 2 h . {\displaystyle f''(x)\approx {\frac {f'(x+h)-f'(x-h)}{2h}}~.} ## Polynomials For a given [polynomial](/source/Polynomial) of degree *n* ≥ 1, expressed in the function *P*(*x*), with real numbers *a* ≠ 0 and *b* and *lower order terms* (if any) marked as l.o.t.: P ( x ) = a x n + b x n − 1 + l . o . t . {\displaystyle P(x)=ax^{n}+\;bx^{n-1}+~l.o.t.} After *n* pairwise differences, the following result can be achieved, where *h* ≠ 0 is a [real number](/source/Real_number) marking the arithmetic difference:[6] Δ h n [ P ] ( x ) = a h n n ! {\displaystyle \Delta _{h}^{n}[P](x)=ah^{n}n!} Only the coefficient of the highest-order term remains. As this result is constant with respect to *x*, any further pairwise differences will have the value 0. ### Inductive proof #### Base case Let *Q*(*x*) be a polynomial of degree 1: Δ h [ Q ] ( x ) = Q ( x + h ) − Q ( x ) = [ a ( x + h ) + b ] − [ a x + b ] = a h = a h 1 1 ! {\displaystyle \Delta _{h}[Q](x)=Q(x+h)-Q(x)=[a(x+h)+b]-[ax+b]=ah=ah^{1}1!} This proves it for the base case. #### Inductive step Let *R*(*x*) be a polynomial of degree *m* − 1 where *m* ≥ 2 and the coefficient of the highest-order term be *a* ≠ 0. Assuming the following holds true for all polynomials of degree *m* − 1: Δ h m − 1 [ R ] ( x ) = a h m − 1 ( m − 1 ) ! {\displaystyle \Delta _{h}^{m-1}[R](x)=ah^{m-1}(m-1)!} Let *S*(*x*) be a polynomial of degree *m*. With one pairwise difference: Δ h [ S ] ( x ) = [ a ( x + h ) m + b ( x + h ) m − 1 + l.o.t. ] − [ a x m + b x m − 1 + l.o.t. ] = a h m x m − 1 + l.o.t. = T ( x ) {\displaystyle \Delta _{h}[S](x)=[a(x+h)^{m}+b(x+h)^{m-1}+{\text{l.o.t.}}]-[ax^{m}+bx^{m-1}+{\text{l.o.t.}}]=ahmx^{m-1}+{\text{l.o.t.}}=T(x)} As *ahm* ≠ 0, this results in a polynomial *T*(*x*) of degree *m* − 1, with *ahm* as the coefficient of the highest-order term. Given the assumption above and *m* − 1 pairwise differences (resulting in a total of *m* pairwise differences for *S*(*x*)), it can be found that: Δ h m − 1 [ T ] ( x ) = a h m ⋅ h m − 1 ( m − 1 ) ! = a h m m ! {\displaystyle \Delta _{h}^{m-1}[T](x)=ahm\cdot h^{m-1}(m-1)!=ah^{m}m!} This completes the proof. ### Application This identity can be used to find the lowest-degree polynomial that intercepts a number of points (*x*, *y*) where the difference on the *x*-axis from one point to the next is a constant *h* ≠ 0. For example, given the following points: x y 1 4 4 109 7 772 10 2641 13 6364 We can use a differences table, where for all cells to the right of the first *y*, the following relation to the cells in the column immediately to the left exists for a cell (*a* + 1, *b* + 1), with the top-leftmost cell being at coordinate (0, 0): ( a + 1 , b + 1 ) = ( a , b + 1 ) − ( a , b ) {\displaystyle (a+1,b+1)=(a,b+1)-(a,b)} To find the first term, the following table can be used: x y Δy Δ2y Δ3y 1 4 4 109 105 7 772 663 558 10 2641 1869 1206 648 13 6364 3723 1854 648 This arrives at a constant 648. The arithmetic difference is *h* = 3, as established above. Given the number of pairwise differences needed to reach the constant, it can be surmised this is a polynomial of degree 3. Thus, using the identity above: 648 = a ⋅ 3 3 ⋅ 3 ! = a ⋅ 27 ⋅ 6 = a ⋅ 162 {\displaystyle 648=a\cdot 3^{3}\cdot 3!=a\cdot 27\cdot 6=a\cdot 162} Solving for *a*, it can be found to have the value 4. Thus, the first term of the polynomial is 4*x*3. Then, subtracting out the first term, which lowers the polynomial's degree, and finding the finite difference again: x y Δy Δ2y 1 4 − 4(1)3 = 4 − 4 = 0 4 109 − 4(4)3 = 109 − 256 = −147 −147 7 772 − 4(7)3 = 772 − 1372 = −600 −453 −306 10 2641 − 4(10)3 = 2641 − 4000 = −1359 −759 −306 13 6364 − 4(13)3 = 6364 − 8788 = −2424 −1065 −306 Here, the constant is achieved after only two pairwise differences, thus the following result: − 306 = a ⋅ 3 2 ⋅ 2 ! = a ⋅ 18 {\displaystyle -306=a\cdot 3^{2}\cdot 2!=a\cdot 18} Solving for *a*, which is −17, the polynomial's second term is −17*x*2. Moving on to the next term, by subtracting out the second term: x y Δy 1 0 − (−17(1)2) = 0 + 17 = 17 4 −147 − (−17(4)2) = −147 + 272 = 125 108 7 −600 − (−17(7)2) = −600 + 833 = 233 108 10 −1359 − (−17(10)2) = −1359 + 1700 = 341 108 13 −2424 − (−17(13)2) = −2424 + 2873 = 449 108 Thus the constant is achieved after only one pairwise difference: 108 = a ⋅ 3 1 ⋅ 1 ! = a ⋅ 3 {\displaystyle 108=a\cdot 3^{1}\cdot 1!=a\cdot 3} It can be found that *a* = 36 and thus the third term of the polynomial is **36*x***. Subtracting out the third term: x y 1 17 − 36(1) = 17 − 36 = −19 4 125 − 36(4) = 125 − 144 = −19 7 233 − 36(7) = 233 − 252 = −19 10 341 − 36(10) = 341 − 360 = −19 13 449 − 36(13) = 449 − 468 = −19 Without any pairwise differences, it is found that the 4th and final term of the polynomial is the constant −19. Thus, the lowest-degree polynomial intercepting all the points in the first table is found: 4 x 3 − 17 x 2 + 36 x − 19 {\displaystyle 4x^{3}-17x^{2}+36x-19} ## Arbitrarily sized kernels Main article: [Finite difference coefficient](/source/Finite_difference_coefficient) Further information: [Five-point stencil](/source/Five-point_stencil) Using [linear algebra](/source/Linear_algebra) one can construct finite difference approximations which utilize an arbitrary number of points to the left and a (possibly different) number of points to the right of the evaluation point, for any order derivative. This involves solving a linear system such that the [Taylor expansion](/source/Taylor_expansion) of the sum of those points around the evaluation point best approximates the Taylor expansion of the desired derivative. Such formulas can be represented graphically on a hexagonal or diamond-shaped grid.[7] This is useful for differentiating a function on a grid, where, as one approaches the edge of the grid, one must sample fewer and fewer points on one side.[8] Finite difference approximations for non-standard (and even non-integer) stencils given an arbitrary stencil and a desired derivative order may be constructed.[9] ### Properties - For all positive k and n Δ k h n ( f , x ) = ∑ j 1 = 0 k − 1 ∑ j 2 = 0 k − 1 ⋯ ∑ j n = 0 k − 1 Δ h n ( f , x + j 1 h + j 2 h + ⋯ + j n h ) . {\displaystyle \Delta _{kh}^{n}\left(f,x\right)=\sum \limits _{j_{1}=0}^{k-1}\sum \limits _{j_{2}=0}^{k-1}\cdots \sum \limits _{j_{n}=0}^{k-1}\Delta _{h}^{n}\left(f,x+j_{1}h+j_{2}h+\cdots +j_{n}h\right).} - [Leibniz rule](/source/Leibniz_rule_(generalized_product_rule)): Δ h n ( f g , x ) = ∑ k = 0 n ( n k ) Δ h k ( f , x ) ⋅ Δ h n − k ( g , x + k h ) . {\displaystyle \Delta _{h}^{n}\left(fg,x\right)=\sum \limits _{k=0}^{n}{\binom {n}{k}}\Delta _{h}^{k}\left(f,x\right)\cdot \Delta _{h}^{n-k}\left(g,x+kh\right).} ## In differential equations Main article: [Finite difference method](/source/Finite_difference_method) An important application of finite differences is in [numerical analysis](/source/Numerical_analysis), especially in [numerical differential equations](/source/Numerical_partial_differential_equations), which aim at the numerical solution of [ordinary](/source/Ordinary_differential_equation) and [partial differential equations](/source/Partial_differential_equation). The idea is to replace the derivatives appearing in the differential equation by finite differences that approximate them. The resulting methods are called [finite difference methods](/source/Finite_difference_method). Common applications of the finite difference method are in computational science and engineering disciplines, such as [thermal engineering](/source/Thermal_engineering), [fluid mechanics](/source/Fluid_mechanics), etc. ## Newton's series The **[Newton series](/source/Newton_polynomial)** consists of the terms of the **Newton forward difference equation**, named after [Isaac Newton](/source/Isaac_Newton); in essence, it is the **Gregory–Newton interpolation formula**[10] (named after [Isaac Newton](/source/Isaac_Newton) and [James Gregory](/source/James_Gregory_(mathematician))), first published in his *[Principia Mathematica](/source/Philosophi%C3%A6_Naturalis_Principia_Mathematica)* in 1687,[11][12] namely the discrete analog of the continuous Taylor expansion, f ( x ) = ∑ k = 0 ∞ Δ k [ f ] ( a ) k ! ( x − a ) k = ∑ k = 0 ∞ ( x − a k ) Δ k [ f ] ( a ) , {\displaystyle f(x)=\sum _{k=0}^{\infty }{\frac {\Delta ^{k}[f](a)}{k!}}\,(x-a)_{k}=\sum _{k=0}^{\infty }{\binom {x-a}{k}}\,\Delta ^{k}[f](a),} which holds for any [polynomial](/source/Polynomial) function f and for many (but not all) [analytic functions](/source/Analytic_function). (It does not hold when f is [exponential type](/source/Exponential_type) π {\displaystyle \pi } . This is easily seen, as the sine function vanishes at integer multiples of π {\displaystyle \pi } ; the corresponding Newton series is identically zero, as all finite differences are zero in this case. Yet clearly, the sine function is not zero.) Here, the expression ( x k ) = ( x ) k k ! {\displaystyle {\binom {x}{k}}={\frac {(x)_{k}}{k!}}} is the [binomial coefficient](/source/Binomial_coefficient), and ( x ) k = x ( x − 1 ) ( x − 2 ) ⋯ ( x − k + 1 ) {\displaystyle (x)_{k}=x(x-1)(x-2)\cdots (x-k+1)} is the "[falling factorial](/source/Falling_factorial)" or "lower factorial", while the [empty product](/source/Empty_product) (*x*)0 is defined to be 1. In this particular case, there is an assumption of unit steps for the changes in the values of *x*, *h* = 1 of the generalization below. Note the formal correspondence of this result to [Taylor's theorem](/source/Taylor's_theorem). Historically, this, as well as the [Chu–Vandermonde identity](/source/Chu%E2%80%93Vandermonde_identity), ( x + y ) n = ∑ k = 0 n ( n k ) ( x ) n − k ( y ) k , {\displaystyle (x+y)_{n}=\sum _{k=0}^{n}{\binom {n}{k}}(x)_{n-k}\,(y)_{k},} (following from it, and corresponding to the [binomial theorem](/source/Binomial_theorem)), are included in the observations that matured to the system of [umbral calculus](/source/Umbral_calculus). Newton series expansions can be superior to Taylor series expansions when applied to discrete quantities like quantum spins (see [Holstein–Primakoff transformation](/source/Holstein%E2%80%93Primakoff_transformation)), [bosonic operator functions](/source/Normal_order#Bosonic_operator_functions) or discrete counting statistics.[13] To illustrate how one may use Newton's formula in actual practice, consider the first few terms of doubling the [Fibonacci sequence](/source/Fibonacci_sequence) *f* = 2, 2, 4, ... One can find a [polynomial](/source/Polynomial) that reproduces these values, by first computing a difference table, and then substituting the differences that correspond to *x*0 (underlined) into the formula as follows, x f = Δ 0 Δ 1 Δ 2 1 2 _ 0 _ 2 2 2 _ 2 3 4 f ( x ) = Δ 0 ⋅ 1 + Δ 1 ⋅ ( x − x 0 ) 1 1 ! + Δ 2 ⋅ ( x − x 0 ) 2 2 ! ( x 0 = 1 ) = 2 ⋅ 1 + 0 ⋅ x − 1 1 + 2 ⋅ ( x − 1 ) ( x − 2 ) 2 = 2 + ( x − 1 ) ( x − 2 ) {\displaystyle {\begin{matrix}{\begin{array}{|c||c|c|c|}\hline x&f=\Delta ^{0}&\Delta ^{1}&\Delta ^{2}\\\hline 1&{\underline {2}}&&\\&&{\underline {0}}&\\2&2&&{\underline {2}}\\&&2&\\3&4&&\\\hline \end{array}}&\quad {\begin{aligned}f(x)&=\Delta ^{0}\cdot 1+\Delta ^{1}\cdot {\dfrac {(x-x_{0})_{1}}{1!}}+\Delta ^{2}\cdot {\dfrac {(x-x_{0})_{2}}{2!}}\quad (x_{0}=1)\\\\&=2\cdot 1+0\cdot {\dfrac {x-1}{1}}+2\cdot {\dfrac {(x-1)(x-2)}{2}}\\\\&=2+(x-1)(x-2)\\\end{aligned}}\end{matrix}}} For the case of nonuniform steps in the values of x, Newton computes the [divided differences](/source/Divided_differences), Δ j , 0 = y j , Δ j , k = Δ j + 1 , k − 1 − Δ j , k − 1 x j + k − x j ∋ { k > 0 , j ≤ max ( j ) − k } , Δ 0 k = Δ 0 , k {\displaystyle \Delta _{j,0}=y_{j},\qquad \Delta _{j,k}={\frac {\Delta _{j+1,k-1}-\Delta _{j,k-1}}{x_{j+k}-x_{j}}}\quad \ni \quad \left\{k>0,\;j\leq \max \left(j\right)-k\right\},\qquad \Delta 0_{k}=\Delta _{0,k}} the series of products, P 0 = 1 , P k + 1 = P k ⋅ ( ξ − x k ) , {\displaystyle {P_{0}}=1,\quad \quad P_{k+1}=P_{k}\cdot \left(\xi -x_{k}\right),} and the resulting polynomial is the [scalar product](/source/Scalar_product),[14] f ( ξ ) = Δ 0 ⋅ P ( ξ ) . {\displaystyle f(\xi )=\Delta 0\cdot P\left(\xi \right).} In analysis with [p-adic numbers](/source/P-adic_number), [Mahler's theorem](/source/Mahler's_theorem) states that the assumption that f is a polynomial function can be weakened all the way to the assumption that f is merely continuous. [Carlson's theorem](/source/Carlson's_theorem) provides necessary and sufficient conditions for a Newton series to be unique, if it exists. However, a Newton series does not, in general, exist. The Newton series, together with the [Stirling series](/source/Stirling_series) and the [Selberg series](/source/Selberg_class), is a special case of the general [difference series](/source/Difference_series), all of which are defined in terms of suitably scaled forward differences. In a compressed and slightly more general form and equidistant nodes the formula reads f ( x ) = ∑ k = 0 ( x − a h k ) ∑ j = 0 k ( − 1 ) k − j ( k j ) f ( a + j h ) . {\displaystyle f(x)=\sum _{k=0}{\binom {\frac {x-a}{h}}{k}}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}f(a+jh).} ## Calculus of finite differences The forward difference can be considered as an [operator](/source/Operator_(mathematics)), called the [difference operator](/source/Difference_operator), which maps the function f to Δ*h*[*f*].[15][16] This operator amounts to Δ h = T h − I , {\displaystyle \Delta _{h}=\operatorname {T} _{h}-\operatorname {I} ,} where T*h* is the [shift operator](/source/Shift_operator) with step h, defined by T*h*[*f*](*x*) = *f*(*x* + *h*), and I is the [identity operator](/source/Identity_operator). The finite difference of higher orders can be defined in recursive manner as Δ*n* *h* ≡ Δ*h*(Δ*n* − 1 *h*). Another equivalent definition is Δ*n* *h* ≡ [T*h* − I]*n*. The difference operator Δ*h* is a [linear operator](/source/Linear_operator), as such it satisfies Δ*h*[*α f* + *β g*](*x*) = *α* Δ*h*[*f*](*x*) + *β* Δ*h*[*g*](*x*). It also satisfies a special [Leibniz rule](/source/Leibniz_rule_(generalized_product_rule)): - Δ h ⁡ ( f ( x ) g ( x ) ) = ( Δ h ⁡ f ( x ) ) g ( x + h ) + f ( x ) ( Δ h ⁡ g ( x ) ) . {\displaystyle \operatorname {\Delta } _{h}{\bigl (}f(x)g(x){\bigr )}={\bigl (}\operatorname {\Delta } _{h}f(x){\bigr )}g(x+h)+f(x){\bigl (}\operatorname {\Delta } _{h}g(x){\bigr )}~.} Similar Leibniz rules hold for the backward and central differences. Formally applying the [Taylor series](/source/Taylor_series) with respect to h, yields the operator equation Δ h = h D + 1 2 ! h 2 D 2 + 1 3 ! h 3 D 3 + ⋯ = e h D − I , {\displaystyle \operatorname {\Delta } _{h}=h\operatorname {D} +{\frac {1}{2!}}h^{2}\operatorname {D} ^{2}+{\frac {1}{3!}}h^{3}\operatorname {D} ^{3}+\cdots =e^{h\operatorname {D} }-\operatorname {I} ,} where D denotes the conventional, continuous derivative operator, mapping f to its derivative *f*′. The expansion is valid when both sides act on [analytic functions](/source/Analytic_function), for sufficiently small h; in the special case that the series of derivatives terminates (when the function operated on is a finite [polynomial](/source/Polynomial)) the expression is exact, for *all* finite stepsizes, h . Thus T*h* = *e**h* D, and formally inverting the exponential yields h D = ln ⁡ ( 1 + Δ h ) = Δ h − 1 2 Δ h 2 + 1 3 Δ h 3 − ⋯ . {\displaystyle h\operatorname {D} =\ln(1+\Delta _{h})=\Delta _{h}-{\tfrac {1}{2}}\,\Delta _{h}^{2}+{\tfrac {1}{3}}\,\Delta _{h}^{3}-\cdots ~.} This formula holds in the sense that both operators give the same result when applied to a polynomial. Even for analytic functions, the series on the right is not guaranteed to converge; it may be an [asymptotic series](/source/Asymptotic_series). However, it can be used to obtain more accurate approximations for the derivative. For instance, retaining the first two terms of the series yields the second-order approximation to *f* ′(*x*) mentioned at the end of the section *[§ Higher-order differences](#Higher-order_differences)*. The analogous formulas for the backward and central difference operators are h D = − ln ⁡ ( 1 − ∇ h ) and h D = 2 arsinh ⁡ ( 1 2 δ h ) . {\displaystyle h\operatorname {D} =-\ln(1-\nabla _{h})\quad {\text{ and }}\quad h\operatorname {D} =2\operatorname {arsinh} \left({\tfrac {1}{2}}\,\delta _{h}\right)~.} The calculus of finite differences is related to the [umbral calculus](/source/Umbral_calculus) of combinatorics. This remarkably systematic correspondence is due to the identity of the [commutators](/source/Commutators) of the umbral quantities to their continuum analogs (*h* → 0 limits), [ Δ h h , x T h − 1 ] = [ D , x ] = I . {\displaystyle \left[{\frac {\Delta _{h}}{h}},x\,\operatorname {T} _{h}^{-1}\right]=[\operatorname {D} ,x]=I.} A large number of formal differential relations of standard calculus involving functions *f*(*x*) thus *systematically map to umbral finite-difference analogs* involving *f*( *x* T−1 *h* ). For instance, the umbral analog of a monomial xn is a generalization of the above falling factorial ([Pochhammer k-symbol](/source/Pochhammer_k-symbol)), ( x ) n = ( x T h − 1 ) n = x ( x − h ) ( x − 2 h ) ⋯ ( x − ( n − 1 ) h ) , {\displaystyle (x)_{n}=\left(x\operatorname {T} _{h}^{-1}\right)^{n}=x\left(x-h\right)\left(x-2h\right)\cdots {\bigl (}x-\left(n-1\right)h{\bigr )},} so that Δ h h ( x ) n = n ( x ) n − 1 , {\displaystyle {\frac {\Delta _{h}}{h}}(x)_{n}=n(x)_{n-1},} hence the above Newton interpolation formula (by matching coefficients in the expansion of an arbitrary function *f*(*x*) in such symbols), and so on. For example, the umbral sine is sin ⁡ ( x T h − 1 ) = x − ( x ) 3 3 ! + ( x ) 5 5 ! − ( x ) 7 7 ! + ⋯ {\displaystyle \sin \left(x\operatorname {T} _{h}^{-1}\right)=x-{\frac {(x)_{3}}{3!}}+{\frac {(x)_{5}}{5!}}-{\frac {(x)_{7}}{7!}}+\cdots } As in the [continuum limit](/source/Continuum_limit), the [eigenfunction](/source/Eigenfunction) of ⁠Δ*h*/*h*⁠ also happens to be an exponential, - Δ h h ( 1 + λ h ) x h = Δ h h e ln ⁡ ( 1 + λ h ) x h = λ e ln ⁡ ( 1 + λ h ) x h , {\displaystyle {\frac {\Delta _{h}}{h}}(1+\lambda h)^{\frac {x}{h}}={\frac {\Delta _{h}}{h}}e^{\ln(1+\lambda h){\frac {x}{h}}}=\lambda e^{\ln(1+\lambda h){\frac {x}{h}}},} and hence *Fourier sums of continuum functions are readily, faithfully mapped to umbral Fourier sums*, i.e., involving the same Fourier coefficients multiplying these umbral basis exponentials.[17] This umbral exponential thus amounts to the exponential [generating function](/source/Generating_function) of the [Pochhammer symbols](/source/Pochhammer_symbol). Thus, for instance, the [Dirac delta function](/source/Dirac_delta_function) maps to its umbral correspondent, the [cardinal sine function](/source/Sinc_function) δ ( x ) ↦ sin ⁡ [ π 2 ( 1 + x h ) ] π ( x + h ) , {\displaystyle \delta (x)\mapsto {\frac {\sin \left[{\frac {\pi }{2}}\left(1+{\frac {x}{h}}\right)\right]}{\pi (x+h)}},} and so forth.[18] [Difference equations](/source/Difference_equation) can often be solved with techniques very similar to those for solving [differential equations](/source/Differential_equation). The inverse operator of the forward difference operator, so then the umbral integral, is the [indefinite sum](/source/Indefinite_sum) or antidifference operator. ### Rules for calculus of finite difference operators Analogous to [rules for finding the derivative](/source/Differentiation_rules), we have: - **Constant rule**: If c is a [constant](/source/Constant_(mathematics)), then Δ c = 0 {\displaystyle \Delta c=0} - **[Linearity](/source/Linearity_of_differentiation)**: If a and b are [constants](/source/Constant_(mathematics)), Δ ( a f + b g ) = a Δ f + b Δ g {\displaystyle \Delta (af+bg)=a\Delta f+b\Delta g} All of the above rules apply equally well to any difference operator as to Δ, including δ and ∇. - **[Product rule](/source/Product_rule)**: Δ ( f g ) = f Δ g + g Δ f + Δ f Δ g ∇ ( f g ) = f ∇ g + g ∇ f − ∇ f ∇ g {\displaystyle {\begin{aligned}\Delta (fg)&=f\,\Delta g+g\Delta f+\Delta f\Delta g\\[4pt]\nabla (fg)&=f\,\nabla g+g\nabla f-\nabla f\nabla g\end{aligned}}} - **[Quotient rule](/source/Quotient_rule)**: ∇ ( f g ) = ( det [ ∇ f ∇ g f g ] ) / ( g ⋅ det [ g ∇ g 1 1 ] ) {\displaystyle \nabla \left({\frac {f}{g}}\right)=\left.\left(\det {\begin{bmatrix}\nabla f&\nabla g\\f&g\end{bmatrix}}\right)\right/\left(g\cdot \det {\begin{bmatrix}g&\nabla g\\1&1\end{bmatrix}}\right)} or ∇ ( f g ) = g ∇ f − f ∇ g g ⋅ ( g − ∇ g ) {\displaystyle \nabla \left({\frac {f}{g}}\right)={\frac {g\,\nabla f-f\,\nabla g}{g\cdot (g-\nabla g)}}} - **[Summation rules](/source/Fundamental_theorem_of_calculus)**: ∑ n = a b Δ f ( n ) = f ( b + 1 ) − f ( a ) ∑ n = a b ∇ f ( n ) = f ( b ) − f ( a − 1 ) {\displaystyle {\begin{aligned}\sum _{n=a}^{b}\Delta f(n)&=f(b+1)-f(a)\\\sum _{n=a}^{b}\nabla f(n)&=f(b)-f(a-1)\end{aligned}}} See references.[19][20][21][22] ## Generalizations - A **generalized finite difference** is usually defined as Δ h μ [ f ] ( x ) = ∑ k = 0 N μ k f ( x + k h ) , {\displaystyle \Delta _{h}^{\mu }[f](x)=\sum _{k=0}^{N}\mu _{k}f(x+kh),} where *μ* = (*μ*0, …, *μN*) is its coefficient vector. An **infinite difference** is a further generalization, where the finite sum above is replaced by an [infinite series](/source/Series_(mathematics)). Another way of generalization is making coefficients *μk* depend on point x: *μk* = *μk*(*x*), thus considering **weighted finite difference**. Also one may make the step h depend on point x: *h* = *h*(*x*). Such generalizations are useful for constructing different [modulus of continuity](/source/Modulus_of_continuity). - The generalized difference can be seen as the polynomial rings *R*[*Th*]. It leads to difference algebras. - Difference operator generalizes to [Möbius inversion](/source/M%C3%B6bius_inversion) over a [partially ordered set](/source/Partially_ordered_set). - As a convolution operator: Via the formalism of [incidence algebras](/source/Incidence_algebra), difference operators and other Möbius inversion can be represented by [convolution](/source/Convolution) with a function on the poset, called the [Möbius function](/source/M%C3%B6bius_function_(combinatorics)) μ; for the difference operator, μ is the sequence (1, −1, 0, 0, 0, …). ## Multivariate finite differences Finite differences can be considered in more than one variable. They are analogous to [partial derivatives](/source/Partial_derivative) in several variables. Some partial derivative approximations are: f x ( x , y ) ≈ f ( x + h , y ) − f ( x − h , y ) 2 h f y ( x , y ) ≈ f ( x , y + k ) − f ( x , y − k ) 2 k f x x ( x , y ) ≈ f ( x + h , y ) − 2 f ( x , y ) + f ( x − h , y ) h 2 f y y ( x , y ) ≈ f ( x , y + k ) − 2 f ( x , y ) + f ( x , y − k ) k 2 f x y ( x , y ) ≈ f ( x + h , y + k ) − f ( x + h , y − k ) − f ( x − h , y + k ) + f ( x − h , y − k ) 4 h k . {\displaystyle {\begin{aligned}f_{x}(x,y)&\approx {\frac {f(x+h,y)-f(x-h,y)}{2h}}\\f_{y}(x,y)&\approx {\frac {f(x,y+k)-f(x,y-k)}{2k}}\\f_{xx}(x,y)&\approx {\frac {f(x+h,y)-2f(x,y)+f(x-h,y)}{h^{2}}}\\f_{yy}(x,y)&\approx {\frac {f(x,y+k)-2f(x,y)+f(x,y-k)}{k^{2}}}\\f_{xy}(x,y)&\approx {\frac {f(x+h,y+k)-f(x+h,y-k)-f(x-h,y+k)+f(x-h,y-k)}{4hk}}.\end{aligned}}} Alternatively, for applications in which the computation of f is the most costly step, and both first and second derivatives must be computed, a more efficient formula for the last case is f x y ( x , y ) ≈ f ( x + h , y + k ) − f ( x + h , y ) − f ( x , y + k ) + 2 f ( x , y ) − f ( x − h , y ) − f ( x , y − k ) + f ( x − h , y − k ) 2 h k , {\displaystyle f_{xy}(x,y)\approx {\frac {f(x+h,y+k)-f(x+h,y)-f(x,y+k)+2f(x,y)-f(x-h,y)-f(x,y-k)+f(x-h,y-k)}{2hk}},} since the only values to compute that are not already needed for the previous four equations are *f*(*x* + *h*, *y* + *k*) and *f*(*x* − *h*, *y* − *k*). For functions with N {\displaystyle N} variables f ( x 1 , x 2 , … , x N ) {\displaystyle f(x_{1},x_{2},\ldots ,x_{N})} , evaluating the full m {\displaystyle m} -th order derivative tensor via finite difference requires O ( N m ) {\displaystyle O(N^{m})} calls of the function f {\displaystyle f} (where we have used the [Big O notation](/source/Big_O_notation) to denote the asymptotic scaling behavior), or O ( N m − m ′ ) {\displaystyle O(N^{m-m'})} calls of the m ′ {\displaystyle m'} -th order derivative of the function f {\displaystyle f} (where m ′ < m {\displaystyle m'