# Numerical Methods

## Design, Analysis, and Computer Implementation of Algorithms

## Anne Greenbaum, Tim P. Chartier

- 464 pages
- English
- ePUB (mobile friendly)
- Available on iOS & Android

# Numerical Methods

## Design, Analysis, and Computer Implementation of Algorithms

## Anne Greenbaum, Tim P. Chartier

## About This Book

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

## Frequently asked questions

## Information

## 1

## MATHEMATICAL MODELING

*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.

*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.

*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.

### 1.1 MODELING IN COMPUTER ANIMATION

**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.

**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

**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)

*F*that is proportional to its displacement from its rest length

_{s}*x*

_{0}. This is expressed mathematically as

*F*= â

_{s}*k*(

*x*â

*x*

_{0})

*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.

*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.