Splitting and Alternating Direction Methods

G.I. Marchuk

Preface 203

Chapter I. Introduction 205

1. Approximation 206
2. Stability 216
3. Convergence 222
4. The Crank-Nicolson scheme 224

Part 1. Algorithms for the Splitting Methods and the Alternating Direction Methods 229

Chapter II. Componentwise Splitting (Fractional Steps) Methods 231

5. The splitting method based on implicit schemes of first-order accuracy 231
6. The componentwise splitting method based on Crank-Nicolson schemes: The case A=A1+A2 232
7. Multicomponent splitting of problems based on Crank-Nicolson schemes 234
8. A general approach to componentwise splitting based on elementary Crank-Nicolson schemes 235
9. A general formulation for the splitting method based on multi- level schemes 236
10. The two-level splitting scheme with weight coefficients 237
11. The splitting method for systems which do not belong to the Cauchy-Kovalevskaya class 238
12. Splitting schemes for the heat conduction equation: Local one- dimensional schemes 239
12.1. The splitting scheme for the heat conduction equation in an orthogonal coordinate system 239
12.2. The splitting scheme for the heat conduction equation in an arbitrary coordinate system 240
12.3. Local one-dimensional schemes 242

Chapter III. Two-Cycle Componentwise Splitting Methods 245

13. The two-cycle componentwise splitting methods: The case A=A1+A2 245
14. The two-cycle multicomponent splitting method 247
15. The two-cycle componentwise splitting method for quasi-linear problems 248
16. A general approach to the two-cycle componentwise splitting method 249
17. The two-cycle componentwise splitting scheme for the heat conduction equation 252

Chapter IV. Splitting Schemes with Factorization of the Operators 255

18. Schemes factorizing the operators 255
19. The implicit splitting scheme with approximate factorization of the operator 258
20. The stabilization method (explicit-implicit scheme with approximate factorization of the operator) 259
21. A general scheme for the method of approximatic factorization of the operator 263
22. The scheme of approximate factorization for the parabolic equation 265

Chapter V. The Predictor-Corrector Method 269

23. The predictor-corrector method: The case A=A1+A2 269
24. The predictor-corrector method: The case A=\Sigma^n_\alfa=1A_\alfa 272
25. The predictor-corrector method for the parabolic equation 273

Chapter VI. The Alternating Direction and the Stabilizing Correction Methods 277

26. The alternating direction method 277
27. The stabilizing correction method 278
28. A general formulation for the stabilizing correction method 279
29. Application of the alternating direction scheme to the parabolic equation 280

Chapter VII. Methods of Splitting with Respect to Physical Processes 283

30. The method of splitting with respect to physical processes 283
31. The method of particles in a cell 285
32. The method of large particles 286

Chapter VIII. The Alternating Triangular Method and the Alternating Operator Method 289

33. The alternating triangular method 289
34. The alternating operator method 291
35. The generalized alternating operator method 292
36. The scheme of the alternating triangular method for the parabolic equation 292

Chapter IX. Splitting Methods and Alternating Direction Methods as Iterative Methods for Stationary Problems 295

37. The stationing method: General concepts of the theory of iterative methods 295
38. Iterative algorithms 297
39. Acceleration of the convergence of iterative methods 299

Part 2. Methods for Studying the Convergence on Splitting and Alternating Direction Schemes 301

Chapter X. Convergence Studies of the Splitting Schemes by Use of the Fourier Method (Spectral Method) 303
40. General statement of the Fourier method 303
41. The Fourier method and the convergence studies of splitting schemes for stationary problems 307
42. The Fourier method and the grounding of the splitting schemes for nonstationary problems 310

Chapter XI. The A Priori Estimates Method and the Convergence Studies of the Splitting Schemes 315

43. The simplest a priori estimates 315
44. A priori estimates for the splitting scheme of type A_j \phi^{j+1}=B_j \phi^j + \tau_j f^j 319
45. The energy inequalities method for constructing a priori estimates 322

Chapter XII. The Splitting of the Evolutionary Problem for a System of Differential Equations 327

46. The splitting of problems defined on fractional intervals and the weak approximation method 327
47. The splitting of problems defined on the whole interval 331
48. The two-cycle splitting of the problem 332
49. Some results on convergence and stability 335

Chapter XIII. Convergence Studies and Optimization of Iterative Methods 339
50. Sufficient conditions for convergence 339
51. The choice of parameters in the commutative alternating direction method 344
52. The choice of parameters in the noncommutative alternating direction method 348
53. The convergence acceleration procedures for the alternating direction method 350
54. Generalizations 352

Chapter XIV. Splitting and Decomposition Methods for Variational Problems 355

55. Splitting and decomposition methods for classical variational problems 355
56. Decomposition of a general variational problem 356
57. A variational problem with restrictions 357
58. The convergence of decomposition algorithms 358

Part 3. Applications of Splitting Methods to Problems of Mathematical Physics 361

Chapter XV. The Heat Conduction Equation 363

59. The two-cycle componentwise splitting scheme for a parabolic
equation with three spatial variables 363
60. Schemes of second-order accuracy for p-dimensional parabolic equations without mixed derivatives 366
61. Schemes for equations with mixed derivatives 368
62. Alternating direction schemes 370
63. Schemes of increased order of accuracy 371
64. Finite element method schemes and splitting schemes for two- dimensional parabolic equations 374

Chapter XVI. Equations of Hyperbolic Type 377

65. The stabilization scheme for the multidimensional equation of oscillations 377
66. Approximate factorization schemes for equations of oscillations 378
67. Local one-dimensional schemes for multidimensional hyperbolic equations 381
68. The splitting scheme for multidimensional hyperbolic systems of equations 383

Chapter XVII. Integro-Differential Transport Equations 389

69. Statement of the problem and the scheme of incomplete splitting 389
70. The scheme of complete splitting 392
71. The scheme of approximate factorization of the operator 392
72. The method of integral identities and the splitting method 394
73. The numerical scheme for the nonstationary transport equation in (x,y) geometry 399
73.1. Approximation in spatial variables 400
73.2. Approximation in the time variable 405
73.3. Approximation in angular variables 406
73.4. Numerical realization of the algorithm 407
74. Splitting methods as iterative algorithms for stationary transport equations 410

Chapter XVIII. The Splitting Method for Problems of Hydrodynamics 413

75. Splitting schemes for Navier-Stokes equations with î- perturbation of incompressible fluid equations 413
76. Splitting schemes restoring divergence for incompressible fluid equations 416
77. The general principle for constructing splitting schemes for Navier-Stokes equations 419

Chapter XIX. Problems in Meteorology 427

78. Equations of atmosphere hydrothermodynamics 427
79. The general splitting method with respect to physical processes based on the separation of characteristic times 432
80. The approximation of equations in spatial variables and the discrete analogues of conservation laws 435
81. The method of splitting with respect to geometric variables and numerical realization 437

Chapter XX. Problems in Oceanology 441

82. Statement of the problem and the splitting of equations with respect to physical processes 441
83. The splitting of adaptation equations in planes and generalization for the nonhydrostatic case 444
84. The splitting of adaptation equations with respect to "topography" 445
85. The splitting of "shallow water" equations with respect to coordinates 447

References 449

Subject Index 461