Numerical Mathematics

by Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto

• ISBN13: 9780387989594
• ISBN10: 0387989595
• Format: Hardcover
• Copyright: 2000-05-01
• Publisher: Springer Verlag

Summary

Numerical mathematics is the branch of mathematics that proposes, develops, analyzes and applies methods from scientific computing to several fields including analysis, linear algebra, geometry, approximation theory, functional equations, optimization and differential equations. Other disciplines, such as physics, the natural and biological sciences, engineering, and economics and the financial sciences frequently give rise to problems that need scientific computing for their solutions.As such, numerical mathematics is the crossroad of several disciplines of great relevance in modern applied sciences, and can become a crucial tool for their qualitative and quantitative analysis.One of the purposes of this book is to provide the mathematical foundations of numerical methods, to analyze their basic theoretical properties (stability, accuracy, computational complexity) and demonstrate their performances on examples and counterexamples which outline their pros and cons. This is done using the MATLAB software environment which is user-friendly and widely adopted. Within any specific class of problems, the most appropriate scientific computing algorithms are reviewed, their theoretical analyses are carried out and the expected results are verified on a MATLAB computer implementation. Every chapter is supplied with examples, exercises and applications of the discussed theory to the solution of real-life problems.This book is addressed to senior undergraduate and graduate students with particular focus on degree courses in Engineering, Mathematics, Physics and Computer Sciences. The attention which is paid to the applications and the related development of software makes it valuable also for researchers and users of scientific computing in a large variety of professional fields.

Table of Contents

Series Preface	v
Preface	vii
PART I: Getting Started
Foundations of Matrix Analysis	1	(32)
Vector Spaces	1	(2)
Matrices	3	(2)
Operations with Matrices	5	(3)
Inverse of a Matrix	6	(1)
Matrices and Linear Mappings	7	(1)
Operations with Block-Partitioned Matrices	7	(1)
Trace and Determinant of a Matrix	8	(1)
Rank and Kernel of a Matrix	9	(1)
Special Matrices	10	(2)
Block Diagonal Matrices	10	(1)
Trapezoidal and Triangular Matrices	11	(1)
Banded Matrices	11	(1)
Eigenvalues and Eigenvectors	12	(2)
Similarity Transformations	14	(2)
The Singular Value Decomposition (SVD)	16	(1)
Scalar Product and Norms in Vector Spaces	17	(4)
Matrix Norms	21	(6)
Relation Between Norms and the Spectral Radius of a Matrix	25	(1)
Sequences and Series of Matrices	26	(1)
Positive Definite, Diagonally Dominant and M-Matrices	27	(3)
Exercises	30	(3)
Principles of Numerical Mathematics	33	(24)
Well-Posedness and Condition Number of a Problem	33	(4)
Stability of Numerical Methods	37	(4)
Relations Between Stability and Convergence	40	(1)
A priori and a posteriori Analysis	41	(2)
Sources of Error in Computational Models	43	(2)
Machine Representation of Numbers	45	(9)
The Positional System	45	(1)
The Floating-Point Number System	46	(3)
Distribution of Floating-Point Numbers	49	(1)
IEC/IEEE Arithmetic	49	(1)
Rounding of a Real Number in Its Machine Representation	50	(2)
Machine Floating-Point Operations	52	(2)
Exercises	54	(3)
PART II: Numerical Linear Algebra
Direct Methods for the Solution of Linear Systems	57	(66)
Stability Analysis of Linear Systems	58	(7)
The Condition Number of a Matrix	58	(2)
Forward a priori Analysis	60	(3)
Backward a priori Analysis	63	(1)
A posteriori Analysis	64	(1)
Solution of Triangular Systems	65	(3)
Implementation of Substitution Methods	65	(2)
Rounding Error Analysis	67	(1)
Inverse of a Triangular Matrix	67	(1)
The Gaussian Elimination Method (GEM) and LU Factorization	68	(11)
GEM as a Factorization Method	72	(4)
The Effect of Rounding Errors	76	(1)
Implementation of LU Factorization	77	(1)
Compact Forms of Factorization	78	(1)
Other Types of Factorization	79	(6)
LDMT Factorization	79	(1)
Symmetric and Positive Definite Matrices: The Cholesky Factorization	80	(2)
Rectangular Matrices: The QR Factorization	82	(3)
Pivoting	85	(4)
Computing the Inverse of a Matrix	89	(1)
Banded Systems	90	(3)
Tridiagonal Matrices	91	(1)
Implementation Issues	92	(1)
Block Systems	93	(4)
Block LU Factorization	94	(1)
Inverse of a Block-Partitioned Matrix	95	(1)
Block Tridiagonal Systems	95	(2)
Sparse Matrices	97	(6)
The Cuthill-McKee Algorithm	98	(2)
Decomposition into Substructures	100	(3)
Nested Dissection	103	(1)
Accuracy of the Solution Achieved Using GEM	103	(3)
An Approximate Computation of K(A)	106	(3)
Improving the Accuracy of GEM	109	(3)
Scaling	110	(1)
Iterative Refinement	111	(1)
Undetermined Systems	112	(3)
Applications	115	(6)
Nodal Analysis of a Structured Frame	115	(3)
Regularization of a Triangular Grid	118	(3)
Exercises	121	(2)
Iterative Methods for Solving Linear Systems	123	(60)
On the Convergence of Iterative Methods	123	(3)
Linear Iterative Methods	126	(10)
Jacobi, Gauss-Seidel and Relaxation Methods	127	(2)
Convergence Results for Jacobi and Gauss-Seidel Methods	129	(2)
Convergence Results for the Relaxation Method	131	(1)
A priori Forward Analysis	132	(1)
Block Matrices	133	(1)
Symmetric Form of the Gauss-Seidel and SOR Methods	133	(2)
Implementation Issues	135	(1)
Stationary and Nonstationary Iterative Methods	136	(23)
Convergence Analysis of the Richardson Method	137	(2)
Preconditioning Matrices	139	(7)
The Gradient Method	146	(4)
The Conjugate Gradient Method	150	(6)
The Preconditioned Conjugate Gradient Method	156	(2)
The Alternating-Direction Method	158	(1)
Methods Based on Krylov Subspace Iterations	159	(9)
The Arnoldi Method for Linear Systems	162	(3)
The GMRES Method	165	(2)
The Lanczos Method for Symmetric Systems	167	(1)
The Lanczos Method for Unsymmetric Systems	168	(3)
Stopping Criteria	171	(3)
A Stopping Test Based on the Increment	172	(2)
A Stopping Test Based on the Residual	174	(1)
Applications	174	(5)
Analysis of an Electric Network	174	(3)
Finite Difference Analysis of Beam Bending	177	(2)
Exercises	179	(4)
Approximation of Eigenvalues and Eigenvectors	183	(62)
Geometrical Location of the Eigenvalues	183	(3)
Stability and Conditioning Analysis	186	(6)
A priori Estimates	186	(4)
The posteriori Estimates	190	(2)
The Power Method	192	(8)
Approximation of the Eigenvalue of Largest Module	192	(3)
Inverse Iteration	195	(1)
Implementation Issues	196	(4)
The QR Iteration	200	(1)
The Basic QR Iteration	201	(2)
The QR Method for Matrices in Hessenberg Form	203	(12)
Householder and Givens Transformation Matrices	204	(3)
Reducing a Matrix in Hessenberg Form	207	(2)
QR Factorization of a Matrix in Hessenberg Form	209	(1)
The Basic QR Iteration Starting from Upper Hessenberg Form	210	(2)
Implementation of Transformation Matrices	212	(3)
The QR Iteration with Shifting Techniques	215	(6)
The QR Method with Single Shift	215	(3)
The QR Method with Double Shift	218	(3)
Computing the Eigenvectors and the SVD of a Matrix	221	(3)
The Hessenberg Inverse Iteration	221	(1)
Computing the Eigenvectors from the Schur Form of a Matrix	221	(1)
Approximate Computation of the SVD of a Matrix	222	(2)
The Generalized Eigenvalue Problem	224	(3)
Computing the Generalized Real Schur Form	225	(1)
Generalized Real Schur Form of Symmetric-Definite Pencils	226	(1)
Methods for Eigenvalues of Symmetric Matrices	227	(6)
The Jacobi Method	227	(3)
The Method of Sturm Sequences	230	(3)
The Lanczos Method	233	(2)
Applications	235	(5)
Analysis of the Buckling of a Beam	236	(2)
Free Dynamic Vibration of a Bridge	238	(2)
Exercises	240	(5)
PART III: Around Functions and Functionals
Rootfinding for Nonlinear Equations	245	(36)
Conditioning of a Nonlinear Equation	246	(2)
A Geometric Approach to Rootfinding	248	(9)
The Bisection Method	248	(3)
The Methods of Chord, Secant and Regula Falsi and Newton's Method	251	(5)
The Dekker-Brent Method	256	(1)
Fixed-Point Iterations for Nonlinear Equations	257	(4)
Convergence Results for Some Fixed-Point Methods	260	(1)
Zeros of Algebraic Equations	261	(8)
The Horner Method and Deflation	262	(1)
The Newton-Horner Method	263	(4)
The Muller Method	267	(2)
Stopping Criteria	269	(3)
Post-Processing Techniques for Iterative Methods	272	(4)
Aitken's Acceleration	272	(3)
Techniques for Multiple Roots	275	(1)
Applications	276	(3)
Analysis of the State Equation for a Real Gas	276	(1)
Analysis of a Nonlinear Electrical Circuit	277	(2)
Exercises	279	(2)
Nonlinear Systems and Numerical Optimization	281	(46)
Solution of Systems of Nonlinear Equations	282	(12)
Newton's Method and Its Variants	283	(1)
Modified Newton's Methods	284	(4)
Quasi-Newton Methods	288	(1)
Secant-Like Methods	288	(2)
Fixed-Point Methods	290	(4)
Unconstrained Optimization	294	(17)
Direct Search Methods	295	(5)
Descent Methods	300	(2)
Line Search Techniques	302	(2)
Descent Methods for Quadratic Functions	304	(3)
Newton-Like Methods for Function Minimization	307	(1)
Quasi-Newton Methods	308	(1)
Secant-Like Methods	309	(2)
Constrained Optimization	311	(8)
Kuhn-Tucker Necessary Conditions for Nonlinear Programming	313	(2)
The Penalty Method	315	(2)
The Method of Lagrange Multipliers	317	(2)
Applications	319	(6)
Solution of a Nonlinear System Arising from Semiconductor Device Simulation	320	(3)
Nonlinear Regularization of a Discretization Grid	323	(2)
Exercises	325	(2)
Polynomial Interpolation	327	(44)
Polynomial Interpolation	328	(5)
The Interpolation Error	329	(1)
Drawbacks of Polynomial Interpolation on Equally Spaced Nodes and Runge's Counterexample	330	(2)
Stability of Polynomial Interpolation	332	(1)
Newton Form of the Interpolating Polynomial	333	(5)
Some Properties of Newton Divided Differences	335	(2)
The Interpolation Error Using Divided Differences	337	(1)
Piecewise Lagrange Interpolation	338	(3)
Hermite-Birkoff Interpolation	341	(2)
Extension to the Two-Dimensional Case	343	(5)
Polynomial Interpolation	343	(1)
Piecewise Polynomial Interpolation	344	(4)
Approximation by Splines	348	(9)
Interpolatory Cubic Splines	349	(4)
B-Splines	353	(4)
Splines in Parametric Form	357	(5)
Bezier Curves and Parametric B-Splines	359	(3)
Applications	362	(6)
Finite Element Analysis of a Clamped Beam	363	(3)
Geometric Reconstruction Based on Computer Tomographies	366	(2)
Exercises	368	(3)
Numerical Integration	371	(44)
Quadrature Formulae	371	(2)
Interpolatory Quadratures	373	(5)
The Midpoint or Rectangle Formula	373	(2)
The Trapezoidal Formula	375	(2)
The Cavalieri-Simpson Formula	377	(1)
Newton-Cotes Formulae	378	(5)
Composite Newton-Cotes Formulae	383	(3)
Hermite Quadrature Formulae	386	(1)
Richardson Extrapolation	387	(4)
Romberg Integration	389	(2)
Automatic Integration	391	(7)
Non Adaptive Integration Algorithms	392	(2)
Adaptive Integration Algorithms	394	(4)
Singular Integrals	398	(4)
Integrals of Functions with Finite Jump Discontinuities	398	(1)
Integrals of Infinite Functions	398	(3)
Integrals over Unbounded Intervals	401	(1)
Multidimensional Numerical Integration	402	(6)
The Method of Reduction Formula	403	(1)
Two-Dimensional Composite Quadratures	404	(3)
Monte Carlo Methods for Numerical Integration	407	(1)
Applications	408	(4)
Computation of an Ellipsoid Surface	408	(2)
Computation of the Wind Action on a Sailboat Mast	410	(2)
Exercises	412	(3)
PART IV: Transforms, Differentiation and Problem Discretization
Orthogonal Polynomials in Approximation Theory	415	(54)
Approximation of Functions by Generalized Fourier Series	415	(4)
The Chebyshev Polynomials	417	(2)
The Legendre Polynomials	419	(1)
Gaussian Integration and Interpolation	419	(5)
Chebyshev Integration and Interpolation	424	(2)
Legendre Integration and Interpolation	426	(2)
Gaussian Integration over Unbounded Intervals	428	(1)
Programs for the Implementation of Gaussian Quadratures	429	(2)
Approximation of a Function in the Least-Squares Sense	431	(2)
Discrete Least-Squares Approximation	431	(2)
The Polynomial of Best Approximation	433	(2)
Fourier Trigonometric Polynomials	435	(7)
The Gibbs Phenomenon	439	(1)
The Fast Fourier Transform	440	(2)
Approximation of Function Derivatives	442	(8)
Classical Finite Difference Methods	442	(2)
Compact Finite Differences	444	(4)
Pseudo-Spectral Derivative	448	(2)
Transforms and Their Applications	450	(8)
The Fourier Transform	450	(3)
(Physical) Linear Systems and Fourier Transform	453	(2)
The Laplace Transform	455	(2)
The Z-Transform	457	(1)
The Wavelet Transform	458	(5)
The Continuous Wavelet Transform	458	(3)
Discrete and Orthonormal Wavelets	461	(2)
Applications	463	(4)
Numerical Computation of Blackbody Radiation	463	(1)
Numerical Solution of Schrodinger Equation	464	(3)
Exercises	467	(2)
Numerical Solution of Ordinary Differential Equations	469	(62)
The Cauchy Problem	469	(3)
One-Step Numerical Methods	472	(1)
Analysis of One-Step Methods	473	(9)
The Zero-Stability	475	(2)
Convergence Analysis	477	(2)
The Absolute Stability	479	(3)
Difference Equations	482	(5)
Multistep Methods	487	(5)
Adams Methods	490	(2)
BDF Methods	492	(1)
Analysis of Multistep Methods	492	(10)
Consistency	493	(1)
The Root Conditions	494	(1)
Stability and Convergence Analysis for Multistep Methods	495	(4)
Absolute Stability of Multistep Methods	499	(3)
Predictor-Corrector Methods	502	(6)
Runge-Kutta Methods	508	(9)
Derivation of an Explicit RK Method	511	(1)
Stepsize Adaptivity for RK Methods	512	(2)
Implicit RK Methods	514	(2)
Regions of Absolute Stability for RK Methods	516	(1)
Systems of ODEs	517	(2)
Stiff Problems	519	(2)
Applications	521	(6)
Analysis of the Motion of a Frictionless Pendulum	522	(1)
Compliance of Arterial Walls	523	(4)
Exercises	527	(4)
Two-Point Boundary Value Problems	531	(50)
A Model Problem	531	(2)
Finite Difference Approximation	533	(9)
Stability Analysis by the Energy Method	534	(4)
Convergence Analysis	538	(2)
Finite Differences for Two-Point Boundary Value Problems with Variable Coefficients	540	(2)
The Spectral Collocation Method	542	(2)
The Galerkin Method	544	(16)
Integral Formulation of Boundary-Value Problems	544	(2)
A Quick Introduction to Distributions	546	(1)
Formulation and Properties of the Galerkin Method	547	(1)
Analysis of the Galerkin Method	548	(2)
The Finite Element Method	550	(6)
Implementation Issues	556	(3)
Spectral Methods	559	(1)
Advection-Diffusion Equations	560	(12)
Galerkin Finite Element Approximation	561	(2)
The Relationship Between Finite Elements and Finite Differences; the Numerical Viscosity	563	(4)
Stabilized Finite Element Methods	567	(5)
A Quick Glance to the Two-Dimensional Case	572	(3)
Applications	575	(3)
Lubrication of a Slider	575	(1)
Vertical Distribution of Spore Concentration over Wide Regions	576	(2)
Exercises	578	(3)
Parabolic and Hyperbolic Initial Boundary Value Problems	581	(46)
The Heat Equation	581	(3)
Finite Difference Approximation of the Heat Equation	584	(2)
Finite Element Approximation of the Heat Equation	586	(2)
Stability Analysis of the &thetas;-Method	588	(5)
Space-Time Finite Element Methods for the Heat Equation	593	(4)
Hyperbolic Equations: A Scalar Transport Problem	597	(2)
Systems of Linear Hyperbolic Equations	599	(3)
The Wave Equation	601	(1)
The Finite Difference Method for Hyperbolic Equations	602	(3)
Discretization of the Scalar Equation	602	(3)
Analysis of Finite Difference Methods	605	(6)
Consistency	605	(1)
Stability	605	(1)
The CFL Condition	606	(2)
Von Neumann Stability Analysis	608	(3)
Dissipation and Dispersion	611	(7)
Equivalent Equations	614	(4)
Finite Element Approximation of Hyperbolic Equations	618	(5)
Space Discretization with Continuous and Discontinuous Finite Elements	618	(2)
Time Discretization	620	(3)
Applications	623	(2)
Heat Conduction in a Bar	623	(1)
A Hyperbolic Model for Blood Flow Interaction with Arterial Walls	623	(2)
Exercises	625	(2)
References	627	(16)
Index of MATLAB Programs	643	(4)
Index	647