Methods of Numerical Mathematics

The present volume is an adaptation of a series of lectures on numerical mathematics which the author has been giving to students of mathematics at the Novosibirsk State University during the span of several years. In dealing with problems of applied and numerical mathematics the author sought to focus his attention on those complicated problems of mathe­ matical physics which, in the course of their solution, can be reduced to simpler and theoretically better developed problems allowing effective algorithmic realization on modern computers. It is usually these kinds of problems that a young practicing scientist runs into after finishing his university studies. Therefore this book is pri­ marily intended for the benefit of those encountering truly complicated problems of mathematical physics for the first time, who may seek help regarding rational approaches to their solution. In writing this book the author has also tried to take into account the needs of scientists and engineers who already have a solid background in practical problems but who lack a systematic knowledge in areas of numerical mathematics and its more general theoretical framework.

1 Fundamentals of the Theory of Difference Schemes.- 1.1. Basic Equations and Their Adjoints.- 1.1.1. Norm Estimates of Certain Matrices.- 1.1.2. Computing the Spectral Bounds of a Positive Matrix.- 1.1.3. Eigenvalues and Eigenfunctions of the Laplace Operator.- 1.1.4. Eigenvalues and Eigenvectors of the Finite-Difference Analog of the Laplace Operator.- 1.2. Approximation.- 1.3. Countable Stability.- 1.4. The Convergence Theorem.- 2 Methods of Constructing Difference Schemes for Differential Equations.- 2.1. Variational Methods in Mathematical Physics.- 2.1.1. Some Problems of Variational Calculation.- 2.1.1. The Ritz Method.- 2.1.3. The Galërkin Method.- 2.1.4. The Method of Least Squares.- 2.2. The Method of Integral Identities.- 2.2.1. Method of Constructing Difference Equations for Problems with Discontinuous Coefficients on the Basis of an Integral Identity.- 2.2.2. The Variational Form of an Integral Identity.- 2.3. Difference Schemes for Equations with Discontinuous Coefficients Based on Variational Principles.- 2.3.1. Simple Difference Equations for a Diffusion Based on the Ritz Method.- 2.3.2. Constructions of Simple Difference Schemes Based on the Galërkin (Finite Elements) Method.- 2.4. Principles for the Construction of Subspaces for the Solution of One-Dimensional Problems by Variational Methods.- 2.4.1. A General Approach to the Construction of Subspaces of Piecewise-Polynomial Functions.- 2.4.2. Constructing a Basis Using Trigonometric Functions and Applying It in Variational Methods.- 2.5. Variational-Difference Schemes for Two-Dimensional Equations of Elliptic Type.- 2.5.1. The Ritz Method.- 2.5.2. The Galërkin Method.- 2.5.3. Methods for Constructing Subspaces.- 2.6. Variational Methods for Multi-Dimensional Problems.- 2.6.1. Methods of Choosing the Subspaces.- 2.6.2. Coordinate-by-Coordinate Methods for Multi-Dimensional Problems.- 2.7. The Method of Fictive Domains.- 3 Interpolation of Net Functions.- 3.1. Interpolation of Functions of One Variable.- 3.1.1. Interpolation of Functions of One Variable by Cubic Splines.- 3.1.2. Piecewise-Cubic Interpolation with Smoothing.- 3.1.3. Smooth Construction.- 3.1.4. The Convergence of Spline Functions.- 3.2. Interpolation of Functions of Two or More Variables.- 3.3. An r-Smooth Approximation to a Function of Several Variables.- 3.4. Elements of the General Theory of Splines.- 4 Methods for Solving Stationary Problems of Mathematical Physics.- 4.1. General Concepts of Iteration Theory.- 4.2. Some Iterative Methods and Their Optimization.- 4.2.1. The Simplest Iteration Method.- 4.2.2. Convergence and Optimization of Stationary Iterative Methods.- 4.2.3. The Successive Over-Relaxation Method.- 4.2.4. The Chebyshev Iteration Method.- 4.2.5. Comparison of the Convergence Rates of Various Iteration Methods for a System of Finite-Difference Equations.- 4.3. Nonstationary Iteration Methods.- 4.3.1. Convergence Theorems.- 4.3.2. The Method of Minimizing the Residuals.- 4.3.3. The Conjugate Gradient Method.- 4.4. The Splitting-Up Method.- 4.4.1. The Commutative Case.- 4.4.2. The Noncommutative Case.- 4.4.3. Variational and Chebyshevian Optimization of Splitting-Up Methods.- 4.5. Iteration Methods for Systems with Singular Matrices.- 4.5.1. Consistent Systems.- 4.5.2. Inconsistent Systems.- 4.5.3. The Matrix Analog of the Method of Fictive Regions.- 4.6. Iterative Methods for Inaccurate Input Data.- 4.7. Direct Methods for Solving Finite-Difference Systems.- 4.7.1. The Fast Fourier Transform.- 4.7.2. The Cyclic Reduction Method.- 4.7.3. Factorization of Difference Equations.- 5 Methods for Solving Nonstationary Problems.- 5.1. Second-Order Approximation Difference Schemes with Time-Varying Operators.- 5.2. Nonhomogeneous Equations of the Evolution Type.- 5.3. Splitting-Up Methods for Nonstationary Problems.- 5.3.1. The Stabilization Method.- 5.3.2. The Predictor-Corrector Method.- 5.3.3. The Component-by-Component Splitting-Up Method.- 5.3.4. Some General Remarks.- 5.4. Multi-Component Splitting.- 5.4.1. The Stabilization Method.- 5.4.2. The Predictor-Corrector Method.- 5.4.3. The Component-by-Component Splitting-Up Method Based on the Elementary Schemes.- 5.4.4. Splitting-Up of Quasi-Linear Problems.- 5.5. General Approach to Component-by-Component Splitting.- 5.6. Methods of Solving Equations of the Hyperbolic Type.- 5.6.1. The Stabilization Method.- 5.6.2. Reduction of the Wave Equation to an Evolution Problem.- 6 Richardson’s Method for Increasing the Accuracy of Approximate Solutions.- 6.1 Ordinary First-Order Differential Equations.- 6.2. General Results.- 6.2.1. The Decomposition Theorem.- 6.2.2. Acceleration of Convergence.- 6.3. Simple Integral Equations.- 6.3.1. The Fredholm Equation of the Second Kind.- 6.3.2. The Volterra Equation of the First Kind.- 6.4. The One-Dimensional Diffusion Equation.- 6.4.1. The Difference Method.- 6.4.2. The Galërkin Method.- 6.5. Nonstationary Problems.- 6.5.1. The Heat Equation.- 6.5.2. The Splitting-Up Method for the Evolutionary Equation.- 6.6. Richardson’s Extrapolation for Multi-Dimensional Problems.- 7 Numerical Methods for Some Inverse Problems.- 7.1. Fundamental Definitions and Examples.- 7.2. Solution of the Inverse Evolution Problem with a Constant Operator.- 7.2.1. The Fourier Method.- 7.2.2. Reduction to the Solution of a Direct Equation.- 7.3. Inverse Evolution Problems with Time-Varying Operators.- 7.4. Methods of Perturbation Theory for Inverse Problems.- 7.4.1. Some Problems of the Linear Theory of Measurements.- 7.4.2. Conjugate Functions and the Notion of Value.- 7.4.3. Perturbation Theory for Linear Functionals.- 7.4.4. Numerical Methods for Inverse Problems and Design of Experiment.- 7.5. Perturbation Theory for Complex Nonlinear Models.- 7.5.1. Fundamental and Adjoint Equations.- 7.5.2. The Adjoint Equation in Perturbation Theory.- 7.5.3. Perturbation Theory for Nonstationary Problems.- 7.5.4. Spectral Methods in Perturbation Theory.- 8 Methods of Optimization.- 8.1. Convex Programming.- 8.2. Linear Programming.- 8.3. Quadratic Programming.- 8.4. Numerical Methods in Convex Programming Problems.- 8.5. Dynamic Programming.- 8.6. Pontrjagin’s Maximum Principle.- 8.7. Extremal Problems with Constraints and Variational Inequalities.- 8.7.1. Elements of the General Theory.- 8.7.2. Examples of Extremal Problems.- 8.7.3. Numerical Methods in Extremal Problems.- 9 Some Problems of Mathematical Physics.- 9.1. The Poisson Equation.- 9.1.1. The Dirichlet Problem for the One-Dimensional Poisson Equation.- 9.1.2. The One-Dimensional von Neumann Problem.- 9.1.3. The Two-Dimensional Poisson Equation.- 9.1.4. A Problem of Boundary Conditions.- 9.2. The Heat Equation.- 9.2.1. The One-Dimensional Problem of Heat Conduction.- 9.2.2. The Two-Dimensional Problem of Heat Conduction.- 9.3. The Wave Equation.- 9.4. The Equation of Motion.- 9.4.1. The Simplest Equations of Motion.- 9.4.2. The Two-Dimensional Equation of Motion with Variable Coefficients.- 9.4.3. The Multi-Dimensional Equation of Motion.- 9.5. The Neutron Transport Equation.- 9.5.1. The Nonstationary Equation.- 9.5.2. The Transport Equation in Self-Adjoint Form.- 10 A Review of the Methods of Numerical Mathematics.- 10.1. The Theory of Approximation, Stability, and Convergence of Difference Schemes.- 10.2. Numerical Methods for Problems of Mathematical Physics.- 10.3. Conditionally Well-Posed Problems.- 10.4. Numerical Methods in Linear Algebra.- 10.5. Optimization Problems in Numerical Methods.- 10.6. Optimization Methods.- 10.7. Some Trends in Numerical Mathematics.- References.- Index of Notation.