Discrete calculus

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 formula_1 of the independent variable. If we so choose, we can make the increment smaller and smaller and find the continuous counterparts of these concepts as "limits". Informally, the limit of discrete calculus as formula_2 is infinitesimal calculus. Even though it serves as a discrete underpinning of calculus, the main value of discrete calculus is in applications.
Two initial constructions.
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 formula_3:
The "doubling function" may be denoted by formula_5 and the "squaring function" by formula_6. The "difference quotient" is the rate of change of the function over one of the intervals formula_7 defined by the formula:
It takes the function formula_9 as an input, that is all the information—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 output another function, the function formula_10, as will turn out. As a matter of convenience, the new function may defined at the middle points of the above intervals:
As the rate of change is that for the whole interval formula_7, any point within it can be used as such a reference or, even better, the whole interval which makes the difference quotient a formula_13-cochain.
The most common notation for the difference quotient is:
If the input of the function represents time, then the difference quotient represents change with respect to time. For example, if formula_9 is a function that takes a time as input and gives the position of a ball at that time as output, then the difference quotient of formula_9 is how the position is changing in time, that is, it is the velocity of the ball.
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 formula_17, where formula_18 is the independent variable, formula_19 is the dependent variable, formula_20 is the formula_19-intercept, and:
This gives an exact value for the slope of a straight line. 
If the function is not linear, however, then the change in formula_19 divided by the change in formula_18 varies. The difference quotient give an exact meaning to the notion of change in output with respect to change in input. To be concrete, let formula_9 be a function, and fix a point formula_18 in the domain of formula_9. formula_28 is a point on the graph of the function. If formula_29 is the increment of formula_18, then formula_31 is the next value of formula_18. Therefore, formula_33 is the increment of formula_28. The slope of the line between these two points is
So formula_36 is the slope of the line between formula_28 and formula_33. 
Here is a particular example, the difference quotient of the squaring function. Let formula_6 be the squaring function. Then:
The difference quotient of the difference quotient is called the "second difference quotient" and it is defined at 
And so on.
Discrete integral calculus is the study of the definitions, properties, and applications of the Riemann sums. The process of finding the value of an 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.
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 a 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 formula_43 and formula_20) is the area of the shaded region formula_45.
So, the interval between formula_43 and formula_20 is divided into a number of equal segments, the length of each segment represented by the symbol formula_1. For each small segment, we have one value of the function formula_49. Call that value formula_50. Then the area of the rectangle with base formula_1 and height formula_50 gives the distance (time formula_1 multiplied by speed formula_50) traveled in that segment. Associated with each segment is the value of the function above it, formula_55. The sum of all such rectangles gives the area between the axis and the piece-wise constant curve, which is the total distance traveled. 
Suppose a function is defined at the mid-points of the intervals of equal length formula_3:
Then the Riemann sum from formula_43 to formula_59 in sigma notation is:
As this computation is carried out for each formula_61, the new function is defined at the points:
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 formula_9 is defined on a partition of the interval formula_64, formula_59, and if formula_66 is a function whose difference quotient is formula_9, then we have:
Furthermore, for every formula_69, we have:
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.
History.
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:
The recent development of discrete calculus, starting with Whitney, has been driven by the needs of applied modeling. 
Applications.
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.
Discrete 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.
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. 
Calculus of differences and sums.
Suppose a function (a formula_71-cochain) formula_9 is defined at points separated by an increment formula_3:
The "difference" (or the exterior derivative, or the coboundary operator) of the function is given by:
It is defined at each of the above intervals; it is a formula_13-cochain.
Suppose a formula_13-cochain formula_78 is defined at each of the above intervals. Then its "sum" is a function (a formula_71-cochain) defined at each of the points by:
These are their properties:
The definitions are applied to graphs as follows. If a function (a formula_71-cochain) formula_9 is defined at the nodes of a graph:
then its "exterior derivative" (or the differential) is the difference, i.e., the following function defined on the edges of the graph (formula_13-cochain):
If formula_78 is a formula_13-cochain, then its "integral" over a sequence of edges formula_96 of the graph is the sum of its values over all edges of formula_96 ("path integral"):
These are the properties:
where a formula_13-chain formula_96 consists of formula_117 for some fixed formula_118, then
See references.
Chains of simplices and cubes.
A simplicial complex formula_120 is a set of simplices that satisfies the following conditions:
By definition, an orientation of a "k"-simplex is given by an ordering of the vertices, written as formula_126, with the rule that two orderings define the same orientation if and only if they differ by an even permutation. Thus every simplex has exactly two orientations, and switching the order of two vertices changes an orientation to the opposite orientation. For example, choosing an orientation of a 1-simplex amounts to choosing one of the two possible directions, and choosing an orientation of a 2-simplex amounts to choosing what "counterclockwise" should mean.
Let formula_120 be a simplicial complex. A simplicial "k"-chain is a finite formal sum 
where each "c""i" is an integer and σ"i" is an oriented "k"-simplex. In this definition, we declare that each oriented simplex is equal to the negative of the simplex with the opposite orientation. For example,
The vector space of "k"-chains on formula_120 is written formula_131. It has a basis in one-to-one correspondence with the set of "k"-simplices in formula_120. To define a basis explicitly, one has to choose an orientation of each simplex. One standard way to do this is to choose an ordering of all the vertices and give each simplex the orientation corresponding to the induced ordering of its vertices.
Let formula_133 be an oriented "k"-simplex, viewed as a basis element of formula_131. The boundary operator 
is the linear operator defined by:
where the oriented simplex 
is the formula_138th face of formula_96, obtained by deleting its formula_138th vertex.
In formula_131, elements of the subgroup
are referred to as cycles, and the subgroup
is said to consist of boundaries. 
A direct computation shows that formula_144. In geometric terms, this says that the boundary of anything has no boundary. Equivalently, the vector spaces formula_145 form a chain complex. Another equivalent statement is that formula_146 is contained in formula_147. 
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 formula_148 of the form
for some formula_150. An elementary cube formula_151 is the finite product of elementary intervals, i.e.
where formula_153 are elementary intervals. Equivalently, an elementary cube is any translate of a unit cube formula_154 embedded in Euclidean space formula_155 (for some formula_156 with formula_157). A set formula_158 is a cubical complex if it can be written as a union of elementary cubes (or possibly, is homeomorphic to such a set) and it contains all of the faces of all of its cubes. The boundary operator and the chain complex are defined similarly to those for simplicial complexes.
More general are cell complexes.
A chain complex formula_159 is a sequence of vector spaces formula_160 connected by linear operators (called boundary operators) formula_161, such that the composition of any two consecutive maps is the zero map. Explicitly, the boundary operators satisfy formula_162, or with indices suppressed, formula_163. The complex may be written out as follows.
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 formula_9 from a simplicial complex formula_120 to another formula_167 is a function from the vertex set of formula_120 to the vertex set of formula_167 such that the image of each simplex in formula_120 (viewed as a set of vertices) is a simplex in formula_167. It generates a linear map, called a chain map, from the chain complex of formula_120 to the chain complex of formula_167. Explicitly, it is given on formula_174-chains by
if formula_176 are all distinct, and otherwise it is set equal to formula_71.
A chain map formula_9 between two chain complexes formula_179 and formula_180 is a sequence formula_181 of homomorphisms formula_182 for each formula_61 that commutes with the boundary operators on the two chain complexes, so formula_184. This is written out in the following commutative diagram:
A chain map sends cycles to cycles and boundaries to boundaries.
See references.
Discrete differential forms: cochains.
For each vector space "Ci" in the chain complex we consider its dual space formula_185 and formula_186 is its dual linear operator
This has the effect of "reversing all the arrows" of the original complex, leaving a cochain complex
The cochain complex formula_189 is the dual notion to a chain complex. It consists of a sequence of vector spaces formula_190 connected by linear operators formula_191 satisfying formula_192. The cochain complex may be written out in a similar fashion to the chain complex.
The index formula_61 in either formula_195 or formula_196 is referred to as the degree (or dimension). The difference between chain and cochain complexes is that, in chain complexes, the differentials decrease dimension, whereas in cochain complexes they increase dimension. 
The elements of the individual vector spaces of a (co)chain complex are called cochains. The elements in the kernel of formula_197 are called cocycles (or closed elements), and the elements in the image of formula_197 are called coboundaries (or exact elements). Right from the definition of the differential, all boundaries are cycles.
The Poincaré lemma states that if formula_199 is an open ball in formula_200, any closed formula_201-form formula_202 defined on formula_199 is exact, for any integer formula_201 with formula_205.
When we refer to cochains as discrete (differential) forms, we refer to formula_197 as the exterior derivative. We also use the calculus notation for the values of the forms:
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:
Stokes' theorem says that the sum of a form formula_202 over the boundary of some orientable manifold formula_210 is equal to the sum of its exterior derivative formula_211 over the whole of formula_210, i.e.,
It is worthwhile to examine the underlying principle by considering an example for formula_214 dimensions. The essential idea can be understood by the diagram on the left, which shows that, in an oriented tiling of a manifold, the interior paths are traversed in opposite directions; their contributions to the path integral thus cancel each other pairwise. As a consequence, only the contribution from the boundary remains. 
See references.
The wedge product of forms.
In discrete calculus, this is a construction that creates from forms higher order forms: adjoining two cochains of degree formula_201 and formula_216 to form a composite cochain of degree formula_217. 
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 formula_218 is a formula_201-cochain and formula_220 is a formula_216-cochain, then 
where formula_96 is a formula_224 -simplex and formula_225, 
is the simplex spanned by formula_120 into the formula_227-simplex whose vertices are indexed by formula_228. So, formula_229 is the formula_201-th "front face" and formula_231 is the formula_216-th "back face" of formula_96, respectively.
The coboundary of the cup product of cochains formula_218 and formula_220 is given by
The cup product of two cocycles is again a cocycle, and the product of a coboundary with a cocycle (in either order) is a coboundary. 
The cup product operation satisfies the identity
In other words, the corresponding multiplication is graded-commutative.
See references.
Laplace operator.
The Laplace operator formula_238 of a function formula_9 at a vertex formula_201, is (up to a factor) the rate at which the average value of formula_9 over a cellular neighborhood of formula_201 deviates from formula_243. The Laplace operator represents the flux density of the gradient flow of a function. For instance, the net rate at which a chemical dissolved in a fluid moves toward or away from some point is proportional to the Laplace operator of the chemical concentration at that point; expressed symbolically, the resulting equation is the diffusion equation. For these reasons, it is extensively used in the sciences for modelling various physical phenomena. 
The codifferential
is an operator defined on formula_174-forms by:
where formula_197 is the exterior derivative or differential and formula_248 is the Hodge star operator.
The codifferential is the adjoint of the exterior derivative according to Stokes' theorem:
Since the differential satisfies formula_250, the codifferential has the corresponding property
The Laplace operator is defined by:
See references.
See also.
 