Discrete calculus or the calculus of discrete functions, is the mathematical study of incremental change, in the same way that geometry is the study of shape and algebra is the study of generalizations of arithmetic operations. The word calculus is a Latin word, meaning originally "small pebble"; as such pebbles were used for calculation, the meaning of the word has evolved and today usually means a method of computation. Meanwhile, calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the study of continuous change.
Discrete calculus has two entry points, differential calculus and integral calculus. Differential calculus concerns incremental rates of change and the slopes of piece-wise linear curves. Integral calculus concerns accumulation of quantities and the areas under piece-wise constant curves. These two points of view are related to each other by the fundamental theorem of discrete calculus.
The study of the concepts of change starts with their discrete form. The development is dependent on a parameter, the increment
\Deltax
\Deltax\to0
Discrete differential calculus is the study of the definition, properties, and applications of the difference quotient of a function. The process of finding the difference quotient is called differentiation. Given a function defined at several points of the real line, the difference quotient at that point is a way of encoding the small-scale (i.e., from the point to the next) behavior of the function. By finding the difference quotient of a function at every pair of consecutive points in its domain, it is possible to produce a new function, called the difference quotient function or just the difference quotient of the original function. In formal terms, the difference quotient is a linear operator which takes a function as its input and produces a second function as its output. This is more abstract than many of the processes studied in elementary algebra, where functions usually input a number and output another number. For example, if the doubling function is given the input three, then it outputs six, and if the squaring function is given the input three, then it outputs nine. The derivative, however, can take the squaring function as an input. This means that the derivative takes all the information of the squaring function—such as that two is sent to four, three is sent to nine, four is sent to sixteen, and so on—and uses this information to produce another function. The function produced by differentiating the squaring function turns out to be something close to the doubling function.
Suppose the functions are defined at points separated by an increment
\Deltax=h>0
a,a+h,a+2h,\ldots,a+nh,\ldots
The "doubling function" may be denoted by
g(x)=2x
f(x)=x2
[x,x+h]
f(x+h)-f(x) | |
h |
.
f
g(x)=2x+h
a+h/2,a+h+h/2,a+2h+h/2,...,a+nh+h/2,...
[x,x+h]
1
The most common notation for the difference quotient is:
\Deltaf | (x+h/2)= | |
\Deltax |
f(x+h)-f(x) | |
h |
.
If the input of the function represents time, then the difference quotient represents change with respect to time. For example, if
f
f
If a function is linear (that is, if the points of the graph of the function lie on a straight line), then the function can be written as
y=mx+b
x
y
b
y
m=
rise | |
run |
=
changeiny | |
changeinx |
=
\Deltay | |
\Deltax |
.
This gives an exact value for the slope of a straight line.
If the function is not linear, however, then the change in
y
x
f
x
f
(x,f(x))
h
x
x+h
x
(x+h,f(x+h))
(x,f(x))
m=
f(x+h)-f(x) | |
(x+h)-x |
=
f(x+h)-f(x) | |
h |
.
m
(x,f(x))
(x+h,f(x+h))
Here is a particular example, the difference quotient of the squaring function. Let
f(x)=x2
\begin{align} | \Deltaf |
\Deltax |
(x)&={(x+h)2-x2\over{h}}\\ &={x2+2hx+h2-x2\over{h}}\\ &={2hx+h2\over{h}}\\ &=2x+h. \end{align}
The difference quotient of the difference quotient is called the second difference quotient and it is defined at
a+h,a+2h,a+3h,\ldots,a+nh,\ldots
Discrete integral calculus is the study of the definitions, properties, and applications of the Riemann sums. The process of finding the value of a sum is called integration. In technical language, integral calculus studies a certain linear operator.
The Riemann sum inputs a function and outputs a function, which gives the algebraic sum of areas between the part of the graph of the input and the x-axis.
A motivating example is the distances traveled in a given time.
distance=speed ⋅ time
If the speed is constant, only multiplication is needed, but if the speed changes, we evaluate the distance traveled by breaking up the time into many short intervals of time, then multiplying the time elapsed in each interval by one of the speeds in that interval, and then taking the sum (a Riemann sum) of the distance traveled in each interval.
When velocity is constant, the total distance traveled over the given time interval can be computed by multiplying velocity and time. For example, travelling a steady 50 mph for 3 hours results in a total distance of 150 miles. In the diagram on the left, when constant velocity and time are graphed, these two values form a rectangle with height equal to the velocity and width equal to the time elapsed. Therefore, the product of velocity and time also calculates the rectangular area under the (constant) velocity curve. This connection between the area under a curve and distance traveled can be extended to any irregularly shaped region exhibiting an incrementally varying velocity over a given time period. If the bars in the diagram on the right represents speed as it varies from an interval to the next, the distance traveled (between the times represented by
a
b
s
So, the interval between
a
b
\Deltax
f(x)
v
\Deltax
v
\Deltax
v
f(x)=v
Suppose a function is defined at the mid-points of the intervals of equal length
\Deltax=h>0
a+h/2,a+h+h/2,a+2h+h/2,\ldots,a+nh-h/2,\ldots
a
b=a+nh
n | |
\sum | |
i=1 |
f(a+ih)\Deltax.
n
a,a+h,a+2h,\ldots,a+nh,\ldots
The fundamental theorem of calculus states that differentiation and integration are inverse operations. More precisely, it relates the difference quotients to the Riemann sums. It can also be interpreted as a precise statement of the fact that differentiation is the inverse of integration.
The fundamental theorem of calculus: If a function
f
[a,b]
b=a+nh
F
f
n-1 | |
\sum | |
i=0 |
f(a+ih+h/2)\Deltax=F(b)-F(a).
\Delta | |
\Deltax |
m | |
\sum | |
i=0 |
f(a+ih+h/2)\Deltax=f(a+mh+h/2).
This is also a prototype solution of a difference equation. Difference equations relate an unknown function to its difference or difference quotient, and are ubiquitous in the sciences.
The early history of discrete calculus is the history of calculus. Such basic ideas as the difference quotients and the Riemann sums appear implicitly or explicitly in definitions and proofs. After the limit is taken, however, they are never to be seen again. However, the Kirchhoff's voltage law (1847) can be expressed in terms of the one-dimensional discrete exterior derivative.
During the 20th century discrete calculus remains interlinked with infinitesimal calculus especially differential forms but also starts to draw from algebraic topology as both develop. The main contributions come from the following individuals:[1]
triangulations (barycentric subdivision, dual triangulation), Poincaré lemma, the first proof of the general Stokes Theorem, and a lot more
simplicial approximation theorem
the Kirchhoff laws stated in terms of the boundary and the coboundary operators
the Hodge star operator, the Hodge decomposition
cochains as integrands
The recent development of discrete calculus, starting with Whitney, has been driven by the needs of applied modeling.[2] [3] [4]
Discrete calculus is used for modeling either directly or indirectly as a discretization of infinitesimal calculus in every branch of the physical sciences, actuarial science, computer science, statistics, engineering, economics, business, medicine, demography, and in other fields wherever a problem can be mathematically modeled. It allows one to go from (non-constant) rates of change to the total change or vice versa, and many times in studying a problem we know one and are trying to find the other.
Physics makes particular use of calculus; all discrete concepts in classical mechanics and electromagnetism are related through discrete calculus. The mass of an object of known density that varies incrementally, the moment of inertia of such objects, as well as the total energy of an object within a discrete conservative field can be found by the use of discrete calculus. An example of the use of discrete calculus in mechanics is Newton's second law of motion: historically stated it expressly uses the term "change of motion" which implies the difference quotient saying The change of momentum of a body is equal to the resultant force acting on the body and is in the same direction. Commonly expressed today as Force = Mass × Acceleration, it invokes discrete calculus when the change is incremental because acceleration is the difference quotient of velocity with respect to time or second difference quotient of the spatial position. Starting from knowing how an object is accelerating, we use the Riemann sums to derive its path.
Maxwell's theory of electromagnetism and Einstein's theory of general relativity have been expressed in the language of discrete calculus.
Chemistry uses calculus in determining reaction rates and radioactive decay (exponential decay).
In biology, population dynamics starts with reproduction and death rates to model population changes (population modeling).
In engineering, difference equations are used to plot a course of a spacecraft within zero gravity environments, to model heat transfer, diffusion, and wave propagation.
The discrete analogue of Green's theorem is applied in an instrument known as a planimeter, which is used to calculate the area of a flat surface on a drawing. For example, it can be used to calculate the amount of area taken up by an irregularly shaped flower bed or swimming pool when designing the layout of a piece of property. It can be used to efficiently calculate sums of rectangular domains in images, to rapidly extract features and detect object; another algorithm that could be used is the summed area table.
In the realm of medicine, calculus can be used to find the optimal branching angle of a blood vessel so as to maximize flow. From the decay laws for a particular drug's elimination from the body, it is used to derive dosing laws. In nuclear medicine, it is used to build models of radiation transport in targeted tumor therapies.
In economics, calculus allows for the determination of maximal profit by calculating both marginal cost and marginal revenue, as well as modeling of markets.[5]
In signal processing and machine learning, discrete calculus allows for appropriate definitions of operators (e.g., convolution), level set optimization and other key functions for neural network analysis on graph structures.[6]
Discrete calculus can be used in conjunction with other mathematical disciplines. For example, it can be used in probability theory to determine the probability of a discrete random variable from an assumed density function.
Suppose a function (a
0
f
\Deltax=h>0
a,a+h,a+2h,\ldots,a+nh,\ldots
(\Deltaf)([x,x+h])=f(x+h)-f(x).
1
Suppose a
1
g
0
\left(\sumg\right)(a+nh)=
n | |
\sum | |
i=1 |
g([a+(i-1)h,a+ih]).
These are their properties:
c
\Deltac=0
a
b
\Delta(af+bg)=a\Deltaf+b\Deltag, \sum(af+bg)=a\sumf+b\sumg
\Delta(fg)=f\Deltag+g\Deltaf+\Deltaf\Deltag
\left(\sum\Deltaf\right)(a+nh)=f(a+nh)-f(a)
\Delta\left(\sumg\right)=g
The definitions are applied to graphs as follows. If a function (a
0
f
a,b,c,\ldots
1
\left(df\right)([a,b])=f(b)-f(a).
g
1
\sigma
\sigma
\int\sigmag=\sum\sigmag([a,b]).
These are the properties:
c
dc=0
a
b
d(af+bg)=adf+bdg, \int\sigma(af+bg)=a\int\sigmaf+b\int\sigmag
d(fg)=fdg+gdf+dfdg
1
\sigma
[a0,a1],[a1,a2],...,[an-1,an]
0
f
\int\sigmadf=f(an)-f(a0)
g
1
0
f(x)=\int\sigmag
where a
1
\sigma
[a0,a1],[a1,a2],...,[an-1,x]
a0
df=g
See references.[7] [8] [9] [10] [3] [11]
S
1. Every face of a simplex from
S
S
2. The non-empty intersection of any two simplices
\sigma1,\sigma2\inS
\sigma1
\sigma2
By definition, an orientation of a k-simplex is given by an ordering of the vertices, written as
(v0,...,vk)
Let
S
N | |
\sum | |
i=1 |
ci\sigmai,
(v0,v1)=-(v1,v0).
The vector space of k-chains on
S
Ck
S
Let
\sigma=(v0,...,vk)
Ck
\partialk:Ck → Ck-1
\partialk(\sigma)=\sum
k | |
i=0 |
(-1)i(v0,...,\widehat{vi},...,vk),
(v0,...,\widehat{vi},...,vk)
i
\sigma
i
In
Ck
Zk=\ker\partialk
Bk=\operatorname{im}\partialk+1
A direct computation shows that
\partial2=0
(Ck,\partialk)
Bk
Zk
A cubical complex is a set composed of points, line segments, squares, cubes, and their n-dimensional counterparts. They are used analogously to simplices to form complexes. An elementary interval is a subset
I\subsetR
I=[\ell,\ell+1] or I=[\ell,\ell]
\ell\inZ
Q
Q=I1 x I2 x … x Id\subsetRd
I1,I2,\ldots,Id
[0,1]n
Rd
n,d\inN\cup\{0\}
n\leqd
X\subseteqRd
More general are cell complexes.
(C*,\partial*)
\ldots,C0,C1,C2,C3,C4,\ldots
\partialn:Cn\toCn-1
\partialn\circ\partialn+1=0
\partial2=0
… \xleftarrow{\partial0}C0 \xleftarrow{\partial1}C1 \xleftarrow{\partial2}C2 \xleftarrow{\partial3}C3 \xleftarrow{\partial4}C4 \xleftarrow{\partial5} …
A simplicial map is a map between simplicial complexes with the property that the images of the vertices of a simplex always span a simplex (therefore, vertices have vertices for images). A simplicial map
f
S
T
S
T
S
T
S
T
k
f((v0,\ldots,vk))=(f(v0),\ldots,f(vk))
f(v0),...,f(vk)
0
A chain map
f
(A*,dA,*)
(B*,dB,*)
f*
fn:An → Bn
n
dB,n\circfn=fn-1\circdA,n
A chain map sends cycles to cycles and boundaries to boundaries.
* | |
C | |
i |
:=Hom(Ci,{\bfR}),
di=\partial
* | |
i |
di-1:
* | |
C | |
i-1 |
\to
*. | |
C | |
i |
… \leftarrow
* | |
C | |
i+1 |
* | |
\stackrel{\partial | |
i}{\leftarrow} C |
* | |
i |
* | |
\stackrel{\partial | |
i-1 |
The cochain complex
(C*,d*)
...,C0,C1,C2,C3,C4,...
dn:Cn\toCn+1
dn+1\circdn=0
… \xrightarrow{d-1
The index
n
Cn
Cn
The elements of the individual vector spaces of a (co)chain complex are called cochains. The elements in the kernel of
d
d
The Poincaré lemma states that if
B
{\bfR}n
p
\omega
B
p
1\lep\len
When we refer to cochains as discrete (differential) forms, we refer to
d
\omega(s)=\ints\omega.
Stokes' theorem is a statement about the discrete differential forms on manifolds, which generalizes the fundamental theorem of discrete calculus for a partition of an interval:
n-1 | |
\sum | |
i=0 |
\DeltaF | |
\Deltax |
(a+ih+h/2)\Deltax=F(b)-F(a).
Stokes' theorem says that the sum of a form
\omega
\Omega
d\omega
\Omega
\int\Omegad\omega=\int\partial\omega.
It is worthwhile to examine the underlying principle by considering an example for
d=2
In discrete calculus, this is a construction that creates from forms higher order forms: adjoining two cochains of degree
p
q
p+q
For cubical complexes, the wedge product is defined on every cube seen as a vector space of the same dimension.
For simplicial complexes, the wedge product is implemented as the cup product: if
fp
p
gq
q
(fp\smilegq)(\sigma)=
p(\sigma | |
f | |
0,1,...,p |
) ⋅
q(\sigma | |
g | |
p,p+1,...,p+q |
)
\sigma
(p+q)
\sigmaS, S\subset\{0,1,...,p+q\}
S
(p+q)
\{0,...,p+q\}
\sigma0,1,
p
\sigmap,
q
\sigma
The coboundary of the cup product of cochains
fp
gq
d(fp\smilegq)=d{fp}\smilegq+(-1)p(fp\smiled{gq}).
The cup product operation satisfies the identity
\alphap\smile\betaq=(-1)pq(\betaq\smile\alphap).
See references.[12]
The Laplace operator
\Deltaf
f
p
f
p
f(p)
The codifferential
\delta:Ck\toCk-1
k
\delta=(-1)n(k-1){\star}d{\star}=(-1)k{\star}-1d{\star},
d
\star
The codifferential is the adjoint of the exterior derivative according to Stokes' theorem:
(η,\delta\zeta)=(dη,\zeta).
d2=0
\delta2={\star}d{\star}{\star}d{\star}=(-1)k(n-k){\star}d2{\star}=0.
The Laplace operator is defined by:
\Delta=(\delta+d)2=\deltad+d\delta.
See references.[14]