Anne Greenbaum - Numerical Methods: Design, Analysis, and Computer Implementation of Algorithms

NUMERICAL
METHODS

DESIGN, ANALYSIS, AND COMPUTER
IMPLEMENTATION OF ALGORITHMS

ANNE GREENBAUM
TIMOTHY P. CHARTIER

Copyright 2012 by Princeton University Press
Published by Princeton University Press, 41 William Street, Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press, 6 Oxford Street, Woodstock, Oxfordshire OX20 1TW

press.princeton.edu

Cover image courtesy of the University of Sheffield and Ansys UK.

All Rights Reserved

Library of Congress Cataloging-in-Publication Data

Greenbaum, Anne.
Numerical methods: design, analysis, and computer implementation of algorithms / Anne Greenbaum, Timothy P. Chartier.
p. cm.
ISBN 978-0-691-15122-9 (hbk. : alk. paper)
1. Numerical analysis. I. Chartier, Timothy P., 1969
II. Title.
QA297.G15 2012
518dc23

2011045732

British Library Cataloging-in-Publication Data is available

This book has been composed in Sabon
Printed on acid-free paper.

Typeset by S R Nova Pvt Ltd, Bangalore, India
Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

To Tanya

for her constant love and support,
whether life is well conditioned or unstable.
TC

In this book we have attempted to integrate a reasonably rigorous mathematical treatment of elementary numerical analysis with motivating examples and applications as well as some historical background. It is designed for use as an upper division undergraduate textbook for a course in numerical analysis that could be in a mathematics department, a computer science department, or a related area. It is assumed that the students have had a calculus course, and have seen Taylors theorem, although this is reviewed in the text. It is also assumed that they have had a linear algebra course. Parts of the material require multivariable calculus, although these parts could be omitted. Different aspects of the subjectdesign, analysis, and computer implementation of algorithmscan be stressed depending on the interests, background, and abilities of the students.

We begin with a chapter on mathematical modeling to make the reader aware of where numerical computing problems arise and the many uses of numerical methods. In a numerical analysis course, one might go through all or some of the applications in this chapter or one might just assign it to students to read. Next is a chapter on the basics of MATLAB [] could be substituted, as long as it is a language that allows easy implementation of high-level linear algebra procedures such as solving a system of linear equations or computing a QR decomposition. This frees the student to concentrate on the use and behavior of these procedures rather than the details of their programming, although the major aspects of their implementation are covered in the text in order to explain proper interpretation of the results.

The next chapter is a brief introduction to Monte Carlo methods. Monte Carlo methods usually are not covered in numerical analysis courses, but they should be. They are very widely used computing techniques and demonstrate the close connection between mathematical modeling and numerical methods. The basic statistics needed to understand the results will be useful to students in almost any field that they enter.

The next chapters contain more standard topics in numerical analysissolution of a single nonlinear equation in one unknown, floating-point arithmetic, conditioning of problems and stability of algorithms, solution of linear systems and least squares problems, and polynomial and piecewise polynomial interpolation. Most of this material is standard, but we do include some recent results about the efficacy of polynomial interpolation when the interpolation points are Chebyshev points. We demonstrate the use of a MATLAB software package called chebfun that performs such interpolation, choosing the degree of the interpolating polynomial adaptively to attain a level of accuracy near the machine precision. In the next two chapters, we discuss the application of this approach to numerical differentiation and integration. We have found that the material through polynomial and piecewise polynomial interpolation can typically be covered in a quarter, while a semester course would include numerical differentiation and integration as well and perhaps some material on the numerical solution of ordinary differential equations (ODEs). Appendix A covers background material on linear algebra that is often needed for review.

The remaining chapters of the book are geared towards the numerical solution of differential equations. There is a chapter on the numerical solution of the initial value problem for ordinary differential equations. This includes a short section on solving systems of nonlinear equations, which should be an easy generalization of the material on solving a single nonlinear equation, assuming that the students have had multivariable calculus. The basic Taylors theorem in multidimensions is included in Appendix B. At this point in a year long sequence, we usually cover material from the chapter entitled More Numerical Linear Algebra, including iterative methods for eigenvalue problems and for solving large linear systems. Next come two-point boundary value problems and the numerical solution of partial differential equations (PDEs). Here we include material on the fast Fourier transform (FFT), as it is used in fast solvers for Poissons equation. The FFT is also an integral part of the chebfun package introduced earlier, so we are now able to tell the reader a little more about how the polynomial interpolation procedures used there can be implemented efficiently.

One can arrange a sequence in which each quarter (or semester) depends on the previous one, but it is also fairly easy to arrange independent courses for each topic. This requires a review of MATLAB at the start of each course and usually a review of Taylors theorem with remainder plus a small amount of additional material from previous chapters, but the amount required from, for example, the linear algebra sections in order to cover, say, the ODE sections is small and can usually be fit into such a course.

We have attempted to draw on the popularity of mathematical modeling in a variety of new applications, such as movie animation and information retrieval, to demonstrate the importance of numerical methods, not just in engineering and scientific computing, but in many other areas as well. Through a variety of examples and exercises, we hope to demonstrate some of the many, many uses of numerical methods, while maintaining the emphasis on analysis and understanding of results. Exercises seldom consist of simply computing an answer; in most cases a computational problem is combined with a question about convergence, order of accuracy, or effects of roundoff. Always an underlying theme is, How much confidence do you have in your computed result? We hope that the blend of exciting new applications with old-fashioned analysis will prove a successful one. Software that is needed for some of the exercises can be downloaded from the books web page, via http://press.princeton.edu/titles/9763.html . Also provided on that site are most of the MATLAB codes used to produce the examples throughout the book.