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.
Author(s): Holger Wendland
Series: Cambridge Texts in Applied Mathematics
Publisher: Cambridge University Press
Year: 2017
Language: English
Pages: 419
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
