Numerical linear equations. Direct and iterative procedures.
algorithmsCholesky factorizationconjugate gradient methodconvection-diffusion equationconvergenceconvergence accelerationerror analysisfinite differenceGauss-Seidel iterationsgeneralized minimal residual methodsGivens rotationGMRESGram-Schmidt methodHelmholtz euationHouseholder reflectorsiterative methodsJacobi iterationKrylov subspace methodslinear least-squares problemsLU factorizationmultigrid methodsorthogonalizationPoisson equationpreconditioningQR factorizationsplitting methodstextbook
Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to numerical analysis (65-01) Numerical linear algebra (65Fxx) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55)
Not only its ubiquity in scientific computing but also all the difficulties arising from the seemingly innocent equation \(Ax = b\), especially if \(A\) is an extremely large matrix, make the numerical solution of systems of linear equations an appealing subject of research and teaching. In this respect, the present book is a welcome addition to the few German books on this subject. In Chapter 1, some basic linear algebra concepts are introduced. This includes a brief error analysis of linear systems; an upper bound on the forward error induced by perturbations of the right hand side is given. Chapter 1 also provides insight on how linear systems often arise in practice. Finite difference approximations to the Poisson equation (1d and unit square), to the Helmholtz equation (1d), and to the convection-diffusion equation (1d and unit square) are considered, leading to systems with symmetric positive definite, symmetric indefinite and nonsymmetric coefficient matrices, respectively. Chapter 2 is devoted to the LU decomposition and its relatives. First, forward/backward substitution algorithms for solving lower/upper triangular systems are described. As for many of the algorithms in this book, an analysis of the computational effort is provided in the form of flop counts. It follows the LU decomposition without pivoting, together with examples, existence/uniqueness results and storage considerations. The need for pivoting is motivated by matrices having a singular leading principal submatrix. Special attention is paid to banded matrices. The chapter is concluded by the Cholesky decomposition for symmetric positive definite matrices and the so called Parlett-Reid-Aasen decomposition for symmetric indefinite matrices, while the more common Bunch-Kaufman factorization is mentioned in passing. Chapter 3 is concerned with orthogonalization techniques, motivated by two practical examples for linear least-squares problems. Both, the full and the economic variant of the QR decomposition are introduced, followed by a detailed description of common numerical methods for its computation: Gram-Schmidt, modified Gram-Schmidt, Householder reflectors, Givens and fast Givens rotations. An example for the numerical instability of Gram-Schmidt is given; this is notably the only place in this book where finite-precision arithmetic considerations play a significant role. Chapter 4, the longest chapter in this book, deals with splitting methods. The relationship between convergence and the spectral radius of the iteration matrix is proven and in the following applied to various flavors of splitting methods. First, Jacobi and Gauss-Seidel iterations are considered; it is shown that both iterations converge if the coefficient matrix \(A\) is either diagonal dominant or irreducible and weakly diagonal dominant. The convergence results for successive overrelaxation include a detailed derivation of the optimal relaxation parameter for consistently ordered matrices. Chebyshev polynomials are proposed as an effective means of accelerating the convergence of splitting methods. Finally, the convergence of all discussed methods is illustrated by applying them to the discretized Poisson equation. In Chapter 5, the conjugate gradient (CG) method is considered, along with standard convergence results as well as preconditioning techniques based on splitting methods and incomplete Cholesky decompositions. Generalized minimal residual (GMRES)-like methods are introduced in Chapter 6, including restarted GMRES, preconditioned GMRES based on incomplete LU decompositions and MINRES. Other Krylov subspace methods, such as QMR, BiCG, CGS, BiCGSTAB, and TFQMR, are described in Chapter 7. Each of these methods is applied to the discretized convection-diffusion equation. The book is concluded by a brief chapter on multigrid methods. Each chapter provides 10--17 exercises, ranging from routine drill exercises to interesting extensions (such as the Uzawa method). Many of the described algorithms come with pseudo code, making them rather easy to implement. On the other hand, there are no pointers to available software for solving systems of linear equations. The reader should be wary that handcrafted implementations are virtually always inferior to sophisticated software packages.
- scientific article; zbMATH DE number 438985 (Why is no real title available?)
- scientific article; zbMATH DE number 4215244 (Why is no real title available?)
- Adaptive sequencing of primal, dual, and design steps in simulation based optimization
- Variational space-time methods for the wave equation
- scientific article; zbMATH DE number 1409634 (Why is no real title available?)
- Numerical methods for linear systems of equations. An introduction to modern methods. With MATLAB-implementations of C. Vömel
This page was built for publication: Numerical linear equations. Direct and iterative procedures.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4818638)