This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

# Difference between revisions of "Discrete calculus article"

(→Principles) |
(→Chains and cochains) |
||

Line 126: | Line 126: | ||

− | ==Chains | + | ==Chains== |

[[File:Simplicial complex example.svg|thumb|200px|A simplicial 3-complex.]] | [[File:Simplicial complex example.svg|thumb|200px|A simplicial 3-complex.]] | ||

Line 203: | Line 203: | ||

\cdots | \cdots | ||

</math> | </math> | ||

+ | See references.<ref name="Bredon">{{cite book|author1=Glen E. Bredon|title=Topology and Geometry (Graduate Texts in Mathematics)|year=1997|publisher=Springer|isbn=90387979263}}</ref> | ||

+ | <ref name="TI">{{cite book|author1=Peter Saveliev|title=Topology Illustrated|year=2016|isbn=1495188752}}</ref> | ||

+ | <ref name="CT">{{cite book|author1=omasz Kaczynski; Konstantin Mischaikow; Marian Mrozek|title=Computational Topology|year=2004|isbn=0-387-40853-3}}</ref> | ||

− | + | ==Discrete differential forms: cochains== | |

+ | |||

+ | For each vector space''C<sub>i</sub>'' we consider its [[dual space]] <math>C_i^* := \mathrm{Hom}(C_i,{\bf R}),</math> and <math>\partial_i</math> by its [[dual space#Transpose of a linear map|dual linear operator]] | ||

: <math>d_{i-1}: C_{i-1}^* \to C_{i}^*.</math> | : <math>d_{i-1}: C_{i-1}^* \to C_{i}^*.</math> | ||

Line 212: | Line 217: | ||

: <math>\cdots \leftarrow C_{i+1}^* \stackrel{d_i}{\leftarrow}\ C_{i}^* \stackrel{d_{i-1}}{\leftarrow} C_{i-1}^* \leftarrow \cdots </math> | : <math>\cdots \leftarrow C_{i+1}^* \stackrel{d_i}{\leftarrow}\ C_{i}^* \stackrel{d_{i-1}}{\leftarrow} C_{i-1}^* \leftarrow \cdots </math> | ||

− | The '''[[cochain complex]]''' <math>(A^*, d^* | + | The '''[[cochain complex]]''' <math>(A^*, d^*)</math> is the [[dual (category theory)|dual]] notion to a chain complex. It consists of a sequence of vector spaces ..., ''A''<sup>0</sup>, ''A''<sup>1</sup>, ''A''<sup>2</sup>, ''A''<sup>3</sup>, ''A''<sup>4</sup>, ... connected by linear operators ''d''<sup>''n''</sup> : ''A''<sup>''n''</sup>→''A''<sup>''n''+1</sup> satisfying ''d''<sup>''n''+1</sup> ∘ ''d''<sup>''n''</sup> = 0. The cochain complex may be written out in a similar fashion to the chain complex. |

::<math> | ::<math> | ||

Line 227: | Line 232: | ||

The index ''n'' in either ''A''<sub>''n''</sub> or ''A''<sup>''n''</sup> 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 index ''n'' in either ''A''<sub>''n''</sub> or ''A''<sup>''n''</sup> 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 | + | The elements of the individual vector spaces of a (co)chain complex are called '''(co)chains'''. The elements in the [[kernel]] of ''d'' are called '''(co)cycles''' (or '''closed''' elements), and the elements in the [[image]] of ''d'' are called '''(co)boundaries''' (or '''exact''' elements). Right from the definition of the differential, all boundaries are cycles. |

+ | |||

+ | The '''[[Poincaré lemma]]'''<!--boldface per WP:R#PLA--> states that if ''B'' is an open ball in '''R'''<sup>''n''</sup>, any closed ''p''-form ''ω'' defined on ''B'' is exact, for any integer ''p'' with {{nowrap|1 ≤ ''p'' ≤ ''n''}}. | ||

+ | |||

+ | The calculus notation is often used for the values of the forms: | ||

+ | $$\omega (s)=\int_s\omega.$$ | ||

See references.<ref name="Bredon">{{cite book|author1=Glen E. Bredon|title=Topology and Geometry (Graduate Texts in Mathematics)|year=1997|publisher=Springer|isbn=90387979263}}</ref> | See references.<ref name="Bredon">{{cite book|author1=Glen E. Bredon|title=Topology and Geometry (Graduate Texts in Mathematics)|year=1997|publisher=Springer|isbn=90387979263}}</ref> | ||

− | <ref name="TI">{{cite book|author1= | + | <ref name="TI">{{cite book|author1=Peter Saveliev|title=Topology Illustrated|year=2016|isbn=1495188752}}</ref> |

− | |||

==Related== | ==Related== |

## Revision as of 14:31, 1 September 2019

Template:Short description Template:About

**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 $\Delta x$ 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:
$$\newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!}
\begin{array}{ccccc}
\begin{array}{|cc|}\hline\text{ discrete }\\ \text{ calculus }\\ \hline\end{array}& \ra{\quad\Delta x\to 0\quad} &\begin{array}{|cc|}\hline\text{ infinitesimal }\\ \text{ calculus }\\ \hline\end{array}
\end{array}$$

## Contents

## Principles

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 point 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 deriving the squaring function turns out to be something close to the doubling function.

The functions are defined at points separated by an increment $\Delta x=h>0$: $$a, a+h, a+2h, ..., a+nh,...$$

The "doubling function" may be denoted by $g(x)=2x$ and the "squaring function" by $f(x)=x^2$. The "difference quotient" now takes the function $f$, defined by the expression "$x^2$", 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 $g(x)=2x+h$, as will turn out. It is defined at the middle points of the above intervals: $$a+h/2, a+h+h/2, a+2h+h/2,..., a+nh+h/2,...$$

The most common symbol for a difference quotient is: $$\frac{\Delta f}{\Delta x}(x+h/2)=\frac{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$ 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 $f$ 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 graph of the function is a straight line), then the function can be written as $y=mx + b$, where $x$ is the independent variable, $y$ is the dependent variable, $b$ is the $y$-intercept, and:

- [math]m= \frac{\text{rise}}{\text{run}}= \frac{\text{change in } y}{\text{change in } x} = \frac{\Delta y}{\Delta x}.[/math]

This gives an exact value for the slope of a straight line. If the graph of the function is not a straight line, however, then the change in $y$ divided by the change in $x$ 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 Template:Math be a function, and fix a point Template:Math in the domain of Template:Math. Template:Math is a point on the graph of the function. If Template:Math is the increment of $x$, then Template:Math is the value of $x$ after (or before) Template:Math. Therefore, Template:Math is the increment of Template:Math. The slope between these two points is

- [math]m = \frac{f(a+h) - f(a)}{(a+h) - a} = \frac{f(a+h) - f(a)}{h}.[/math]

So Template:Math is the slope of the line between Template:Math and Template:Math.

Here is a particular example, the difference quotient of the squaring function at the input 3. Let $f(x)=x^2$ be the squaring function. Then:

- [math]\begin{align}\frac{\Delta f}{\Delta x}(3) &={(3+h)^2 - 3^2\over{h}} \\ &={9 + 6h + h^2 - 9\over{h}} \\ &={6h + h^2\over{h}} \\ &= 6 + h \end{align} [/math]

The process just described can be performed for any point in the domain of the squaring function. This defines the *difference quotient function* of the squaring function, or just the *difference quotient* of the squaring function for short. A computation similar to the one above shows that the difference quotient of the squaring function is the doubling function plus $h$.

*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.

- [math]\mathrm{Distance} = \mathrm{Speed} \cdot \mathrm{Time}[/math]

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 fluctuating velocity over a given time period. If Template:Math in the diagram on the right represents speed as it varies over time, the distance traveled (between the times represented by Template:Math and Template:Math) is the area of the shaded region Template:Math.

To evaluate that area, a method would be to divide up the distance between Template:Math and Template:Math into a number of equal segments, the length of each segment represented by the symbol Template:Math. For each small segment, we can choose one value of the function Template:Math. Call that value Template:Math. Then the area of the rectangle with base Template:Math and height Template:Math gives the distance (time Template:Math multiplied by speed Template:Math) traveled in that segment. Associated with each segment is the value of the function above it, Template:Math. The sum of all such rectangles gives the area between the axis and the curve, which is the total distance traveled.

The functions are defined at points separated by an increment $\Delta x=h>0$: $$a+h/2, a+h+h/2, a+2h+h/2,..., a+nh+h/2,...$$

The notation for Riemann sum is:

- [math]\sum_a^b f(x)\, \Delta x.[/math]

The new function is defined at the points: $$a, a+h, a+2h, ..., a+nh,...$$

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 Template:Math is defined on a partition of the interval Template:Math and if Template:Math is a function whose difference quotient is Template:Math, then

- [math]\sum_{a}^{b} f(x)\,\Delta x = F(b) - F(a).[/math]

Furthermore, for every Template:Math in the interval Template:Math,

- [math]\frac{\Delta}{\Delta x}\sum_a^x f(t)\, \Delta t = f(x).[/math]

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.

## Applications

Discrete calculus is used indirectly 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 and an optimal solution is desired. 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 Riemann sums to derive its path.

Maxwell's theory of electromagnetism and Einstein's theory of general relativity are also expressed in the language of differential calculus. Chemistry also uses calculus in determining reaction rates and radioactive decay. In biology, population dynamics starts with reproduction and death rates to model population changes.

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.

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, in order 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 providing a way to easily calculate both marginal cost and marginal revenue.

Discrete calculus is the standard way to solve differential equations. For instance, spacecraft use difference equations to approximate curved courses within zero gravity environments.

## Calculus of differences

A **(forward) difference** is an expression of the form

- [math] \Delta_h[f](x) = f(x + h) - f(x). [/math]

**Constant rule**: If Template:Mvar is a constant, then

- [math]\Delta c = 0[/math]

**Linearity**: if Template:Mvar and Template:Mvar are constants,

- [math]\Delta (a f + b g) = a \,\Delta f + b \,\Delta g[/math]

- [math] \begin{align} \Delta (f g) &= f \,\Delta g + g \,\Delta f + \Delta f \,\Delta g \end{align}[/math]

- [math]\begin{align} \sum_{n=a}^{b} \Delta f(n) &= f(b+1)-f(a) \end{align}[/math]

See references.^{[1]}^{[2]}^{[3]}.
^{[4]}^{[5]}^{[6]}^{[7]}

## Chains

A **simplicial complex** [math]\mathcal{K}[/math] is a set of simplices that satisfies the following conditions:

- 1. Every face of a simplex from [math]\mathcal{K}[/math] is also in [math]\mathcal{K}[/math].
- 2. The non-empty intersection of any two simplices [math]\sigma_1, \sigma_2 \in \mathcal{K}[/math] is a face of both [math]\sigma_1[/math] and [math]\sigma_2[/math].

By definition, an orientation of a *k*-simplex is given by an ordering of the vertices, written as (*v*_{0},...,*v*_{k}), 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 *S* be a simplicial complex. A simplicial *k*-chain is a finite formal sum

- [math]\sum_{i=1}^N c_i \sigma_i, \,[/math]

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,

- [math] (v_0,v_1) = -(v_1,v_0).[/math]

The group of *k*-chains on *S* is written *C _{k}*. This is a free abelian group which has a basis in one-to-one correspondence with the set of

*k*-simplices in

*S*. 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 σ = (*v*_{0},...,*v*_{k}) be an oriented *k*-simplex, viewed as a basis element of *C _{k}*. The

**boundary operator**

- [math]\partial_k: C_k \rightarrow C_{k-1}[/math]

is the linear operator defined by:

- [math]\partial_k(\sigma)=\sum_{i=0}^k (-1)^i (v_0 , \dots , \widehat{v_i} , \dots ,v_k),[/math]

where the oriented simplex

- [math](v_0 , \dots , \widehat{v_i} , \dots ,v_k)[/math]

is the *i*^{th} face of *σ*, obtained by deleting its *i*^{th} vertex.

In *C _{k}*, elements of the subgroup

- [math]Z_k = \ker \partial_k[/math]

are referred to as **cycles**, and the subgroup

- [math]B_k = \operatorname{im} \partial_{k+1}[/math]

is said to consist of **boundaries**.

A direct computation shows that ∂^{2} = 0. In geometric terms, this says that the boundary of anything has no boundary. Equivalently, the abelian groups

- [math](C_k, \partial_k)[/math]

form a chain complex. Another equivalent statement is that *B _{k}* is contained in

*Z*.

_{k}A **cubical complex** or **cubical set** is a set composed of points, line segments, squares, cubes, and their *n*-dimensional counterparts. They are used analogously to simplicial complexes.

An **elementary interval** is a subset [math]I\subsetneq\mathbf{R}[/math] of the form

- [math]I = [\ell, \ell+1]\quad\text{or}\quad I=[\ell, \ell][/math]

for some [math]\ell\in\mathbf{Z}[/math]. An **elementary cube** [math]Q[/math] is the finite product of elementary intervals, i.e.

- [math]Q=I_1\times I_2\times \cdots\times I_d\subsetneq \mathbf{R}^d[/math]

where [math]I_1,I_2,\ldots,I_d[/math] are elementary intervals. Equivalently, an elementary cube is any translate of a unit cube [math][0,1]^n[/math] embedded in Euclidean space [math]\mathbf{R}^d[/math] (for some [math]n,d\in\mathbf{N}\cup\{0\}[/math] with [math]n\leq d[/math]).^{[8]} A set [math]X\subseteq\mathbf{R}^d[/math] is a **cubical** **complex** (or **cubical set**) if it can be written as a union of elementary cubes (or possibly, is homeomorphic to such a set).^{[9]}

A **chain complex** [math](A_*, d_*)[/math] is a sequence of vector spaces ..., *A*_{0}, *A*_{1}, *A*_{2}, *A*_{3}, *A*_{4}, ... connected by linear operators (called **boundary operators** or **differentials**) *d*_{n} : *A*_{n}→*A*_{n−1}, such that the composition of any two consecutive maps is the zero map. Explicitly, the differentials satisfy *d*_{n} ∘ *d*_{n+1} = 0, or with indices suppressed, *d*^{2} = 0. The complex may be written out as follows.

- [math] \cdots \xleftarrow{d_0} A_0 \xleftarrow{d_1} A_1 \xleftarrow{d_2} A_2 \xleftarrow{d_3} A_3 \xleftarrow{d_4} A_4 \xleftarrow{d_5} \cdots [/math]

See references.^{[10]}
^{[11]}
^{[12]}

## Discrete differential forms: cochains

For each vector space*C _{i}* we consider its dual space [math]C_i^* := \mathrm{Hom}(C_i,{\bf R}),[/math] and [math]\partial_i[/math] by its dual linear operator

- [math]d_{i-1}: C_{i-1}^* \to C_{i}^*.[/math]

This has the effect of "reversing all the arrows" of the original complex, leaving a cochain complex

- [math]\cdots \leftarrow C_{i+1}^* \stackrel{d_i}{\leftarrow}\ C_{i}^* \stackrel{d_{i-1}}{\leftarrow} C_{i-1}^* \leftarrow \cdots [/math]

The **cochain complex** [math](A^*, d^*)[/math] is the dual notion to a chain complex. It consists of a sequence of vector spaces ..., *A*^{0}, *A*^{1}, *A*^{2}, *A*^{3}, *A*^{4}, ... connected by linear operators *d*^{n} : *A*^{n}→*A*^{n+1} satisfying *d*^{n+1} ∘ *d*^{n} = 0. The cochain complex may be written out in a similar fashion to the chain complex.

- [math] \cdots \xrightarrow{d^{-1}} A^0 \xrightarrow{d^0} A^1 \xrightarrow{d^1} A^2 \xrightarrow{d^2} A^3 \xrightarrow{d^3} A^4 \xrightarrow{d^4} \cdots [/math]

The index *n* in either *A*_{n} or *A*^{n} 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 **(co)chains**. The elements in the kernel of *d* are called **(co)cycles** (or **closed** elements), and the elements in the image of *d* are called **(co)boundaries** (or **exact** elements). Right from the definition of the differential, all boundaries are cycles.

The **Poincaré lemma** states that if *B* is an open ball in **R**^{n}, any closed *p*-form *ω* defined on *B* is exact, for any integer *p* with Template:Nowrap.

The calculus notation is often used for the values of the forms: $$\omega (s)=\int_s\omega.$$

See references.^{[10]}
^{[11]}

## Related

- Calculus of finite differences
- Numerical differentiation
- Divided differences
- Finite difference coefficients
- Finite difference method
- Finite volume method

## Further reading

## References

- ↑ Template:Cite book
- ↑ Template:Cite book
- ↑ Template:Cite book
- ↑ Template:Cite book
- ↑ Ames, W. F., (1977).
*Numerical Methods for Partial Differential Equations*, Section 1.6. Academic Press, New York. Template:ISBN. - ↑ Hildebrand, F. B., (1968).
*Finite-Difference Equations and Simulations*, Section 2.2, Prentice-Hall, Englewood Cliffs, New Jersey. - ↑ Template:Cite journal.
- ↑ Template:Cite journal
- ↑ Template:Cite book
- ↑
^{10.0}^{10.1}Template:Cite book - ↑
^{11.0}^{11.1}Template:Cite book - ↑ Template:Cite book

- Discrete Calculus, Grady, Leo J., Polimeni, Jonathan R., 2010