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

# Difference between revisions of "Discrete calculus article"

(→History) |
(→Principles) |
||

Line 34: | Line 34: | ||

==Principles== | ==Principles== | ||

− | 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 and a point in the domain, 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 the doubling function. | + | 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 and a point in the domain, 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. |

− | In more explicit terms the "doubling function" may be denoted by | + | In more explicit terms 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$, as will turn out. |

The most common symbol for a difference quotient is: | The most common symbol for a difference quotient is: | ||

Line 42: | Line 42: | ||

This notation is known as [[Leibniz's notation]]. | This notation is known as [[Leibniz's notation]]. | ||

− | If the input of the function represents time, then the difference quotient represents change with respect to time. For example, if | + | 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 function|linear]] (that is, if the [[Graph of a function|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> | :<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 | + | 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 {{math|''f''}} be a function, and fix a point {{math|''a''}} in the domain of {{math|''f''}}. {{math|(''a'', ''f''(''a''))}} is a point on the graph of the function. If {{math|''h''}} is the increment of $x$, then {{math|''a'' + ''h''}} is the value of $x$ after (or before) {{math|''a''}}. Therefore, {{math|(''a'' + ''h'', ''f''(''a'' + ''h''))}} is the increment of {{math|(''a'', ''f''(''a''))}}. 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> | :<math>m = \frac{f(a+h) - f(a)}{(a+h) - a} = \frac{f(a+h) - f(a)}{h}.</math> | ||

Line 54: | Line 53: | ||

So {{math|''m''}} is the slope of the line between {{math|(''a'', ''f''(''a''))}} and {{math|(''a'' + ''h'', ''f''(''a'' + ''h''))}}. | So {{math|''m''}} is the slope of the line between {{math|(''a'', ''f''(''a''))}} and {{math|(''a'' + ''h'', ''f''(''a'' + ''h''))}}. | ||

− | Here is a particular example, the difference quotient of the squaring function at the input 3. Let | + | 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}} \\ | |

− | |||

− | |||

− | :<math>\begin{align}f | ||

&={9 + 6h + h^2 - 9\over{h}} \\ | &={9 + 6h + h^2 - 9\over{h}} \\ | ||

&={6h + h^2\over{h}} \\ | &={6h + h^2\over{h}} \\ | ||

− | &= | + | &= 6 + h |

\end{align} | \end{align} | ||

</math> | </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$. | ||

+ | |||

+ | ''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 number, which gives the algebraic sum of areas between 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. | ||

+ | |||

+ | [[File:Constant velocity.png|left|thumb|Constant velocity]] | ||

+ | [[File:Riemann sum as region under curve.svg|right|thumb|280px|Integration can be thought of as measuring the area under a curve, defined by {{math|''f''(''x'')}}, between two points (here {{math|''a''}} and {{math|''b''}}).]] | ||

+ | 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 {{math|''f''(''x'')}} in the diagram on the right represents speed as it varies over time, the distance traveled (between the times represented by {{math|''a''}} and {{math|''b''}}) is the area of the shaded region {{math|''s''}}. | ||

+ | |||

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

+ | |||

+ | The notation for Riemann sum is <math>\sum </math>: | ||

+ | |||

+ | :<math>\sum_a^b f(x)\, \Delta x.</math> |

## Revision as of 13:06, 29 August 2019

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

It has two major branches, differential calculus and integral calculus. Differential calculus concerns incremental rates of change and the slopes of discrete curves. Integral calculus concerns accumulation of quantities and the areas under and between such curves. These two branches are related to each other by the fundamental theorem of discrete calculus.

These concepts of change start in their discrete form. Then by making the increment smaller and smaller, we find their contonuous counterparts via this *limit*:
$$\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}$$

## History

The early history of discrete calculus is the history of calculus.

Discrete calculus remain interlinked with infinitesimal calculus especially differential forms. Discrete calculus relies on "discrete differential forms", i.e., cochains. It cannot then be separated from the rest of exterior calculus or from algebraic topology. Therefore, the credit for the creation of discrete calculus should first go to the following individuals (roughly 1850 - 1950):

*Hermann Grassmann*: exterior algebra*Gregorio Ricci-Curbastro, Tullio Levi-Civita*: tensor calculus*Henri Poincaré*: triangulations (barycentric subdivision, dual triangulation), Poincare duality, Poincare lemma, the first proof of the general Stokes Theorem, and a lot more*Vito Volterra*: "The first mathematician to have written down Stokes' formula for an arbitrary dimension was probably V. Volterra." -- Dieudonne*L. E. J. Brouwer*: simplicial approximation*Élie Cartan, Georges de Rham*: the notion of differential form, the exterior derivative as a coordinate-independent linear operator, exactness/closedness of forms, the de Rham's theorem (the de Rham cohomology is equivalent to the singular cohomology)*Emmy Noether, Heinz Hopf, Leopold Vietoris, Walther Mayer*: modules of chains, the boundary operator, chain complexes*J.W. Alexander, Solomon Lefschetz, Lev Pontryagin, Andrey Kolmogorov, Norman Steenrod, Eduard Čech*: the early cochain notions*W. V. D. Hodge*: the Hodge star operator, the Hodge decomposition*Samuel Eilenberg, Saunders Mac Lane, Norman Steenrod, J.H.C. Whitehead*: the rigorous version of algebraic topology*Hassler Whitney*: cochains as integrands

The current development of discrete calculus is driven by the needs of applied modeling.

## Calculus of sequences

## Principles

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 and a point in the domain, 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.

In more explicit terms 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$, as will turn out.

The most common symbol for a difference quotient is: $$\frac{\Delta f}{\Delta x}.$$ This notation is known as Leibniz's notation.

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

*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 number, which gives the algebraic sum of areas between 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 notation for Riemann sum is [math]\sum [/math]:

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