Numerical Analysis in Modern Scientific Computing

by Deuflhard, Peter; Hohmann, Andreas

• ISBN13: 9780387954103
• ISBN10: 0387954104
• eBook ISBN(s): 9780387215846
• Edition: 2nd
• Format: Hardcover
• Copyright: 2003-03-01
• Publisher: Springer Nature
• More Book Details
• Purchase Benefits

Summary

This introductory book directs the reader to a selection of useful elementary numerical algorithms on a reasonably sound theoretical basis, built up within the text. The primary aim is to develop algorithmic thinking -- emphasizing long living computational concepts over fast changing software issues. The guiding principle is to explain modern numerical analysis concepts applicable in complex scientific computing at much simpler model problems. For example, the two adaptive techniques in numerical quadrature elaborated here carry the germs for either extrapolation methods or multigrid methods in differential equations, which are not treated here. The presentation draws on geometrical intuition wherever appropriate, supported by a large number of illustrations. Numerous exercises are included for further practice and improved understanding. This text will appeal to undergraduate and graduate students as well as researchers in mathematics, computer science, science, and engineering. At the same time it is addressed to practical computational scientists who, via self-study, wish to become acquainted with modern concepts of numerical analysis and scientific computing on an elementary level. Sole prerequisite is undergraduate knowledge in Linear Algebra and Calculus.

Author Biography

Peter Deufihard is founder and president of Zuse Institute Berlin (ZIB) and Professor of Numerical Analysis and Scientific Computing at the Free University of Berlin.

Table of Contents

Preface	vii
Outline	xi
Linear Systems	1	(20)
Solution of Triangular Systems	3	(1)
Gaussian Elimination	4	(3)
Pivoting Strategies and Iterative Refinement	7	(7)
Cholesky Decomposition for Symmetric Positive Definite Matrices	14	(7)
Exercises	16	(5)
Error Analysis	21	(36)
Sources of Errors	22	(2)
Condition of Problems	24	(10)
Normwise Condition Analysis	26	(5)
Componentwise Condition Analysis	31	(3)
Stability of Algorithms	34	(10)
Stability Concepts	35	(2)
Forward Analysis	37	(5)
Backward Analysis	42	(2)
Application to Linear Systems	44	(13)
A Zoom into Solvability	44	(2)
Backward Analysis of Gaussian Elimination	46	(3)
Assessment of Approximate Solutions	49	(3)
Exercises	52	(5)
Linear Least-Squares Problems	57	(24)
Least-Squares Method of Gauss	57	(9)
Formulation of the Problem	57	(3)
Normal Equations	60	(2)
Condition	62	(3)
Solution of Normal Equations	65	(1)
Orthogonalization Methods	66	(8)
Givens Rotations	68	(2)
Householder Reflections	70	(4)
Generalized Inverses	74	(7)
Exercises	78	(3)
Nonlinear Systems and Least-Squares Problems	81	(38)
Fixed-Point Iterations	81	(5)
Newton Methods for Nonlinear Systems	86	(6)
Gauss-Newton Method for Nonlinear Least-Squares Problems	92	(7)
Nonlinear Systems Depending on Parameters	99	(20)
Solution Structure	100	(2)
Continuation Methods	102	(11)
Exercises	113	(6)
Linear Eigenvalue Problems	119	(32)
Condition of General Eigenvalue Problems	120	(3)
Power Method	123	(3)
QR-Algorithm for Symmetric Eigenvalue Problems	126	(6)
Singular Value Decomposition	132	(5)
Stochastic Eigenvalue Problems	137	(14)
Exercises	148	(3)
Three-Term Recurrence Relations	151	(28)
Theoretical Background	153	(5)
Orthogonality and Three-Term Recurrence Relations	153	(3)
Homogeneous and Inhomogeneous Recurrence Relations	156	(2)
Numerical Aspects	158	(10)
Condition Number	160	(6)
Idea of the Miller Algorithm	166	(2)
Adjoint Summation	168	(11)
Summation of Dominant Solutions	169	(3)
Summation of Minimal Solutions	172	(4)
Exercises	176	(3)
Interpolation and Approximation	179	(58)
Classical Polynomial Interpolation	180	(17)
Uniqueness and Condition Number	180	(4)
Hermite Interpolation and Divided Differences	184	(8)
Approximation Error	192	(1)
Min-Max Property of Chebyshev Polynomials	193	(4)
Trigonometric Interpolation	197	(7)
Bezier Techniques	204	(14)
Bernstein Polynomials and Bezier Representation	205	(6)
De Casteljau Algorithm	211	(7)
Splines	218	(19)
Spline Spaces and B-Splines	219	(7)
Spline Interpolation	226	(4)
Computation of Cubic Splines	230	(3)
Exercises	233	(4)
Large Symmetric Systems of Equations and Eigenvalue Problems	237	(32)
Classical Iteration Methods	239	(5)
Chebyshev Acceleration	244	(5)
Method of Conjugate Gradients	249	(7)
Preconditioning	256	(5)
Lanczos Methods	261	(8)
Exercises	266	(3)
Definite Integrals	269	(56)
Quadrature Formulas	270	(3)
Newton-Cotes Formulas	273	(6)
Gauss-Christoffel Quadrature	279	(8)
Construction of the Quadrature Formula	280	(5)
Computation of Nodes and Weights	285	(2)
Classical Romberg Quadrature	287	(11)
Asymptotic Expansion of the Trapezoidal Sum	288	(2)
Idea of Extrapolation	290	(5)
Details of the Algorithm	295	(3)
Adaptive Romberg Quadrature	298	(12)
Principle of Adaptivity	299	(2)
Estimation of the Approximation Error	301	(3)
Derivation of the Algorithm	304	(6)
Hard Integration Problems	310	(3)
Adaptive Multigrid Quadrature	313	(12)
Local Error Estimation and Refinement Rules	314	(4)
Global Error Estimation and Details of the Algorithm	318	(3)
Exercises	321	(4)
References	325	(6)
Software	331	(2)
Index	333