A Theoretical Introduction to Numerical Analysis

by Ryaben'kii; Victor S.

• ISBN13: 9781584886075
• ISBN10: 1584886072
• eBook ISBN(s): 9781000738285
• Additional ISBN(s): 9781420011166
• Edition: 1st
• Format: Hardcover
• Copyright: 2006-11-02
• Publisher: Chapman & Hall/
• More Book Details

Summary

A Theoretical Introduction to Numerical Analysis presents the general methodology and principles of numerical analysis, illustrating these concepts using numerical methods from real analysis, linear algebra, and differential equations. The book focuses on how to efficiently represent mathematical models for computer-based study.An accessible yet rigorous mathematical introduction, this book provides a pedagogical account of the fundamentals of numerical analysis. The authors thoroughly explain basic concepts, such as discretization, error, efficiency, complexity, numerical stability, consistency, and convergence. The text also addresses more complex topics like intrinsic error limits and the effect of smoothness on the accuracy of approximation in the context of Chebyshev interpolation, Gaussian quadratures, and spectral methods for differential equations. Another advanced subject discussed, the method of difference potentials, employs discrete analogues of Calderon's potentials and boundary projection operators. The authors often delineate various techniques through exercises that require further theoretical study or computer implementation.By lucidly presenting the central mathematical concepts of numerical methods, A Theoretical Introduction to Numerical Analysis provides a foundational link to more specialized computational work in fluid dynamics, acoustics, and electromagnetism.

Table of Contents

Preface	xi
Acknowledgments	xiii
Introduction	1	(20)
Discretization	4	(2)
Exercises	5	(1)
Conditioning	6	(1)
Exercises	7	(1)
Error	7	(5)
Unavoidable Error	8	(2)
Error of the Method	10	(1)
Round-off Error	10	(1)
Exercises	11	(1)
On Methods of Computation	12	(9)
Accuracy	13	(1)
Operation Count	14	(1)
Stability	14	(1)
Loss of Significant Digits	15	(3)
Convergence	18	(1)
General Comments	18	(1)
Exercises	19	(2)
I. Interpolation of Functions. Quadratures	21	(94)
Algebraic Interpolation	25	(36)
Existence and Uniqueness of Interpolating Polynomial	25	(10)
The Lagrange Form of Interpolating Polynomial	25	(1)
The Newton Form of Interpolating Polynomial. Divided Differences	26	(5)
Comparison of the Lagrange and Newton Forms	31	(1)
Conditioning of the Interpolating Polynomial	32	(1)
On Poor Convergence of Interpolation with Equidistant Nodes	33	(1)
Exercises	34	(1)
Classical Piecewise Polynomial Interpolation	35	(8)
Definition of Piecewise Polynomial Interpolation	35	(1)
Formula for the Interpolation Error	35	(3)
Approximation of Derivatives for a Grid Function	38	(2)
Estimate of the Unavoidable Error and the Choice of Degree for Piecewise Polynomial Interpolation	40	(2)
Saturation of Piecewise Polynomial Interpolation	42	(1)
Exercises	42	(1)
Smooth Piecewise Polynomial Interpolation (Splines)	43	(14)
Local Interpolation of Smoothness s and Its Properties	43	(5)
Nonlocal Smooth Piecewise Polynomial Interpolation	48	(5)
Proof of Theorem 2.11	53	(3)
Exercises	56	(1)
Interpolation of Functions of Two Variables	57	(4)
Structured Grids	57	(2)
Unstructured Grids	59	(1)
Exercises	60	(1)
Trigonometric Interpolation	61	(30)
Interpolation of Periodic Functions	62	(11)
An Important Particular Choice of Interpolation Nodes	62	(5)
Sensitivity of the Interpolating Polynomial to Perturbations of the Function Values	67	(1)
Estimate of Interpolation Error	68	(4)
An Alternative Choice of Interpolation Nodes	72	(1)
Interpolation of Functions on an Interval. Relation between Algebraic and Trigonometric Interpolation	73	(18)
Periodization	73	(2)
Trigonometric Interpolation	75	(1)
Chebyshev Polynomials. Relation between Algebraic and Trigonometric Interpolation	75	(2)
Properties of Algebraic Interpolation with Roots of the Chebyshev Polynomial Tn+1(x) as Nodes	77	(1)
An Algorithm for Evaluating the Interpolating Polynomial	78	(1)
Algebraic Interpolation with Extrema of the Chebyshev Polynomial Tn(x) as Nodes	79	(1)
More on the Lebesgue Constants and Convergence of Interpolants	80	(9)
Exercises	89	(2)
Computation of Definite Integrals. Quadratures	91	(24)
Trapezoidal Rule, Simpson's Formula, and the Like	91	(11)
General Construction of Quadrature Formulae	92	(1)
Trapezoidal Rule	93	(5)
Simpson's Formula	98	(4)
Exercises	102	(1)
Quadrature Formulae with No Saturation. Gaussian Quadratures	102	(6)
Exercises	107	(1)
Improper Integrals. Combination of Numerical and Analytical Methods	108	(2)
Exercises	110	(1)
Multiple Integrals	110	(5)
Repeated Integrals and Quadrature Formulae	111	(1)
The Use of Coordinate Transformations	112	(1)
The Notion of Monte Carlo Methods	113	(2)
II. Systems of Scalar Equations	115	(134)
Systems of Linear Algebraic Equations: Direct Methods	119	(54)
Different Forms of Consistent Linear Systems	120	(4)
Canonical Form of a Linear System	120	(1)
Operator Form	121	(1)
Finite-Difference Dirichlet Problem for the Poisson Equation	121	(3)
Exercises	124	(1)
Linear Spaces, Norms, and Operators	124	(9)
Normed Spaces	126	(3)
Norm of a Linear Operator	129	(2)
Exercises	131	(2)
Conditioning of Linear Systems	133	(7)
Condition Number	134	(2)
Characterization of a Linear System by Means of Its Condition Number	136	(3)
Exercises	139	(1)
Gaussian Elimination and Its Tri-Diagonal Version	140	(17)
Standard Gaussian Elimination	141	(4)
Tri-Diagonal Elimination	145	(3)
Cyclic Tri-Diagonal Elimination	148	(1)
Matrix Interpretation of the Gaussian Elimination. LU Factorization	149	(4)
Cholesky Factorization	153	(1)
Gaussian Elimination with Pivoting	154	(1)
An Algorithm with a Guaranteed Error Estimate	155	(1)
Exercises	156	(1)
Minimization of Quadratic Functions and Its Relation to Linear Systems	157	(2)
Exercises	159	(1)
The Method of Conjugate Gradients	159	(5)
Construction of the Method	159	(4)
Flexibility in Specifying the Operator A	163	(1)
Computational Complexity	163	(1)
Exercises	163	(1)
Finite Fourier Series	164	(9)
Fourier Series for Grid Functions	165	(3)
Representation of Solution as a Finite Fourier Series	168	(1)
Fast Fourier Transform	169	(2)
Exercises	171	(2)
Iterative Methods for Solving Linear Systems	173	(38)
Richardson Iterations and the Like	174	(20)
General Iteration Scheme	174	(4)
A Necessary and Sufficient Condition for Convergence	178	(3)
The Richardson Method for A = A* > 0	181	(7)
Preconditioning	188	(4)
Scaling	192	(1)
Exercises	193	(1)
Chebyshev Iterations and Conjugate Gradients	194	(4)
Chebyshev Iterations	194	(2)
Conjugate Gradients	196	(1)
Exercises	197	(1)
Krylov Subspace Iterations	198	(6)
Definition of Krylov Subspaces	199	(2)
GMRES	201	(3)
Exercises	204	(1)
Multigrid Iterations	204	(7)
Idea of the Method	205	(3)
Description of the Algorithm	208	(2)
Bibliography Comments	210	(1)
Exercises	210	(1)
Overdetermined Linear Systems. The Method of Least Squares	211	(20)
Examples of Problems that Result in Overdetermined Systems	211	(3)
Processing of Experimental Data. Empirical Formulae	211	(2)
Improving the Accuracy of Experimental Results by Increasing the Number of Measurements	213	(1)
Weak Solutions of Full Rank Systems. QR Factorization	214	(11)
Existence and Uniqueness of Weak Solutions	214	(3)
Computation of Weak Solutions. QR Factorization	217	(3)
Geometric Interpretation of the Method of Least Squares	220	(1)
Overdetermined Systems in the Operator Form	221	(1)
Exercises	222	(3)
Rank Deficient Systems. Singular Value Decomposition	225	(6)
Singular Value Decomposition and Moore-Penrose Pseudoinverse	225	(2)
Minimum Norm Weak Solution	227	(2)
Exercises	229	(2)
Numerical Solution of Nonlinear Equations and Systems	231	(18)
Commonly Used Methods of Rootfinding	233	(4)
The Bisection Method	233	(1)
The Chord Method	234	(1)
The Secant Method	235	(1)
Newton's Method	236	(1)
Fixed Point Iterations	237	(5)
The Case of One Scalar Equation	237	(3)
The Case of a System of Equations	240	(2)
Exercises	242	(1)
Newton's Method	242	(7)
Newton's Linearization for One Scalar Equation	242	(2)
Newton's Linearization for Systems	244	(2)
Modified Newton's Methods	246	(1)
Exercises	247	(2)
III. The Method of Finite Differences for the Numerical Solution of Differential Equations	249	(222)
Numerical Solution of Ordinary Differential Equations	253	(54)
Examples of Finite-Difference Schemes. Convergence	253	(7)
Examples of Difference Schemes	254	(2)
Convergent Difference Schemes	256	(3)
Verification of Convergence for a Difference Scheme	259	(1)
Approximation of Continuous Problem by a Difference Scheme. Consistency	260	(11)
Truncation Error δf(h)	261	(1)
Evaluation of the Truncation Error δf(h)	262	(2)
Accuracy of Order hk	264	(1)
Examples	265	(4)
Replacement of Derivatives by Difference Quotients	269	(1)
Other Approaches to Constructing Difference Schemes	269	(2)
Exercises	271	(1)
Stability of Finite-Difference Schemes	271	(13)
Definition of Stability	272	(1)
The Relation between Consistency, Stability, and Convergence	273	(4)
Convergent Scheme for an Integral Equation	277	(1)
The Effect of Rounding	278	(2)
General Comments. A-stability	280	(3)
Exercises	283	(1)
The Runge-Kutta Methods	284	(4)
The Runge-Kutta Schemes	284	(2)
Extension to Systems	286	(2)
Exercises	288	(1)
Solution of Boundary Value Problems	288	(5)
The Shooting Method	289	(2)
Tri-Diagonal Elimination	291	(1)
Newton's Method	291	(1)
Exercises	292	(1)
Saturation of Finite-Difference Methods by Smoothness	293	(8)
Exercises	300	(1)
The Notion of Spectral Methods	301	(6)
Exercises	306	(1)
Finite-Difference Schemes for Partial Differential Equations	307	(120)
Key Definitions and Illustrating Examples	307	(20)
Definition of Convergence	307	(2)
Definition of Consistency	309	(3)
Definition of Stability	312	(5)
The Courant, Friedrichs, and Lewy Condition	317	(2)
The Mechanism of Instability	319	(1)
The Kantorovich Theorem	320	(2)
On the Efficacy of Finite-Difference Schemes	322	(1)
Bibliography Comments	323	(1)
Exercises	324	(3)
Construction of Consistent Difference Schemes	327	(22)
Replacement of Derivatives by Difference Quotients	327	(6)
The Method of Undetermined Coefficients	333	(7)
Other Methods. Phase Error	340	(4)
Predictor-Corrector Schemes	344	(1)
Exercises	345	(4)
Spectral Stability Criterion for Finite-Difference Cauchy Problems	349	(20)
Stability with Respect to Initial Data	349	(1)
A Necessary Spectral Condition for Stability	350	(2)
Examples	352	(10)
Stability in C	362	(1)
Sufficiency of the Spectral Stability Condition in l2	362	(3)
Scalar Equations vs. Systems	365	(2)
Exercises	367	(2)
Stability for Problems with Variable Coefficients	369	(8)
The Principle of Frozen Coefficients	369	(3)
Dissipation of Finite-Difference Schemes	372	(5)
Exercises	377	(1)
Stability for Initial Boundary Value Problems	377	(45)
The Babenko-Gelfand Criterion	377	(8)
Spectra of the Families of Operators. The Godunov-Ryaben'kii Criterion	385	(17)
The Energy Method	402	(7)
A Necessary and Sufficient Condition of Stability. The Kreiss Criterion	409	(9)
Exercises	418	(4)
Maximum Principle for the Heat Equation	422	(5)
An Explicit Scheme	422	(3)
An Implicit Scheme	425	(1)
Exercises	426	(1)
Discontinuous Solutions and Methods of Their Computation	427	(18)
Differential Form of an Integral Conservation Law	428	(8)
Differential Equation in the Case of Smooth Solutions	428	(1)
The Mechanism of Formation of Discontinuities	429	(2)
Condition at the Discontinuity	431	(2)
Generalized Solution of a Differential Problem	433	(1)
The Riemann Problem	434	(2)
Exercises	436	(1)
Construction of Difference Schemes	436	(9)
Artificial Viscosity	437	(1)
The Method of Characteristics	438	(1)
Conservative Schemes. The Godunov Scheme	439	(5)
Exercises	444	(1)
Discrete Methods for Elliptic Problems	445	(26)
A Simple Finite-Difference Scheme. The Maximum Principle	446	(7)
Consistency	447	(1)
Maximum Principle and Stability	448	(3)
Variable Coefficients	451	(1)
Exercises	452	(1)
The Notion of Finite Elements. Ritz and Galerkin Approximations	453	(18)
Variational Problem	454	(4)
The Ritz Method	458	(2)
The Galerkin Method	460	(4)
An Example of Finite Element Discretization	464	(2)
Convergence of Finite Element Approximations	466	(3)
Exercises	469	(2)
IV. The Methods of Boundary Equations for the Numerical Solution of Boundary Value Problems	471	(36)
Boundary Integral Equations and the Method of Boundary Elements	475	(8)
Reduction of Boundary Value Problems to Integral Equations	475	(4)
Discretization of Integral Equations and Boundary Elements	479	(1)
The Range of Applicability for Boundary Elements	480	(3)
Boundary Equations with Projections and the Method of Difference Potentials	483	(24)
Formulation of Model Problems	484	(4)
Interior Boundary Value Problem	485	(1)
Exterior Boundary Value Problem	485	(1)
Problem of Artificial Boundary Conditions	485	(1)
Problem of Two Subdomains	486	(1)
Problem of Active Shielding	487	(1)
Difference Potentials	488	(10)
Auxiliary Difference Problem	488	(1)
The Potential u+ = P+ νγ	489	(3)
Difference Potential u- = P- νγ	492	(1)
Cauchy Type Difference Potential w&plusman; = p&plusman; νγ	493	(4)
Analogy with Classical Cauchy Type Integral	497	(1)
Solution of Model Problems	498	(7)
Interior Boundary Value Problem	498	(2)
Exterior Boundary Value Problem	500	(1)
Problem of Artificial Boundary Conditions	501	(1)
Problem of Two Subdomains	501	(2)
Problem of Active Shielding	503	(2)
General Remarks	505	(1)
Bibliography Comments	506	(1)
List of Figures	507	(2)
Referenced Books	509	(8)
Referenced Journal Articles	517	(4)
Index	521