Optimization in Solving Elliptic Problems

✍ Scribed by Eugene G. D'yakonov

• Publisher: CRC Press
• Year: 2017
• Tongue: English
• Leaves: 591
• Edition: 1
• Category: Library

✦ Synopsis

Optimization in Solving Elliptic Problems focuses on one of the most interesting and challenging problems of computational mathematics - the optimization of numerical algorithms for solving elliptic problems. It presents detailed discussions of how asymptotically optimal algorithms may be applied to elliptic problems to obtain numerical solutions meeting certain specified requirements. Beginning with an outline of the fundamental principles of numerical methods, this book describes how to construct special modifications of classical finite element methods such that for the arising grid systems, asymptotically optimal iterative methods can be applied.
Optimization in Solving Elliptic Problems describes the construction of computational algorithms resulting in the required accuracy of a solution and having a pre-determined computational complexity. Construction of asymptotically optimal algorithms is demonstrated for multi-dimensional elliptic boundary value problems under general conditions. In addition, algorithms are developed for eigenvalue problems and Navier-Stokes problems. The development of these algorithms is based on detailed discussions of topics that include accuracy estimates of projective and difference methods, topologically equivalent grids and triangulations, general theorems on convergence of iterative methods, mixed finite element methods for Stokes-type problems, methods of solving fourth-order problems, and methods for solving classical elasticity problems.
Furthermore, the text provides methods for managing basic iterative methods such as domain decomposition and multigrid methods. These methods, clearly developed and explained in the text, may be used to develop algorithms for solving applied elliptic problems. The mathematics necessary to understand the development of such algorithms is provided in the introductory material within the text, and common specifications of algorithms that have been developed for typical problems in mathema

✦ Table of Contents

Cover
Half Title
Title Page
Copyright Page
Preface
Editor's Preface
The Author
The Editor
Basic Notation
Table of Contents
Introduction
§ 1. Modern formulations of elliptic boundary value problems
1.1. Variational principles of mathematical physics
1.2. Variational problems in a Hilbert space
1.3. Completion of a preHilbert space and basic properties of Sobolev spaces
1.4. Generalized solutions of elliptic boundary value problems
§ 2. Projective-grid methods (finite element methods)
2.1. Rayleigh-Ritz method
2.2. Bubnov-Galerkin method and projective methods
2.3. Projective-grid methods (finite element methods)
2.4. The simplest projective-grid operators
2.5. Composite grids and triangulations; local grid refinement
§ 3. Methods of solution of discretized problems; asymptotically optimal and nearly optimal preconditioners
3.1. Specificity of grid systems; direct methods
3.2. Classical iterative methods
3.3. Iterative methods with spectrally equivalent operators; optimal preconditioning
3.4. Symmetrizations of systems
3.5. Coarse grid continuation (multigrid acceleration of the basic iterative algorithm)
3.6. Some nonelliptic applications
§ 4. Invariance of operator inequalities under projective approximations
4.1. Rayleigh-Ritz method and Gram matrices
4.2. Projective approximations of operators
4.3. Spectral equivalence of grid operators defined on topologically equivalent triangulations
4.4. Spectral equivalence of grid operators defined on composite triangulations with local refinements
§ 5. N-widths of compact sets and optimal numerical methods for classes of problems
5.1. Approximations of compact sets and criteria for optimality of computational algorithms
5.2. Estimates of N-widths in spaces like W12 (.)
5.3. Optimality of projective-grid methods
Chapter 1: General theory of numerical methods for operator equations
§ 1. General questions
1.1. General notions
1.2. A general convergence theorem
1.3. Estimates of accuracy of projective methods
1.4. Estimates using supplementary Hilbert spaces
§ 2. Conditions for correctness of discrete problems
2.1. A priori estimates of solutions
2.2. Theorems of correctness
2.3. Derivatives of nonlinear operators
2.4. Theorems of correctness for differentiable operators
§ 3. Iterative methods with model symmetric operators
3.1. Estimates of rates of convergence in the Euclidean space H(B) of the modified method of the simple iteration
3.2. Estimates of the rate of convergence in the Euclidean space H(B2)
3.3. Condition numbers of symmetrized linear systems; generalizations for nonlinear problems
3.4. A posteriori estimates
3.5. Modifications of Richardson's iteration
3.6. Use of orthogonalization
3.7. Adaptation of iterative parameters
3.8. Modified gradient methods
3.9. Nonsymmetric model operators
§ 4. Solution of grid systems and asymptotic estimates of the required computational work
4.1. Estimates of the computational work in the modified method of the simple iteration
4.2. Modified classical iterative methods with spectrally equivalent model operators
4.3. Continuation methods (multigrid acceleration of a basic iterative algorithm)
§ 5. Block elimination of unknowns; Schur matrices; cooperative operators
5.1. Block elimination of unknowns
5.2. Basic properties of Schur matrices
5.3. Schur complements in the case of Gram matrices
5.4. Cooperative model operators
Chapter 2: Projective-grid methods for second-order elliptic equations and systems
§ 1. Projective-grid methods associated with triangulation of the region and piecewise polynomial functions
1.1. Topologically equivalent grids and triangulations
1.2. Composite triangulations
1.3. Piecewise linear and piecewise polynomial functions
1.4. Polylinear functions and their generalizations
1.5. Prism grids; cylindrical coordinates
1.6. Boundary value problems on regions with non-Lipschitz boundary
1.7. Use of symmetry of the solution
§ 2. Linear homotopy and change of space variables in constructing projective-grid methods
2.1. Change of variables in projective-grid methods
2.2. Standard quasitriangles and quasisquares
2.3. Linear and central homotopy in space
2.4. Piecewise affine mappings
2.5. Quasiuniform triangulations; the metric space of simplicial cells
§ 3. Accuracy estimates for projective-grid methods
3.1 Approximation of Sobolev spaces and error estimates for projective-grid methods for polyhedral regions
3.2. Steklov's and Sobolev's averagings
3.3. Error estimates under approximation of the region
3.4. Error estimates for PGMs on composite grids with local refinement
3.5. Increasing the accuracy and a posteriori estimates
§ 4. Model projective-grid operator on parallelepiped grids
4.1. Regular triangulations
4.2. Spectral equivalence of projective-grid and difference operators
4.3. The prismatic elements
§ 5. Hierarchical bases; estimates of angles between finite element subspaces
5.1. Splittings of finite element subspaces
5.2. Angles between subspaces; local analysis
5.3. Estimates of angles between finite element subspaces associated with d-dimensional simplexes
5.4. Local numerical estimation of angles between subspaces
§ 6. Nonconforming finite element methods
6.1. The simplest nonconforming finite element methods
6.2. The form of grid operators for model regions
6.3. The spectral equivalence of operators on topologically equivalent triangulations
Chapter 3: Estimates of computational work in solving model grid systems
§ 1. Fast direct methods for model grid systems in a rectangle and parallelepiped
1.1. Separation of variables and the fast discrete Fourier transform
1.2. Partial problems
1.3. Reduction and march methods
1.4. Fast direct methods for grid systems in a triangle or triangular prism
1.5. Basic difference operators on a parallelepiped grid; difference analogs of integration by parts
§ 2. Alternating direction iteration (ADI) methods and splitting operators; additive splitting of the inverse operator
2.1. Basic computational algorithms
2.2. Analysis of the commutative case
2.3. Optimization of iteration parameters for the two-dimensional case
2.4. Estimates of computational work
2.5. Generalized splitting operators
2.6. Grid methods with generalized splitting operators for nonstationary problems
2.7. Additive splitting of the inverse operator (additive Schwarz methods)
§ 3. Iterative methods with factored operators
3.1. Basic classes of methods; factored model operators
3.2. Alternate triangular method
3.3. Incomplete factorization
3.4. Factorization of the matrix associated with a hierarchical basis
§ 4. Two-stage iterative methods with inner iterations
4.1. Basic computational algorithms
4.2. Spectral equivalence of operators Ah and Bh
4.3. Conditions for relationships of type Ck between operators Lh and Bh
4.4. Nonlinear operators
4.5. Optimization with respect to inner iterations
4.6. Nonnegative operators
§ 5. Cutting methods (domain decomposition methods)
5.1. Connection with the block elimination methods; basic computational algorithms
5.2. Structure of the grid operators
5.3. Estimates of the rate of convergence
5.4. Estimates of the required computational work
5.5. Possible generalizations for other types of operators
5.6. Construction of nearly asymptotically optimal model operators and additivity in definition of spaces V1/2 (R)
5.7. Additive splitting of the inverse model operator
§ 6. Fictitious domain methods
6.1. Basic computational algorithms for Neumann's type and some mixed boundary conditions
6.2. Conditions of spectral equivalence of the model grid operator for the original domain and the Schur complement for the extended domain
6.3. Grid extension theorems; use of regions with slits
6.4. Dirichlet boundary conditions and generalizations of the Treftz method
§ 7. Multigrid methods; multigrid construction of asymptotically optimal preconditioners
7.1. Basic computational algorithms and classes of multigrid methods
7.2. Simplest estimates of convergence for two-grid methods
7.3. Symmetrized multigrid method
7.4. Multigrid construction of asymptotically optimal preconditioners
7.5. Estimates of spectral equivalence and required computational work
7.6. Other types of operators and possible generalizations
§ 8. Effective iterative methods for general grid systems
8.1. General grid systems for model regions
8.2. Use of model regions and respective model operators
8.3. Applicability of effective iterative methods
8.4. Use of linearization of nonlinear operators
8.5. Use of inner iterations with the nonnegative error reduction operator
Chapter 4: Construction of topologically equivalent grids
§ 1. Basic approaches to constructing grids
1.1. General ideas
1.2. Conformal and quasiconformal mappings for d = 2
1.3. Use of elliptic generating systems
§ 2. Algebraic methods for constructing quasiuniform triangulations of special type for standard blocks
2.1. Triangulations of type T(.; p) for a standard quasitriangle
2.2. Triangulations of type T(.; p) and T(.; Pi.,P2) for a standard quasisquare
§ 3. Algebraic-geometric methods
3.1. Combination of geometric and algebraic methods
3.2. Cutting of the region into several standard quasisquares and standard quasitriangles
3.3. Geometric problems dealing with special partitions of two-dimensional regions into standard blocks
§ 4. Generalizations for multidimensional blocks
4.1. Refinement of an n-dimensional simplex
4.2. Triangulations of type T(S;p) for a standard quasisimplex
4.3. Triangulations of type T(C; p) for a standard quasicube
4.4. Triangulations of type T(Pr; p, pi) for a standard simplicial quasiprism
4.5. Partitions of multidimensional regions
Chapter 5: Asymptotic minimization of computational work in solving second-order elliptic equations and systems
§ 1. Basic boundary value problems for elliptic equations associated with positive definite quadratic forms
1.1. Modified projective-grid methods for two-dimensional problems
1.2. Asymptotically optimal iterative methods
1.3. The choice of model operators and regions
1.4. Analysis of multigrid acceleration of the basic iterative algorithm
1.5. Proof of the strengthened variant of the Kohnogorov-Bakhvalov hypothesis
1.6. Solutions with more smoothness
§ 2. General linear elliptic equations and multidimensional regions
2.1. Iterative methods for symmetrized grid systems
2.2. General case of invertible elliptic operator
2.3. Generalizations for multidimensional problems
2.4. Iterative methods with orthogonalization
2.5. Singular elliptic operators
§ 3. Strongly elliptic systems and elasticity problems
3.1. Construction of PGMs and model grid operators
3.2. Boundary value elasticity problems with positive definite operators
3.3. Elasticity problems with nonnegative operators
3.4. Domain symmetry
3.5. Cylindrical coordinates
§ 4. Multigrid construction of asymptotically optimal preconditioners for two-dimensional elasticity problems
4.1. Original splitting of the finite element space
4.2. Estimates for the angle between the subspaces
4.3. Multigrid construction of spectrally equivalent operators
§ 5. Quasilinear elliptic problems
5.1. Weakly nonlinear monotone operators
5.2. Nonlinearity of bounded power
5.3. Antisymmetric quadratic nonlinearity
5.4. Nonlinear perturbation of linear invertible operator
5.5. Variational inequalities
Chapter 6: Estimates of computational work of optimal type for difference methods
§ 1. Estimates of computational work for second-order elliptic equations and systems in model regions
1.1. The first boundary value problem for the equation with variable coefficients in a d-dimensional model region
1.2. Conditions for correctness of the difference problem
1.3. Error estimates
1.4. Asymptotically optimal algorithms
1.5. Strongly elliptic systems and boundary value problems in the theory of elasticity
1.6. Difference schemes with higher order approximation
§ 2. A difference analog of W22(Q) for a d-dimensional parallelepiped
2.1. Basic inequalities
2.2. Correctness conditions
2.3. Asymptotically optimal algorithms for grid systems
§ 3. Difference methods for quasilinear elliptic problems
3.1. Difference embedding theorems
3.2. Applicability of effective iterative methods
3.3. Geometrical nonlinear problems in the theory of elasticity and shells
§ 4. Boundary value problems in a rectangle for fourth-order elliptic equations and systems
4.1. The first boundary value problem for equations with variable coefficients
4.2. Strongly elliptic systems
§ 5. Linear and nonlinear problems of plates and shells theory
5.1. Linear problems for elastic plates
5.2. Linear problems of shells theory
5.3. Nonlinear problems of shell theory; von Karman type systems
5.4. Nonlinear shell problems written in displacements
5.5. Two-dimensional flow of viscous incompressible fluids
Chapter 7: Minimization of computational work for systems of Stokes and Navier-Stokes type
§ 1. Saddle-point problems and saddle operators
1.1. Lagrangian function and saddle operators
1.2. Correctness of problems with strongly saddle operators
1.3. Correctness of more general problems
1.4. Perturbation of the parameter
1.5. Variational problems with large parameters; the penalty method
1.6. Examples of problems from hydrodynamics and elasticity
§ 2. Projective methods for problems with saddle operators
2.1. General scheme
2.2. Error estimates
2.3. General theorem on convergence
§ 3. Theorems on divergence of vector field
3.1. Differential case (normal solvability of divergence operator)
3.2. Projective-grid (mixed finite element) methods for d = 2
3.3. Three-dimensional problems
3.4. Composite triangulations
3.5. Use of domain symmetry and other generalizations
§ 4. Asymptotically optimal algorithms for Stokes type problems
4.1. Construction of grid problems and error estimates
4.2. Modified classical iterative methods
4.3. Strengthened variant of the Kolmogorov-Bakhvalov hypothesis for Stokes type problems
4.4. Systems with Schur matrices
4.5. Generalizations for other problems and PGMs
§ 5. Iterative methods with model saddle operators
5.1. Basic classes of methods
5.2. Convergence for linear problems
5.3. Convergence theorems for nonlinear problems
5.4. Convergence of iterative methods with cooperative model operators
5.5. Possible generalizations
§ 6. Asymptotically optimal algorithms for nonlinear Navier-Stokes systems
6.1. Projective-grid (mixed finite element) methods
6.2. Properties of linearized operators
6.3. Effective iterative methods and minimization of computational work
6.4. Other effective algorithms and possible generalizations
Chapter 8: Asymptotically optimal algorithms for fourth-order elliptic problems
§ 1. Boundary value problems in a rectangle
1.1. Projective-grid method for the first boundary problem in a rectangle
1.2. Two-stage iterative methods
§ 2. Reduction to problems of Stokes type
2.1. Spaces of rotors of functions in W22 (.)
2.2. Examples of resulting boundary value problems (in a variational setting)
2.3. Examples of resulting nonsymrnetric and nonlinear problems
§ 3. Asymptotically optimal algorithms for problems with linear constraints
3.1. Projective-grid methods
3.2. Construction of asymptotically optimal preconditioners
3.3. Effective iterative methods
§ 4. Asymptotically optimal algorithms for stiffened plates and shells
4.1. Variational formulations in strengthened Sobolev spaces
4.2. Reduction to Stokes type systems
4.3. Projective-grid (mixed finite element) methods
4.4. Multigrid construction of asymptotically optimal preconditioners
Chapter 9: Effective algorithms for spectral problems
§ 1. The Rayleigh-Ritz method for spectral problems
1.1. Operator formulations for spectral problems in mathematical physics
1.2. Variational properties of the eigenvalues and the minimax Courant-Fisher principle
1.3. The Rayleigh-Ritz method
1.4. Gaps between subspaces
1.5. Symmetries of eigenfunctions
§ 2. Error estimates for the Rayleigh-Ritz and projective methods
2.1. Auxiliary key inequalities
2.2. Estimates for approximation of the eigenvalues in the Rayleigh-Ritz method
2.3. Estimates for gaps between subspaces
2.4. Estimates of accuracy for projective-grid methods
§ 3. A posteriori error estimates
3.1. Properties of residuals
3.2. A posteriori error estimates
§ 4. Modified gradient methods with model operators
4.1. Basic computational algorithms
4.2. Analysis of the modified gradient method with fixed step size
4.3. A posteriori adaptation of iterative parameters
4.4. Modified method of steepest descent and its generalizations
4.5. The general case of the symmetric operator M
§ 5. Modified gradient methods with presence of perturbations
5.1. Basic computational algorithms
5.2. Auxiliary inequalities
5.3. Convergence
5.4. Determination of eigenvectors
5.5. Eigenvalue clustering.
§ 6. Modified subspace iteration method
6.1. Basic computational algorithms
6.2. Convergence of the method
6.3. Eigenspaces and their direct sums
6.4. Eigenspaces for smaller eigenvalues
§ 7. Estimates of computational work for spectral elliptic problems
7.1. Spectral problems with second-order operators
7.2. Spectral elliptic problems with fourth-order operators
7.3. Spectral problems with linear constraints
7.4. Regularization with respect to a and effective iterative methods
7.5. Final conunents
Bibliography
Index