Sensors - May 2002 - Imitating Life: An Introduction to Computer Simulation and Modeling, Part 1

Computers have long been used to create numerical and logical models or simulations of real-world systems. Indeed, a large part of the motivation for developing the first computers in the 1930s and 1940s was to be able to perform calculations to simulate and analyze physical systems, such as electrical circuits and the flight of artillery shells. Since then, computer simulation has become an indispensable tool of scientists, engineers, economists, and other people who work with, and desire to understand, the behavior of complex systems. The purpose of this article is to serve as an overview of some of the underlying techniques used to implement computer simulations.

Why do you build and use computer simulation models? While there are many reasons, the following are among the most common.

Those Who Can’t Do, Simulate
In many cases, testing a real-world system can be prohibitively expensive or outright impossible. Seeing how an automobile collapses when it hits a barrier is an example of an expensive exercise to conduct in reality. But by crashing simulated cars into simulated walls on a workstation, automotive safety engineers can quickly evaluate potential designs and reduce the number of real cars that must be instrumented and sacrificed at the test track.

An example of an impossible-to-realize experiment would be estimating the environmental damage wrought by an asteroid colliding with the earth. At present, we lack the ability to conduct this experiment in actuality. But on a computer, we can safely slam simulated asteroids of all sizes and shapes into various parts of a simulated earth all day long without having to worry about triggering real-world mass extinction.

Those Who Can’t Simulate, Can’t Do
Many systems are so complex that their correctness and behavior can’t be easily or confidently predicted, either analytically or through experience and intuition. An integrated circuit (IC) is one example of such a system. For the device to function properly, tens or hundreds of thousands of individual circuits must operate exactly as planned. Isolating errors in the finished product can be difficult. For this reason, software vendors have developed numerous specialized circuit-simulation tools to let the designer simulate a circuit’s performance on a computer under a variety of operating conditions and stimuli, and monitor the behavior of the circuit at any point. Without such tools, the development of even moderately complex ICs is vastly more difficult and expensive, and in many cases, nearly impossible.

Beyond allowing engineers to see if their designs work, computer simulations allow the rapid comparison of alternative designs. By comparing the performance of various permutations of a given design, an engineer can optimize the performance, cost, or other desirable attributes of the design, subject to the constraints within which it must function.

Finally, you can use computer simulations to obtain qualitative insights into how a system behaves. Even relatively simple systems can exhibit nonintuitive and genuinely surprising behaviors, which may not be apparent from their mathematical formulations. Computer modeling and simulation has greatly aided research into complex systems in such fields as ecology, climatology, and astrophysics.

Mathematical Functions as Models

Figure 1. A function may be thought of as a black box that accepts one or more input values and instantaneously returns a related output value in response.

One of the simplest models you can build is a mathematical function. This provides one or more output variables with values dependent on one or more input variables. You can think of a function as a black box that monitors the values of one or more input variables and instantaneously computes a value of an output variable based on the inputs (see Figure 1). The output value depends only on the present values of the inputs, not on their past values or on past values of the output variable. You can make functions exhibit time-dependent behavior by making time (t) an input variable.

You can represent functions in many ways. One of the most familiar is closed-form algebraic equations, such as y = ax² + bx + c or y = k sin(x). Although a closed-form equation provides a compact and unambiguous representation of a function, in many cases it can be difficult to derive an appropriate expression. This is especially true in cases where the function is based on a set of arbitrary data points.

You can take several approaches to represent functions based on sets of arbitrary data. For example, you can often fit a curve based on either polynomials or other analytic functions. When you use polynomials, you can fit an nth-order polynomial (y = a_nxⁿ + ....a₁x + a₀ ) to a set of n data points so that the resulting curve passes through each data point. While the resulting curve can often provide an excellent fit for interpolated points between the original data points, be extremely cautious about using the function for extrapolation outside the domain. Polynomial fits can rapidly become poor approximations outside the domain of the data used to create them.

When it becomes necessary to represent a large number of arbitrary points, you can often use look-up tables and local interpolation techniques. Instead of trying to represent an arbitrary set of points by fitting a single high-order polynomial to them, you break up the function into small segments, and represent each segment between its end points (knots) by a different low-order polynomial. The use of a zeroeth-order polynomial (a constant) provides the discontinuous staircase approximation provided by a look-up table, while a first-order polynomial (ax + b) provides a connect-the-dots approximation, which allows for linear interpolation within each segment (see Figure 2).

Figure 2. Different order piecewise approximation techniques represent functions in different ways. A constant approximation yields a staircase function, and higher-order representations provide more continuous characteristics.

TABLE 1
A Nonnumerical Function
Day of Week (Input)	Go to Work? (Output)
Sunday	No
Monday	Maybe
Tuesday	Yes
Wednesday	Yes
Thursday	Yes
Friday	Maybe
Saturday	No

Another popular piecewise representation technique is called a cubic spline, which is based on the use of a third-order (ax³ + bx²+ cx + d) approximation. A cubic spline approximation provides two major advantages over a first-order approximation. The first is potentially a better fit for interpolated function values. The second is that the slope of the represented function is contznuous as you cross from one segment to another; this continuity can be a desirable or necessary feature for some models.

While a function can be mathematical in the sense of returning a number, a function can take any well-defined variables as inputs and present them as outputs. You can represent these kinds of functions by logical expressions, statements in a computer lanüuage, or look-up tables. Table 1 is an example of a nonnumerical function. Functions can also be nested, where the inputs of a particular function are derived from the outputs of others (see Figure 3).

Figure 3. Individual functions can be cascaded into more complex ones, as shown by this flow-graph. To obtain a final result, you have to determine a correct evaluation order.

A computer spreadsheet is an example of a program that is used to quickly and easily evaluate networks of functions.

Interdependence and Feedback
You can build a network with two functions, let’s say F1 and F2, where F1 uses F2 as one of its inputs, and F2 uses F1 as one of its inputs. In a spreadsheet, this condition is called a circular reference and results in the cells describing the functions to assume undefined values. Because a circular reference involves feeding back the result of a function to its own input, often passing though other functions, it’s also often called a static feedback loop.

Figure 4. A feedback control loop is an example of a system containing a circular reference, or static feedback loop. Such loops imply simultaneous relationships that a valid solution must satisfy.

Although a static feedback loop can stop a spreadsheet cold, in many systems these loops are an essential part of the model and indicate that there are simultaneous and interdependent relationships that a valid solution must satisfy. A simple and obvious example of a system containing static feedback is a feedback control system (see Figure 4). This system has an output variable (Y), an input variable (X), and an internal error variable (

), as well as a feed-forward amplifier with a gain of a and a feedback amplifier with a gain of –b. The relationships in this system can be described by:

Figure 5. Static feedback loops can hide in systems without explicit feedback. The simultaneous relationships in this electrical circuit (A) result in static feedback loops in the equivalent function-based model (B).

The simultaneous relationships between X and Y form a pair of simultaneous equations. In this case, the equations are trivial and can readily be solved to yield an expression relating Y to X.

A system doesn’t need to have explicit feedback loops in its real-world structure to have static feedback relationships in its mathematical model. Electrical circuits are common examples of systems with such hidden feedback. The circuit in Figure 5 is an example of a physical system that doesn’t have any obvious feedback but possesses several simultaneous relationships that become apparent only when you derive the mathematical model. For this circuit, the various functions of the feedback loop are:

Nonlinear Systems

Figure 6. When one or more of the simultaneous relationships in a system are nonlinear, such as current vs. voltage for the diode shown in this circuit, you may have to use iterative methods to solve the resulting sets of equations.

In cases in which the simultaneous equations arising from feedback loops are linear, such as the electrical circuit of the previous example, you can use standard techniques from linear algebra to obtain solutions. But while linear systems are convenient to solve, real-world phenomena are rarely strictly linear—springs break and resistors burn out. Many models incorporating static feedback require solutions that consist of sets of nonlinear equations. For example, Figure 6 shows an electrical circuit that is a simple nonlinear system. The value of the voltage source (V_S), the resistor (R), and the exponential characteristics of the diode define the current (I) flowing through the circuit, and it’s simultaneously defined by the following relationships:

V_D	= voltage across the diode
V_T	= diode thermal voltage (~0.026 V at room temperature)
k	= constant dependent on the diode’s construction (in amperes)

While some nonlinear equations can be solved analytically, it doesn’t take a great deal of complexity to exceed what may be convenient, or even possible, with analytic techniques. In these cases, you have to use numerical techniques to find approximate solutions.

In general, the way you find a numerical solution to a nonlinear equation (or set of equations) is to take a guess at a solution and then check to see how close the guess comes to satisfying the equation (or equations). Based on how far off the guess is and the direction in which it is off, you modify the guess and repeat the process. When a guess satisfies the conditions of the equation to a satisfactory degree, you halt the process and take that value to be the solution. Techniques that use repetitive guessing to find a solution to a set of equations are called iterative methods.

Although the concept behind iterative methods can sound simple, the details of how to come up with a series of good guesses that quickly converge to a desired result can require a significant degree of mathematical sophistication and knowledge about the system you’re trying to model. In the example above, you can derive an iterative formula from Equation 5 that computes a new and, let’s hope, better guess in terms of the last guess.

TABLE 2
Example of Converging Iterative Function
Iteration	V_D
Initial Guess	1
1	0.5748486
2	0.5774748
3	0.5774594
4	0.5774595
5	0.5774595

For example, assume V = 5 V, R = 1000

, and k = 10^–12 A. If you start with an initial guess for VD of 1 V, the successive values of VD appear in Table 2.

In this example, the guessing process is nearly trivial. You can pick almost any positive initial guess for V_D, and the equation will quickly converge on a valid solution.

While the iteration formula of Equation 6 converges quickly on a solution, you can also derive formulas that don’t converge quickly—or even at all. One such example for the problem above is:

TABLE 3
Example of Nonconverging Iterative Function
Iteration	V_D
Initial Guess	1
1	-50539842
2	5
3	-Overflow

If you execute this iterative formula, the results will quickly overflow the computer (see Table 3).

While there are techniques for deriving iteration formulas, there are no one-size-fits-all methods for solving nonlinear equations, as there are for solving their linear counterparts. Because different types of simulation problems generate equations with different characteristics, appropriate solution methods must be chosen and often optimized to suit a particular class of problems.

Continuous Field Problems
Many interesting problems are not readily described by a few discrete variables, as the voltages and currents in the electric circuits

Figure 7. A variable defined continuously as a function over some region of space, such as the temperature of a plate heated by a soldering iron (A), can often be approximated by a uniform grid of discrete variables (B). Solutions to the approximated model can then be obtained through the use of finite difference techniques.

presented earlier could be, but are better understood as continuous functions over some region of space. Examples of such spatially continuous systems are mechanical stress in a structure and electromagnetic fields in free space. In each of these systems, the solution takes the form of one or more variables, which vary continuously over some spatial region of interest.

An example of a continuous field model is the distribution of temperature in a solid. Figure 7A shows a flat metal plate being heated by a soldering iron at a single point. In the actual system, every point on the plate will have an associated temperature. For an idealized 2D thermal conductor, the temperature can be found by solving a partial differential equation (Poisson’s equation):

T(x,y)	= temperature at position (x,y)
Q(x,y)	= amount of heat introduced into the surface by the soldering iron, also as a function of position

Because computers (which operate on discrete values) can’t represent such continuous variables as T(x,y) directly, you have to define T as a selected set of discrete points. One class of solution methods for this type of problem is called finite difference methods. These methods convert a continuous field to a discrete form by representing it as a series of points spaced on a rectangular grid (see Figure 7B). When the continuous variable T(x,y) is replaced by a set of discrete variables (T_i,j), you can develop a discrete approximation to Poisson’s equation:

When you define an equation for each point (T_i,j), you get a set of linear simultaneous equations, which when solved yield T for each point.

Many systems of interest, however, contain objects and discontinuities that can’t be accurately represented without resorting to a fine grid. While a finer grid can produce more accurate simulations, it also increases the computational costs of solving the problem.

Finite difference models tend to generate large sets of linear equations. For example, a problem grid consisting of m × n grid points will result in m × n equations with m × n variables. You’ll typically represent this as a matrix with m × n columns and m × n rows. You can see that a grid of even modest resolution (e.g., 100 by 100 points) will generate a very large set of equations (10,000 equations with 10,000 unknowns).

Although the memory and speed of modern computers make it feasible to solve large sets of simultaneous equations, more efficient modeling techniques let you tackle even bigger simulation problems with greater accuracy. One such class of techniques, which is especially useful for solving continuous field problems, is called finite element analysis.

Figure 8. In finite element analysis, you can model nonuniform shapes by approximating them with a mesh of 2D or 3D modeling elements. In this case, triangles.

Finite element analysis maps the geometry of the system to be simulated onto a mesh of elements, often triangles or quadrilaterals. Figure 8 shows how a curved object can be described by triangular elements. Because the elements vary in size, you can use a few large elements to describe homogeneous areas of the problem (e.g., the deep interior of an object) and smaller but more numerous elements to describe areas of higher detail (e.g., the perimeter).

In a finite element model, you compute a solution only at the vertices of the elements to arrive at the solution to the problem. As in the case of finite difference models, the number of simultaneous equations generated by a finite element model is proportional to the number of vertices in the model. Representing an arbitrary geometry with a given degree of accuracy, however, usually requires far fewer finite element vertices than finite difference grid points. This results in smaller sets of equations, which can be solved more quickly and with less memory.

Because the equations to be solved for a vertex value depend on both the number and the geometries (shapes, orientations, and sizes) of the elements of which the vertex is a part, they tend to be significantly more complex than those used by finite difference analysis.

Figure 9. Although a finite element simulation model is solved only at the vertices, or nodes, of the modeling element, interpolation techniques can let you determine the approximate values of the solution at points inside the element.

The formulation of the models used to describe the elements provides an additional advantage in that interpolated solution values can often be readily obtained for any points within the element. In the case of an element based on a first-order linear model (see Figure 9), the solution value (temperature) can be determined anywhere within that element as a linear function of the position (T(x,y) = ax + by + c). For this reason, more complex higher-element models are often defined so as to include intermediate vertices along the edges of the elements to allow more accurate interpolations inside the element boundaries.

You can also extend finite element analysis to simulate 3D problems by choosing the appropriate element type. For 3D simulations, you often use tetrahedra (four-pointed pyramids) and deformed cubic shapes (bricks) as the modeling elements. By combining linear solution methods with iterative methods, you can also formulate finite element simulations that can accurately model nonlinear effects, such as saturation in magnetic models or nonelastic deformation in mechanical models.

Next Time
The second part of this two-part series will discuss simulation models for systems that change over time—continuous systems, discrete-time systems, and discrete-event systems. In addition, this part will include a look at some of the commercial software you might use in particular types of applications. “Imitating Life: An Introduction to Computer Simulation and Modeling, Part 2,” will appear on this web site next month as an Online Exclusive.

Editor’s Note
All of the computer simulation images appearing in this article were created in the Maxwell 3D software package and provided courtesy of Ansoft Corp., Pittsburgh, PA.