Numerical Linear Algebra

Description

Numerical Linear Algebra (NLA) is a subarea of Applied Mathematics. It is mainly concerned with the development, implementation and analysis of nu- merical algorithms for solving linear problems. In general, such linear prob- lems arise when discretising a continuous problem by restricting it to a finite- dimensional subspace of the original solution space. Hence, the development and analysis of numerical algorithms is almost always problem-dependent. The more is known about the underlying problem, the better a suitable algorithm can be developed. Contents......Page 6 Preface......Page 10 PART ONE PRELIMINARIES......Page 12 1 Introduction......Page 14 1.1 Examples Leading to Linear Systems......Page 16 1.2 Notation......Page 21 1.3 Landau Symbols and Computational Cost......Page 24 1.4 Facts from Linear Algebra......Page 28 1.5 Singular Value Decomposition......Page 35 1.6 Pseudo-inverse......Page 37 Exercises......Page 40 2.1 Floating Point Arithmetic......Page 41 2.2 Norms for Vectors and Matrices......Page 43 2.3 Conditioning......Page 57 2.4 Stability......Page 65 Exercises......Page 66 PART TWO BASIC METHODS......Page 68 3.1 Back Substitution......Page 70 3.2 Gaussian Elimination......Page 72 3.3 LU Factorisation......Page 76 3.4 Pivoting......Page 82 3.5 Cholesky Factorisation......Page 87 3.6 QR Factorisation......Page 89 3.7 Schur Factorisation......Page 95 3.8 Solving Least-Squares Problems......Page 98 Exercises......Page 111 4.1 Introduction......Page 112 4.2 Banach’s Fixed Point Theorem......Page 113 4.3 The Jacobi and Gauss–Seidel Iterations......Page 117 4.4 Relaxation......Page 127 4.5 Symmetric Methods......Page 136 Exercises......Page 141 5 Calculation of Eigenvalues......Page 143 5.1 Basic Localisation Techniques......Page 144 5.2 The Power Method......Page 152 5.3 Inverse Iteration by von Wielandt and Rayleigh......Page 154 5.4 The Jacobi Method......Page 164 5.5 Householder Reduction to Hessenberg Form......Page 170 5.6 The QR Algorithm......Page 173 5.7 Computing the Singular Value Decomposition......Page 182 Exercises......Page 191 PART THREE ADVANCED METHODS......Page 192 6.1 The Conjugate Gradient Method......Page 194 6.2 GMRES and MINRES......Page 214 6.3 Biorthogonalisation Methods......Page 237 6.4 Multigrid......Page 255 Exercises......Page 269 7 Methods for Large Dense Systems......Page 271 7.1 Multipole Methods......Page 272 7.2 Hierarchical Matrices......Page 293 7.3 Domain Decomposition Methods......Page 318 Exercises......Page 338 8 Preconditioning......Page 340 8.1 Scaling and Preconditioners Based on Splitting......Page 342 8.2 Incomplete Splittings......Page 349 8.3 Polynomial and Approximate Inverse Preconditioners......Page 357 8.4 Preconditioning Krylov Subspace Methods......Page 368 Exercises......Page 379 9.1 Sparse Solutions......Page 381 9.2 Basis Pursuit and Null Space Property......Page 383 9.3 Restricted Isometry Property......Page 389 9.4 Numerical Algorithms......Page 395 Exercises......Page 404 Bibliography......Page 406 Index......Page 414