Difference Equations (Finite Difference Schemes)

There are many methods for converting ODEs and PDEs to difference equations [53,55,484]. As will be discussed in §7.3, a very simple, order-preserving method is to replace each derivative with a finite difference:

$$\dot x(t)\isdefs \frac{d}{dt} x(t) \isdefs \lim_{\delta\to 0} \frac{x(t) - x(t-\delta)}{\delta} \;\approx\; \frac{x(n T)-x[(n-1)T]}{T} \protect$$ (2.2)

for sufficiently small $T$ (the sampling interval). This is formally known as the backward difference operation for approximating differentiation. We will discuss a variety of such methods in §7.3 and Appendix D.

As a simple example, consider a mass $m$ driven along a frictionless surface by a driving force $f(t)$ , as in Fig.1.1, and suppose we wish to know the resulting velocity of the mass $v(t)$ , assuming it starts out with position and velocity 0 at time 0 (i.e., $x(0)=v(0)=0$ ). Then, from Newton's $f=ma$ relation, the ODE is

$$f(t) = m\,{\dot v}(t),$$

and the difference equation resulting from the backward-difference substitution is

$$f(nT) \eqsp m \frac{v(nT) - v[(n-1)T]}{T}, \quad n=0,1,2,\ldots\,.$$

Solving for $v(nT)$ yields the following finite difference scheme:

$$v(nT) \eqsp v[(n-1)T] + \frac{T}{m} f(nT), \quad n=0,1,2,\ldots \protect$$ (2.3)

with $v(-T)\isdeftext 0$ . In general, the driving force $f$ could depend on the current state of the system (e.g., if a spring and/or dashpot were introduced). In such a case, Eq.(1.3) may not be computable. (A delay-free loop could appear in the signal flow diagram.) Also, a finite force at time $t$ cannot produce an instantaneous velocity at time $t$ , so Eq.(1.3) is not ``physical'' in that sense, since $v(nT)$ depends on $f(nT)$ . To address both of these issues, we can instead use the forward difference approximation to the derivative:

$$\dot x(t) \eqsp \lim_{\delta\to 0} \frac{x(t+\delta) - x(t)}{\delta} \;\approx\; \frac{x[(n+1)T]-x(n T)}{T} \protect$$ (2.4)

As $T\to0$ , the forward and backward difference operators approach the same limit (since $x(t)$ is presumed continuous). Using this we obtain what is called an explicit finite difference scheme:

$$v[(n+1)T] \eqsp v(nT) + \frac{T}{m} f(nT), \quad n=0,1,2,\ldots \protect$$ (2.5)

with $v(0)\isdeftext 0$ .

A finite difference scheme is said to be explicit when it can be computed forward in time in terms of quantities from previous time steps, as in this example. Thus, an explicit finite difference scheme can be implemented in real time as a causal digital filter.

There are also implicit finite-difference schemes which may correspond to non-causal digital filters [452]. Implicit schemes are generally solved using iterative and/or matrix-inverse methods, and they are typically used offline (not in real time) [558].

There is also an interesting class of explicit schemes called semi-implicit finite-difference schemes which are obtained from an implicit scheme by imposing a fixed upper limit on the number of iterations in, say, Newton's method for iterative solution [558]. Thus, any implicit scheme that can be quickly solved by iterative methods can be converted to an explicit scheme for real-time usage. One technique for improving the iterative convergence rate is to work at a very high sampling rate, and initialize the iteration for each sample at the solution for the previous sample [558].

In this book, we will be concerned almost exclusively with explicit linear finite-difference schemes, i.e., causal digital filter models of one sort or another. That is, the main thrust is to obtain as much ``physical modeling power'' as possible from ordinary digital filters and delay lines. We will also be able to easily add memoryless nonlinearities where needed (such as implemented by table look-ups and short polynomial evaluations) as a direct result of the physical meaning of the signal samples.