Numerical Computation 2: Methods, Software, and Analysis

ISBN-13: 9783540620570 / Angielski / Miękka / 1997 / 496 str.

Christoph W. Ueberhuber

Opis

Part of a two-volume introduction on numerical computation, which emphasises software aspects, this book is intended for courses on numerical analysis. It also includes a bibliography.

Recenzje

"The two volumes can be highly recommended for newcomers in the area as well as for people working for a long time in or with computer numerics." 

EUROSIM - Simulation News Europe

 

"... This book is highly recommended to students, scientists, anad engineers interested in the numerical solution of mathematical problems. It is very useful as a handbook for both newcomers and experts. Every science/engineering/mathematics/computer science library should have a copy of this book."

Matti Vuorinen, Mathematical Reviews 2003

Spis treści

10 Best Approximation.- 10.1 Mathematical Foundations.- 10.2 Continuous Least Squares Approximation.- 10.2.1 Mathematical Foundations.- 10.2.2 Best Approximation with Orthogonality.- 10.2.3 The Normal Equations.- 10.2.4 The Approximation Error.- 10.2.5 Orthogonal Polynomials.- 10.3 Discrete Least Squares Approximation.- 10.3.1 Linear Least Squares Approximation.- 10.3.2 Nonlinear Least Squares Approximation.- 10.4 Uniform Best Approximation.- 10.4.1 Uniformly Best Approximating Polynomials.- 10.5 Approximation Algorithms.- 10.6 Approximation Software for Special Functions.- 10.6.1 Elementary Functions.- 10.6.2 Funpack.- 10.6.3 IMSL Libraries.- 10.6.4 NAG Libraries.- 11 The Fourier Transform.- 11.1 Background.- 11.2 Mathematical Foundations.- 11.2.1 Trigonometric Approximation.- 11.2.2 The Spectrum.- 11.3 Trigonometric Interpolation.- 11.4 Convolution.- 11.5 Manipulation of the Signal Spectrum.- 11.5.1 Case Study: The Filtering of a Noisy Signal.- 11.6 DFT Algorithms.- 11.6.1 The Fast Fourier Transform (FFT).- 11.6.2 FFT of Real Functions.- 11.6.3 FFT in Two or More Dimensions.- 11.7 FFT Software Packages.- 11.7.1 FFTPACK.- 11.7.2 VFFTPK.- 11.8 FFT Routines in Software Libraries.- 11.8.1 IMSL Software Libraries.- 11.8.2 NAG Software Libraries.- 11.9 Other FFT Programs.- 11.9.1 TOMS Collection.- 11.9.2 Various NETLIB Software.- 12 Numerical Integration.- 12.1 Fundamentals of Integration.- 12.1.1 Integration Regions.- 12.1.2 Weight Functions.- 12.1.3 Integration Methods.- 12.1.4 Sensitivity of Integration Problems.- 12.1.5 Inherent Uncertainty of Numerical Integration.- 12.2 Preprocessing of Integration Problems.- 12.2.1 Transformation of Integrals.- 12.2.2 Decomposition of Integration Regions.- 12.2.3 Iteration of Integrals.- 12.3 Univariate Integration Formulas.- 12.3.1 Construction of Integration Formulas.- 12.3.2 Simple Interpolatory Quadrature Formulas.- 12.3.3 Compound Quadrature Formulas.- 12.3.4 Romberg Formulas.- 12.3.5 Nonlinear Extrapolation.- 12.3.6 Special Methods.- 12.4 Multivariate Integration Formulas.- 12.4.1 Construction Principles.- 12.4.2 Polynomial Integration Formulas.- 12.4.3 Number-Theoretic Integration Formulas.- 12.4.4 Monte Carlo Techniques.- 12..4.5 Lattice Rules.- 12.4.6 Special Methods.- 12.5 Integration Algorithms.- 12.5.1 Error Estimation.- 12.5.2 Sampling Strategy.- 12.5.3 Adaptive Integration Algorithms and Programs.- 12.5.4 Software for Univariate Problems: Globally Adaptive Integration Programs.- 12.5.5 Software for Multivariate Problems: Globally Adaptive Integration Programs.- 12.5.6 Reliability Enhancement.- 12.5.7 Multiple Integrands.- 13 Systems of Linear Equations.- 13.1 Design Stage.- 13.1.1 Type of Problem.- 13.1.2 Structural Properties of System Matrices.- 13.1.3 Types of Solutions.- 13.1.4 Algorithms and Software Requirements.- 13.2 Realization Stage.- 13.3 Verification Stage.- 13.4 Mathematical Foundations.- 13.4.1 Linear Spaces.- 13.4.2 Vector Norms.- 13.4.3 Orthogonality.- 13.4.4 Linear Functions.- 13.4.5 Matrices.- 13.4.6 Inverse of a Matrix.- 13.4.7 Eigenvalues of a Matrix.- 13.4.8 Matrix Norms.- 13.4.9 Determinant of a Matrix.- 13.5 Special Properties of Matrices.- 13.5.1 Symmetric and Hermitian Matrices.- 13.5.2 Orthogonal and Unitary Matrices.- 13.5.3 Positive Definite Matrices.- 13.6 Special Types of Matrices.- 13.6.1 Diagonal Matrices.- 13.6.2 Triangular Matrices.- 13.6.3 Block Matrices.- 13.6.4 Hessenberg Matrices.- 13.6.5 Tridiagonal Matrices.- 13.6.6 Band Matrices.- 13.6.7 Permutation Matrices.- 13.7 Singular Value Decomposition.- 13.7.1 Geometry of Linear Transformations.- 13.7.2 Structure of Linear Transformations.- 13.7.3 Generalized Inverse Mappings.- 13.7.4 General Solution of Linear Systems.- 13.7.5 The Solution of Homogeneous Systems.- 13.7.6 Linear Data Fitting.- 13.8 The Condition of Linear Systems.- 13.8.1 Condition of Regular Systems.- 13.8.2 Effects of a Perturbed Right-Hand Side.- 13.8.3 Effects of a Perturbed Matrix.- 13.9 Condition of Least Squares Problems.- 13.10 Condition Analysis Using the SVD.- 13.10.1 Case Study: Condition Analysis.- 13.11 Direct Methods.- 13.11.1 The Elimination Principle.- 13.11.2 LU Factorization.- 13.11.3 Pivot Strategies.- 13.12 Special Types of Linear Systems.- 13.12.1 Symmetric, Positive Definite Matrices.- 13.12.2 Band Matrices.- 13.13 Assessment of the Accuracy Achieved.- 13.13.1 Condition Number Estimates.- 13.13.2 Backward Error Analysis.- 13.13.3 Iterative Refinement.- 13.13.4 Experimental Condition Analysis.- 13.14 Methods for Least Squares Problems.- 13.14.1 Normal Equations.- 13.14.2 QR Method.- 13.15 LAPACK—The Fundamental Linear Algebra Package.- 13.15.1 The History of LAPACK.- 13.15.2 LAPACK and BLAS.- 13.15.3 Block Algorithms.- 13.15.4 Structure of LAPACK.- 13.16 LAPACK Black Box Programs.- 13.16.1 Linear Equations.- 13.16.2 Linear Least Squares Problems.- 13.17 LAPACK Computational Routines.- 13.17.1 Error Bounds.- 13.17.2 Orthogonal Factorizations.- 13.17.3 Singular Value Decomposition (SVD).- 13.18 LAPACK Documentation.- 13.18.1 Parameters.- 13.18.2 Error Handling.- 13.19 LAPACK Storage Schemes.- 13.19.1 Conventional Storage.- 13.19.2 Packed Storage.- 13.19.3 Storage of Band Matrices.- 13.19.4 Tridiagonal and Bidiagonal Matrices.- 13.19.5 Orthogonal or Unitary Matrices.- 13.20 Block Size for Block Algorithms.- 13.21 LAPACK Variants and Extensions.- 14 Nonlinear Equations.- 14.1 Iterative Methods.- 14.1.1 Fixed-Point Iteration.- 14.1.2 Convergence of Iterative Methods.- 14.1.3 Rate of Convergence.- 14.1.4 Determination of the Initial Values.- 14.1.5 The Termination of an Iteration.- 14.2 Nonlinear Scalar Equations.- 14.2.1 The Multiplicity of a Zero.- 14.2.2 The Condition of a Nonlinear Equation.- 14.2.3 The Bisection Method.- 14.2.4 Newton’s Method.- 14.2.5 The Secant Method.- 14.2.6 Muller’s Method.- 14.2.7 Efficiency Assessment.- 14.2.8 The Acceleration of Convergence.- 14.2.9 Polyalgorithms.- 14.2.10 Roots of Polynomials.- 14.3 Systems of Nonlinear Equations.- 14.3.1 Generalized Linear Methods.- 14.3.2 Newton’s Method.- 14.3.3 The Secant Method.- 14.3.4 Modification Methods.- 14.3.5 Large Nonlinear Systems.- 14.4 Nonlinear Data Fitting.- 14.4.1 Minimization Methods.- 14.4.2 The Levenberg-Marquardt Method.- 14.4.3 The Powell Method.- 14.4.4 Special Functions.- 15 Eigenvalues and Eigenvectors.- 15.1 Mathematical Foundations.- 15.1.1 The Characteristic Polynomial.- 15.1.2 Similarity.- 15.1.3 Eigenvectors.- 15.1.4 Unitary Similarity.- 15.1.5 Similarity to (Quasi) Diagonal Matrices.- 15.1.6 Bounds for the Eigenvalues.- 15.2 Condition of Eigenvalue Problems.- 15.3 The Power Method.- 15.3.1 The Inverse Power Method.- 15.3.2 The Inverse Power Method with Spectral Shifts.- 15.4 The QR Algorithm.- 15.4.1 The QR Algorithm with Spectral Shifts.- 15.4.2 Efficiency Improvement of the QR Algorithm.- 15.5 The Diagonal Reduction.- 15.5.1 ‘The Jacobi Method.- 15.6 The Hessenberg Reduction.- 15.6.1 The Givens Algorithm.- 15.6.2 The Householder Algorithm.- 15.7 LAPACK Programs.- 15.7.1 Symmetric Eigenproblems.- 15.7.2 Nonsymmetric Eigenproblems.- 15.7.3 Singular Value Decomposition (SVD).- 15.7.4 Generalized, Symmetric Eigenproblems.- 15.7.5 Generalized, Nonsymmetric Eigenproblems.- 16 Large, Sparse Linear Systems.- 16.1 Storage Schemes for Iterative Methods.- 16.1.1 Coordinate (COO) Format.- 16.1.2 Compressed Row Storage (CRS) Format.- 16.1.3 Modified CRS (MRS) Format.- 16.1.4 Compressed Column Storage (CCS Format).- 16.1.5 Block Compressed Row Storage (BCRS) Format.- 16.1.6 Compressed Diagonal Storage (CDS) Format.- 16.1.7 LAPACK (BND) Format for Band Matrices.- 16.1.8 Jagged Diagonal Storage (JDS) Format.- 16.1.9 Skyline Storage (SKS) Format.- 16.2 Storage Schemes for Symmetric Matrices.- 16.3 Storage Schemes for Direct Methods.- 16.3.1 Band Format.- 16.3.2 General Storage Schemes.- 16.4 Comparison of Storage Schemes.- 16.5 Direct Methods.- 16.5.1 Gaussian Elimination for Sparse Linear Systems.- 16.5.2 Band Matrices.- 16.5.3 Poisson Matrices.- 16.5.4 Matrices with General Sparsity Structure.- 16.6 Iterative Methods.- 16.7 Minimization Methods.- 16.7.1 The Gauss-Seidel Method.- 16.7.2 Gradient Methods.- 16.7.3 The Jacobi Method.- 16.7.4 The Conjugate Gradient Method.- 16.7.5 The Krylov Method.- 16.8 Stationary Iterative Methods.- 16.8.1 The Jacobi Method.- 16.8.2 The Gauss-Seidel Method.- 16.8.3 The Successive Over-Relaxation (SOR) Method.- 16.8.4 The Symmetric SOR (SSOR) Method.- 16.9 Non-Stationary Iterative Methods.- 16.9.1 The Conjugate Gradient Method (CG Method).- 16.9.2 The CG Method on the Normal Equations.- 16.9.3 The MINRES and the SYMMLQ Method.- 16.9.4 The Generalized Minimal Residual (GMRES) Method.- 16.9.5 The Bi-Conjugate Gradient (BiCG) Method.- 16.9.6 The Quasi-Minimal Residual (QMR) Method.- 16.9.7 The Squared CG (CGS) Method.- 16.9.8 The Stabilized BiCG (BiCGSTAB) Method.- 16.9.9 Chebyshev Iteration.- 16.10 Preconditioning.- 16.10.1 Jacobi Preconditioning.- 16.10.2 SSOR Preconditioning.- 16.10.3 Incomplete Factorization.- 16.10.4 Incomplete Block Factorization.- 16.10.5 Incomplete LQ Factorization.- 16.10.6 Polynomial Preconditioning.- 16.11 Matrix-Vector Products.- 16.11.1 Matrix-Vector Product Using the CRS Format.- 16.11.2 Matrix-Vector Product Using the CDS Format.- 16.12 Parallelism.- 16.13 Selecting an Iterative Method.- 16.13.1 Properties of Iterative Methods.- 16.13.2 Case Study: Comparison of Iterative Methods.- 16.14 Software for Sparse Systems.- 16.15 Basic Software.- 16.15.1 The Harwell-Boeing Collection.- 16.15.2 Sparse-Blas.- 16.15.3 Sparskit.- 16.16 Dedicated Software Packages.- 16.16.1 Itpack.- 16.16.2 Templates.- 16.16.3 Slap.- 16.16.4 Y12M.- 16.16.5 Umfpack.- 16.16.6 Pim.- 16.17 Routines from Software Libraries.- 16.17.1 IMSL Software Libraries.- 16.17.2 NAG Software Libraries.- 16.17.3 Harwell Library.- 17 Random Numbers.- 17.1 Random Number Generators.- 17.2 The Generation of Uniform Random Numbers.- 17.2.1 Congruential Generators.- 17.2.2 Uniform Random Vectors.- 17.2.3 Improving Random Number Generators.- 17.3 The Generation of Non-uniform Random Numbers.- 17.3.1 The Inversion Method for Univariate Distributions.- 17.3.2 The Rejection Method.- 17.3.3 The Composition Method.- 17.4 Testing Random Number Generators.- 17.5 Software for Generating Random Numbers.- 17.5.1 Programming Languages.- 17.5.2 IMSL Library.- 17.5.3 NAG Library.- Glossary of Notation.- Author Index.