应用数值线性代数 英文影印版2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

应用数值线性代数 英文影印版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 Introduction1

1.1 Basic Notation1

1.2 Standard Problems of Numerical Linear Algebra1

1.3 General Techniques2

1.3.1 Matrix Factorizations3

1.3.2 Perturbation Theory and Condition Numbers4

1.3.3 Effects of Roundoff Error on Algorithms5

1.3.4 Analyzing the Speed of Algorithms5

1.3.5 Engineering Numerical Software6

1.4 Example:Polynomial Evaluation7

1.5 Floating Point Arithmetic9

1.5.1 Further Details12

1.6 Polynomial Evaluation Revisited15

1.7 Vector and Matrix Norms19

1.8 References and Other Topics for Chapter 123

1.9 Questions for Chapter 124

2 Linear Equation Solving31

2.1 Introduction31

2.2 Perturbation Theory32

2.2.1 Relative Perturbation Theory35

2.3 Gaussian Elimination38

2.4 Error Analysis44

2.4.1 The Need for Pivoting45

2.4.2 Formal Error Analysis of Gaussian Elimination46

2.4.3 Estimating Condition Numbers50

2.4.4 Practical Error Bounds54

2.5 Improving the Accuracy of a Solution60

2.5.1 Single Precision Iterative Refinement62

2.5.2 Equilibration62

2.6 Blocking Algorithms for Higher Performance63

2.6.1 Basic Linear Algebra Subroutines(BLAS)66

2.6.2 How to Optimize Matrix Multiplication67

2.6.3 Reorganizing Gaussian Elimination to Use Level 3 BLAS72

2.6.4 More About Parallelism and Other Performance Issues75

2.7 Special Linear Systems76

2.7.1 Real Symmetric Positive Definite Matrices76

2.7.2 Symmetric Indefinite Matrices79

2.7.3 Band Matrices79

2.7.4 General Sparse Matrices83

2.7.5 Dense Matrices Depending on Fewer Than O(n2)Pa-rameters90

2.8 References and Other Topics for Chapter 293

2.9 Questions for Chapter 293

3 Linear Least Squares Problems101

3.1 Introduction101

3.2 Matrix Factorizations That Solve the Linear Least Squares Prob-lem105

3.2.1 Normal Equations106

3.2.2 QR Decomposition107

3.2.3 Singular Value Decomposition109

3.3 Perturbation Theory for the Least Squares Problem117

3.4 Orthogonal Matrices118

3.4.1 Householder Transformations119

3.4.2 Givens Rotations121

3.4.3 Roundoff Error Analysis for Orthogonal Matrices123

3.4.4 Why Orthogonal Matrices?124

3.5 Rank-Deficient Least Squares Problems125

3.5.1 Solving Rank-Deficient Least Squares Problems Using the SVD128

3.5.2 Solving Rank-Deficient Least Squares Problems Using QR with Pivoting130

3.6 Performance Comparison of Methods for Solving Least Squares Problems132

3.7 References and Other Topics for Chapter 3134

3.8 Questions for Chapter 3134

4 Nonsymmetric Eigenvalue Problems139

4.1 Introduction139

4.2 Canonical Forms140

4.2.1 Computing Eigenvectors from the Schur Form148

4.3 Perturbation Theory148

4.4 Algorithms for the Nonsymmetric Eigenproblem153

4.4.1 Power Method154

4.4.2 Inverse Iteration155

4.4.3 Orthogonal Iteration156

4.4.4 QR Iteration159

4.4.5 Making QR Iteration Practical163

4.4.6 Hessenberg Reduction164

4.4.7 Tridiagonal and Bidiagonal Reduction166

4.4.8 QR Iteration with Implicit Shifts167

4.5 Other Nonsymmetric Eigenvalue Problems173

4.5.1 Regular Matrix Pencils and Weierstrass Canonical Form173

4.5.2 Singular Matrix Pencils and the Kronecker Canonical Form180

4.5.3 Nonlinear Eigenvalue Problems183

4.6 Summary184

4.7 References and Other Topics for Chapter 4187

4.8 Questions for Chapter 4187

5 The Symmetric Eigenproblem and Singular Value Decompo-sition195

5.1 Introduction195

5.2 Perturbation Theory197

5.2.1 Relative Perturbation Theory207

5.3 Algorithms for the Symmetric Eigenproblem210

5.3.1 Tridiagonal QR Iteration212

5.3.2 Rayleigh Quotient Iteration214

5.3.3 Divide-and-Conquer216

5.3.4 Bisection and Inverse Iteration228

5.3.5 Jacobi's Method232

5.3.6 Performance Comparison235

5.4 Algorithms for the Singular Value Decomposition237

5.4.1 QR Iteration and Its Variations for the Bidiagonal SVD242

5.4.2 Computing the Bidiagonal SVD to High Relative Accuracy245

5.4.3 Jacobi's Method for the SVD248

5.5 Differential Equations and Eigenvalue Problems254

5.5.1 The Toda Lattice255

5.5.2 The Connection to Partial Differential Equations259

5.6 References and Other Topics for Chapter 5260

5.7 Questions for Chapter 5260

6 Iterative Methods for Linear Systems265

6.1 Introduction265

6.2 On-line Help for Iterative Methods266

6.3 Poisson's Equation267

6.3.1 Poisson's Equation in One Dimension267

6.3.2 Poisson's Equation in Two Dimensions270

6.3.3 Expressing Poisson's Equation with Kronecker Products274

6.4 Summary of Methods for Solving Poisson's Equation277

6.5 Basic Iterative Methods279

6.5.1 Jacobi's Method281

6.5.2 Gauss-Seidel Method282

6.5.3 Successive Overrelaxation283

6.5.4 Convergence of Jacobi's,Gauss-Seidel,and SOR(ω) Methods on the Model Problem285

6.5.5 Detailed Convergence Criteria for Jacobi's,Gauss-Seidel,and SOR(ω)Methods286

6.5.6 Chebyshev Acceleration and Symmetric SOR(SSOR)294

6.6 Krylov Subspace Methods299

6.6.1 Extracting Information about A via Matrix-Vector Mul-tiplication301

6.6.2 Solving Ax=b Using the Krylov Subspace κk305

6.6.3 Conjugate Gradient Method307

6.6.4 Convergence Analysis of the Conjugate Gradient Method312

6.6.5 Preconditioning316

6.6.6 Other Krylov Subspace Algorithms for Solving Ax=b319

6.7 Fast Fourier Transform321

6.7.1 The Discrete Fourier Transform323

6.7.2 Solving the Continuous Model Problem Using Fourier Series324

6.7.3 Convolutions325

6.7.4 Computing the Fast Fourier Transform326

6.8 Block Cyclic Reduction327

6.9 Multigrid331

6.9.1 Overview of Multigrid on the Two-Dimensional Poisson's Equation332

6.9.2 Detailed Description of Multigrid on the One-Dimensional Poisson's Equation337

6.10 Domain Decomposition347

6.10.1 Nonoverlapping Methods348

6.10.2 Overlapping Methods351

6.11 References and Other Topics for Chapter 6356

6.12 Questions for Chapter 6356

7 Iterative Methods for Eigenvalue Problems361

7.1 Introduction361

7.2 The Rayleigh-Ritz Method362

7.3 The Lanczos Algorithm in Exact Arithmetic366

7.4 The Lanczos Algorithm in Floating Point Arithmetic375

7.5 The Lanczos Algorithm with Selective Orthogonalization382

7.6 Beyond Selective Orthogonalization383

7.7 Iterative Algorithms for the Nonsymmetric Eigenproblem384

7.8 References and Other Topics for Chapter 7386

7.9 Questions for Chapter 7386

Bibliography389

Index409