Numerical Methods for Grid Equations

The finite-difference solution of mathematical-physics differential equations is carried out in two stages: 1) the writing of the difference scheme (a differ­ ence approximation to the differential equation on a grid), 2) the computer solution of the difference equations, which are written in the form of a high­ order system of linear algebraic equations of special form (ill-conditioned, band-structured). Application of general linear algebra methods is not always appropriate for such systems because of the need to store a large volume of information, as well as because of the large amount of work required by these methods. For the solution of difference equations, special methods have been developed which, in one way or another, take into account special features of the problem, and which allow the solution to be found using less work than via the general methods. This work is an extension of the book Difference M ethod3 for the Solution of Elliptic Equation3 by A. A. Samarskii and V. B. Andreev which considered a whole set of questions connected with difference approximations, the con­ struction of difference operators, and estimation of the ~onvergence rate of difference schemes for typical elliptic boundary-value problems. Here we consider only solution methods for difference equations. The book in fact consists of two volumes.

1 Direct Methods for Solving Difference Equations.- 1.1 Grid equations. Basic concepts.- 1.1.1 Grids and grid functions.- 1.1.2 Difference derivatives and various difference identities.- 1.1.3 Grid and difference equations.- 1.1.4 The Cauchy problem and boundary-value problems for difference equations.- 1.2 The general theory of linear difference equations.- 1.2.1 Properties of the solutions of homogeneous equations.- 1.2.2 Theorems about the solutions of linear equations.- 1.2.3 The method of variation of parameters.- 1.2.4 Examples.- 1.3 The solution of linear equations with constant coefficients.- 1.3.1 The characteristic equation. The simple-roots case.- 1.3.2 The multiple-root case.- 1.3.3 Examples.- 1.4 Second-order equations with constant coefficients.- 1.4.1 The general solution of a homogeneous equation.- 1.4.2 The Chebyshev polynomials.- 1.4.3 The general solution of a non-homogeneous equation.- 1.5 Eigenvalue difference problems.- 1.5.1 A boundary-value problem of the first kind.- 1.5.2 A boundary-value problem of the second kind.- 1.5.3 A mixed boundary-value problem.- 1.5.4 A periodic boundary-value problem.- 2 The Elimination Method.- 2.1 The elimination method for three-point equations.- 2.1.1 The algorithm.- 2.1.2 Two-sided elimination.- 2.1.3 Justification of the elimination method.- 2.1.4 Sample applications of the elimination method.- 2.2 Variants of the elimination method.- 2.2.1 The flow variant of the elimination method.- 2.2.2 The cyclic elimination metod.- 2.2.3 The elimination method for complicated systems.- 2.2.4 The non-monotonic elimination method.- 2.3 The elimination method for five-point equations.- 2.3.1 The monotone elimination algorithm.- 2.3.2 Justification of the method.- 2.3.3 A variant of non-monotonic elimination.- 2.4 The block-elimination method.- 2.4.1 Systems of vector equations.- 2.4.2 Elimination for three-point vector equations.- 2.4.3 Elimination for two-point vector equations.- 2.4.4 Orthogonal elimination for two-point vector equations.- 2.4.5 Elimination for three-point equations with constant coefficents.- 3 The Cyclic Reduction Method.- 3.1 Boundary-value problems for three-point vector equations.- 3.1.1 Statement of the boundary-value problems.- 3.1.2 A boundary-value problem of the first kind.- 3.1.3 Other boundary-value problems for difference equations.- 3.1.4 A high-accuracy Dirichlet difference problem.- 3.2 The cylic reduction method for a boundary-value problem of the first kind.- 3.2.1 The odd-even elimination process.- 3.2.2 Transformation of the right-hand side and inversion of the matrices.- 3.2.3 The algorithm for the method.- 3.2.4 The second algorithm of the method.- 3.3 Sample applications of the method.- 3.3.1 A Dirichlet difference problem for Poisson’s equation in a rectangle.- 3.3.2 A high-accuracy Dirichlet difference problem.- 3.4 The cyclic reduction method for other boundary-value problems.- 3.4.1 A boundary-value problem of the second kind.- 3.4.2 A periodic problem.- 3.4.3 A boundary-value problem of the third kind.- 4 The Separation of Variables Method.- 4.1 The algorithm for the discrete Fourier transform.- 4.1.1 Statement of the problem.- 4.1.2 Expansion in sines and shifted sines.- 4.1.3 Expansion in cosines.- 4.1.4 Transforming a real-valued periodic grid function.- 4.1.5 Transforming a complex-valued periodic grid function.- 4.2 The solution of difference problems by the Fourier method.- 4.2.1 Eigenvalue difference problems for the Laplace operator in a rectangle.- 4.2.2 Poisson’s equation in a rectangle; expansion in a double series.- 4.2.3 Expansion in a single series.- 4.3 The method of incomplete reduction.- 4.3.1 Combining the Fourier and reduction methods.- 4.3.2 The solution of boundary-value problems for Poisson’s equation in a rectangle.- 4.3.3 A high-accuracy Dirichlet difference problem in a rectangle.- 4.4 The staircase algorithm and the reduction method for solving tridiagonal systems of equations.- 4.4.1 The staircase algorithm for the case of tridiagonal matrices with scalar elements.- 4.4.2 The staircase algorithm for the case of a block-tridiagonal matrix.- 4.4.3 Stability of the staircase algorithm.- 4.4.4 The reduction method for three-point scalar equations.