Editing Finite difference

{{Use American English|date = March 2019}}
{{Short description|Discrete analog of a derivative}}
{{Use mdy dates|date=September 2011}}
A '''finite difference''' is a mathematical expression of the form {{math|''f''(''x'' + ''b'') − ''f''(''x'' + ''a'')}}. Finite differences (or the associated [[difference quotient]]s) are often used as approximations of derivatives, such as in [[numerical differentiation]].

The [[difference operator]], commonly denoted <math>\Delta</math>, is the [[operator (mathematics)|operator]] that maps a function {{mvar|f}} to the function <math>\Delta[f]</math> defined by
<math display="block">\Delta[f](x) = f(x+1)-f(x).</math>
A [[difference equation]] is a [[functional equation]] that involves the finite difference operator in the same way as a [[differential equation]] involves [[derivative]]s. There are many similarities between difference equations and differential equations. Certain [[Recurrence relation#Relationship to difference equations narrowly defined|recurrence relations]] can be written as difference equations by replacing iteration notation with finite differences.

In [[numerical analysis]], finite differences are widely used for [[#Relation with derivatives|approximating derivatives]], and the term "finite difference" is often used as an abbreviation of "finite difference approximation of derivatives".<ref name="WilmottHowison1995">{{cite book|author1=Paul Wilmott|author2=Sam Howison|author3=Jeff Dewynne|title=The Mathematics of Financial Derivatives: A Student Introduction|year=1995|publisher=Cambridge University Press|isbn=978-0-521-49789-3|page=[https://archive.org/details/mathematicsoffin00wilm/page/137 137]|url-access=registration|url=https://archive.org/details/mathematicsoffin00wilm/page/137}}</ref><ref name="Olver2013">{{cite book|author=Peter Olver|author-link=Peter J. Olver|title=Introduction to Partial Differential Equations|year=2013|publisher=Springer Science & Business Media|isbn=978-3-319-02099-0| page=182}}</ref><ref name="Chaudhry2007">{{cite book|author=M Hanif Chaudhry|title=Open-Channel Flow|year=2007| publisher=Springer|isbn=978-0-387-68648-6|pages=369}}</ref>

Finite differences were introduced by [[Brook Taylor]] in 1715 and have also been studied as abstract self-standing mathematical objects in works by [[George Boole]] (1860), [[L. M. Milne-Thomson]] (1933), and {{interlanguage link|Károly Jordan|de}} (1939). Finite differences trace their origins back to one of [[Jost Bürgi]]'s algorithms ({{circa|1592}}) and work by others including [[Isaac Newton]]. The formal calculus of finite differences can be viewed as an alternative to the [[calculus]] of [[infinitesimal]]s.<ref>Jordán, op. cit., p. 1 and Milne-Thomson, p. xxi. Milne-Thomson,  Louis Melville (2000):  ''The Calculus of Finite Differences'' (Chelsea Pub Co, 2000)  {{ISBN|978-0821821077}}</ref>

==Basic types==
[[File:Finite difference method.svg|The three types of the finite differences. The central difference about ''x'' gives the best approximation of the derivative of the function at ''x''.|307x307px|thumb]]
Three basic types are commonly considered: ''forward'', ''backward'', and ''central'' finite differences.<ref name="WilmottHowison1995"/><ref name="Olver2013"/><ref name="Chaudhry2007"/>

A '''{{vanchor|forward difference}}''', denoted <math>\Delta_h[f],</math> of a [[function (mathematics)|function]] {{mvar|f}} is a function defined as
<math display="block"> \Delta_h[f](x) =  f(x + h) - f(x). </math>

Depending on the application, the spacing {{mvar|h}} may be variable or constant.  When omitted, {{mvar|h}} is taken to be 1; that is, 
<math display="block"> \Delta[f](x) =  \Delta_1[f](x) =f(x+1)-f(x) .</math>

A '''{{vanchor|backward difference}}''' uses the function values at {{mvar|x}} and {{math|''x'' − ''h''}}, instead of the values at {{math|''x'' + ''h''}} and&nbsp;{{mvar|x}}:
<math display="block"> \nabla_h[f](x) =  f(x) - f(x-h)=\Delta_h[f](x-h). </math>

Finally, the '''{{vanchor|central difference}}''' is given by
<math display="block"> \delta_h[f](x) = f(x+\tfrac{h}2)-f(x-\tfrac{h}2)=\Delta_{h/2}[f](x)+\nabla_{h/2}[f](x).</math>

== Relation with derivatives ==
{{main|difference quotient}}
{{anchor|finite difference approximation}}
The approximation of [[derivative]]s by finite differences plays a central role in [[finite difference method]]s for the [[numerical analysis|numerical]] solution of [[differential equation]]s, especially [[boundary value problem]]s.

The [[derivative]] of a function {{mvar|f}} at a point {{mvar|x}}  is defined by the [[limit of a function|limit]]
<math display="block"> f'(x) = \lim_{h \to 0} \frac{f(x+h) - f(x)}{h}. </math>

If {{mvar|h}} has a fixed (non-zero) value instead of approaching zero, then the right-hand side of the above equation would be written
<math display="block"> \frac{f(x + h) - f(x)}{h} = \frac{\Delta_h[f](x)}{h}. </math>

Hence, the forward difference divided by {{mvar|h}} approximates the derivative when {{mvar|h}} is small. The error in this approximation can be derived from [[Taylor's theorem]]. Assuming that {{mvar|f}} is twice differentiable, we have
<math display="block"> \frac{\Delta_h[f](x)}{h} - f'(x) = o(h)\to 0 \quad  \text{as }h \to 0. </math>

The same formula holds for the backward difference:
<math display="block"> \frac{\nabla_h[f](x)}{h} - f'(x) = o(h)\to 0 \quad  \text{as }h \to 0. </math>

However, the central (also called centered) difference yields a more accurate approximation. If {{mvar|f}} is three times differentiable,
<math display="block"> \frac{\delta_h[f](x)}{h} - f'(x) =  o\left(h^2\right) . </math>

The main problem{{citation needed|date=December 2017}} with the central difference method, however, is that oscillating functions can yield zero derivative. If  {{math|1=''f''(''nh'') = 1}} for {{mvar|n}} odd, and {{math|1=''f''(''nh'') = 2}}  for {{mvar|n}} even, then {{math|1=''f''′(''nh'') = 0}} if it is calculated with the [[central difference scheme]]. This is particularly troublesome if the domain of {{mvar|f}} is discrete. See also [[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).<ref name="WilmottHowison1995"/><ref name="Olver2013"/><ref name="Chaudhry2007"/>

==Higher-order differences==
{{more citations needed|section|date=July 2018}}  <!-- this section is linked to further down in the article -->

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 {{math|''f''′(''x'' + {{sfrac|''h''|2}})}}  and {{math|''f''′(''x'' − {{sfrac|''h''|2}})}}   and applying a central difference formula for the derivative of {{math|''f''′}} at {{mvar|x}}, we obtain the central difference approximation of the second derivative of {{mvar|f}}:

;Second-order central :<math> 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) - 2 f(x) + f(x-h)}{h^{2}} . </math>

Similarly we can apply other differencing formulas in a recursive manner.

;Second order forward :<math> 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) - 2 f(x+h) + f(x)}{h^{2}} . </math>
;Second order backward :<math> 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) - 2 f(x-h) + f(x - 2h)}{h^{2}} . </math>

More generally, the  '''{{mvar|n}}-th order forward, backward, and central''' differences are given by, respectively,

;Forward :<math>\Delta^n_h[f](x) = \sum_{i = 0}^{n} (-1)^{n-i} \binom{n}{i} f\bigl(x + i h\bigr),</math>
;Backward :<math>\nabla^n_h[f](x) = \sum_{i = 0}^{n} (-1)^i \binom{n}{i} f(x - ih),</math>
;Central :<math>\delta^n_h[f](x) = \sum_{i = 0}^{n} (-1)^i \binom{n}{i} f\left(x + \left(\frac{n}{2} - i\right) h\right).</math>

These equations use [[binomial coefficient]]s after the summation sign shown as {{math|<big><big>(</big></big>{{su|p=''n''|b=''i''|a=c}}<big><big>)</big></big>}}.  Each row of [[Pascal's triangle]] provides the coefficient for each value of {{mvar|i}}.

Note that the central difference will, for odd {{mvar|n}}, have {{mvar|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  <math>\ \delta^n[f](\ x - \tfrac{\ h\ }{ 2 }\ )\ </math>  and  <math>\ \delta^n[f](\ x + \tfrac{\ h\ }{ 2 }\ ) ~.</math>

Forward differences applied to a [[sequence]] are sometimes called the [[binomial transform]] of the sequence, and have a number of interesting combinatorial properties. Forward differences may be evaluated using the [[Nörlund&ndash;Rice integral]]. The integral representation for these types of series is interesting, because the integral can often be evaluated using [[asymptotic expansion]] or [[saddle-point]] techniques; by contrast, the forward difference series can be extremely hard to evaluate numerically, because the binomial coefficients grow rapidly for large {{mvar|n}}.

The relationship of these higher-order differences with the respective derivatives is  straightforward,
<math display="block">\frac{d^n f}{d x^n}(x) = \frac{\Delta_h^n[f](x)}{h^n}+o(h) = \frac{\nabla_h^n[f](x)}{h^n}+o(h) = \frac{\delta_h^n[f](x)}{h^n} + o\left(h^2\right).</math>

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 {{mvar|h}}. However, the combination
<math display="block"> \frac{\Delta_h[f](x) - \frac12 \Delta_h^2[f](x)}{h} = - \frac{f(x+2h)-4f(x+h)+3f(x)}{2h} </math>
approximates {{math|''f''′(''x'')}} up to a term of order {{math|''h''<sup>2</sup>}}. This can be proven by expanding the above expression in [[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.

==Polynomials==
For a given [[polynomial]] of degree {{math|''n'' &ge; 1}}, expressed in the function {{math|''P''(''x'')}}, with real numbers {{math|''a'' &ne; 0}} and {{math|''b''}} and ''lower order terms'' (if any) marked as {{math|''l.o.t.''}}:
<math display="block">P(x) = ax^n + bx^{n-1} + l.o.t.</math>

After {{math|''n''}} pairwise differences, the following result can be achieved, where {{math|''h'' &ne; 0}} is a [[real number]] marking the arithmetic difference:<ref>{{cite web| url=https://divisbyzero.com/2018/02/13/finite-differences-of-polynomials/| title=Finite differences of polynomials| date=February 13, 2018 }}</ref>
<math display="block">\Delta_h^n [P](x) = ah^nn!</math>

Only the coefficient of the highest-order term remains. As this result is constant with respect to {{math|''x''}}, any further pairwise differences will have the value {{math|0}}.

===Inductive proof===
====Base case====
Let {{math|''Q''(''x'')}} be a polynomial of degree {{math|1}}:
<math display=block>\Delta_h [Q](x) = Q(x + h) - Q(x) = [a(x + h) + b] - [ax + b] = ah = ah^11!</math>

This proves it for the base case.

====Inductive step====
Let {{math|''R''(''x'')}} be a polynomial of degree {{math|''m''&nbsp;−&nbsp;1}} where {{math|''m'' &ge; 2}} and the coefficient of the highest-order term be {{math|''a'' &ne; 0}}. Assuming the following holds true for all polynomials of degree {{math|''m''&nbsp;−&nbsp;1}}:
<math display="block">\Delta_h^{m-1} [R](x) = ah^{m-1}(m-1)!</math>

Let {{math|''S''(''x'')}} be a polynomial of degree {{math|''m''}}. With one pairwise difference:
<math display=block>\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)</math>

As {{math|''ahm'' &ne; 0}}, this results in a polynomial {{math|''T''(''x'')}} of degree {{math|''m'' − 1}}, with {{math|''ahm''}} as the coefficient of the highest-order term. Given the assumption above and {{math|''m'' − 1}} pairwise differences (resulting in a total of {{math|''m''}} pairwise differences for {{math|''S''(''x'')}}), it can be found that:
<math display="block">\Delta_h^{m-1} [T](x) = ahm \cdot h^{m-1}(m-1)! = a h^m m!</math>

This completes the proof.

===Application===
This identity can be used to find the lowest-degree polynomial that intercepts a number of points {{math|(''x'', ''y'')}} where the difference on the ''x''-axis from one point to the next is a constant {{math|''h'' &ne; 0}}. For example, given the following points:

{| class="wikitable"
|-
! ''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 {{math|''y''}}, the following relation to the cells in the column immediately to the left exists for a cell {{math|(''a'' + 1, ''b'' + 1)}}, with the top-leftmost cell being at coordinate {{math|(0, 0)}}:
<math display="block">(a+1, b+1) = (a, b+1) - (a, b)</math>

To find the first term, the following table can be used:

{| class="wikitable"
|-
! {{math|''x''}} !! {{math|''y''}} !! {{math|&Delta;''y''}} !! {{math|&Delta;<sup>2</sup>''y''}} !! {{math|&Delta;<sup>3</sup>''y''}}
|-
! 1
| 4
|-
! 4
| 109|| 105
|-
! 7
| 772|| 663|| 558
|-
! 10
| 2641|| 1869|| 1206|| 648
|-
! 13
| 6364|| 3723|| 1854|| 648
|}

This arrives at a constant {{math|648}}. The arithmetic difference is {{math|1=''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 {{math|3}}. Thus, using the identity above:
<math display="block">648 = a \cdot 3^3 \cdot 3! = a \cdot 27 \cdot 6 = a \cdot 162</math>

Solving for {{math|''a''}}, it can be found to have the value {{math|4}}. Thus, the first term of the polynomial is {{math|4''x''<sup>3</sup>}}.

Then, subtracting out the first term, which lowers the polynomial's degree, and finding the finite difference again:

{| class="wikitable"
|-
! {{mvar|x}} !! {{mvar|y}} !! {{math|&Delta;''y''}} !! {{math|&Delta;<sup>2</sup>''y''}}
|-
! 1
| {{math|4 − 4(1)<sup>3</sup> {{=}} 4 − 4 {{=}} 0}}
|-
! 4
| {{math|109 − 4(4)<sup>3</sup> {{=}} 109 − 256 {{=}} −147}}|| −147
|-
! 7
| {{math|772 − 4(7)<sup>3</sup> {{=}} 772 − 1372 {{=}} −600}}|| −453|| −306
|-
! 10
| {{math|2641 − 4(10)<sup>3</sup> {{=}} 2641 − 4000 {{=}} −1359}}|| −759|| −306
|-
! 13
| {{math|6364 − 4(13)<sup>3</sup> {{=}} 6364 − 8788 {{=}} −2424}}|| −1065|| −306
|}

Here, the constant is achieved after only two pairwise differences, thus the following result:
<math display="block">-306 = a \cdot 3^2 \cdot 2! = a \cdot 18</math>

Solving for {{math|''a''}}, which is {{math|−17}}, the polynomial's second term is {{math|−17''x''<sup>2</sup>}}.

Moving on to the next term, by subtracting out the second term:

{| class="wikitable"
|-
! {{math|''x''}} !! {{math|''y''}} !! {{math|&Delta;''y''}}
|-
! 1
| {{math|0 − (−17(1)<sup>2</sup>) {{=}} 0 + 17 {{=}} 17}}
|-
! 4
| {{math|−147 − (−17(4)<sup>2</sup>) {{=}} −147 + 272 {{=}} 125}}|| 108
|-
! 7
| {{math|−600 − (−17(7)<sup>2</sup>) {{=}} −600 + 833 {{=}} 233 }}|| 108
|-
! 10
| {{math|−1359 − (−17(10)<sup>2</sup>) {{=}} −1359 + 1700 {{=}} 341 }}|| 108
|-
! 13
| {{math|−2424 − (−17(13)<sup>2</sup>) {{=}} −2424 + 2873 {{=}} 449 }}|| 108
|}

Thus the constant is achieved after only one pairwise difference:
<math display="block">108 = a \cdot 3^1 \cdot 1! = a \cdot 3</math>

It can be found that {{math|1=''a'' = 36}} and thus the third term of the polynomial is {{math|'''36''x'''''}}. Subtracting out the third term:

{| class="wikitable"
|-
! {{math|''x''}} !! {{math|''y''}}
|-
! 1
| {{math|17 − 36(1) {{=}} 17 − 36 {{=}} −19}}
|-
! 4
| {{math|125 − 36(4) {{=}} 125 − 144 {{=}} −19}}
|-
! 7
| {{math|233 − 36(7) {{=}} 233 − 252 {{=}} −19}} 
|-
! 10
| {{math|341 − 36(10) {{=}} 341 − 360 {{=}} −19}}
|-
! 13
| {{math|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 {{math|−19}}. Thus, the lowest-degree polynomial intercepting all the points in the first table is found:
<math display="block">4x^3 - 17x^2 + 36x - 19</math>

==Arbitrarily sized kernels==
{{main|Finite difference coefficient}}
{{further|Five-point stencil}}

Using [[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]] 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.<ref>{{cite journal|last1=Fraser|first1=Duncan C.|title=On the Graphic Delineation of Interpolation Formulæ| journal=Journal of the Institute of Actuaries|date=1 January 1909|volume=43|issue=2|pages=235–241|doi=10.1017/S002026810002494X| url=https://archive.org/stream/journal43instuoft#page/236/mode/2up|access-date=17 April 2017}}</ref>
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.<ref>[http://commons.wikimedia.org/wiki/File:FDnotes.djvu notes]</ref>
Finite difference approximations for non-standard (and even non-integer) stencils given an arbitrary stencil and a desired derivative order may be constructed.<ref>[http://web.media.mit.edu/~crtaylor/calculator.html Finite Difference Coefficients Calculator]</ref>

===Properties===
* For all positive {{mvar|k}} and {{mvar|n}} <math display="block">\Delta^n_{kh} (f, x) = \sum\limits_{i_1=0}^{k-1} \sum\limits_{i_2=0}^{k-1} \cdots \sum\limits_{i_n=0}^{k-1} \Delta^n_h \left(f, x+i_1h+i_2h+\cdots+i_nh\right).</math>
* [[Leibniz rule (generalized product rule)|Leibniz rule]]: <math display="block">\Delta^n_h (fg, x) = \sum\limits_{k=0}^n \binom{n}{k} \Delta^k_h (f, x) \Delta^{n-k}_h(g, x+kh).</math>

==In differential equations==
{{main article|Finite difference method}}
An important application of finite differences is in [[numerical analysis]], especially in [[numerical partial differential equations|numerical differential equations]], which aim at the numerical solution of [[ordinary differential equation|ordinary]] and [[partial differential equation]]s. 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 method]]s.

Common applications of the finite difference method are in computational science and engineering disciplines, such as [[thermal engineering]], [[fluid mechanics]], etc.

==Newton's series==
The '''[[Newton polynomial|Newton series]]''' consists of the terms of the '''Newton forward difference equation''', named after [[Isaac Newton]];  in essence, it is  the '''Gregory–Newton interpolation formula'''<ref>[[Burkard Polster]]/Mathologer (2021). [https://www.youtube.com/watch?v=4AuV93LOPcE&t=964s " Why don't they teach Newton's calculus of 'What comes next?' " on YouTube]</ref> (named after [[Isaac Newton]] and [[James Gregory (mathematician)|James Gregory]]), first published in his ''[[Philosophiæ Naturalis Principia Mathematica|Principia Mathematica]]'' in 1687,<ref>Newton, Isaac, (1687). [https://archive.org/details/bub_gb_KaAIAAAAIAAJ/page/n459 <!-- pg=466 quote=sir isaac newton principia mathematica. --> ''Principia'', Book III, Lemma V, Case 1]</ref><ref>{{cite journal|url=http://math.colgate.edu/~integers/sjs3/sjs3.pdf|title=Three notes on Ser's and Hasse's representations for the zeta-functions|author=Iaroslav V. Blagouchine|journal=Integers (Electronic Journal of Combinatorial Number Theory)|volume=18A|pages=1–45|date=2018|doi=10.5281/zenodo.10581385 |arxiv=1606.02044}}</ref> namely the discrete analog of the continuous Taylor expansion,

{{Equation box 1
|indent =:
|equation = <math>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)  ,
</math> 
|cellpadding= 6
|border
|border colour = #0073CF
|background colour=#F9FFF7}}
which holds for any [[polynomial]] function {{mvar|f}} and for many (but not all)  [[analytic function]]s. (It does not hold when {{mvar|f}} is [[exponential type]] <math>\pi</math>. This is easily seen, as the sine function vanishes at integer multiples of <math>\pi</math>; 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
<math display="block">\binom{x}{k} = \frac{(x)_k}{k!}</math>
is the [[binomial coefficient]], and
<math display="block">(x)_k=x(x-1)(x-2)\cdots(x-k+1)</math>
is the "[[falling factorial]]" or "lower factorial", while  the [[empty product]] {{math|(''x'')<sub>0</sub>}} is defined to be&nbsp;1.  In this particular case, there is an assumption of unit steps for the changes in the values of {{math|''x'', ''h'' {{=}} 1}} of the generalization below.

Note the formal correspondence of this result to [[Taylor's theorem]].  Historically, this, as well as the [[Chu–Vandermonde identity]],  
<math display="block">(x+y)_n=\sum_{k=0}^n \binom{n}{k} (x)_{n-k} \,(y)_k ,</math>
(following from it, and corresponding to the [[binomial theorem]]),  are included in the observations that matured to the system of [[umbral calculus]].

Newton series expansions can be superior to Taylor series expansions when applied to discrete quantities like quantum spins (see [[Holstein–Primakoff transformation]]), [[Normal_order#Bosonic_operator_functions|bosonic operator functions]] or discrete counting statistics.<ref name="Hucht">{{cite journal| doi=10.21468/SciPostPhys.10.1.007| title=Newton series expansion of bosonic operator functions| year=2021| last1=König| first1=Jürgen| last2=Hucht| first2=Fred| journal = SciPost Physics| volume=10| issue=1| page=007| arxiv=2008.11139| bibcode=2021ScPP...10....7K| s2cid=221293056| doi-access=free }}</ref>

To illustrate how one may use Newton's formula in actual practice, consider the first few terms of doubling the [[Fibonacci sequence]] {{math|''f'' {{=}} 2, 2, 4, ...}} One can find a [[polynomial]] that reproduces these values, by first computing a difference table, and then substituting the differences that correspond to {{math|''x''<sub>0</sub>}} (underlined) into the formula as follows,
<math display=block>
\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{align}
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{align}
\end{matrix}
</math>

For the case of nonuniform steps in the values of {{mvar|x}}, Newton computes the [[divided differences]],
<math display=block>\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\le \max \left( j \right)-k \right\},\qquad \Delta 0_k = \Delta _{0,k}</math>
the series of products,
<math display="block">{P_0}=1,\quad \quad P_{k+1}=P_k\cdot \left( \xi -x_k \right) ,</math>
and the resulting polynomial is the [[scalar product]],<ref>[[Robert D. Richtmyer|Richtmeyer, D.]] and  Morton, K.W., (1967). ''Difference Methods for Initial Value Problems'', 2nd ed., Wiley, New York.</ref>
<math display="block">f(\xi ) = \Delta 0 \cdot P\left( \xi  \right).</math>

In analysis with [[p-adic number|{{mvar|p}}-adic numbers]], [[Mahler's theorem]] states that the assumption that {{mvar|f}} is a polynomial function can be weakened all the way to the assumption that {{mvar|f}} is merely continuous.

[[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]] and the [[Selberg class|Selberg series]], is a special case of the general [[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
<math display="block">f(x) = \sum_{k=0}\binom{\frac{x-a}h}{k} \sum_{j=0}^k (-1)^{k-j}\binom{k}{j}f(a+j h).</math>

==Calculus of finite differences==

The forward difference can be considered as an [[Operator (mathematics)|operator]], called the [[difference operator]], which maps the function {{mvar|f}} to {{math|Δ<sub>''h''</sub>[''f'']}}.<ref>{{cite book|author-link=George Boole|last=Boole|first=George|year=1872|title=A Treatise on the Calculus of Finite Differences|edition=2nd|publisher=Macmillan and Company|url=https://archive.org/details/cu31924031240934|via=[[Internet Archive]] }} Also, a Dover reprint edition, 1960.</ref><ref>{{cite book|last=Jordan|first=Charles|orig-year=1939|year=1965|title=Calculus of Finite Differences|publisher=Chelsea Publishing|isbn=978-0-8284-0033-6|url=https://books.google.com/books?id=3RfZOsDAyQsC&pg=PA1|via=Google books }}</ref> This operator amounts to <math display="block">\Delta_h = \operatorname{T}_h - \operatorname I\ ,</math> where {{math|T<sub>''h''</sub>}} is the [[shift operator]] with step {{mvar|h}}, defined by {{nobr|{{math|T<sub>''h''</sub>[''f''](''x'') {{=}} ''f''(''x'' + ''h'')}},}}  and {{math|I}} is the [[identity operator]].

The finite difference of higher orders can be defined in recursive manner as {{nobr|{{math|Δ{{su|b=''h''|p=''n''}} ≡ Δ<sub>''h''</sub>(Δ{{su|b=''h''|p=''n'' − 1}})}}.}} Another equivalent definition is {{nobr|{{math|Δ{{su|b=''h''|p=''n''}} ≡ [T<sub>''h''</sub> − I]<sup>''n''</sup>}}.}}

The difference operator {{math|Δ<sub>''h''</sub>}} is a [[linear operator]], as such it satisfies {{nobr|{{math|Δ<sub>''h''</sub>[''α f'' + ''β g''](''x'') {{=}} ''α'' Δ<sub>''h''</sub>[''f''](''x'') + ''β'' Δ<sub>''h''</sub>[''g''](''x'')}}.}}

It also satisfies a special [[Leibniz rule (generalized product rule)|Leibniz rule]]:
:<math>\ \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) ~.</math>
Similar Leibniz rules hold for the backward and central differences.

Formally applying the [[Taylor series]] with respect to {{mvar|h}}, yields the operator equation
<math display="block"> \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\ ,</math>
where {{math|D}} denotes the conventional, continuous derivative operator, mapping {{mvar|f}} to its derivative {{nobr|{{math|''f''′}}.}} The expansion is valid when both sides act on [[analytic function]]s, for sufficiently small {{mvar|h}}; in the special case that the series of derivatives terminates (when the function operated on is a finite [[polynomial]]) the expression is exact, for ''all'' finite stepsizes, {{nobr| {{mvar|h}} .}} Thus {{nobr|{{math| T<sub>''h''</sub> {{=}} ''e''<sup>''h'' D</sup>}},}} and formally inverting the exponential yields 
<math display="block"> h\operatorname D = \ln(1+\Delta_h) = \Delta_h - \tfrac{1}{2} \, \Delta_h^2 + \tfrac{1}{3} \, \Delta_h^3 - \cdots ~.</math>
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]]. 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 {{math|''f''&nbsp;′(''x'')}} mentioned at the end of the section ''{{slink||Higher-order differences}}''.

The analogous formulas for the backward and central difference operators are
<math display="block"> h\operatorname D = -\ln(1-\nabla_h) \quad \text{ and } \quad h\operatorname D = 2 \operatorname{arsinh}\left(\tfrac12 \, \delta_h\right) ~.</math>

The calculus of finite differences is related to the [[umbral calculus]] of combinatorics. This remarkably systematic correspondence is due to the identity of the [[commutators]] of the umbral quantities to their continuum analogs ({{math|''h'' → 0}} limits),

{{Equation box 1
|indent =:
|equation = 
<math>  \left[ \frac{\Delta_h}{h} , x\, \operatorname T^{-1}_h \right] = [ \operatorname D , x ] = I .</math>
|cellpadding= 6
|border
|border colour = #0073CF
|background colour=#F9FFF7}}

A large number of formal differential relations of standard calculus involving 
functions {{math|''f''(''x'')}} thus ''systematically map to umbral finite-difference analogs'' involving {{nobr|{{math|''f''( ''x'' T{{su|b=''h''|p=−1}} )}}.}}

For instance, the umbral analog of a monomial {{mvar|x<sup>n</sup>}} is a generalization of the above falling factorial ([[Pochhammer k-symbol]]),  
<math display="block">\ (x)_n\equiv  \left(\ x\ \operatorname T_h^{-1}\right)^n = x \left( x - h \right)\left( x - 2 h \right) \cdots \bigl( x - \left( n - 1 \right)\ h \bigr)\ ,</math> 
so that 
<math display="block">\ \frac{\Delta_h}{h} (x)_n = n\ (x)_{n-1}\ ,</math>
hence the above Newton interpolation formula (by matching coefficients in the expansion of an arbitrary function {{math|''f''(''x'')}} in such symbols), and so on.

For example, the umbral sine is
<math display="block">\ \sin \left(x\ \operatorname T_h^{-1}\right) = x -\frac{(x)_3}{3!} +  \frac{(x)_5}{5!} - \frac{(x)_7}{7!} + \cdots\ </math>

As in the [[continuum limit]], the [[eigenfunction]] of {{math|{{sfrac|Δ<sub>''h''</sub>|''h''}}}} also happens to be an exponential,

:<math>\ \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}}\ ,</math>

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.<ref>{{cite journal| last =Zachos| first =C.| author-link = Cosmas Zachos| year =2008| title = Umbral deformations on discrete space-time| journal = International Journal of Modern Physics A| volume =23| issue=13| pages =200–214| doi = 10.1142/S0217751X08040548| arxiv =0710.2306| bibcode = 2008IJMPA..23.2005Z| s2cid = 16797959 }}</ref> This umbral exponential thus amounts to the exponential [[generating function]] of the [[Pochhammer symbol]]s.

Thus, for instance,  the [[Dirac delta function]] maps to its umbral correspondent, the [[Sinc function|cardinal sine function]] 
<math display="block">\ \delta (x) \mapsto \frac{\sin \left[ \frac{\pi}{2}\left(1+\frac{x}{h}\right) \right]}{ \pi (x+h) }\ ,</math>
and so forth.<ref>{{cite journal| last1 = Curtright| first1 = T. L.| last2 = Zachos| first2 = C. K.| doi = 10.3389/fphy.2013.00015| title = Umbral Vade Mecum| journal = Frontiers in Physics| volume = 1| year = 2013| pages = 15| arxiv = 1304.0429| bibcode = 2013FrP.....1...15C| s2cid = 14106142| doi-access = free }}</ref> [[Difference equation]]s can often be solved with techniques very similar to those for solving [[differential equation]]s.

The inverse operator of the forward difference operator, so then the umbral integral, is the [[indefinite sum]] or antidifference operator.

===Rules for calculus of finite difference operators===
Analogous to [[Differentiation rules|rules for finding the derivative]], we have:
* '''Constant rule''': If {{mvar|c}} is a [[Constant (mathematics)|constant]], then <math display="block">\ \Delta c = 0\ </math>
* '''[[Linearity of differentiation|Linearity]]''': If {{mvar|a}} and {{mvar|b}} are [[Constant (mathematics)|constants]], <math display="block">\ \Delta (a\ f + b\ g) = a \ \Delta f + b \ \Delta g\ </math>

All of the above rules apply equally well to any difference operator as to {{math|Δ}}, including {{math|δ}} and {{nobr|{{math|∇}}.}}

* '''[[Product rule]]''': <math display="block">\begin{align}
\ \Delta (f g) &= f \,\Delta g + g \,\Delta f + \Delta f \,\Delta g \\[4pt]
\nabla (f g) &= f \,\nabla g + g \,\nabla f - \nabla f \,\nabla g
\ \end{align}</math>
* '''[[Quotient rule]]''': <math display="block">\ \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) </math> or <math display="block"> \nabla\left( \frac{f}{g} \right)= \frac {g \,\nabla f - f \,\nabla g}{g \cdot (g - \nabla g)}\ </math>
* '''[[Fundamental theorem of calculus|Summation rules]]''': <math display="block">\begin{align}
\ \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{align}</math>

See references.<ref>
{{cite book
|last1=Levy|first1=H.
|last2=Lessman|first2=F.
|year=1992
|title=Finite Difference Equations
|publisher=Dover
|isbn=0-486-67260-3
}}
</ref><ref>
{{cite book
|last=Ames|first=W.F.
|year=1977
|title=Numerical Methods for Partial Differential Equations
|at=Section&nbsp;1.6
|publisher=Academic Press
|place=New York, NY
|isbn=0-12-056760-1
}}
</ref><ref>
{{cite book
|last=Hildebrand|first=F.B.|author-link=Francis B. Hildebrand
|year=1968
|title=Finite-Difference Equations and Simulations
|at=Section&nbsp;2.2
|publisher=Prentice-Hall
|place=Englewood Cliffs, NJ
}}
</ref><ref>
{{cite journal
| first1 = Philippe| last1 = Flajolet
| first2 = Robert| last2 = Sedgewick| author-link2 = Robert Sedgewick (computer scientist)
| year = 1995
| title = Mellin transforms and asymptotics: Finite differences and Rice's integrals
| journal = Theoretical Computer Science
| volume = 144| issue = 1–2| pages = 101–124
| doi = 10.1016/0304-3975(94)00281-M
| url = http://algo.inria.fr/flajolet/Publications/FlSe95.pdf
}}
</ref>

==Generalizations==

*A '''generalized finite difference''' is usually defined as <math display="block">\Delta_h^\mu[f](x) = \sum_{k=0}^N \mu_k f(x+kh),</math> where {{math|1=''μ'' = (''μ''<sub>0</sub>, …, ''μ<sub>N</sub>'')}} is its coefficient vector. An '''infinite difference''' is a further generalization, where the finite sum above is replaced by an [[Series (mathematics)|infinite series]]. Another way of generalization is making coefficients {{math|''μ<sub>k</sub>''}} depend on point {{mvar|x}}: {{math|1=''μ<sub>k</sub>'' = ''μ<sub>k</sub>''(''x'')}}, thus considering '''weighted finite difference'''. Also one may make the step {{mvar|h}} depend on point {{mvar|x}}: {{math|1=''h'' = ''h''(''x'')}}. Such generalizations are useful for constructing different [[modulus of continuity]].
*The generalized difference can be seen as the polynomial rings {{math|''R''[''T<sub>h</sub>'']}}. It leads to difference algebras.
*Difference operator generalizes to [[Möbius inversion]] over a [[partially ordered set]].
*As a convolution operator: Via the formalism of [[incidence algebra]]s, difference operators and other Möbius inversion can be represented by [[convolution]] with a function on the poset, called the [[Möbius function (combinatorics)|Möbius function]] {{mvar|μ}}; for the difference operator, {{mvar|μ}} is the sequence {{nowrap|(1, −1, 0, 0, 0, …)}}.

==Multivariate finite differences==

Finite differences can be considered in more than one variable. They are analogous to [[partial derivative]]s in several variables.

Some partial derivative approximations are:
<math display=block>\begin{align}
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) - 2 f(x,y) + f(x-h,y)}{h^2} \\
f_{yy}(x,y) &\approx  \frac{f(x,y+k) - 2 f(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{align}</math>

Alternatively, for applications in which the computation of {{mvar|f}}  is the most costly step, and both first and second derivatives must be computed, a more efficient formula for the last case is
<math display=block> f_{xy}(x,y) \approx \frac{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)}{2hk},</math>
since the only values to compute that are not already needed for the previous four equations are {{math|''f''(''x'' + ''h'', ''y'' + ''k'')}}   and {{math|''f''(''x'' − ''h'', ''y'' − ''k'')}}.

==See also==
{{columns-list|colwidth=20em|
* [[Discrete calculus]]
* [[Divided differences]]
* [[Finite-difference time-domain method]] (FDTD)
* [[Finite volume method]]
* [[FTCS scheme]]
* [[Gilbreath's conjecture]]
* [[Sheffer sequence]]
* [[Summation by parts]]
* [[Time scale calculus]]
* [[Upwind differencing scheme for convection]]
}}

== References ==
<references/>
{{refbegin}}
* Richardson, C. H. (1954): ''An Introduction to the Calculus of Finite Differences'' (Van Nostrand (1954) [http://babel.hathitrust.org/cgi/pt?id=mdp.39015000982945;view=1up;seq=5 online copy]
* Mickens, R. E. (1991): ''Difference Equations: Theory and Applications'' (Chapman and Hall/CRC) {{ISBN|978-0442001360}}

{{refend}}
== External links ==
* {{springer|title=Finite-difference calculus|id=p/f040230}}
* [http://reference.wolfram.com/mathematica/tutorial/NDSolvePDE.html#c:4 Table of useful finite difference formula generated using Mathematica]
* D. Gleich (2005),  [https://web.archive.org/web/20090419132601/http://www.stanford.edu/~dgleich/publications/finite-calculus.pdf ''Finite Calculus: A Tutorial for Solving Nasty Sums'']
* [http://mathformeremortals.wordpress.com/2013/01/12/a-numerical-second-derivative-from-three-points/ Discrete Second Derivative from Unevenly Spaced Points]

{{Calculus topics}}

[[Category:Finite differences| ]]
[[Category:Numerical differential equations]]
[[Category:Mathematical analysis]]
[[Category:Factorial and binomial topics]]
[[Category:Linear operators in calculus]]
[[Category:Numerical analysis]]
[[Category:Non-Newtonian calculus]]