Introduction to Numerical Analysis March 16, 2009ME 501B – Engineering Analysis 1Numerical Methods for Numerical Methods for PDEsPDEsLarry CarettoMechanical Engineering 501BSeminar in Engineering AnalysisMarch 16, 20092Outline• Review midterm solutions• Review basic material on numerical calculus– Expressions for derivatives, error and error order• Numerical methods for the diffusion equation– Explicit and Implicit– First and second order time derivatives3Numerical Analysis• Want to express derivatives and integrals in terms of discrete data points• Use different methods– Develop interpolation polynomial and integrate or differentiate this result– Use Taylor series to get expressions for derivatives• Want expressions and measure of error with their use4Finite Difference Grids• Subdivide region into discrete points• Spacing between the points may be uniform or non-uniform• Example: grid for xmin≤ x ≤ xmaxwith N+1 nodes numbered from zero to N• Initial node value, x0= xmin• Final grid node value, xN= xmax• Nodal spacing Δxi=xi–xi-1(i = 1, N)• Uniform spacing, h = Δxi= (xmin–xmax)/N• N+1 nodes give N spaces5Finite Difference Grids II• Non-uniform grid illustrated below●----●-------●----------●---~ ~---●------●-----●x0x1x2x3xN-2xN-1xN• Two space dimensions require x and y grids (M+1 y nodes)x0= xminxN= xmaxxi–xi-1= Δxiy0= ymjnyM= ymaxyj–yj-1=Δyj• Most general case has three space dimensions (x, y, z, and time)Δx1Δx2Δx3ΔxN-1ΔxN6Finite Difference Grids III• Grid notation for four independent variables: x, y, z and tx0= xminxN= xmaxxi–xi-1= Δxiy0= ymjnyM= ymaxyj–yj-1= Δyjz0= zminzK= zmaxzk–zk-1= Δzkt0= tmintL= tmaxtn–tn-1= Δtn• Dependent variable u(x,y,z,t) at discrete points u(xi, yj, zk, tn)• Use notation below for this value of u),,,(nkjinijktzyxuu =Introduction to Numerical Analysis March 16, 2009ME 501B – Engineering Analysis 27Derivative Expressions• Obtain from differentiating interpolation polynomials or from Taylor series• Series expansion for f(x) about x = a....)-(!31)-(!21)()()(333222+++−+====axdxfdaxdxfdaxdxdfafxfaxaxax∑∞===0)-(!1)(nnaxnnaxdxfdnxf• Note: d0f/dx0= f and 0! = 1• What is error from truncating series?8Truncation Error• If we truncate series after m terms∑∑∞+====+=10)-(!1)-(!1)(mnnaxnnmnnaxnnaxdxfdnaxdxfdnxfTerms used Truncation error, εm• Can write truncation error as single term at unknown location (derivation based on the theorem of the mean)1111)-(!)1(1)-(!1+=++∞+==+==∑mxmmmnnaxnnmaxdxfdmaxdxfdnξεξ unknown (between x and a)9Derivative Expressions• Look at finite-difference grid with equal spacing: h = Δxso xi= x0+ ih• Want Taylor series for fi+k= f(xi+k) in terms of fi= f(xi) and derivatives at x = xixi+k–xi= [x0+ (i + k)h] – [x0+ ih] = kh.....)(!31)(!21)()(333222++++=+===khdxfdkhdxfdkhdxdfxfkhxfiiixxxxxxiiiiixxnnnixxixxidxfdfdxfdfdxdff====== ... 22'''10Derivative Expressions II• Combine all definitions for compact series notation.....)(!31)(!21)()(333222++++=+===khdxfdkhdxfdkhdxdfxfkhxfiiixxxxxxii• Use this formula to get expansions for various grid locations about x = xiand use results to get derivative expressions.....!3)(!2)(3'''2'''++++=+khfkhfkhfffiiiiki11Derivative Expressions III• Apply general equation for k = 1 and k = –1.....!3!23'''2'''1++++=+hfhfhfffiiiiiAhhffhfhfhfffiiiiiii+−=−−−−=++ 1'''''1'.....!3!2.!3)(!2)(3'''2'''++++=+khfkhfkhfffiiiiki.....!3!23'''2'''1+−+−=−hfhfhfffiiiiiAhhffhfhfhfffiiiiiii+−=−−+−=−− 1'''''1'.....!3!2ForwardBackward12Derivative Expressions IV• Subtract fi+1and fi-1expressions.....!3!23'''2'''1++++=+hfhfhfffiiiii.....!3!23'''2'''1+−+−=−hfhfhfffiiiii2114'''''2'''11'2.....!5!3Ahhffhfhfhfffiiiiiii+−=−++−=−+−+• Result called central difference expression.....!52!3225'''3''''11+++=−−+hfhfhfffiiiiiIntroduction to Numerical Analysis March 16, 2009ME 501B – Engineering Analysis 313Order of the Error• Forward and backward derivative have error term that is proportional to h• Central difference error is proportional to h2• Error proportional to hncalled nthorder• Reducing step size by a factor of a reduces nthorder error by annhh⎟⎟⎠⎞⎜⎜⎝⎛≈1212εε14Order of the Error Notation• Write the error term for ntherror term as O(hn) – Big oh notation, O, denotes order– Recognizes that factor multiplying hnmay change slightly with h)(2211'hOhfffiii+−=−+)(1'hOhfffiii+−=+)(1'hOhfffiii+−=−First order forward First order backwardSecond order central15Other Derivatives• Second-order, central-difference, second derivative()22114'''''2'''211''2.....!5!32hOhfffhfhfhffffiiiiiiiii+−+=−++−+=−+−+• Second-order, forward and backward difference, first derivatives...32342'''12'++−+−=++hfhffffiiiii...32342'''12'+++−=−−hfhffffiiiii16Other Derivative Expressions• Can derive various finite-difference expressions for derivatives– Derivative order, first, second, etc.– Order of the error (typically second although higher orders used)– Forward, backwards and central difference expressions (typically use central except at boundaries)– Derive by Taylor series manipulations– See results on page 271 of Hoffman17Order of Error Examples• Table 1 in “introduction” notes shows first derivative error for exaround x = 1– Using first- and second-order forward and second-order central differences– Step h = 0.4, 0.2, and 0.1– Error ratio for doubling step size• 4.01 to 4.02 for central differences• 2.07 to 2.15 for first-order forward differences• 4.32 to 4.69 for second-order forward)log()log()log()log(loglog12121212hhhhn−−=⎟⎠⎞⎜⎝⎛⎟⎠⎞⎜⎝⎛≈εεεε18Roundoff Error• Possible in derivative expressions from subtracting close differences• Example f(x) = ex: f’(x) ≈ (ex+h–ex-h)/(2h) and error at x = 1 is (e1+h–e1-h)/(2h) - e3105.4718282.2)1.0(2722815.2004166.3−=−−= xE9105.4597182818284.2)0001.0(27180100139.27185536702.2−=−−= xE9109.5718281828.2)0000001.0(203887182815566.287247182821002.2−=−−= xESecond order errorIntroduction to Numerical Analysis March 16, 2009ME 501B – Engineering Analysis 419Error vs. Step Size Plot• Plot the log of the error versus the log of the step size• For regions where there is no roundoff error this will be a straight line whose slope is the order of the