Numerical Methods for Grid Equations

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.