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

Solution Methods Iterative Techniques Lecture 6

Motivation Consider a standard second order finite difference discretization of V2u=f on a regular grid, in 1, 2, and 3 dimensions Au= f SMA-HPC⊙2003MT Solution Methods: Iterative Techniques 1

1D Finite Differences Motivation △m=b +1 6 1z=13 n points m× n matrix bandwidth b=1 Cost of Gaussian elimination O(bin)=O(n SMA-HPC⊙2003MT Solution Methods: Iterative Techniques 2

2D Finite Differences Motivation 2,y+1 了,+1, -1 0510152025 nz=105 7× points 72×m2 matrix bandwidth b=n Cost of Gaussian elimination O(b2n)=O(n4) SMA-HPC⊙2003MT Solution Methods: Iterative Techniques 3

3D Finite Differences Motivation ,k+1 2+1,,k k 了a,y+1,k 元-1,了,k i,,k-1 020406080100120 nz=725 7×× n points 3×m3 matrix bandwidth b Cost of Gaussian elimination 0(b2n)=0(n) SMA-HPC⊙2003MT Solution Methods: Iterative Techniques 4

Jacobi Basic Iterative Methods Intuitive Interpretation Instead of solving f we solve Wa+f, N1 t starting from an arbitrary u(a, 0 We expect u(m,t→∞)→u(a) SMA-HPC⊙2003MT Solution Methods: Iterative Techniques 5

Jacobi Basic Iterative Methods Intuitive Interpretation To solve at +f we use an inexpensive(explicit) method For instance 1- △22+1-20;+ t fi f=fir u+1=u+△t(f-Au)=(I-△tA)u+△tf SMA-HPC⊙2003MT Solution Methods: Iterative Techniques 6

Jacobi Basic Iterative Methods Intuitive Interpretation Stability dictates that 2 △t< 2 Thus, we take At as large as possible, i. e(At=h2/ 2) +1 2 A+。f +11 (a2+1+0-1+b2)for=1,m SMA-HPC⊙2003MT Solution Methods: Iterative Techniques 7

Jacobi Basic Iterative Methods Matrix Form Split A D: Diagonal A=D-L-U L: Lower triangular U: Upper triangular Au= f becomes (D-L-U)u= f Iterative method Dw+=(L+U)w”+f SMA-HPC⊙2003MT Solution Methods: Iterative Techniques 8

Jacobi Basic Iterative Methods Matrix Form uT+=D(L+U)u+D-If D(D-A)u+D- f (I-D-A)u+D-f +i=RJu+D-if RJ=(I-D- A): Jacobi iteration Matrix Da1=b2/2 +1 1 212+1+2-1+b2 f2)fori=1,…7 SMA-HPC⊙2003MT Solution Methods: Iterative Techniques 9