Heath - Scientific Computing (523150), страница 96
Текст из файла (страница 96)
The conjugategradient method proved ineffective as a direct method owing to rounding error, so it wastemporarily discarded until the early 1970s, when its use as an iterative method was popularized by Reid, Golub, and others (see [102]). For a negative result on the existence of atrue analogue of the conjugate gradient method for nonsymmetric systems, see [75]. The358CHAPTER 11. PARTIAL DIFFERENTIAL EQUATIONSmultigrid method was popularized in the late 1970s by Brandt and numerous others. Classicreferences on iterative methods for linear systems are [115, 263, 280]. For more up-to-datetreatments of iterative methods, see the surveys [15, 87, 147] or the more comprehensivetreatises [12, 114, 194, 218].
For an introduction to multigrid methods, see [24, 139, 271].Review Questions11.1 True or false: For solving a timedependent partial differential equation, a finite difference method that is both consistentand stable converges to the true solution as thestepsizes in time and in space go to zero.11.2 True or false: The Gauss-Seidel iterativemethod for solving a system of linear equationsAx = b always converges.11.3 True or false: The Gauss-Seidel methodis a special case of SOR (successive overrelaxation) for solving a system of linear equations.11.4 How does a semidiscrete method differfrom a fully discrete method for solving a timedependent partial differential equation?11.5 (a) Explain briefly the method of linesfor solving an initial value problem for a timedependent partial differential equation in onespace dimension.(b) How might the method of lines be usedto solve a pure boundary value problem fora time-independent PDE in two space dimensions?11.6 Other than the usual concerns of stability and accuracy, what additional importantconsideration enters into the choice of a numerical method for solving a system of ODEsarising from semidiscretization of a PDE usingthe method of lines?11.7 In using a fully discrete finite differencemethod for solving a time-dependent partialdifferential equation with one space dimension,can the sizes of the time step and space stepbe chosen independently of each other? Why?11.8 Fully discrete finite difference and finiteelement methods for solving boundary valueproblems convert the original differential equation into a system of algebraic equations.
Whydoes the resulting n × n linear system usuallyrequire far less work to solve than the usualO(n3 ) that might be expected?11.9 Which of the following types of partialdifferential equations are time-dependent?(a) Elliptic(b) Parabolic(c) Hyperbolic11.10 Classify each of the following partialdifferential equations as hyperbolic, parabolic,or elliptic. Also, state whether each equationis time-dependent or time-independent.(a) Laplace equation(b) Wave equation(c) Heat equation(d ) Poisson equation11.11 What is meant by the stencil of a finitedifference method for solving a PDE numerically?11.12 The heat equation ut = cuxx with appropriate initial and boundary conditions canbe solved numerically by using a second-order,centered finite difference approximation foruxx and then solving the resulting system ofordinary differential equations in time by somenumerical method.(a) On what ODE method in time is theCrank-Nicolson method based?(b) What advantage does the Crank-Nicolsonmethod have over the use of the backward Euler method?(c) What fundamental advantage do both ofthese methods have over the use of Euler’smethod?11.13 In solving the Laplace equation on theunit square using the standard second-orderaccurate finite difference scheme in both spacedimensions, what is the maximum number ofunknown solution variables that are involvedin any one equation of the resulting linear algebraic system?REVIEW QUESTIONS11.14 Consider the numerical solution of theheat equation, ut = cuxx , by a fully discretefinite difference method.
For the spatial discretization, suppose that we approximate thesecond derivative by the standard second-orderaccurate, centered difference formula.(a) Why is Euler’s method impractical for thetime integration?(b) Name a method for numerically solving theheat equation that is unconditionally stableand second-order accurate in both space andtime.(c) On what ODE method is the time integration in this method based?11.15 Implicit finite difference methods forsolving time-dependent PDEs require the solution of a system of equations at each timestep. In using the backward Euler or trapezoid method to solve the heat equation in onespace dimension, what is the nonzero patternof the matrix of the linear system to be solvedat each time step?11.16 (a) For a finite difference method forsolving a PDE numerically, what is meant bythe terms consistency, stability, and convergence?(b) How does the Lax Equivalence Theoremrelate these terms to each other?11.17 Suppose you are solving the heat equation ut = uxx by applying an ODE methodto solve the semidiscrete system of ODEs resulting from spatial discretization using thestandard second-order central difference approximation to the second derivative.
Each ofthe following ODE methods then gives a timestepping procedure that may or may not beconsistent, stable, or convergent. State whichof these three properties, if any, apply for eachmethod listed (note that none, one, or morethan one of the properties may apply in a givencase).(a) Euler’s method with ∆t = ∆x(b) Backward Euler method with ∆t = ∆x(c) The “zero method,” which produces theanswer 0 at every time step11.18 List two advantages and two disadvantages of iterative methods compared with di-359rect methods for solving large sparse systemsof linear algebraic equations.11.19 What principal factor limits the usefulness of direct methods based on matrix factorization for solving very large sparse systems oflinear equations?11.20 What is the computational complexityof a fast Poisson solver for a problem with nmesh points?11.21 What is meant by fill in the factorization of a sparse matrix?11.22 Explain briefly how the minimum degree algorithm works for reordering a symmetric positive definite sparse matrix to limit fillin its Cholesky factor.11.23 Explain briefly how the nested dissection algorithm works for reordering a symmetric positive definite sparse matrix to limit fillin its Cholesky factor.11.24 What is the general form of a stationary iterative method for solving a system oflinear equations Ax = b?11.25 (a) What is meant by a splitting of amatrix A?(b) What form of iterative method for solvinga linear system Ax = b results from such asplitting?(c) What condition on the splitting guaranteesthat the resulting iterative scheme is locallyconvergent?(d ) For the matrix4 1A=,1 4what is the splitting for the Jacobi method?(e) For the same matrix as in part d, what isthe splitting for the Gauss-Seidel method?11.26 In solving a nonsingular system of linear equations Ax = b, what property of thematrix A would necessarily cause the Jacobiiterative method to fail outright?11.27 Which of the following methods forsolving a linear system are stationary iterativemethods?(a) Jacobi method360CHAPTER 11.
PARTIAL DIFFERENTIAL EQUATIONS(b) Steepest descent method(c) Iterative refinement(d ) Gauss-Seidel method(e) Conjugate gradient method(f ) SOR method11.28 (a) In words (or formulas if you prefer), describe the difference between the Jacobiand Gauss-Seidel iterative methods for solvinga system of linear algebraic equations.(b) Which method is more rapidly convergent?(c) Which method requires less storage for thesuccessive approximate solutions?11.29 Listed below are several properties thatmay pertain to various methods for solvingsystems of linear equations.
For each of theproperties listed, state whether this qualitymore accurately describes direct or iterativemethods:(a) The entries of the matrix are not alteredduring the computation.(b) A good prior estimate for the solution ishelpful.(c) The matrix entries are stored explicitly, using a standard storage scheme such as an array.(d ) The work required depends on the conditioning of the problem.(e) Once a given system has been solved, another system with the same matrix but a different right-hand side is easily solved.(f ) Acceleration parameters or preconditionersare usually employed.(g) The maximum possible accuracy is relatively easy to attain.(h) “Black box” software is relatively easy toimplement.(i ) The matrix can be defined implicitly by itsaction on an arbitrary vector.(j ) A factorization of the matrix is usually performed.(k ) The amount of work required can often bedetermined in advance.11.30 Let A be a nonsingular matrix.
Denotethe strict lower triangular portion of A by L,the diagonal of A by D, and the strict uppertriangle of A by U .(a) Express the Jacobi iteration scheme forsolving the linear system Ax = b in terms ofL, D, and U .(b) Express the Gauss-Seidel iteration schemefor solving the linear system Ax = b in termsof L, D, and U .11.31 What are the usual bounds on the relaxation parameter ω in the SOR method?11.32 Rank the following iterative methodsfor solving systems of linear equations in order of their usual speed of convergence, fromfastest to slowest:(a) Gauss-Seidel(b) Jacobi(c) SOR with optimal relaxation parameter ω11.33 The conjugate gradient method forsolving a symmetric positive definite system oflinear equations is in principle a direct method.Why is it used in practice as an iterativemethod instead?11.34 What two key features largely accountfor the effectiveness of the conjugate gradientmethod for solving large sparse symmetric positive definite linear systems?11.35 When using the conjugate gradientmethod to solve a system of linear algebraicequations Ax = b, how can you accelerate itsconvergence rate?11.36 (a) What is meant by preconditioningin the conjugate gradient method?(b) List at least two types of preconditionersused with the conjugate gradient method.11.37 Why are some stationary iterativemethods for solving linear systems sometimescalled smoothers?11.38 Explain briefly the basic idea of multigrid methods.11.39 (a) Explain the difference between theV-cycle and the W-cycle in multigrid methods.(b) How does full multigrid differ from eitherof these?11.40 For solving linear systems arising fromelliptic boundary value problems, which typeof method, iterative or direct, suffers a greaterincrease in work as the dimension of the problem increases? Why?EXERCISES36111.41 Is any type of method capable of solving linear systems arising from elliptic boundary value problems in time proportional to thenumber of grid points? If so, name one, and ifnot, why not?Exercises11.1 Suppose you are given a general-purposesubroutine for solving initial value problemsfor systems of n first-order ODEs y 0 = f (t, y),and this is the only software tool you haveavailable.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
