Heath - Scientific Computing
Описание файла
PDF-файл из архива "Heath - Scientific Computing", который расположен в категории "". Всё это находится в предмете "численные методы" из 6 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "численные методы и алгоритмы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
SCIENTIFIC COMPUTINGAn Introductory SurveyMichael T. HeathUniversity of Illinoisat Urbana-ChampaigniicCopyright 1997by The McGraw-Hill Companies. All rights reserved.About the AuthorMichael T. Heath holds four positions at the University of Illinois at Urbana-Champaign:Professor in the Department of Computer Science, Director of the Computational Scienceand Engineering 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 fromStanford University. Before joining the University of Illinois in 1991, he spent a number ofyears at Oak Ridge National Laboratory, first as Eugene P. Wigner Postdoctoral Fellow andlater as Computer Science Group Leader in the Mathematical Sciences Research Section.His research interests are in numerical analysis—particularly numerical linear algebra andoptimization—and in parallel computing. He has has been an editor of the SIAM Journalon Scientific Computing, SIAM Review, and the International Journal of High PerformanceComputing Applications, as well as several conference proceedings. In 2000, he was namedan ACM Fellow.iiiivTo MonaContentsPrefacexiiiNotationxvii1 Scientific Computing1.1 Introduction . .
. . . . . . . . . . . . . . . . .1.1.1 General Strategy . . . . . . . . . . . .1.2 Approximations in Scientific Computation . .1.2.1 Sources of Approximation . . . . . . .1.2.2 Data Error and Computational Error1.2.3 Truncation Error and Rounding Error1.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.2 Normalization . . . . . . . . . . . . . .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........................................................................................................................................................................................................................................................................................................................................................................................................................1122234556888101011121313141520212223viCONTENTS1.5Historical Notes and Further Reading . .
. . . . . . . . . . . . . . . . . . .2 Systems of Linear Equations2.1 Linear Systems . . . . . . . . . . . . . . . . . . . .2.1.1 Singularity and Nonsingularity . . . . . . .2.2 Solving Linear Systems . . . . . . . . . . . . . . . .2.2.1 Triangular Linear Systems .
. . . . . . . . .2.2.2 Elementary Elimination Matrices . . . . . .2.2.3 Gaussian Elimination and LU Factorization2.2.4 Pivoting . . . . . . . . . . . . . . . . . . . .2.2.5 Implementation of Gaussian Elimination . .2.2.6 Complexity of Solving Linear Systems . . .2.2.7 Gauss-Jordan Elimination . . . . . . . . . .2.2.8 Solving Modified Problems . .
. . . . . . .2.3 Norms and Condition Numbers . . . . . . . . . . .2.3.1 Vector Norms . . . . . . . . . . . . . . . . .2.3.2 Matrix Norms . . . . . . . . . . . . . . . . .2.3.3 Condition Number of a Matrix . . . . . . .2.4 Accuracy of Solutions . . . . . . . . . . .
. . . . .2.4.1 Residual of a Solution . . . . . . . . . . . .2.4.2 Estimating Accuracy . . . . . . . . . . . . .2.4.3 Improving Accuracy . . . . . . . . . . . . .2.5 Special Types of Linear Systems . . . . . . . . . .2.5.1 Symmetric Positive Definite Systems . . . .2.5.2 Symmetric Indefinite Systems . . . . . . . .2.5.3 Band Systems . . . . .
. . . . . . . . . . . .2.6 Iterative Methods for Linear Systems . . . . . . . .2.7 Software for Linear Systems . . . . . . . . . . . . .2.7.1 LINPACK and LAPACK . . . . . . . . . .2.7.2 Basic Linear Algebra Subprograms . . . . .2.8 Historical Notes and Further Reading . . . . . . .3 Linear Least Squares3.1 Data Fitting . . . . . . . . . .
. . . . . . .3.2 Linear Least Squares . . . . . . . . . . . .3.3 Normal Equations Method . . . . . . . . .3.3.1 Orthogonality . . . . . . . . . . . .3.3.2 Normal Equations Method . . . .3.3.3 Augmented System Method . . . .3.4 Orthogonalization Methods . . . . . . . .3.4.1 Triangular Least Squares Problems3.4.2 Orthogonal Transformations .
. . .3.4.3 QR Factorization . . . . . . . . . .3.4.4 Householder Transformations . . .3.4.5 Givens Rotations . . . . . . . . . .....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................25............................3737373940414244495051525454565758586062636365666767696970............83838485868789899090909195CONTENTS..................................................................981011021031031054 Eigenvalues and Singular Values4.1 Eigenvalues and Eigenvectors .
. . . . . . . . . . . . . . .4.1.1 Nonuniqueness . . . . . . . . . . . . . . . . . . . .4.1.2 Characteristic Polynomial . . . . . . . . . . . . . .4.1.3 Properties of Eigenvalue Problems . . . . . . . . .4.1.4 Similarity Transformations . . . . . . . . . .
. . .4.1.5 Conditioning of Eigenvalue Problems . . . . . . . .4.2 Methods for Computing All Eigenvalues . . . . . . . . . .4.2.1 Characteristic Polynomial . . . . . . . . . . . . . .4.2.2 Jacobi Method for Symmetric Matrices . . . . . .4.2.3 QR Iteration . . . . . . .
. . . . . . . . . . . . . .4.2.4 Preliminary Reduction . . . . . . . . . . . . . . . .4.3 Methods for Computing Selected Eigenvalues . . . . . . .4.3.1 Power Method . . . . . . . . . . . . . . . . . . . .4.3.2 Normalization .
. . . . . . . . . . . . . . . . . . . .4.3.3 Geometric Interpretation . . . . . . . . . . . . . .4.3.4 Shifts . . . . . . . . . . . . . . . . . . . . . . . . .4.3.5 Deflation . . . . . . . . . . . . . . . . . . . . . . .4.3.6 Inverse Iteration . . . . . . . . . . . . . . . . . . .4.3.7 Rayleigh Quotient . . . . . .
. . . . . . . . . . . .4.3.8 Rayleigh Quotient Iteration . . . . . . . . . . . . .4.3.9 Lanczos Method for Symmetric Matrices . . . . . .4.3.10 Spectrum-Slicing Methods for Symmetric Matrices4.4 Generalized Eigenvalue Problems . . . . . . . . . . . . . .4.5 Singular Values . . . . . . . . . . . . . . .
. . . . . . . . .4.5.1 Singular Value Decomposition . . . . . . . . . . . .4.5.2 Applications of SVD . . . . . . . . . . . . . . . . .4.6 Software for Eigenvalues and Singular Values . . . . . . .4.7 Historical Notes and Further Reading . . . . . . . . . . .........................................................................................................................................................................................................................................................................................115115116116117118120121121122124125126126127128128129129130131132133135136136137138140.......1511511521531541541551583.53.63.73.4.6 Gram-Schmidt Orthogonalization3.4.7 Rank Deficiency .
. . . . . . . .3.4.8 Column Pivoting . . . . . . . . .Comparison of Methods . . . . . . . . .Software for Linear Least Squares . . . .Historical Notes and Further Reading .vii........................5 Nonlinear Equations5.1 Nonlinear Equations . . .
. . . . . . . . . . . .5.1.1 Solutions of Nonlinear Equations . . . .5.1.2 Convergence Rates of Iterative Methods5.2 Nonlinear Equations in One Dimension . . . . .5.2.1 Bisection Method . . . . . . . . . . . . .5.2.2 Fixed-Point Iteration . . . . . . . . . .
.5.2.3 Newton’s Method . . . . . . . . . . . . ........................................................................................................................................viiiCONTENTS.............................................................................................................................................................................................................................1601621631641651651661671691691711711736 Optimization6.1 Optimization Problems .
. . . . . . . . . . . . .6.1.1 Local versus Global Optimization . . . .6.1.2 Relationship to Nonlinear Equations . .6.1.3 Accuracy of Solutions . . . . . . . . . .6.2 One-Dimensional Optimization . . . . . . . . .6.2.1 Golden Section Search . . . . . . . . . .6.2.2 Successive Parabolic Interpolation . .
