Heath scientific computing

SCIENTIFIC COMPUTING
An Introductory Survey

Michael T. Heath
University of Illinois at Urbana-Champaign

ii

Copyright c 1997 by The McGraw-Hill Companies. All rights reserved.

About the Author

Michael T. Heath holds four positions at the University of Illinois at Urbana-Champaign: Professor in the Department of Computer Science, Director of the Computational Science andEngineering Program, Director of the Center for Simulation of Advanced Rockets, and Senior Research Scientist at the National Center for Supercomputing Applications (NCSA). He received a B.A. in Mathematics from the University of Kentucky, an M.S. in Mathematics from the University of Tennessee, and a Ph.D. in Computer Science from Stanford University. Before joining the University of Illinois in 1991, hespent a number of years at Oak Ridge National Laboratory, first as Eugene P. Wigner Postdoctoral Fellow and later as Computer Science Group Leader in the Mathematical Sciences Research Section. His research interests are in numerical analysis—particularly numerical linear algebra and optimization—and in parallel computing. He has has been an editor of the SIAM Journal on Scientific Computing, SIAMReview, and the International Journal of High Performance Computing Applications, as well as several conference proceedings. In 2000, he was named an ACM Fellow.

iii

iv

To Mona

Contents

Preface Notation 1 Scientific Computing 1.1 Introduction . . . . . . . . . . . . . . . . . . . 1.1.1 General Strategy . . . . . . . . . . . . 1.2 Approximations in Scientific Computation . . 1.2.1Sources of Approximation . . . . . . . 1.2.2 Data Error and Computational Error 1.2.3 Truncation Error and Rounding Error 1.2.4 Absolute Error and Relative Error . . 1.2.5 Sensitivity and Conditioning . . . . . 1.2.6 Backward Error Analysis . . . . . . . 1.2.7 Stability and Accuracy . . . . . . . . . 1.3 Computer Arithmetic . . . . . . . . . . . . . 1.3.1 Floating-Point Numbers . . . . . . . . 1.3.2Normalization . . . . . . . . . . . . . . 1.3.3 Properties of Floating-Point Systems . 1.3.4 Rounding . . . . . . . . . . . . . . . . 1.3.5 Machine Precision . . . . . . . . . . . 1.3.6 Subnormals and Gradual Underflow . 1.3.7 Exceptional Values . . . . . . . . . . . 1.3.8 Floating-Point Arithmetic . . . . . . . 1.3.9 Cancellation . . . . . . . . . . . . . . 1.4 Mathematical Software . . . . . . .. . . . . . 1.4.1 Mathematical Software Libraries . . . 1.4.2 Scientific Computing Environments . . 1.4.3 Practical Advice on Software . . . . . v

xiii xvii 1 1 2 2 2 3 4 5 5 6 8 8 8 10 10 11 12 13 13 14 15 20 21 22 23

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .. . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

vi 1.5

CONTENTS Historical Notes and Further Reading . . . . . . . . . . . . . . . . . . . . . 25 37 3737 39 40 41 42 44 49 50 51 52 54 54 56 57 58 58 60 62 63 63 65 66 67 67 69 69 70 83 83 84 85 86 87 89 89 90 90 90 91 95

2 Systems of Linear Equations 2.1 Linear Systems . . . . . . . . . . . . . . . . . . . . 2.1.1 Singularity and Nonsingularity . . . . . . . 2.2 Solving Linear Systems . . . . . . . . . . . . . . . . 2.2.1 Triangular Linear Systems . . . . . . . . . . 2.2.2 Elementary...