# Algorithms

Numerical Analysis: Mathematics of Scientific Computing by David R. Kincaid and Ward Cheney (Brooks Cole) Some of the topics discussed include: Mathematical preliminaries, computer arithmetic, solving systems of linear equations, approximating functions, and numerical solution of partial differential equations. This highly successful and scholarly book introduces students with diverse backgrounds to the various types of mathematical analysis that are commonly needed in scientific computing. The subject of numerical analysis is treated from a mathematical point of view, offering a complete analysis of methods for scientific computing with careful proofs and scientific background.

Numerical analysis involves the study, development, and analysis of algorithms for obtaining numerical solutions to various mathematical problems. Frequently, numer­ical analysis is called the mathematics of scientific computing.

The algorithms that we study invariably are destined for use on high‑speed com­puters, and therefore another crucial step intervenes before the solution to a problem can be obtained: a computer program or code must be written to communicate the algorithm to the computer. This is, of course, a nontrivial matter, but there are so many choices of computers and computer languages that it is a topic best left out of the science of numerical analysis per se.

There are certainly many other purposes to which computers can be put besides the numerical solution of mathematical problems: providing basic communications, keeping large data bases, playing games, "net surfing," writing novels, accounting, and so on. Solving mathematical problems numerically on the computer is scientific computing. The development of the associated algorithms (procedures) and the study of their behavior are the mathematics of scientific computing.

Often the development of an algorithm is stimulated by a constructive proof in mathematics. In classical analysis, nonconstructive methods are frequently used, but generally they do not lead to algorithms. For example, existence and uniqueness theorems might be established by assuming that they are not true and then following the trail of a logical argument until arriving at a contradiction. Not every constructive proof will lead to a successful algorithm, however. A difficulty that may arise is that an analytical solution to a given problem may be several steps away from a numerical solution. Or it might be completely impractical because of slow convergence or the need for lengthy computation.

As an example of the gap between an existence theorem and a numerical solution of a problem, consider the ubiquitous matrix equation Ax = b. We know that it has a unique solution whenever A is nonsingular. But this fact may be of little solace when we are faced with a large linear system containing empirical data and we wish to compute an approximate numerical solution.

This book has evolved over many years from lecture notes that accompany certain upper‑division and graduate courses in mathematics and computer sciences at The University of Texas at Austin. These courses introduce students to the algorithms and methods that are commonly needed in scientific computing. The mathematical underpinnings of these methods are emphasized as much as their algorithmic aspects. The students have been diverse: mathematics, engineering, science, and computer science undergraduates, as well as graduate students from various disciplines. Portions of the book also have been used to lay the groundwork in several graduate courses devoted to special topics in numerical analysis, such as the numerical solution of differential equations, numerical linear algebra, and approximation theory. Our approach has always been to treat the subject from a mathematical point of view, with attention given to its rich offering of theorems, proofs, and interesting ideas. From these arise many computational procedures and intriguing questions of computer science. Of course, our motivation comes from the practical world of scientific computing, which dictates the choice of topics and the manner of treating each. For example, with some topics it is more instructive to discuss the theoretical foundations of the subject and not attempt to analyze algorithms in detail. In other cases, the reverse is true, and the students learn much from programming simple algorithms themselves and experimenting with them‑although we offer a blanket admonition to use well‑tested software, such as from program libraries, on problems that arise from applications.

There is some overlap between this book and our more elementary text, Numerical Mathematics and Computing, Fourth Edition (Brooks/Cole). That book is addressed to students having more modest mathematical preparation (and sometimes less enthusiasm for the theoretical side of the subject). In that text, there is a different menu of topics, and no topic is pursued to any great depth. The present book, on the other hand, is intended for a course that offers a more scholarly treatment of the subject; many topics are dealt with at length. Occasionally we broach topics that heretofore have not found their way into standard textbooks at this level. In this category are the multigrid method, procedures for multivariate interpolation, homotopy (or continuation) methods, delay differential equations, and optimization.

The algorithms in the book are presented in a pseudocode that contains additional details beyond the mathematical formulas.