麻省理工学院：《偏微分方程式数字方法》（英文版）Lecture 7 Iterative Method

Iterative Methods Multigrid Techniques Lecture 7

Background Developed over the last 25 years- Brandt (1973) published first paper with practical results Offers the possibility of solving a problem with work and storage proportional to the number of unknowns Well developed for linear elliptic problems application to other equations is still an active area of research Good Introductory Reference: A Multigrid Tutorial, W.L. Briggs, V.E.Henson, and S F. McCormick, SIAM Monograph, 2000 SMA-HPC⊙2003MT Iterative Methods: Multigrid Techniques 1

Some ideas Basic Principles 1. Multigrid is an iterative method a good initial guess will reduce the number of iterations to solve An Wh= fn by iteration, we could take un w2h, Where Azh W2h= f2h but the number of iterations needed to solve An uh= fn still O(n2) SMA-HPC⊙2003MT Iterative Methods: Multigrid Techniques 2

Some ideas Basic Principles 2. If after a few iterations. the error is smooth we could solve for the error on a coarser mesh, e.g A2h e2h=roh Smooth functions can be represented on coarser grIds, Coarse grid solutions are cheaper SMA-HPC⊙2003MT Iterative Methods: Multigrid Techniques 3

Smoother Basic Principles If the high frequency components of the error decay faster than the low frequency components, we say that the iterative method is a smoother. SMA-HPC⊙2003MT Iterative Methods: Multigrid Techniques 4

Smoother Basic Principles Jacobi ← LOW MODES→}<一 HIGH MODES 000 02 0000 14161820 mode k v(modek-2) n=19 15(mode k=15) Is Jacobi a smoother? →NO SMA-HPC⊙2003MT Iterative Methods: Multigrid Techniques 5

Smoother Basic Principles Under-Relaxed Jacobi 05 1/2 R=R3+(1-)0 ①=23 -5 (UNSTABLE) =1 mode k 入(a)=u(R)+(1-a)=1-c(1-入(E)), 1=1 SMA-HPC⊙2003MT Iterative Methods: Multigrid Techniques 6

Smoother Basic Principles Under-Relaxed Jacob Iterations required to reduce an error mode by a factor of 100 n=19 0=1 500 -0=23 8101214161820 mode k SMA-HPC⊙2003MT Iterative Methods: Multigrid Techniques 7

Smoother Basic Principles Gauss-Seidel Recall -06 mode k =19 Is Gauss-Seidel a good smoother? SMA-HPC⊙2003MT Iterative Methods: Multigrid Techniques 8

Smoother Basic Principles Gauss-Seidel Iterations required to reduce an a error mode by a factor of 100 n=19 gEz 0246810121416182 node k GS is a good smoother SMA-HPC⊙2003MT Iterative Methods: Multigrid Techniques 9