A Multigrid Tutorial-William L. Briggs--second edition

多重网格法比较经典的一本书，作者：William L. BriggsThis page intentionally left blankA MultigridTut○mlSecond editionilliam L. BriggsDepartment of MathematicsUniversity of Colorado at DenverDenver ColoradoVan Emden hensonCenter for Applied Scientific Computingawrence Livermore National LaboratoryLivermore. CaliforniaSteve f. mccormickDepartment of Applied MathematicsUniversity of Colorado at BoulderBoulder coloradoSociety for Industrial and Applied MathematicsCopyright @2000 by the Society for Industrial and Applied mathematics1098765432All rights reserved. Printed in the United States of America. No part of this bookmay be reproduced, stored, or transmitted in any manner without the writtenpermission of the publisher. For information, write to the Society for Industrialand Applied Mathematics, 3600 University City Science Center, Philadelphia,PA19104-2688Portions of this work were performed under the auspices of the U.S. Departmentof Energy by University of California Lawrence Livermore National Laboratoryunder contract W-7405-Eng-48Library of Congress Cataloging-in-Publication DataBriggs, william Lmultigrid tutorial 2nd ed / William L. Briggs, Van Emden Henson, Steve F.McCormickP, cmIncludes bibliographical references and indexISBN089871-4621(pbk)1. Differential equations, Partial--Numerical solutions. 2. Multigrid methods(Numerical analysis) I. Henson, Van Emden. II. McCormick, S. F. III. TitleQA377.3752000s15353-dc2100-024103SUIL is a registered trademarkTo the ladiesJulie, Teri, Lynda, Katie, JenniferThis page intentionally left blankContentsPreface to the Second EditioIXPreface to the First Edition1 Model ProblemsExercises42 Basic Iterative MethodsExercises273 Elements of Multigrid31Exercises,,,,,,,,,,,,,,4 Implementation45Exercises65 Some TheoryExercises916 Nonlinear Problems95EexciSes7 Selected Applications113Exercises1338 Algebraic Multigrid (AMG)137EXercises1599 Multilevel Adaptive Methods163Exercises17410 Finite Elements177Exercises186Bibliography189Index191This page intentionally left blankPreface to the SecondEditionTwelve years have passed since the publication of the first edition of A MultigridTutorial. During those years, the field of multigrid and multilevel methods hasexpanded at a tremendous rate, reflecting progress in the development and analysisof algorithms and in the evolution of computing environments. Because of thesechanges, the first edition of the book has become increasingly outdated and theneed for a new edition has become quite apparentWith the overwhelming growth in the subject, an area in which I have neverdone serious research, I felt remarkably unqualified to attempt a new edition. Re-alizing that I needed some help, i recruited two experts to assist with the projectSteve McCormick(Department of Applied Mathematics, University of Colorado atBoulder) is one of the original researchers in the field of multigrid methods and thereal instigator of the first edition. There could be no better collaborator on thesubject. Van Emden Henson(Center for Applied Scientific Computing, LawrenceLivermore National Laboratory) has specialized in applications of multigrid meth-ods, with a particular emphasis on algebraic multigrid methods. Our collaborationon a previous siAm monograph made him an obvious choice as a co-author.With the team in place, we began deliberating on the content of the new edi-tion. It was agreed that the first edition should remain largely intact with littlemore than some necessary updating. Our aim was to add a roughly equal amountof new material that reflects important core developments in the field. a topicthat probably should have been in the first edition comprises Chapter 6: FAS(Full Approximation Scheme), which is used for nonlinear problems. Chapter 7 isa collection of methods for four special situations that arise frequently in solvingboundary value problems: Neumann boundary conditions, anisotropic problemsvariable-mesh problems, and variable-coefficient problems. One of the chief moti-vations for writing a second edition was the recent surge of interest in algebraicmultigrid methods, which is the subject of Chapter 8. In Chapter 9, we attemptto explain the complex subject of adaptive grid methods, as it appears in the FAC(Fast Adaptive Composite) Grid Method. Finally, in Chapter 10, we depart fromthe predominantly finite difference approach of the book and show how finite ele-ment formulations arise. This chapter provides a natural closing because it ties aknot in the thread of variational principles that runs through much of the bookThere is no question that the new material in the second half of this edition ismore advanced than that presented in the first edition. However, we have tried tocreate a safe passage between the two halves, to present many motivating examples