Phorgy Phynance

Archive for January 2012

Network Theory and Discrete Calculus – Differentiation Rules

leave a comment »

This post is part of a series

In the previous post, we introduced discrete calculus on a binary tree. In particular, we introduced two sets of basis 1-forms we’ll refer to as

  1. Graph bases \{du^+,du^-\} and
  2. Coordinate bases \{dt,dx\}

related by

du^\pm = \Delta u \mathbf{e}^\pm = \frac{\Delta u}{2\Delta t} dt \pm \frac{\Delta u}{2\Delta x} dx

and saw that discrete 1-forms can be expressed in either left- or right-components forms

\alpha = \overleftarrow{\alpha_t} dt + \overleftarrow{\alpha_x} dx = dt \overrightarrow{\alpha_t} + dx \overrightarrow{\alpha_x},

where, in general, the left- and right-component 0-forms do not coincide, i.e.

\overleftarrow{\alpha_t} \ne \overrightarrow{\alpha_t} and \overleftarrow{\alpha_x} \ne \overrightarrow{\alpha_x}

due to the noncommutativity of discrete 0-forms and discrete 1-forms.

Product Rule

Recall the exterior derivative of a discrete 0-form f may be expressed in left-component form as

df = \overleftarrow{\partial_t f} dt + \overleftarrow{\partial_x f} dx

where

\begin{aligned} \overleftarrow{\partial_t f} = \sum_{(i,j)} \left[\frac{f(i+1,j+1)+f(i-1,j+1) -2f(i,j)}{2\Delta t}\right] \mathbf{e}^{(i,j)} \end{aligned}

and

\begin{aligned} \overleftarrow{\partial_x f} = \sum_{(i,j)} \left[\frac{f(i+1,j+1) -f(i-1,j+1)}{2\Delta x}\right] \mathbf{e}^{(i,j)} \end{aligned}

Although the product rule is satisfied, i.e.

d(fg) = (df)g + f(dg),

note the discrete 0-form g is on the right of the discrete 1-form df and the discrete 0-form f is on the left of the discrete 1-form dg. Attempting to express the product rule in left components, we find

\begin{aligned} d(fg) &= \overleftarrow{\partial_t (fg)} dt + \overleftarrow{\partial_x (fg)} dx \\ &= (\overleftarrow{\partial_t f} dt + \overleftarrow{\partial_x f} dx )g + f(\overleftarrow{\partial_t g} dt + \overleftarrow{\partial_x g} dx).\end{aligned}

In order to move g to the left of the coordinate bases above, we need to know the commutation relations

[dt,g] and [dx,g].

These commutation relations may be determined by noting that for any two discrete 0-forms f and g, we have

[df,g] = [dg,f].

Therefore,

\begin{aligned} { [dt,g] }&= [dg,t] \\ &= \overleftarrow{\partial_t g} [dt,t] + \overleftarrow{\partial_x g} [dx,t] \\ &= \Delta t \overleftarrow{\partial_t g} dt + \Delta t \overleftarrow{\partial_x g} dx\end{aligned}

and

\begin{aligned} { [dx,g] }&= [dg,x] \\ &= \overleftarrow{\partial_t g} [dt,x] + \overleftarrow{\partial_x g} [dx,x] \\ &= \Delta t \overleftarrow{\partial_t g} dx + \frac{(\Delta x)^2}{\Delta t} \overleftarrow{\partial_x g} dt,\end{aligned}

where use has been made of the coordinate commutation relations in the previous post.

Putting everything together, we find the product rule above implies the left components satisfy

\overleftarrow{\partial_t (fg)} = (\overleftarrow{\partial_t f}) g + f(\overleftarrow{\partial_t g})+ \Delta t (\overleftarrow{\partial_t f})(\overleftarrow{\partial_t g}) + \frac{(\Delta x)^2}{\Delta t} (\overleftarrow{\partial_x f})( \overleftarrow{\partial_x g})

and

\overleftarrow{\partial_x (fg)} = (\overleftarrow{\partial_x f}) g + f(\overleftarrow{\partial_x g})+ \Delta t (\overleftarrow{\partial_x f})(\overleftarrow{\partial_t g}) + \Delta t (\overleftarrow{\partial_t f})( \overleftarrow{\partial_x g})

Change of Variables

Change of variables is something straightforward, yet has many applications, so it is worth writing it down here for future reference.

Let S be a discrete 0-form with

dS = \overleftarrow{\partial_t S} dt + \overleftarrow{\partial_x S} dx.

If \overleftarrow{\partial_x S} is invertible, we can rewrite this as

dx = \frac{1}{\overleftarrow{\partial_x S}} (dS - \overleftarrow{\partial_t S} dt).

Given any other discrete 0-form V, we have

dV = \left.\overleftarrow{\partial_t V}\right|_x dt + \overleftarrow{\partial_x V} dx = \left.(\overleftarrow{\partial_t V} \right|_x- \frac{\overleftarrow{\partial_x V}}{\overleftarrow{\partial_x S}} \left.\overleftarrow{\partial_t S}\right|_x) dt + \frac{\overleftarrow{\partial_x V}}{\overleftarrow{\partial_x S}} dS.

From this, we can read off the discrete chain rules

\overleftarrow{\partial_x V} = \overleftarrow{\partial_S V} \overleftarrow{\partial_x S}

and

\left.\overleftarrow{\partial_t V}\right|_S = \left.\overleftarrow{\partial_t V} \right|_x-\overleftarrow{\partial_S V} \left.\overleftarrow{\partial_t S}\right|_x.

Written by Eric

January 8, 2012 at 11:20 pm