Numerical Methods

Design, Analysis, and Computer Implementation of Algorithms

Anne Greenbaum, Tim P. Chartier

• Publisher: Princeton University Press
• Year: 2012
• ISBN:
  9781400842674
• Topic: Mathematics
• Subtopic: Applied Mathematics
• Index: Mathematics

A rigorous and comprehensive introduction to numerical analysis Numerical Methods provides a clear and concise exploration of standard numerical analysis topics, as well as nontraditional ones, including mathematical modeling, Monte Carlo methods, Markov chains, and fractals. Filled with appealing examples that will motivate students, the textbook considers modern application areas, such as information retrieval and animation, and classical topics from physics and engineering. Exercises use MATLAB and promote understanding of computational results.The book gives instructors the flexibility to emphasize different aspects—design, analysis, or computer implementation—of numerical algorithms, depending on the background and interests of students. Designed for upper-division undergraduates in mathematics or computer science classes, the textbook assumes that students have prior knowledge of linear algebra and calculus, although these topics are reviewed in the text. Short discussions of the history of numerical methods are interspersed throughout the chapters. The book also includes polynomial interpolation at Chebyshev points, use of the MATLAB package Chebfun, and a section on the fast Fourier transform. Supplementary materials are available online.

• Clear and concise exposition of standard numerical analysis topics
• Explores nontraditional topics, such as mathematical modeling and Monte Carlo methods
• Covers modern applications, including information retrieval and animation, and classical applications from physics and engineering
• Promotes understanding of computational results through MATLAB exercises
• Provides flexibility so instructors can emphasize mathematical or applied/computational aspects of numerical methods or a combination
• Includes recent results on polynomial interpolation at Chebyshev points and use of the MATLAB package Chebfun
• Short discussions of the history of numerical methods interspersed throughout
• Supplementary materials available online

1

MATHEMATICAL MODELING

Numerical methods play an important role in modern science. Scientific exploration is often conducted on computers rather than laboratory equipment. While it is rarely meant to completely replace work in the scientific laboratory, computer simulation often complements this work.

For example, the aerodynamic simulation of two NASCAR autos pictured in figure 1.1(a) requires the numerical solution of partial differential equations (PDEs) that model the flow of air past the car. An auto body must be smooth and sleek, so it is often modeled using cubic (or higher order) splines. Similar computations are done in designing aircraft. We will study the numerical issues in using splines and solving PDEs in chapters 8 and 14, respectively.

Figure 1.1. (a) A simulation of two NASCAR autos depicts the streamlines of air produced as a car drafts and is about to pass another. (Simulation performed with STAR-CCM+.) (b) Solving protein-folding models utilizes numerical optimization.

Other examples occur in the field of mathematical biology, an active area of research in industry, government, and academia. Numerical algorithms play a crucial role in this work. For example, protein-folding models are often solved as large optimization problems. Protein arranges itself in such a way as to minimize energy—nature has no trouble finding the right arrangement, but it is not so easy for humans. The field of numerical optimization is an entire subject on its own, so it will not be covered in this book. The numerical methods described here, however, form the core of most optimization procedures.

Before studying issues in the analysis and implementation of efficient and accurate numerical methods, we first look briefly at the topic of mathematical modeling, which turns real-world problems into the sorts of mathematical equations that numerical analysts can tackle. The mathematical formulation usually represents only a model of the actual physical situation, and it is often important for the numerical analyst or computational scientist to know something about the origin of the model; in fact, numerical analysts sometimes work directly with scientists and engineers in devising the mathematical model. This interaction is important for a number of reasons. First, many algorithms do not produce the exact solution but only an approximate one. An understanding of the origin of the problem is necessary to determine what constitutes an acceptably good “approximate” solution: an error of a few centimeters might be acceptable in locating an enemy tank, but it would not be acceptable in locating a tumor for laser surgery! Second, even if the algorithm theoretically produces the exact solution, when implemented on a computer using finite-precision arithmetic, the results produced will most likely be inexact. Part of numerical analysis is the understanding of the impact of finite-precision computations on the accuracy of results. We will look more deeply at the issues in computing in finite precision in chapter 5.

In this chapter we present a variety of applications that involve numerical computation and come from the mathematical modeling of various processes.

1.1 MODELING IN COMPUTER ANIMATION

Many of the computer generated graphics that dominate the silver screen are produced with dynamic simulation; that is, a model is created, often using the laws of physics, and numerical methods are then used to compute the results of that model. In this section, we will look at the role of numerics in animation that appeared in the 2002 film Star Wars: Episode II Attack of the Clones. In particular, we will take a careful look at some of the special effects used to digitally create the character of Yoda, a Jedi master who first appeared as a puppet in the Star Wars saga in the 1980 film, The Empire Strikes Back. In the 2002 film, Yoda was digitally created, which required heavy use of numerical algorithms.

A key aspect of creating a digital Yoda involves producing believable movement of the character. The movement of Yoda’s body is described using key-frame animation, in which a pose is specified at particular points in time and the computer automatically determines the poses in the intervening frames through interpolation. (We will discuss several interpolation techniques in chapter 8.) Animators have many controls over such movement, with the ability to specify, for instance, velocities and tangents of motion. While animators indicate the movement of Yoda’s body, the computer must determine the resulting flow of his robe.

1.1.1 A Model Robe

Referring to figure 1.2, we see that the robe is represented with triangles and the motion of each vertex of the robe must be determined. Each vertex is modeled as a particle, which in this context is a pointlike object that has mass, position, and velocity, and responds to forces, but has no size.

Figure 1.2. Stages of simulation in the animation of the digitally created Yoda in the fight scene with Count Dooku in Star Wars Episode II. Two layers of Yoda’s clothing, seen in (b) and (c), were computed separately. A process known as collision detection ensured that the inner layer of clothing did not intersect the outer robe and become visible. A simplified model of cloth illumination created the appearance of a real garment, producing the final rendering of the image in (d) [22]. (Courtesy of Lucasfilm Ltd. Star Wars: Episode II - Attack of the Clones™ & © 2002 Lucasfilm Ltd. All rights reserved. Used under authorization. Unauthorized duplication is a violation of applicable law. Digital Work by Industrial Light & Magic.)

The motion of a particle is governed by Newton’s second law, which is expressed mathematically by the equation

where y is a distance function of time t. Note that the equations involve vector-valued functions since our computations are performed in three dimensions. Since a particle has mass (m ≠ 0), equation (1.1) can be rewritten as the second-order ordinary differential equation (ODE)

This ODE is part of an initial value problem since the state of the particle at some initial time is given. In the case of a movie, this is where the scene (which may be several seconds or a fraction of a second in duration) begins.

To keep the shape of the robe, pairs of neighboring particles are attached to each other using a spring force. Hooke’s law states that a spring exerts a force F_s that is proportional to its displacement from its rest length x₀. This is expressed mathematically as

F_s = −k(x − x₀)

where x denotes the current position of the spring and k is the spring constant. For simplicity, we have stated the one-dimensional formulation of Hooke’s law, but to model the Jedi’s robe a three-dimensional version is used.

Many other forces are computed to animate Yoda’s robe, including gravity, wind forces, collision forces, friction, and even completely made-up forces that are invented solely to achieve the motion that the director requests. In the simplest of cases, an analytic solution of the model may exist. In computer animation, however, the forces acting on the particle constantly change and finding an analytic solution for each frame—if even possible—would be impractical. Instead, numerical methods are used to find approximate solutions by simulating the motion of the particles over discrete time steps. There is a large body of literature on the numerical solution of initial value problems for ODEs, and some of the methods will be covered in chapter 11.

B...