lördag 23 november 2013

Constructive Calculus in Finite Precision


The Constructive Calculus of BodyandSoul essentially consists of constructing solutions to algebraic and differential equations by computational numerical methods and thus must take into account the finite precision representation as single, double or multiple precision used by computers when performing computations with real numbers using round-off.

The basic concepts of (Lipschitz) continuity and differentiability are introduced in BodyandSoul without reference to the difficult concept of limit and therefore naturally generalize to include finite precision, while the heavy use of limits in Standard Calculus does not.

It is thus natural to define a real-valued function $f(t)$ of a real variable $t$ to be Lipschitz continuous with Lipschitz constant $L$ in finite precision $\epsilon > 0$, if for all $t$ and $\Delta t$
  • $\vert f(t+\Delta t) - f(t)\vert\le L(\vert\Delta t\vert + \epsilon)$.  
We see that here $\Delta t$ will effectively be bounded below by $\epsilon$.

Further, it is natural to define a real-valued function $t\rightarrow f(t)$ of a real variable $t$ to be differentiable with derivative $Df(t)$ in finite precision $\epsilon$, if there is a constant $K$ such that for all $t$ and $\Delta t$
  • $\vert f(t+\Delta t) - f(t) - Df(t)\Delta t\vert\le K(\vert\Delta t\vert^2 + \epsilon )$. 
In this case $\Delta t$ will effectively be bounded below by $\sqrt{\epsilon}$.

We compare with the limit definition of continuity:
  •  f(t) = $\lim_{\vert\Delta t\vert\rightarrow 0}f(t+\Delta t)$,
which requires infinite precision to make sense.

Even more importantly, we compare with the limit definition of the derivative:
  •  Df(t) = $\lim_{\vert\Delta t\vert\rightarrow 0}\frac{f(t+\Delta t) - f(t)}{\Delta t}$,
with division by the infinitely small (but non-zero) quantity $\Delta t$, which requires infinite precision and even so is difficult to grasp, in particular for the student.

The limit definitions can be (and are) used in Symbolic Calculus with derivatives determined by symbolic and not numerical computation, but present severe difficulties in Constructive Calculus in finite precision. The definitions without limits of Constructive Calculus can also be used in Symbolic Calculus by setting $\epsilon =0$, and thus are more versatile.

The essence of Constructive Calculus is to compute solutions to differential equations involving derivatives, thus essentially to compute integrals numerically in finite precision by time stepping as a well-posed numerically stable process, while derivatives may be computed symbolically on restricted classes of functions such as the piecewise polynomials of finite element methods thus circumventing the ill-posedness of numerical differentiation.  

Inga kommentarer:

Skicka en kommentar