standard tridiagonal algorithm. Given un , one solves () for un+1/2 , substitutes on the right-hand side of (), and then solves for un+1 . The key question is how to choose the iteration parameter r | Multigrid Methods for Boundary Value Problems 871 standard tridiagonal algorithm. Given u one solves for un 1 2 substitutes on the right-hand side of and then solves for u 1. The key question is how to choose the iteration parameter r the analog of a choice of timestep for an initial value problem. As usual the goal is to minimize the spectral radius of the iteration matrix. Although it is beyond our scope to go into details here it turns out that for the optimal choice of r the ADI method has the same rate of convergence as SOR. The individual iteration steps in the ADI method are much more complicated than in SOR so the ADI method would appear to be inferior. This is in fact true if we choose the same parameter r for every iteration step. However it is possible to choose a different r for each step. If this is done optimally then ADI is generally more efficient than SOR. We refer you to the literature 1 -4 for details. Our reason for not fully implementing ADI here is that in most applications it has been superseded by the multigrid methods described in the next section. Our advice is to use SOR for trivial problems . 20 x 20 or for solving a larger problem once only where ease of programming outweighs expense of computer time. Occasionally the sparse matrix methods of are useful for solving a set of difference equations directly. For production solution of large elliptic problems however multigrid is now almost always the method of choice. CITED REFERENCES AND FURTHER READING Hockney . and Eastwood . 1981 Computer Simulation Using Particles New York McGraw-Hill Chapter 6. Young . 1971 Iterative Solution of Large Linear Systems New York Academic Press . 1 Stoer J. and Bulirsch R. 1980 Introduction to NumericalAnalysis New York Springer-Verlag . 2 Varga . 1962 Matrix Iterative Analysis Englewood Cliffs NJ Prentice-Hall . 3 Spanier J. 1967 in Mathematical Methods for Digital Computers Volume 2 New York Wiley Chapter .
