Sign in

username:

password:



Not a member?

Search Online Books



Search tips

Free Online Books

Sponsor

Evaluate multicore with Texas Instruments:
Low-cost evaluation module & free software development kit available NOW.

Chapters

See Also

Embedded SystemsFPGAElectronics

Physical Audio Signal Processing
    Finite-Difference Schemes
       Von Neumann Analysis

Chapter Contents:

Search Physical Audio Signal Processing

  

Book Index | Global Index

Would you like to be notified by email when Julius Orion Smith III publishes a new entry into his blog?

  

Von Neumann Analysis

Von Neumann analysis is used to verify the stability of a finite-difference scheme. We will only consider one time dimension, but any number of spatial dimensions.

The procedure, in principle, is to perform a spatial Fourier transform along all spatial dimensions, thereby reducing the finite-difference scheme to a time recursion in terms of the spatial Fourier transform of the system. The system is then stable if this time recursion is at least marginally stable as a digital filter.

Let's apply von Neumann analysis to the finite-difference scheme for the ideal vibrating string Eq.$ \,$(D.3):

$\displaystyle y_{n+1,m}= y_{n,m+1}+ y_{n,m-1}- y_{n-1,m} \protect$

There is only one spatial dimension, so we only need a single 1D Discrete Time Fourier Transform (DTFT) along $ m$ [451]. Using the shift theorem for the DTFT, we obtain
$\displaystyle Y_{n+1}(k)$ $\displaystyle =$ $\displaystyle (e^{jkX} + e^{-jkX})Y_n(k) - Y_{n-1}(k)$  
  $\displaystyle =$ $\displaystyle 2\cos(kX)Y_n(k) - Y_{n-1}(k)$  
  $\displaystyle \isdef$ $\displaystyle 2c_kY_n(k) - Y_{n-1}(k) \protect$ (D.8)

where $ k=2\pi/\lambda$ denotes radian spatial frequency (wavenumber). (On a more elementary level, the DTFT along $ m$ can be carried out by substituting $ Y_n(k)e^{jkX}$ for $ y(n,m)$ in the finite-difference scheme.) This is now a second-order difference equation (digital filter) that needs its stability checked. This can be accomplished most easily using the Durbin recursion [449], or we can check that the poles of the recursion do not lie outside the unit circle in the $ z$ plane.

A method equivalent to checking the pole radii, and typically used when the time recursion is first order, is to compute the amplification factor as the complex gain $ G(k)$ in the relation

$\displaystyle Y_{n+1}(k) = G(k)Y_n(k). $

The finite-difference scheme is then declared stable if $ \vert G(k)\vert\leq 1$ for all spatial frequencies $ k$.

Since the finite-difference scheme of the ideal vibrating string is so simple, let's find the two poles. Taking the z transform of Eq.$ \,$(D.8) yields

$\displaystyle zY(z,k) = 2c_k Y(z,k) - z^{-1}Y(z,k) $

yielding the following characteristic polynomial:

$\displaystyle z^2 - 2c_k z - 1 = 0 $

Applying the quadratic formula to find the roots yields

$\displaystyle z = c_k \pm \sqrt{c_k^2 - 1}. $

The squared pole moduli are then given by

$\displaystyle \left\vert z\right\vert^2 = c_k^2 \pm (c_k^2 - 1) = \left\{\begi... ...eq 1 \\ [5pt] [1,1], & \left\vert c_k\right\vert\leq 1 \\ \end{array}\right.. $

Thus, for marginal stability, we require $ \left\vert c_k\right\vert\leq 1$, and the poles become

$\displaystyle z = c_k \pm j\sqrt{1-c_k^2} = \cos(kX) \pm j\sin(kX) = e^{\pm jkX}. $

Since the range of spatial frequencies is $ k\in[-\pi/X,\pi/X]$, we spontaneously have $ \vert c_k\vert\leq1$ for all $ k$. Therefore, we have shown by von Neumann analysis that the finite-difference scheme Eq.$ \,$(D.3) for the ideal vibrating string is stable.

In summary, von Neumann analysis verifies that no spatial Fourier components in the system are growing exponentially with respect to time.

Previous: Characteristic Polynomial Equation
Next: Equivalence of Digital Waveguide and Finite Difference Schemes

Order a Hardcopy of Physical Audio Signal Processing

About the Author: Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.


Comments

No comments yet for this page


Add a Comment
You need to login before you can post a comment (best way to prevent spam). ( Not a member? )