Applied Numerical Linear Algebra ——J.D Demmel APPL

文件名称: Applied Numerical Linear Algebra ——J.D Demmel

所属分类: C

开发工具:

文件大小: 2mb

下载次数: 0

上传时间: 2010-11-18

提供者: thinks_********

下载 (2mb)

不能下载？报告错误

详细说明： APPLIED NUMERICAL LINEAR ALGEBRA James W. Demmel University of California Berkeley, California Society for Industrial and Applied Mathematics Philadelphia Contents Preface ix 1 Introduction 1 1.1 Basic Notation 1 1.2 Standard Problems of Numerical Linear Algebra 1 1.3 General Techniques 2 1.3.1 Matrix Factorizations 3 1.3.2 Perturbation Theory and Condition Numbers 4 1.3.3 Effects of Roundoff Error on Algorithms 5 1.3.4 Analyzing the Speed of Algorithms 5 1.3.5 Engineering Numerical Software 6 1.4 Example: Polynomial Evaluation 7 1.5 Floating Point Arithmetic 9 1.5.1 Further Details 12 1.6 Polynomial Evaluation Revisited 15 1.7 Vector and Matrix Norms 19 1.8 References and Other Topics for Chapter 1 23 1.9 Questions for Chapter 1 24 2 Linear Equation Solving 31 2.1 Introduction 31 2.2 Perturbation Theory 32 2.2.1 Relative Perturbation Theory 35 2.3 Gaussian Elimination 38 2.4 Error Analysis 44 2.4.1 The Need for Pivoting 45 2.4.2 Formal Error Analysis of Gaussian Elimination 46 2.4.3 Estimating Condition Numbers 50 2.4.4 Practical Error Bounds 54 2.5 Improving the Accuracy of a Solution 60 2.5.1 Single Precision Iterative Refinement 62 2.5.2 Equilibration 62 2.6 Blocking Algorithms for Higher Performance 63 2.6.1 Basic Linear Algebra Subroutines (BLAS) 66 2.6.2 How to Optimize Matrix Multiplication 67 2.6.3 Reorganizing Gaussian Elimination to Use Level 3 BLAS 72 2.6.4 More About Parallelism and Other Performance Issues . 75 vi Contents 2.7 2.8 2.9 Special Linear Systems 2.7.1 Real Symmetric Positive Definite Matrices 2.7.2 Symmetric Indefinite Matrices 2.7.3 Band Matrices 2.7.4 General Sparse Matrices 2.7.5 Dense Matrices Depending on Fewer Than O(n2) Pa- rameters References and Other Topics for Chapter 2 Questions for Chapter 2 76 76 79 79 83 90 93 93 3 Linear Least Squares Problems 101 3.1 Introduction 101 3.2 Matrix Factorizations That Solve the Linear Least Squares Prob- lem 105 3.2.1 Normal Equations 106 3.2.2 QR Decomposition 107 3.2.3 Singular Value Decomposition 109 3.3 Perturbation Theory for the Least Squares Problem 117 3.4 Orthogonal Matrices 118 3.4.1 Householder Transformations 119 3.4.2 Givens Rotations 121 3.4.3 Roundoff Error Analysis for Orthogonal Matrices . . . . 123 3.4.4 Why Orthogonal Matrices? 124 3.5 Rank-Deficient Least Squares Problems 125 3.5.1 Solving Rank-Deficient Least Squares Problems Using the SVD 128 3.5.2 Solving Rank-Deficient Least Squares Problems Using QR with Pivoting 130 3.6 Performance Comparison of Methods for Solving Least Squares Problems 132 3.7 References and Other Topics for Chapter 3 134 3.8 Questions for Chapter 3 134 4 Nonsymmetric Eigenvalue Problems 4.1 Introduction 4.2 Canonical Forms 4.2.1 Computing Eigenvectors from the Schur Form 4.3 Perturbation Theory 4.4 Algorithms for the Nonsymmetric Eigenproblem 4.4.1 Power Method 4.4.2 Inverse Iteration 4.4.3 Orthogonal Iteration 4.4.4 QR Iteration 4.4.5 Making QR Iteration Practical 4.4.6 Hessenberg Reduction 139 139 140 148 148 153 154 155 156 159 163 164 Contents 4.5 4.6 4.7 4.8 vii 4.4.7 4.4.8 Other 4.5.1 4.5.2 Tridiagonal and Bidiagonal Reduction 166 QR Iteration with Implicit Shifts 167 Nonsymmetric Eigenvalue Problems 173 Regular Matrix Pencils and Weierstrass Canonical Form 173 Singular Matrix Pencils and the Kronecker Canonical Form 180 4.5.3 Nonlinear Eigenvalue Problems 183 Summary 184 References and Other Topics for Chapter 4 187 Questions for Chapter 4 187 5 The Symmetric Eigenproblem and Singular Value Decompo- sition 195 5.1 Introduction 195 5.2 Perturbation Theory 197 5.2.1 Relative Perturbation Theory 207 5.3 Algorithms for the Symmetric Eigenproblem 210 5.3.1 Tridiagonal QR Iteration 212 5.3.2 Rayleigh Quotient Iteration 214 5.3.3 Divide-and-Conquer 216 5.3.4 Bisection and Inverse Iteration 228 5.3.5 Jacobi's Method 232 5.3.6 Performance Comparison 235 5.4 Algorithms for the Singular Value Decomposition 237 5.4.1 QR Iteration and Its Variations for the Bidiagonal SVD 242 5.4.2 Computing the Bidiagonal SVD to High Relative Accuracy245 5.4.3 Jacobi's Method for the SVD 248 5.5 Differential Equations and Eigenvalue Problems 254 5.5.1 The Toda Lattice 255 5.5.2 The Connection to Partial Differential Equations . . . . 259 5.6 References and Other Topics for Chapter 5 260 5.7 Questions for Chapter 5 260 6 Iterative Methods for Linear Systems 265 6.1 Introduction 265 6.2 On-line Help for Iterative Methods 266 6.3 Poisson's Equation 267 6.3.1 Poisson's Equation in One Dimension 267 6.3.2 Poisson's Equation in Two Dimensions 270 6.3.3 Expressing Poisson's Equation with Kronecker Products 274 6.4 Summary of Methods for Solving Poisson's Equation 277 6.5 Basic Iterative Methods 279 6.5.1 Jacobi's Method 281 6.5.2 Gauss-Seidel Method 282 6.5.3 Successive Overrelaxation 283 viii Contents 6.5.4 Convergence of Jacobi's, Gauss-Seidel, and SOR(u;) Methods on the Model Problem 6.5.5 Detailed Convergence Criteria for Jacobi's, Gauss-Seidel, and SOR(o;) Methods 6.5.6 Chebyshev Acceleration and Symmetric SOR (SSOR) . 6.6 Krylov Subspace Methods 6.6.1 Extracting Information about A via Matrix-Vector Mul- tiplication 6.6.2 Solving Ax = b Using the Krylov Subspace /C^ 6.6.3 Conjugate Gradient Method 6.6.4 Convergence Analysis of the Conjugate Gradient Method 6.6.5 Preconditioning 6.6.6 Other Krylov Subspace Algorithms for Solving Ax = b . 6.7 Fast Fourier Transform 6.7.1 The Discrete Fourier Transform 6.7.2 Solving the Continuous Model Problem Using Fourier Series 6.7.3 Convolutions 6.7.4 Computing the Fast Fourier Transform 6.8 Block Cyclic Reduction 6.9 Multigrid 6.9.1 Overview of Multigrid on the Two-Dimensional Poisson's Equation 6.9.2 Detailed Description of Multigrid on the One-Dimensional Poisson's Equation 6.10 Domain Decomposition 6.10.1 Nonoverlapping Methods 6.10.2 Overlapping Methods 6.11 References and Other Topics for Chapter 6 6.12 Questions for Chapter 6 285 286 294 299 301 305 307 312 316 319 321 323 324 325 326 327 331 332 337 347 348 351 356 356 7 Iterative Methods for Eigenvalue Problems 361 7.1 Introduction ^361 7.2 The Rayleigh-Ritz Method 362 7.3 The Lanczos Algorithm in Exact Arithmetic 366 7.4 The Lanczos Algorithm in Floating Point Arithmetic 375 7.5 The Lanczos Algorithm with Selective Orthogonalization . . . . 382 7.6 Beyond Selective Orthogonalization 383 7.7 Iterative Algorithms for the Nonsymmetric Eigenproblem . . . 384 7.8 References and Other Topics for Chapter 7 386 7.9 Questions for Chapter 7 386 Bibliography 389 Index 409 ...展开收缩

(系统自动生成,下载前可以参看下载内容)