信号处理中数学方法课件电子

MultigridMethods

MultigridMethods

- 多重网格

History

MultigridMethods

多重网格法的思想虽然早在30年代就有人提出，但真正广泛应用于工程技术问题是在1977年布朗特（Brandt）的开创性文章之后才开始的

近十多年在许多应用问题上取得显著效果,受到日益广泛的关注

思想其实很简单,可以看成是定常迭代方法的推广或应用

背景历史

HighlightsofMultigrid:

The1-dModelProblem

Poissonequationin[0,1]:

uf

withboundaryconditions

u0u10

Discretizedas:

ui12uiui1 f

h2 i

u u 0

LeadstoalinearequationCu=f,with

2 1

u1

f1

1

1

2 1

u

2

f2

12 1

u3

f3

Ch2

u

f

f

12 1 uN2

N2

12

uN

1

A

fN1

EigenvalueofMatrixA

Eigenvaluej

Eigenvectorvj

能否改进经典方法？？

TheeigenvectorsofG arethesameasthoseofA,andareFourierModes:

visinikNk12N1

Theeigenvaluesof Gare

12sin2k2N

Sotheeffectofrelaxationonthemodesis

Note:Novalue

of willdampoutthelowfrequencywaves

1

0

.5

0

-0

.5

-1

N=400

13

12

23

1

0 200 400

Manyrelaxationschemes

havethesmoothingproperty,whereoscillatory

modesoftheerrorare

eliminatedeffectively,butsmoothmodesaredamped

veryslowly.

Initialerror,

Errorafter35iterationsw

2

1

0

-1

-2

0 0.5 1

循环格式：V循环

MultigridMethods

h2h

4h8h

16h

问题讨论

网格数：2m×n+2mm是层数，

n是最小一层的网格数

Smootherrorcanberepresentedonacoarsegrid

Asmoothfunction:

1

0.5

0

-0.5

-1

0 0.5 1

Onthecoarsegrid,thesmootherrorappearstoberelativelyhigherinfrequency:intheexampleitisthe4-mode,outofapossible16,onthefine

grid,1/4thewayupthe

Canberepresentedbylinearspectrum.Onthecoarse

interpolationfromacoarsergrid:

1

grid,itisthe4-modeoutofapossible8,henceitis1/2thewayupthespectrum.

0 5

0

-0 5

-1

0

0 5 1

Relaxationwillbemoreeffectiveonthismodeifdoneonthecoarsergrid!!

Performrelaxationonfinegriduntilerrorissmooth.

Ahuh fh

Computeresidual,rhfhAhuh

r

Transferittothecoarsegrid

I

r2h

2h hh

Coarse-gridCorrection

Solvethecoarse-gridresidualequationtoobtaintheerror:

A2he2h r2h e2h A2h1r2h

Interpolatetheerrortothefinegridandcorrectthefine-gridsolution:

uhuh

Ihe2h

2h

ComputerhfhAhuh u uheh

I

e

Restrict Interpolate

h

r2h I2hrh

SolveA2he2hr2h

e2h A2h1r2h

eh

h 2h2h

05

10

Interpolationandrestrictionoperators:

05

05

010

025

10025

Ih

10

I2h 01

0

I2h

02510025

2h

05

05 h

10

05

h

010

02510

025

Linear Injection Full-weighting

Interpolation

ToolsNeeded

Coarse-gridOperator

Twomethods:

A2h .

Discretizeequationatlargerspacing

I

A

h

UseGalerkinFormula:

A2h

2h hh

I2h

uhGAhfh uhuheh

f2hI2hfhAhuh

ehIhu2h

h 2h

u2hGA2hf2h u2hu2he2h

2h e

f4hI4hf2hA2hu2h

2hI2hu4h

4h

u4hGA4hf4h

f8hI8hf4hA4hu4h

u4hu4h

e4hI4hu8h

e4h

4h 8h

u8hGA8hf8h u8hu8he8h

eHAH1fH

W循环

问题讨论

FMV循环

问题讨论

OtherProblems

Analysis

多重网格法已从理论上被证明至少对于线性的椭圆型问题(典型问题如Laplace方程)是一种最优的数值方法。

其计算工作量仅仅与网格节点数的一次方成