A Multigrid Tutorial
40
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
40
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Publié par
Langue
English
Multigrid for nonlinear problems: an overviewVan Emden HensonCenter for Applied Scientific ComputingLawrence Livermore National Laboratoryvhenson@llnl.govhttp://www.casc.gov/CASC/people/hensonJanuary 23, 2003This work was performed, in part, under the auspices of the United States Department of Energy by University of California Lawrence Livermore National Laboratory under contract number W-7405-Eng-48.Outline• Multigrid: a 30-second introduction• The scalar Newton’s method• Newton’s method for systems• Multigrid for Newton’s method: Newton-MG• Nonlinear multigrid: full approximation storage (FAS)• Numerical examples of Newton-MG and FAS2o f 3 8The 1-d Model Problem− ∆u = f• Poisson’s equation: in [0,1], with boundary conditions .u ( 0 ) = u ( 1 ) = 0• Discretized as:2u = u = 0−u +2u −u =h f0 Ni −1 i i +1 iAu = f• Leads to the Matrix equation , where f u 12 − 1 1 fu− 1 2 − 1 22 u f − 1 2 − 133A = , u = , f = u N − 2− 1 2 − 1 f N − 2 u N − 1− 1 2 fN − 1 3o f 3 8Weighted Jacobi Relaxation• Consider the iteration:ω2( n ew ) ( o ld ) ( o ld ) ( o ld )u ← ( 1 − ω ) u + ( u + u + h f )i i i − 1 i + 1 i2• Letting A = D-L-U, the matrix form is:− 1 2 − 1( new ) ( old )u = ( 1 − ω ) I + ωD ( L + U ) u + ωh D f2 − 1( old ).= R u + ωh D fω( ...
Voir
Publié par
Langue
English
Multigrid for nonlinear problems: an overview
Van Emden Henson CenterforAppliedScientificComputing LawrenceLivermoreNationalLaboratory
vhenson@lgovnl.
http://www.casc.gov/CASC/people/henson
January23,2003
This work was performed, in part, under the auspices of the United States Department of Energy by University of California Lawrence Livermore National Laboratory under contract number W-7405-Eng-48.
Outline
Multigrid: a 30-second introduction
The scalar Newtons method
Newtons method for systems
Multigrid for Newtons method: Newton-MG
Nonlinear multigrid: full approximation storage (FAS)
Numerical examples of Newton-MG and FAS
2 of 38
The 1-d Model Problem
Poissons equation:−∆u= [0,1], with boundary in conditionsu(0)=u(1)=0 . Discretized as: 2 −ui−1+2ui−ui+1=h f
u=u
0N
=0
Leads to the Matrix equationu= , where
−1 =−12−21−12−1,u=uNuuu132−2,f=fNff213−2 −1−12−21uN−1fN1 −
3 of 38
Weighted Jacobi Relaxation
Consider the iteration: ui( wn e)← (1−ω)uoldi)+ω2(uio−l1d)+uoi+l1d)+h2fi)
Letting-L-U=DA,the matrix form is:
u(new)= (1ω−)I+ ωD−1(L+U)uold)+ ωh2D−1f
=Rωu(old)+ ωh2D−1f.
e≡u(exact)−u(approx) It is easy to see that if , then
e(new)=Rωe(old)
4 of 38
Relaxation Smoothes the Error
Initial error, 2 1 0 - 1 - 2 0 0 . 5 1 Error after 35 iteration sweeps:
2 1 0 - 1 - 2
0
0 . 5
1
Manyrelaxationschemes havethemootsgnih propertyw,rehe oscilrytoa modesoftheerrorare eliminatedeffectively,butsmoothmodesaredampedveryslowly.
5 of 38
Smooth error can be represented accurately on a coarse grid
A smooth function: 1 0 . 5 0 - 0 . 5 - 1 0 0 . 5 1 Can be represented by linear interpolation from a coarser grid: 1 0 . 5
0 - 0 . 5 - 1 0
0 . 5
1
On the coarse grid, the smooth error appears to be relatively higher in frequency: in the example it is the 4-mode, out of a possible 16, on the fine grid, 1/4 the way up the spectrum. On the coarse grid, it is the 4-mode out of a possible 8, hence it is 1/2 the way up the spectrum.
Relaxation will be more effective on this mode if done on the coarser grid!!
6 of 38
Coarse-grid Correction
Perform relaxation onuh=f on fine grid until error is smooth.
Compute residual,r2h=f−Auh and transfer to the coarse gridr2h=Ihrh.
Solve the coarse-grid residual equation to obtain the error: 2he2h=r2h, ∴e2h= (A2h)1r2h
Interpolate the error to the fine grid and correct the fine-grid solution: uh←uh+I2he2h
7 of 38
Coarse-grid Correction
Relax onuh=f Computerh=f−A uh
Restrict r2h=Ih2rh
Correct u←u+e
Solve2e2h=r2h − e2h= (A2h)1r2h
Interpolate eh≈I2he2h
8of38
Tools Needed
Interpolation and restriction operators:
...
0.5 1.0 0 50 5 0 25 1 0 0 25 0 1 0 2hh=.01..01505500,Ih2h=001010,Ih2h=0.25 1.000..52215.0 0.25 . . . . Linear Injection Full-weighting Interpolation Coarse-grid OperatorA2 . Two methods: (1) Discretize equation at larger spacing (2) Use Galerkin Formula: A2=Ih2A I2h
9 of 38
Recursion: the (ν,0) V-cycle
Major question: How do we solve the coarse-grid residual equation?swAnre:erucsroin! uh←Gν(A,f)u←u+e 2←Ih2(f−A uh)eh←I2hu2h u2h←G(A2,f2)u2u2e2 4←I24h(f2−A2u2h)e2h←I24hu4h u4h←Gν(A4,f4)u4←u4+e4 8←I84h(f4−A4u4h)e4h←I84hu8h u8h←Gν(A8,f8)u8←u8+e8
eH= (A)−1f
10 of 38
lt Muoiugtrisdmuosoetshceorarrosrecgormidpsonteontdsamp
smoother
Finest Grid
A Multigrid V-cycle
Prolongation-transfer from coarse to fine grid
Restriction-transfer from fine to coarse grid
First Coarse Grid
Note: smaller grid
11of38
