## More General Finite-Difference Methods

The FDA and bilinear transform of the previous sections can be viewed as first-order conformal maps from the analog plane to the digital plane. These maps are one-to-one and therefore non-aliasing. The FDA performs well at low frequencies relative to the sampling rate, but it introduces artificial damping at high frequencies. The bilinear transform preserves the frequency axis exactly, but over a warped frequency scale. Being first order, both maps preserve the number of poles and zeros in the model.We may only think in terms of mapping the plane to the plane for

*linear, time-invariant*systems. This is because Laplace transform analysis is not defined for nonlinear and/or time-varying differential equations (no plane). Therefore, such systems are instead digitized by some form of

*numerical integration*to produce solutions that are ideally sampled versions of the continuous-time solutions. It is often necessary to work at sampling rates much higher than the desired audio sampling rate, due to the bandwidth-expanding effects of nonlinear elements in the continuous-time system. A tutorial review of numerical solutions of Ordinary Differential Equations (ODE), including nonlinear systems, with examples in the realm of audio effects (such as a diode clipper), is given in [555]. Finite difference schemes specifically designed for nonlinear discrete-time simulation, such as the energy-preserving ``Kirchoff-Carrier nonlinear string model'' and ``von Karman nonlinear plate model'', are discussed in [53]. The remaining sections here summarize a few of the more elementary techniques discussed in [555].

### General Nonlinear ODE

In state-space form (§1.3.7) [449],^{8.7}a general class of th-order Ordinary Differential Equations (ODE), can be written as

where denotes time in seconds, denotes a vector of

*state variables*at time ,

In this case, standard methods for converting a filter from continuous to discrete time may be used, such as the FDA (§7.3.1) and bilinear transform (§7.3.2).

^{8.8}

### Forward Euler Method

The finite-difference approximation (Eq.(7.2)) with the derivative evaluated at time yields the*forward Euler method*of numerical integration:

where denotes the

*approximation*to computed by the forward Euler method. Note that the ``driving function'' is evaluated at time , not . As a result, given, and the input vector for all , Eq.(7.10) can be iterated forward in time to compute for all . Since is an arbitrary function, we have a solver that is applicable to nonlinear, time-varying ODEs Eq.(7.8). Because each iteration of the forward Euler method depends only on past quantities, it is termed an

*explicit method*. In the LTI case, an explicit method corresponds to a

*causal*digital filter [449]. Methods that depend on current and/or future solution samples (

*i.e.*, for ) are called

*implicit methods*. When a nonlinear numerical-integration method is implicit, each step forward in time typically uses some number of iterations of Newton's Method (see §7.4.5 below).

### Backward Euler Method

An example of an implicit method is the*backward Euler*method:

Because the derivative is now evaluated at time instead of , the backward Euler method is implicit. Notice, however, that if time were reversed, it would become explicit; in other words, backward Euler is implicit in forward time and explicit in reverse time.

### Trapezoidal Rule

The*trapezoidal rule*is defined by

Thus, the trapezoidal rule is driven by the

*average*of the derivative estimates at times and . The method is implicit in either forward or reverse time. The trapezoidal rule gets its name from the fact that it approximates an integral by summing the areas of trapezoids. This can be seen by writing Eq.(7.12) as

*bilinear transform*in the linear, time-invariant case. Carrying Eq.(7.12) to the frequency domain gives

### Newton's Method of Nonlinear Minimization

Newton's method [162],[166, p. 143] finds the minimum of a nonlinear (scalar) function of several variables by locally approximating the function by a quadratic surface, and then stepping to the bottom of that ``bowl'', which generally requires a matrix inversion. Newton's method therefore requires the function to be ``close to quadratic'', and its effectiveness is directly tied to the accuracy of that assumption. For smooth functions, Newton's method gives very rapid*quadratic convergence*in the last stages of iteration. Quadratic convergence implies, for example, that the number of significant digits in the minimizer approximately doubles each iteration. Newton's method may be derived as follows: Suppose we wish to minimize the real, positive function with respect to . The vector Taylor expansion [546] of about gives

Applying Eq.(7.13) iteratively, we obtain Newton's method:

where is given as an initial condition. When the is any

*quadratic form*in , then , and Newton's method produces in one iteration; that is, for every .

### Semi-Implicit Methods

A*semi-implicit*method for numerical integration is based on an implicit method by using only one iteration of Newton's method [354,555]. This effectively converts the implicit method into a corresponding explicit method. Best results are obtained for highly oversampled systems (

*i.e.*, is larger than typical audio sampling rates).

### Semi-Implicit Backward Euler

The*semi-implicit backward Euler*method is defined by [555]

where denotes an estimate of the second time derivative .

### Semi-Implicit Trapezoidal Rule

The*semi-implicit trapezoidal rule*method is given by [555]

### Summary

We have looked at a number of methods for solving nonlinear ordinary differential equations, including explicit, implicit, and semi-implicit numerical integration methods. Specific methods included the explicit forward Euler (similar to the finite difference approximation of §7.3.1), backward Euler (implicit), trapezoidal rule (implicit, and equivalent to the bilinear transform of §7.3.2 in the LTI case), and semi-implicit variants of the backward Euler and trapezoidal methods. As demonstrated and discussed further in [555], implicit methods are generally more accurate than explicit methods for nonlinear systems, with semi-implicit methods (§7.4.6) typically falling somewhere in between. Semi-implicit methods therefore provide a source of improved explicit methods. See [555] and the references therein for a discussion of accuracy and stability of such schemes, as well as applied examples.### Further Reading in Nonlinear Methods

Other well known numerical integration methods for ODEs include second-order backward difference formulas (commonly used in circuit simulation [555]), the fourth-order Runge-Kutta method [99], and their various explicit, implicit, and semi-implicit variations. See [555] for further discussion of these and related finite-difference schemes, and for application examples in the*virtual analog*area (digitization of musically useful analog circuits). Specific digitization problems addressed in [555] include electric-guitar distortion devices [553,556], the classic ``tone stack'' [552] (an often-used bass, midrange, and treble control circuit in guitar amplifiers), the Moog VCF, and other electronic components of amplifiers and effects. Also discussed in [555] is the ``K Method'' for nonlinear system digitization, with comparison to nonlinear wave digital filters (see Appendix F for an introduction to

*linear*wave digital filters). The topic of

*real-time finite difference schemes*for virtual analog systems remains a lively research topic [554,338,293,84,264,364,397]. For

*Partial Differential Equations*(PDEs), in which spatial derivatives are mixed with time derivatives, the finite-difference approach remains fundamental. An introduction and summary for the LTI case appear in Appendix D. See [53] for a detailed development of finite difference schemes for solving PDEs, both linear and nonlinear, applied to digital sound synthesis. Physical systems considered in [53] include bars, stiff strings, bow coupling, hammers and mallets, coupled strings and bars, nonlinear strings and plates, and acoustic tubes (voice, wind instruments). In addition to numerous finite-difference schemes, there are chapters on finite-element methods and spectral methods.

**Next Section:**

Summary of Lumped Modeling

**Previous Section:**

Digitization of Lumped Models