Computational error and complexity in science and engineering (Q1774498)

This monograph for graduates in engineering, computer science and mathematics focuses on error and complexity. Both topics allow to estimate the quality and the cost of the results produced by an algorithm. The nearly 250 pages consist of six chapters with further subdivisions. Chapter 1 introduces into the subject, discusses the distinction between science and engineering and considers capability, limitation, tools, types and models of computation. Moreover, it gives a first impression of computer representable numbers and highlights problem solving. The next two chapters are devoted to the two main topics of the book: Chapter 2 is an exposition of all that is connected with error. Among others it introduces errors, discusses the importance of relative errors, defines computable errors and shows how to compute and to estimate them. Complexity is the core of Chapter 3. Turing machines, Gödel's incompleteness theorem, P- and NP-problems, NP-completeness and probabilistic complexity are some of the keywords appearing here. Chapter 4 deals with errors and approximations in digital computers. Number representation is widely discussed including the importance of the base 2 system, floating point numbers and details of the IEEE 754 standard. Chapter 5 presents several numerical algorithms together with their error and complexity. Topics are interpolation, direct and iterative linear system solvers including singular systems, eigenproblems, linear programming with Karmarkar's algorithm, numerical differentiation and integration. Error and complexity in error-free computation as well as that in parallel and probabilistic computations are described in Chapter 6. Examples are included throughout the text to illustrate the underlying ideas. Sometimes program segments in Matlab are added. References are listed at the end of each chapter.