Numerical Methods for Grid Equations: v. 2

Table of Contents:
5 The Mathematical Theory of Iterative Methods.- 5.1 Several results from functional analysis.- 5.1.1 Linear spaces.- 5.1.2 Operators in linear normed spaces.- 5.1.3 Operators in a Hilbert space.- 5.1.4 Functions of a bounded operator.- 5.1.5 Operators in a finite-dimensional space.- 5.1.6 The solubility of operator equations.- 5.2 Difference schemes as operator equations.- 5.2.1 Examples of grid-function spaces.- 5.2.2 Several difference identities.- 5.2.3 Bounds for the simplest difference operators.- 5.2.4 Lower bounds for certain difference operators.- 5.2.5 Upper bounds for difference operators.- 5.2.6 Difference schemes as operator equations in abstract spaces.- 5.2.7 Difference schemes for elliptic equations with constant coefficients.- 5.2.8 Equations with variable coefficients and with mixed derivatives.- 5.3 Basic concepts from the theory of iterative methods.- 5.3.1 The steady state method.- 5.3.2 Iterative schemes.- 5.3.3 Convergence and iteration counts.- 5.3.4 Classification of iterative methods.- 6 Two-Level Iterative Methods.- 6.1 Choosing the iterative parameters.- 6.1.1 The initial family of iterative schemes.- 6.1.2 The problem for the error.- 6.1.3 The self-adjoint case.- 6.2 The Chebyshev two-level method.- 6.2.1 Construction of the set of iterative parameters.- 6.2.2 On the optimality of the a priori estimate.- 6.2.3 Sample choices for the operator D.- 6.2.4 On the computational stability of the method.- 6.2.5 Construction of the optimal sequence of iterative parameters.- 6.3 The simple iteration method.- 6.3.1 The choice of the iterative parameter.- 6.3.2 An estimate for the norm of the transformation operator.- 6.4 The non-self-adjoint case. The simple iteration method.- 6.4.1 Statement of the problem.- 6.4.2 Minimizing the norm of the transformation operator.- 6.4.3 Minimizing the norm of the resolving operator.- 6.4.4 The symmetrization method.- 6.5 Sample applications of the iterative methods.- 6.5.1 A Dirichlet difference problem for Poisson's equation in a rectangle.- 6.5.2 A Dirichlet difference problem for Poisson's equation in an arbitrary region.- 6.5.3 A Dirichlet difference problem for an elliptic equation with variable coefficients.- 6.5.4 A Dirichlet difference problem for an elliptic equation with mixed derivatives.- 7 Three-Level Iterative Methods.- 7.1 An estimate of the convergence rate.- 7.1.1 The basic family of iterative schemes.- 7.1.2 An estimate for the norm of the error.- 7.2 The Chebyshev semi-iterative method.- 7.2.1 Formulas for the iterative parameters.- 7.2.2 Sample choices for the operator D.- 7.2.3 The algorithm of the method.- 7.3 The stationary three-level method.- 7.3.1 The choice of the iterative parameters.- 7.3.2 An estimate for the rate of convergence.- 7.4 The stability of two-level and three-level methods relative to a priori data.- 7.4.1 Statement of the problem.- 7.4.2 Estimates for the convergence rates of the methods.- 8 Iterative Methods of Variational Type.- 8.1 Two-level gradient methods.- 8.1.1 The choice of the iterative parameters.- 8.1.2 A formula for the iterative parameters.- 8.1.3 An estimate of the convergence rate.- 8.1.4 Optimality of the estimate in the self-adjoint case.- 8.1.5 An asymptotic property of the gradient methods in the self-adjoint case.- 8.2 Examples of two-level gradient methods.- 8.2.1 The steepest-descent method.- 8.2.2 The minimal residual method.- 8.2.3 The minimal correction method.- 8.2.4 The minimal error method.- 8.2.5 A sample application of two-level methods.- 8.3 Three-level conjugate-direction methods.- 8.3.1 The choice of the iterative parameters. An estimate of the convergence rate.- 8.3.2 Formulas for the iterative parameters. The three-level iterative scheme.- 8.3.3 Variants of the computational formulas.- 8.4 Examples of the three-level methods.- 8.4.1 Special cases of the conjugate-direction methods.- 8.4.2 Locally optimal three-level methods.- 8.5 Accelerating the convergence of two-level methods in the self-adjoint case.- 8.5.1 An algorithm for the acceleration process.- 8.5.2 An estimate of the effectiveness.- 8.5.3 An example.- 9 Triangular Iterative Methods.- 9.1 The Gauss-Seidel method.- 9.1.1 The iterative scheme for the method.- 9.1.2 Sample applications of the method.- 9.1.3 Sufficient conditions for convergence.- 9.2 The successive over-relaxation method.- 9.2.1 The iterative scheme. Sufficient conditions for covergence.- 9.2.2 The choice of the iterative parameter.- 9.2.3 An estimate of the spectral radius.- 9.2.4 A Dirichlet difference problem for Poisson'5 The Mathematical Theory of Iterative Methods.- 5.1 Several results from functional analysis.- 5.1.1 Linear spaces.- 5.1.2 Operators in linear normed spaces.- 5.1.3 Operators in a Hilbert space.- 5.1.4 Functions of a bounded operator.- 5.1.5 Operators in a finite-dimensional space.- 5.1.6 The solubility of operator equations.- 5.2 Difference schemes as operator equations.- 5.2.1 Examples of grid-function spaces.- 5.2.2 Several difference identities.- 5.2.3 Bounds for the simplest difference operators.- 5.2.4 Lower bounds for certain difference operators.- 5.2.5 Upper bounds for difference operators.- 5.2.6 Difference schemes as operator equations in abstract spaces.- 5.2.7 Difference schemes for elliptic equations with constant coefficients.- 5.2.8 Equations with variable coefficients and with mixed derivatives.- 5.3 Basic concepts from the theory of iterative methods.- 5.3.1 The steady state method.- 5.3.2 Iterative schemes.- 5.3.3 Convergence and iteration counts.- 5.3.4 Classification of iterative methods.- 6 Two-Level Iterative Methods.- 6.1 Choosing the iterative parameters.- 6.1.1 The initial family of iterative schemes.- 6.1.2 The problem for the error.- 6.1.3 The self-adjoint case.- 6.2 The Chebyshev two-level method.- 6.2.1 Construction of the set of iterative parameters.- 6.2.2 On the optimality of the a priori estimate.- 6.2.3 Sample choices for the operator D.- 6.2.4 On the computational stability of the method.- 6.2.5 Construction of the optimal sequence of iterative parameters.- 6.3 The simple iteration method.- 6.3.1 The choice of the iterative parameter.- 6.3.2 An estimate for the norm of the transformation operator.- 6.4 The non-self-adjoint case. The simple iteration method.- 6.4.1 Statement of the problem.- 6.4.2 Minimizing the norm of the transformation operator.- 6.4.3 Minimizing the norm of the resolving operator.- 6.4.4 The symmetrization method.- 6.5 Sample applications of the iterative methods.- 6.5.1 A Dirichlet difference problem for Poisson's equation in a rectangle.- 6.5.2 A Dirichlet difference problem for Poisson's equation in an arbitrary region.- 6.5.3 A Dirichlet difference problem for an elliptic equation with variable coefficients.- 6.5.4 A Dirichlet difference problem for an elliptic equation with mixed derivatives.- 7 Three-Level Iterative Methods.- 7.1 An estimate of the convergence rate.- 7.1.1 The basic family of iterative schemes.- 7.1.2 An estimate for the norm of the error.- 7.2 The Chebyshev semi-iterative method.- 7.2.1 Formulas for the iterative parameters.- 7.2.2 Sample choices for the operator D.- 7.2.3 The algorithm of the method.- 7.3 The stationary three-level method.- 7.3.1 The choice of the iterative parameters.- 7.3.2 An estimate for the rate of convergence.- 7.4 The stability of two-level and three-level methods relative to a priori data.- 7.4.1 Statement of the problem.- 7.4.2 Estimates for the convergence rates of the methods.- 8 Iterative Methods of Variational Type.- 8.1 Two-level gradient methods.- 8.1.1 The choice of the iterative parameters.- 8.1.2 A formula for the iterative parameters.- 8.1.3 An estimate of the convergence rate.- 8.1.4 Optimality of the estimate in the self-adjoint case.- 8.1.5 An asymptotic property of the gradient methods in the self-adjoint case.- 8.2 Examples of two-level gradient methods.- 8.2.1 The steepest-descent method.- 8.2.2 The minimal residual method.- 8.2.3 The minimal correction method.- 8.2.4 The minimal error method.- 8.2.5 A sample application of two-level methods.- 8.3 Three-level conjugate-direction methods.- 8.3.1 The choice of the iterative parameters. An estimate of the convergence rate.- 8.3.2 Formulas for the iterative parameters. The three-level iterative scheme.- 8.3.3 Variants of the computational formulas.- 8.4 Examples of the three-level methods.- 8.4.1 Special cases of the conjugate-direction methods.- 8.4.2 Locally optimal three-level methods.- 8.5 Accelerating the convergence of two-level methods in the self-adjoint case.- 8.5.1 An algorithm for the acceleration process.- 8.5.2 An estimate of the effectiveness.- 8.5.3 An example.- 9 Triangular Iterative Methods.- 9.1 The Gauss-Seidel method.- 9.1.1 The iterative scheme for the method.- 9.1.2 Sample applications of the method.- 9.1.3 Sufficient conditions for convergence.- 9.2 The successive over-relaxation method.- 9.2.1 The iterative scheme. Sufficient conditions for covergence.- 9.2.2 The choice of the iterative parameter.- 9.2.3 An estimate of the spectral radius.- 9.2.4 A Dirichlet difference problem for Poisson's equation in a rectangle.- 9.2.5 A Dirichlet difference problem for an elliptic equation with variable coefficients.- 9.3 Triangular methods.- 9.3.1 The iterative scheme.- 9.3.2 An estimate of the convergence rate.- 9.3.3 The choice of the iterative parameter.- 9.3.4 An estimate for the convergence rates of the Gauss-Seidel and relaxation methods.- 10 The Alternate-Triangular Method.- 10.1 The general theory of the method.- 10.1.1 The iterative scheme.- 10.1.2 Choice of the iterative parameters.- 10.1.3 A method for finding ? and ?.- 10.1.4 A Dirichlet difference problem for Poisson's equation in a rectangle.- 10.2 Boundary-value difference problems for elliptic equations in a rectangle.- 10.2.1 A Dirichlet problem for an equation with variable coefficients.- 10.2.2 A modified alternate-triangular method.- 10.2.3 A comparison of the variants of the method.- 10.2.4 A boundary-value problem of the third kind.- 10.2.5 A Dirichlet difference problem for an equation with mixed derivatives.- 10.3 The alternate-triangular method for elliptic equations in arbitrary regions.- 10.3.1 The statement of the difference problem.- 10.3.2 The construction of an alternate-triangular method.- 10.3.3 A Dirichlet problem for Poisson's equation in an arbitrary region.- 11 The Alternating-Directions Method.- 11.1 The alternating-directions method in the commutative case.- 11.1.1 The iterative scheme for the method.- 11.1.2 The choice of the parameters.- 11.1.3 A fractionally-linear transformation.- 11.1.4 The optimal set of parameters.- 11.2 Sample applications of the method.- 11.2.1 A Dirichlet difference problem for Poisson's equation in a rectangle.- 11.2.2 A boundary-value problem of the third kind for an elliptic equation with separable variables.- 11.2.3 A high-accuracy Dirichlet difference problem.- 11.3 The alternating-directions method in the general case.- 11.3.1 The case of non-commuting operators.- 11.3.2 A Dirichlet difference problem for an elliptic equation with variable coefficients.- 12 Methods for Solving Equationswith Indefinite and Singular Operators.- 12.1 Equations with real indefinite operators.- 12.1.1 The iterative scheme. The choice of the iterative parameters.- 12.1.2 Transforming the operator in the self-adjoint case.- 12.1.3 The iterative method with the Chebyshev parameters.- 12.1.4 Iterative methods of variational type.- 12.1.5 Examples.- 12.2 Equations with complex operators.- 12.2.1 The simple iteration method.- 12.2.2 The alternating-directions method.- 12.3 General iterative methods for equations with singular operators.- 12.3.1 Iterative schemes in the case of a non-singular operator B.- 12.3.2 The minimum-residual iterative method.- 12.3.3 A method with the Chebyshev parameters.- 12.4 Special methods.- 12.4.1 A Neumann difference problem for Poisson'5 The Mathematical Theory of Iterative Methods.- 5.1 Several results from functional analysis.- 5.1.1 Linear spaces.- 5.1.2 Operators in linear normed spaces.- 5.1.3 Operators in a Hilbert space.- 5.1.4 Functions of a bounded operator.- 5.1.5 Operators in a finite-dimensional space.- 5.1.6 The solubility of operator equations.- 5.2 Difference schemes as operator equations.- 5.2.1 Examples of grid-function spaces.- 5.2.2 Several difference identities.- 5.2.3 Bounds for the simplest difference operators.- 5.2.4 Lower bounds for certain difference operators.- 5.2.5 Upper bounds for difference operators.- 5.2.6 Difference schemes as operator equations in abstract spaces.- 5.2.7 Difference schemes for elliptic equations with constant coefficients.- 5.2.8 Equations with variable coefficients and with mixed derivatives.- 5.3 Basic concepts from the theory of iterative methods.- 5.3.1 The steady state method.- 5.3.2 Iterative schemes.- 5.3.3 Convergence and iteration counts.- 5.3.4 Classification of iterative methods.- 6 Two-Level Iterative Methods.- 6.1 Choosing the iterative parameters.- 6.1.1 The initial family of iterative schemes.- 6.1.2 The problem for the error.- 6.1.3 The self-adjoint case.- 6.2 The Chebyshev two-level method.- 6.2.1 Construction of the set of iterative parameters.- 6.2.2 On the optimality of the a priori estimate.- 6.2.3 Sample choices for the operator D.- 6.2.4 On the computational stability of the method.- 6.2.5 Construction of the optimal sequence of iterative parameters.- 6.3 The simple iteration method.- 6.3.1 The choice of the iterative parameter.- 6.3.2 An estimate for the norm of the transformation operator.- 6.4 The non-self-adjoint case. The simple iteration method.- 6.4.1 Statement of the problem.- 6.4.2 Minimizing the norm of the transformation operator.- 6.4.3 Minimizing the norm of the resolving operator.- 6.4.4 The symmetrization method.- 6.5 Sample applications of the iterative methods.- 6.5.1 A Dirichlet difference problem for Poisson's equation in a rectangle.- 6.5.2 A Dirichlet difference problem for Poisson's equation in an arbitrary region.- 6.5.3 A Dirichlet difference problem for an elliptic equation with variable coefficients.- 6.5.4 A Dirichlet difference problem for an elliptic equation with mixed derivatives.- 7 Three-Level Iterative Methods.- 7.1 An estimate of the convergence rate.- 7.1.1 The basic family of iterative schemes.- 7.1.2 An estimate for the norm of the error.- 7.2 The Chebyshev semi-iterative method.- 7.2.1 Formulas for the iterative parameters.- 7.2.2 Sample choices for the operator D.- 7.2.3 The algorithm of the method.- 7.3 The stationary three-level method.- 7.3.1 The choice of the iterative parameters.- 7.3.2 An estimate for the rate of convergence.- 7.4 The stability of two-level and three-level methods relative to a priori data.- 7.4.1 Statement of the problem.- 7.4.2 Estimates for the convergence rates of the methods.- 8 Iterative Methods of Variational Type.- 8.1 Two-level gradient methods.- 8.1.1 The choice of the iterative parameters.- 8.1.2 A formula for the iterative parameters.- 8.1.3 An estimate of the convergence rate.- 8.1.4 Optimality of the estimate in the self-adjoint case.- 8.1.5 An asymptotic property of the gradient methods in the self-adjoint case.- 8.2 Examples of two-level gradient methods.- 8.2.1 The steepest-descent method.- 8.2.2 The minimal residual method.- 8.2.3 The minimal correction method.- 8.2.4 The minimal error method.- 8.2.5 A sample application of two-level methods.- 8.3 Three-level conjugate-direction methods.- 8.3.1 The choice of the iterative parameters. An estimate of the convergence rate.- 8.3.2 Formulas for the iterative parameters. The three-level iterative scheme.- 8.3.3 Variants of the computational formulas.- 8.4 Examples of the three-level methods.- 8.4.1 Special cases of the conjugate-direction methods.- 8.4.2 Locally optimal three-level methods.- 8.5 Accelerating the convergence of two-level methods in the self-adjoint case.- 8.5.1 An algorithm for the acceleration process.- 8.5.2 An estimate of the effectiveness.- 8.5.3 An example.- 9 Triangular Iterative Methods.- 9.1 The Gauss-Seidel method.- 9.1.1 The iterative scheme for the method.- 9.1.2 Sample applications of the method.- 9.1.3 Sufficient conditions for convergence.- 9.2 The successive over-relaxation method.- 9.2.1 The iterative scheme. Sufficient conditions for covergence.- 9.2.2 The choice of the iterative parameter.- 9.2.3 An estimate of the spectral radius.- 9.2.4 A Dirichlet difference problem for Poisson's equation in a rectangle.- 9.2.5 A Dirichlet difference problem for an elliptic equation with variable coefficients.- 9.3 Triangular methods.- 9.3.1 The iterative scheme.- 9.3.2 An estimate of the convergence rate.- 9.3.3 The choice of the iterative parameter.- 9.3.4 An estimate for the convergence rates of the Gauss-Seidel and relaxation methods.- 10 The Alternate-Triangular Method.- 10.1 The general theory of the method.- 10.1.1 The iterative scheme.- 10.1.2 Choice of the iterative parameters.- 10.1.3 A method for finding ? and ?.- 10.1.4 A Dirichlet difference problem for Poisson's equation in a rectangle.- 10.2 Boundary-value difference problems for elliptic equations in a rectangle.- 10.2.1 A Dirichlet problem for an equation with variable coefficients.- 10.2.2 A modified alternate-triangular method.- 10.2.3 A comparison of the variants of the method.- 10.2.4 A boundary-value problem of the third kind.- 10.2.5 A Dirichlet difference problem for an equation with mixed derivatives.- 10.3 The alternate-triangular method for elliptic equations in arbitrary regions.- 10.3.1 The statement of the difference problem.- 10.3.2 The construction of an alternate-triangular method.- 10.3.3 A Dirichlet problem for Poisson's equation in an arbitrary region.- 11 The Alternating-Directions Method.- 11.1 The alternating-directions method in the commutative case.- 11.1.1 The iterative scheme for the method.- 11.1.2 The choice of the parameters.- 11.1.3 A fractionally-linear transformation.- 11.1.4 The optimal set of parameters.- 11.2 Sample applications of the method.- 11.2.1 A Dirichlet difference problem for Poisson's equation in a rectangle.- 11.2.2 A boundary-value problem of the third kind for an elliptic equation with separable variables.- 11.2.3 A high-accuracy Dirichlet difference problem.- 11.3 The alternating-directions method in the general case.- 11.3.1 The case of non-commuting operators.- 11.3.2 A Dirichlet difference problem for an elliptic equation with variable coefficients.- 12 Methods for Solving Equationswith Indefinite and Singular Operators.- 12.1 Equations with real indefinite operators.- 12.1.1 The iterative scheme. The choice of the iterative parameters.- 12.1.2 Transforming the operator in the self-adjoint case.- 12.1.3 The iterative method with the Chebyshev parameters.- 12.1.4 Iterative methods of variational type.- 12.1.5 Examples.- 12.2 Equations with complex operators.- 12.2.1 The simple iteration method.- 12.2.2 The alternating-directions method.- 12.3 General iterative methods for equations with singular operators.- 12.3.1 Iterative schemes in the case of a non-singular operator B.- 12.3.2 The minimum-residual iterative method.- 12.3.3 A method with the Chebyshev parameters.- 12.4 Special methods.- 12.4.1 A Neumann difference problem for Poisson's equation in a rectangle.- 12.4.2 A direct method for the Neumann problem.- 12.4.3 Iterative schemes with a singular operator B.- 13 Iterative Methods for Solving Non-Linear Equations.- 13.1 Iterative methods. The general theory.- 13.1.1 The simple iteration method for equations with a monotone operator.- 13.1.2 Iterative methods for the case of a differentiate operator.- 13.1.3 The Newton-Kantorovich method.- 13.1.4 Two-stage iterative methods.- 13.1.5 Other iterative methods.- 13.2 Methods for solving non-linear difference schemes.- 13.2.1 A difference scheme for a one-dimensional elliptic quasi-linear equation.- 13.2.2 The simple iteration method.- 13.2.3 Iterative methods for quasi-linear elliptic difference equations in a rectangle.- 13.2.4 Iterative methods for weakly-nonlinear equations.- 14 Example Solutions of Elliptic Grid Equations.- 14.1 Methods for constructing implicit iterative schemes.- 14.1.1 The regularizer principle in the general theory of iterative methods.- 14.1.2 Iterative schemes with a factored operator.- 14.1.3 A method for implicity inverting the operator B (a two-stage method).- 14.2 Examples of solving elliptic boundary-value problems.- 14.2.1 Direct and iterative methods.- 14.2.2 A high-accuracy Dirichlet difference problem in the multi-dimensional case.- 14.2.3 A boundary-value problem of the third kind for an equation with mixed derivatives in a rectangle.- 14.2.4 Iterative methods for solving a difference problem.- 14.3 Systems of elliptic equations.- 14.3.1 A Dirichlet problem for systems of elliptic equations in a p-dimensional parallelipiped.- 14.3.2 A system of equations from elasticity theory.- 14.4 Methods for solving elliptic equations in irregular regions.- 14.4.1 Difference problems in regions of complex form and methods for their solution.- 14.4.2 Decomposition of regions.- 14.4.3 An algorithm for the domain decomposition method.- 14.4.4 The method of domain augmentation to a rectangle.- 15 Methods for Solving Elliptic Equationsin Curvilinear Orthogonal Coordinates.- 15.1 Posing boundary-value problems for differential equations.- 15.1.1 Elliptic equations in a cylindrical system of coordinates.- 15.1.2 Boundary-value problems for equations in a cylindrical coordinate system.- 15.2 The solution of difference problems in cylindrical coordinates.- 15.2.1 Difference schemes without mixed derivatives in the axially-symmetric case.- 15.2.2 Direct methods.- 15.2.3 The alternating-directions method.- 15.2.4 The solution of equations defined on the surface of a cylinder.- 15.3 Solution of difference problems in polar coordinate systems.- 15.3.1 Difference schemes for equations in a circle or a ring.- 15.3.2 The solubility of the boundary-value difference problems.- 15.3.3 The superposition principle for a problem in a circle.- 15.3.4 Direct methods for solving equations in a circle or a ring.- 15.3.5 The alternating-directions method.- 15.3.6 Solution of difference problems in a ring sector.- 15.3.7 The general variable-coefficients case.- Appendices.- Construction of the minimax polynomial.- Translator's note.