Mathematics Laboratory MATH M0050
Popular in Course
verified elite notetaker
Popular in Mathematics (M)
verified elite notetaker
MA 162 Pl Anly Geo Calc II
verified elite notetaker
verified elite notetaker
One Day of Notes
verified elite notetaker
verified elite notetaker
verified elite notetaker
This 171 page Class Notes was uploaded by Elna Vandervort on Saturday September 19, 2015. The Class Notes belongs to MATH M0050 at Purdue University taught by Staff in Fall. Since its upload, it has received 43 views. For similar materials see /class/208035/math-m0050-purdue-university in Mathematics (M) at Purdue University.
Reviews for Mathematics Laboratory
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/19/15
THE 3RD SYMPOSIUM ON ANALYSIS AND PDES PURDUE UNIVERSITY MAY 27730 2007 A FREEBOUNDARY PROBLEM FOR THE EVOLUTION p LAPLACIAN EQUATION WITH HEAT COMBUSTION BOUNDARY CONDITION TUNG To COLUMBIA UNIVERSITY NEW YORK NY We consider the following freeboundary problem given a nonnegative function uo de ned in R whose positivity set is a bounded domain 90 nd a domain 9 C R X 0T for some positive T and a function uz t such that utApu in9 1 ugt0 inQ u0andlDull onBQ 0lttltT u0 uo in 90 The operator Apu div lDulp 2 Du is known as the p LaplacianI This problem in the case p 2 has been studied by Caffarelli and Vazquezi In this work I will prove the following result in the case p gt 2 Theorem Let 90 be a bounded convex domain whose boundary is OFF The function u0z is concave and in C1D Qo Then there is a solution uQ of the problem 1 which exists up to a vanishing time T Moreover the vanishing time T is nite the freeboundary 89 is in C00 for positive t and this solution is unique REFERENCES 1 LACa arelli and JLVazquez A free boundary problem for the heat equation arising in ame propagation Trans Amer Math Socv347 1995 4117441 The Numerical Approximation of Solutions of Partial Differential Equations of Elliptic and Parabolic Types Jim Douglas Jr SER Visiting Professor of Mathematics University of Wyoming Laramie WY USA University of Wyoming Spring Semester 2009 Lecture 1 Two Point Boundary Problems Throughout most of the lectures on two point boundary problems we shall consider the problem given by Lu auxxcu f XE01 u g XEB01 where for some oz gt 0 aX 2 oz and CX Z 0 At times we shall assume that CX 2 oz A Finite Difference Method h 1N717 x ih m i 9h Ii Xiilyxih 1109 TJi The object is to approximate u i 0 7 N by VI7 i 0 7 N where W is determined as the solution of a linear algebraic system of the form ik ik LhWi ZBIJMj Z Yij 177N7 jiik jiik W0 5 07 WV gV Let m Hem OgnEngMpO39 From Taylor series expansions 1 pm EUR4 7 11 owmhk l k 2 or 3 1 1 xi EWHH 7 1M 7 wxxxjhz 0 11 4ooh37 1 1 dim1 111397111217 mjh200 14mh31 1 1 1 5in Eui1 i7 57L Eui i717 9in ui1 ui717 1 6Xa6yu p aiui1 7 Lli 7 317uii LI 1 Apply these relations to 11 aux and 11 u 7auxxi 6xa6fui 5h M S Miiaii3ooiiuii4ooh2 Define Lh by LhW39 76Xa67Wi i cW7 1 Then Lhuf i c7 177N717 U0 g07 LIN gN7 The finite difference equation LhW 17 W0 g07 WN gN Existence and uniqueness of a solution will follow from either of the convergence arguments to come A Maximum Principle Convergence Proof Assume here that CX 2 oz gt 0 and let z u W39 Then LhZ39 E 177N 17 20 ZN 0 Either z 0 i 0 7 N in which case the solution of the difference equation coincides with that of the differential equation on the nodes X or there must exist an integer k 1 S k S N 1 such that miaxz zk If zk gt 0 then the piecewise linear interpolant Wh of Wi is concave at in 6Xa6ywk 07 since zk 2 zkil So the error equation 6xa6fzk ka 6k implies that aZk S ka S 6k S Miiaii3ooii ii4ooh2 If zk lt 0 then Wh is convex at Xk and Mk 2 Miiaii3ooiiuii4ooh2 Thus if CX 2 Oz and ax gt O on I 1 miaxiu 7 Wii MHaiisooiiuii4ooh2 Theorem Assume that ax gt O and CX 2 04 gt O forx E I and that Ha 3 00 is finite IfHu 4 00 is finite then Huiwh 2 400h 7 1 000 S WHE 3mm 04 Where u is the solution of the two point boundary problem and Wh is the piecewise linear interpolant of the solution of the finite difference equation A Discrete Energy Estimate Proof L2 f fgfx2dxltoo H10 f1 Hin Hng llfxllg lt 00 H30 f 6 H10 1 0 1 0 with associated inner products and norms given by f7g0 fgdx7 f7g1f7g0 flt7gX07 and HfHo Wm jawx 7 l 2 2 ml f12 lax dx 7 l Hle WHLZ Hng W32 The Poincar inequality states that HfHo Owl C0117 f E H6I Denote spaces corresponding to L2I and H1I by 2 and hl with inner products and norms respectively being given by f7goh N71 1 1 E figih 5f0g0 ngNh7 iifii0h f7 iw i1 f7g1h N fvg0h Zwyfb kghh i1 l figoh 5 6ygoh7 iifiim 19 in Denote the hl seminorm on hi1 f E h1 f0 fN O by mm maxim Lemma Let f E htl Then its 2 and I norms are bounded by its h1 seminorm Wow S Wm Hmem ltW1h Moreover if g 6 htl the discrete Green39s formula N 6Xa6yfg Z gal 6715 67g h i1 holds Proof Express f in the form Then a 20 h x MM j1 and the first two inequalities follow The third conclusion can be shown by summation by parts but perhaps a more enlightening approach is to recognize the relation between 6Xa67fg and a corresponding L2 inner product Extend 3 1 to the piecewiseconstant function AX by setting 2 AX a I 1 7 X Xi717xi7 177N7 2 and let F and G be the piecewiselinear functions interpolating and g at the nodes Then AFXXG dx 7 AFXGX dx I I N 5xa5if7g Z aii wyfhwygh 77 i1 as was to be shown An immediate corollary is that llfl m f 6 hi 1h 2lf so that the seminorm on hi1 is equivalent to the full norm there The 2 convergence argument is easy Test the error equation against 2 and sum over i 1 N7 1 and apply Green39s formula aii MZ ll 6y22 h l 62 2 6 2 l 2 Here we need assume only that 312agt0 and c720 Vi Then by Cauchy Schwarz alzlih S llEllohllleoh S llEllohlZl1h7 so that lZl1h S willlgllow S a 1MallUll4ooh2 Theorem Assume that Ha gm and HuHMX are finite Then Hui WHOM Hui WH0h u7 Wm S MH3H3ooHUH4ooh2 The analysis above for error has been presented in essentially the simplest possible way consequently the theorem is not close to best possible Since the primary aim of these lectures is to treat a variety of finite element procedures for partial differential equations we shall not pursue deeper results here However it is valuable to consider briefly some extensions and possible improvements related to the finite difference procedure Inclusion of a first order term Consider the two point boundary problem Lu7auxxbuxcu f XEIO17 u g7 X613I017 where Redefine Lh as LhW 76Xa6yw biQXW C W 7 1 where 1 8xWi 2hWi1 W121 The finite difference equation Lhw 7 a 11 Nel W0 07 WN gN Then with 6 O u kmhk l k 2 or 37 Lh ifi5i7 177N17 UN gN7 U0 07 Again with z u 7 W LZ39lt 397 l39l77Nl7 ZOZN0 Rewrite Lhz l l LhZi p 3 EhbiWi1 34 t ai7Wi 1 ai EhbiWi71l CiWi 6i If Mh lt a then the maximum principle holds and z 9h2 as before We will defer the 2 argument as it is essentially the same as for the Galerkin method Variable Grid Spacing In many practical problems the use of a regular grid frequently is inappropriate Consider the irregular grid 1 0 X0 lt X1 lt X2 lt lt XN 17 hi Xi Xi717Xi71 Xi l xi717 2 and with 1544 fX 7 B 07 i extend the definition of the second order difference operator to be 7 2 Wi1 Wi Wi W121 6Xa6yw 7 apr T 7 a gt The finite difference method is defined as before LhW39 7 76Xa6yw l cW i1N71 W0g07 WNgN A simple but tedious Taylor series expansion argument shows that LhUi i7 l il S Mlllal 2Oollul 3m maxhj7 i1N71 J The maximum principle convergence analysis is essentially unchanged except for the loss of accuracy caused by the poorer estimate of 8 Only relatively minor modifications in the definitions of the terms entering the 2 argument are required in order to carry that proof through as well Hence it can be shown that llui Wllooh llui Wl oh lui W 1h S Mllal zoolllul 300 mjaxhj Since the point of using a variable grid is to localize the difficulties in approximating u the global arguments and global error estimates above fail to indicate the true value of varying the grid however we shall defer discussing arguments that localize the regularity requirements to the treatment of finite element methods Discontinuous coefficients Consider the simple example when 31 O Xlt 7 ax N l 32 XltX 1 For the original differential equation written in divergence form consistency at the point X Y requires that lim ux lim ux and lim vx lim v 7 xi XL xi XL where VX 3XUXX represents the flux associated with the differential operator If X1 lt x lt X then introduce a Lagrange multiplier to replace the nonexistent value Wm this multiplier serves to enforce the continuity of the approximate solution at x Then approximate the left and right fluxes V and Vi at x by 7 W39 7 V7 73177 VJr 732 X 7 Xiil X 7 X ie instead of thinking of the approximate solution as being linear between X1 and Xi consider it to be a broken line maintaining the continuity of the flux There are two ways to impose this concept One would be by adding the point i to the grid and require that with V and VJr as defined above VJ V For the two point boundary problem this is feasible though not altogether convenient however for several space variables it could cause a considerable modification of a computer code based on an orderly grid Alternatively we can eliminate algebraically by finding an effective value aeff iquot of the coefficient a such that gt 2 Wi W121 7 V Vl aeffgi Xi 7 Xiil Set 7X71 39yh and solve for by equating V and Vi x 7 Wiil W 7 x a 7 a 7 1 WW 2 1 Vlhi implies that 71 a a a a lt1 2 gt ilWi7172Wigt v 17v v 17v The effective conductivity coefficient is given by a lt31 32 gt 31 32 3132 1 i i 7 em v 17v v 17v 17v31v32 which is more easily recognized as the length weighted harmonic average of 31 and 32 hi 1 Ylhi aeffi7 31 32 This can be generalized to treat variable ax discontinuous or not on I by taking h X 1 7 7 dx aeffji x71 30 The definition above for an effective conductivity coefficient extends to multiple dimensions This evaluation will be seen later to correspond to the use of a mixed finite element or finite volume method Now having found aeffIil replace aiil in the definition of 6Xa6yw to obtain a definition of the second difference compatible with discontinuous a ie let 2 Wi1 Wi Wi W121 6Xa6ywi 7 hi Befri hi1 7 aefmi hi 7 and define the finite difference procedure accordingly Tihonov and Samarskii published a series of papers in the 6039s showing that this choice of the conductivity coefficient leads to improved accuracy the method then coincides with the piecewiselinear Galerkin method Tridiagonal Linear Algebraic Equations Tridiagonal systems of linear algebraic equations will arise in the discussion of a very large number of numerical methods to be treated in these lectures including the finite difference method Their solution is of course a simple exercise in Gaussian elimination Let ao cV 0 and write the linear system as ailIlii1b39W39C39W391 7 077N Forward elimination 1o Normalize the first equation 50 7617 V0 50607 70 Befo 2o For1N 5i biiai Yiilra 39Yi ich WI ism71W Then I 07 7N717 Wi YiWi1 4713 WN 4PM Backward substitution 3 ForN71O Wi 4Pi YiWi1 Let us count the operations In the forward elimination there are slightly less than N 1 divisions l 4N l 1 multiplies l 2N l 1 additions In the back solution there are N multiplies l N additions Thus there are essentially nine arithmetic operations per unknown If the same tridiagonal matrix arises with several right hand sides then the factorization need not be repeated and only the right hand side operations are required in this case only three multiplies and two additions per unknown are needed to solve the equations Lecture 2 Finite Differences for a Mildly Nonlinear Problem Consider the mildly nonlinear two point boundary problem given by XEI7 4am cx7 u H X E 8 07 07 Here a ax as before and fx has been absorbed in the the function X7 u Assume that The finite difference approximation of u is the solution of 76Xa6yw l cx7 W 07 177N717 W0 WN 07 which generates a nonlinear algebraic problem It is necessary to establish existence and uniqueness separately We shall demonstrate uniqueness first and then determine existence as a consequence of the convergence of an iteration for its solution Lemma There exists at most one solution of the finite difference equation Proof Let W0 and W2 be two solutions and set 2 W17 W9 Then 76Xa6yz l cx7 W1 7 cx7 W2 07 i 17 7 N 71 Since by the mean value theorem cx7 W1 7 cx7 W2 oil2 it follows that 2 satisfies the linear equation 76Xa6yz l oilz 07 and since cf 2 0 then uniqueness is a consequence of previous results To establish the existence of a solution of the difference equation let us define and prove convergent an iterative procedure for it We should like to choose 3 such that B gt maXcuXC X 6 I7 C 6 IR however this would require us to assume that cLl is bounded on IR Let us derive a rough bound for W Assume for the moment that W is a solution of the difference equation and let v O for i 07 N Then v satisfies the equation 76X36yVi l cx7 vi cx7 07 i 17 N 71 So W W 7 v satisfies an equation of the form 7 76Xa6yW l cjjW 7cX 07 1 Now test the last equation against W 367W67W l 63 W7 W 7cx 07 W7 Thus 1 lWl1 S gllch Ollo p7 so that any solution of the difference equation is bounded in hi1 and by the Poincare inequality uniformly on I by p Hence it is possible to modify the definition of X7 v when lvl gt p to X7 v X7 signvp without affecting any eventual solution of either the differential or difference problem Then it is feasible to require 3 to satisfy 3 gt maXcuxC X 6 I7 lCl p Initialize the iteration arbitrarily but such that iWi0i p7 1N71 W30 WIS 0 Then with W k wk O for all k let 76Xa6ywk i wim wlik lh 7 cx7 W k71 zk W00 W0917 then 76X36yzki 32 lt5 7 of 2W1 i 1 N 71 Test this against 20 35Yzk75 k 2007200 5 CE ZR17ZRgt g 6 a c zltkgt7 2 6 a c zltk1gt7zltk1gt 7 so that 1 2 1 new w 5 5 c zltkgt7 2W 1 g 5 6 e c zltk1gt7zltk1gt Apply the inequality 367272 2 39yizig 2 39szHg along with the non negativity of cu B iizmiig BHVHZ 1 Thus if 7392 B i 2y then 0 lt 739 lt 1 and iizmiio Tiizk 1iio THHzWo imply that k Wk W0 20 A W 11 Moreover 6xa6ywki WWW 7 Wk71 CXiv WakU 76Xa6yWi CXh Wi7 so that W is the solution of the difference equation Essentially the same iterative argument produces a solution of the differential problem Note also that lkl1 a O in htl analogously the iteration converges in H6 in the differential problem Then it will follow from a lemma which appears early in the treatment of finite element methods to follow that u E H2I A better iteration can be based on the expansion 86 k 7 RA 7 RA 0 7 k4 X7 W 7 X7 W 8ux W W W gt 826 2 7 k 7 k4 0 lt auz W W gt This leads to the Newton iteration given by 5X357WkCUWIlt1WIlt CWk1CUWk1Wk17 and quadratic convergence ie Hzkii0 Ciizk 1iig can be expected if the initial guess is sufficiently close to the solution W A safe strategy is to take a few of the iterations described earlier and then to shift to the Newton iteration The analysis of the error e u 7 W is trivial since e satisfies 6X3679i l ciei 5h 808N 0 1N71 7 where lsil Ma7 ch2 for uniform subintervals Thus testing against e leads immediately to the error estimate llelll cmiamihz This finishes the treatment of the two point boundary problem by finite differences in these lectures The Piecewise Linear Finite Element Method We continue treating the usual two point boundary problem Lu auxxcu f XE01 u g XEB01 now by the finite element method that is the simplest analogue of the finite difference procedures considered above Assume for the time being that the coefficients aX and CX are smooth and that f 6 L2 Also assume that aX 2 oz gt 0 and CX Z 0 Let HklzeL2l zah e u 571 k 7 idxl 7 7 7quot397 7 k z zlxzdx ilk gt and k seminorm lzllt llzkll0 As above let with norm HampI z E H1I 20 21 0 The Poincare inequality in the lemma below is slightly more precise than that given earlier Le a i Z 6 H0 then llzll0lt7 lzlli l thusll H1 and l l1 are equivalent on HampI Proof The inequality is an immediate consequence of the string X l X 2 l 1 zXtdt gxz zXt dt glezll O X E 0 0 1 and the corresponding Inequality related to the Integral from to 1 lZXl lt suffices to treat vanishing boundary values If not let E u 7 g017 X l gNX7 so that 30 31 O and E f Lg01 X gNX f gN a goiax a Clg01 x W For smooth 3 and c E L2 if f 6 L2 so that E satisfies a boundary value problem of the same form as u and vanishes on 8 In what follows the assumptions on the coefficients will not be repeated unless a change in the assumptions is desired Lemma If f E L2I then the solution u of the two point boundary problem with g 0 satisfies u e H2I m H30 Proof This is a formal proof to convert it to a rigorous proof approximate f E L2I by a sequence of functions fm C C OI converging to f in L2I obtain the a priori estimates below for the solution um corresponding to n and then let m a 00 Test the differential equation against H and integrate the second order term by parts aux7 ux i cu7 u f u7 so that by the Cauchy Schwarz and Poincare inequalities aiuii CLAN S iifiioiiuiio S Ciifiioiuil Thus Huiil Ciifiio Now for smooth coefficients auxx f 7 cu 7 axux7 and iiUxxiio S C iifiio iiuii1 C iifiim as was to be shown Lecture 3 Next let us consider the approximation of a function u E H2I by continuous piecewise linear functions Let 0X0ltX1ltltXN17 I39X391X397 hiX397X391 Define the piecewiselinear interpoant Ju of u over the partition Xi to be 7 Ui71 Jux u1 i ui h X7 X17 X E I7 i 17 7 N Lemma If u E H2I and Ju is its piecewiselinear interpoant over Xi then N 2 uiJu C u2dxh1 cu hz ii iio L xx i i2 N iuiJuil S CZuixdxhi S Ciuigh7 i1 where h max hi I Proof This lemma is a very special case of a general approximation lemma called the BrambleHilbert lemma Set Ju v and consider the approximation on the subinterval I By the mean value theorem there exists a point 5 E I such that L545 Hi ihlliil VXX7 X E I 7 so that vx u1 l LIXEX7 X17 X E I Then the Taylor expansion with integral remainder gives 00 iil l uxi71X Xi71 l X t7X1uXXtdt VX Um71 7 uXEX exisl t 7X1uxxt dt 5 vx7X7X1X uxxtdt fixi1uxxtdt 1 X71 Then by the trivial inequality 3 l b2 2a2 l b2 and Cauchy Schwarz X X U7 v2x 2 tixi12dt ugh dt 71 X71 x 2X 7 X12E 7 Xiil 6 Mix df X71 l A 2 7 X 13 hiX 7 X 12 LI X df I Integrate this inequality over the left half lilof I 3 7 2 lti 2 Izu v XdX7 64h IZ uxxdx A similar bound holds for the right half of I so that adding over the subintervals leads to h max hi 3 V 3 7 2lti h 2d lti 2h llu vies IUxx X764lul2 7 Hence N uiv 7 h lu2 dx gCu hz ii Ho 8 L iiz Next let us estimate iu 7 vil Differentiating the expansion for ux gives 5 u 7 vxx iX um dt x 7 x1uxxx so that uxivx2x 2 gagg u xdtX7X12u xx Integrate over I uxivx2 dx 2 hi u x dt hIZuixx dx 4h2 HEX dx 1 l l 1 Adding over subintervals and taking the square root gives 1 N 2 u7v1 2 hIZu2 dx 2u2h lex H Now let us turn to the formulation and analysis ofa Galerkin finite element method based on the piecewise linear approximation space Mh v E C0I v is piecewise linear over X A basis for Mh is given by the hat functions 11 EMh i0N where 11 Xj6ij7 i7j077N Mhov Mh v0vN0 dith N l 1 and dithp N71 Galerkin finite element methods are associated with weak forms of the differential problems If our equation is multiplied by a function v and the second order term is integrated by parts and the homogeneous boundary condition applied the result is the equation Au7 v aux7 VX l cu7 v f7 V In order that the equation make sense u and v should belong to HIU For the boundary condition to be satisfied by u we need to have u E HampI Since the boundary condition is strongly imposed on u it suffices to require that v E HampI So the weak form of the two point boundary problem related to the bilinear form A7 is given by seeking u E HampI such that Auv 1 7v7 VV 6 HampI Other weak forms of the differential problem will be introduced later and associated with other types of finite element methods It is a standard topic in the study of differential equations ordinary or partial to determine the relationship between the solutions of weak forms of boundary problems and of their strong forms The hypotheses that we have imposed on the coefficients and the data function f are adequate to imply that the unique solution of the weak problem is such that u E H2I HampI and consequently satisfies the original strong problem The basic idea in the Galerkin method is to take a subspace of HampI such that functions in H U or in H2I H3I can be approximated closely We have seen that a function in H2 O H6 can be approximated by its linear interpolant which is in Mhp to 9h in H1 and 9h2 in L2 Thus it is reasonable to seek an approximation of the solution of the weak form of the boundary problem in Mm though we shall temporarily delay consideration of the rate of convergence of the approximate solution as the mesh spacing h a 0 Repeating the Galerkin finite element approximation Wh 6 M of the solution u is the solution of AW17 v awhx7 VX l CW17 v f7 v7 VV 6 Mm The problem is linear and finite dimensional LemmaThere eXists a unique solution of the Galerkin problem on Mhp Moreover the Galerkin solution is bounded 1 lWhl1 S llfllo 04 Proof Test against Wh alWhlg S aWhX7 Wxh CWIM Wh f7 W S llfllOlWhlh and all three conclusions follow Before proving convergence as h H 0 let us consider the algebraic problem generated by this Galerkin method The matricial equivalent of the inner product form of the Galerkin problem can be derived as follows The solution has the representation N71 Wh Z W UlX j1 this leads to the equations N71 N71 ameJMLX chwjwi fw i1N71 F1 11 Set O iJ a jX7 ixC j71Ji7 WI leiii Let A be the matrix with entries 04 and let W and 4p be vectors corresponding to W and 4 respectively Then the inner product form is equivalent to the linear algebraic equations AW 4p Since the supports of 15 and 1 do not intersect unless li ijl 1 the only nonzero elements in the ith row of A are 0431217 04313 afld aii1 Thus the tridiagonal matrix algorithm applies to the matricial formulation It will be convenient to consider either of the two equivalent formulations of the Galerkin method interchangeably in the discussion to follow Note first that both formulations are in terms of positivedefinite symmetric operators symmetry is obvious positive definiteness follows from the fact that alulg Au7 Comparison of finite difference and Galerkin methods Let us construct the linear equations explicitly in the case of uniform subintervals Note that the integrals in matricial formulation all are over intervals of length h or 2h and consequently contain a factor h and we need to compensate for this factor to give a closer comparison between the finite difference equations and the Galerkin equations Since h 1XXH7 xHltxltxJ 11JX hilogurlix7 Xjltxltxj17 then 1 awiilx phx 7 axdx7 h l 1 3 i1x7 ix pI axdx7 1 aipix lzlhx p u 3XdX 4311121 whx 7 a i1x7 ix and Ma4715 cxx 7 XX 7 X1dx7 c1111 p cxx 7 X12dx L1 cxx1 7 X2dx7 1 CiMHWI 77 cxx 7 xx1 XdX39 Let 1 5i E3 i71X7 ix7 I3917N7 and EJij7 i7 ji71ii1 i1N71 Consider the special case of the two point boundary problem given by quXu f xel u 07 X68 Then the Galerkin equation reduces to 1 pWi1 2W W121 1 2 1 1 5Wi1 gWi EWH EUMML I 177N17 whereas the finite difference equation reduces to using W to denote its solution 1Wu172wiw1W 1N71 hZ Thus the second order term is the same in the two equations the zero order term in the finite difference equation is replaced by a Simpson quadrature and if the function f is interpreted to be its piecewiselinear interpoant the right hand side is also replaced by a Simpson quadrature The effect of shifting from finite differences to Galerkin finite elements is that the lower order terms in the equation get smeared a bit While this appears to be a minor perturbation we shall see that the solution of the Galerkin method maintains second order accuracy 9h2 for variable spacing in the grid Xi which is not in general true for the finite difference method It also requires less smoothness of the data in order to obtain this accuracy H1 and L2 Analyses of the Error in the Galerkin Approximation Since MILO C H U it follows that the error 2 u7 Wh E H6I satisfies the equations Au7 v 7 AW17 v Az7 v azx7 VX l cz7 v 07 V 6 MM We cannot assume that z 6 MM so that we cannot decide immediately that z 0 However we can write 2 in the form Z CCWh7 EAhp Then AWh7C7 v Au7C7 v au 7 OX VXcu 7 C v7 V 6 MM Since Wh 7 C 6 MM it can be employed as a test function in the equation above 04Wh CE S AWh C7Wh C A C7Wh 0 MH CH1HWh CH17 where we have assumed that maxax7 cx M lt 00 Thus there exists a constant K such that HWhiC h S KHU CHh VC Mh0 HLHWhHl HUC1HWhCH1 1 KW 7 Nb VC 6 Mm Since the piecewiselinear interpolant Ju of u is in Mhp 1 2 ciuizh N llui Whlll S 1 KllUJUll1 S C l i1 where h max h and 1 dku 2 g kBltBltWgt dxgt BCI Note that the error estimate naturally localizes by involving estimates subinterval by subinterval l u The Hl inequality is the energy norm estimate of the error and frequently is the error estimate of greatest interest in engineering or scientific computations Note that the error is bounded in terms of the local smoothness of the solution and is optimal in the sense that it can be proved that if there eXists a sequence Mhmo of piecewiselinear spaces on I for which 1 h maxh O and inf ui 7 0 n I a Wm H CH1 h a 7 then u must itself be piecewise linear and the points at which the slope of u is discontinuous must belong to Xmi for n sufficiently large Let us look for a bound on llu 7 While This can be accomplished by means of a duality argument as follows Our current differential operator L is self adjoint so that its adjoint L is equal to L Let 4p 6 H2 O H6 be the solution of E0 W Xk l C4 L Wh Then ll pllg Cllu7 while So ll Whllg Uquot Wm WM Uquot W awxlx CW Au 7 Wh74p Au 7 Wh74p 7 v7 V 6 MM Thus ll Whllg S Mllui Whlll ll 7 Vll17 V E Mme Since inf ll Vll1 S Clwlzh S Cllu Whlloh 0 VEMqy Hence 1 2 any h Clulghz N iiue While clue Whilth c Du i1 Again this is an optimal order estimate for the error in L2 since llu 7 While 0h2 implies that u is piecewise linear We are unable to localize the h lifting of the H1 error estimate to an L2 estimate by this argument The analysis was given under the simplification that u O on 8 if instead u g7 X E 8 all that needs be done is to impose the boundary values on Wh and modify the Galerkin method to require finding Wh E Mh such that AW17 v f7 v7 V 6 MM Wh g7 X E 8 Note two things First the test space remains Mm since the two additional degrees of freedom in Mh over MILO are specified by satisfying the boundary values Second a glance through the error analysis shows that the same error estimates will follow Let us collect the error bounds into a theorem Theorem Let u be the solution of the two point boundary problem and Wh that of the Galerkin approximation Assume that the coefficients a and c are smooth and that ax 2 04 gt 07 CX 2 07 maxax7 cx M lt 00 Then there exist constants C such that N lluiwhlll S CZlu i1 llui Whllo lt Cllui Whlllh 7 4 3117 S Clulzhi l A 2 gm h Clulghz Lecture 4 L analysis of the Galerkin error Continue studying the piecewise linear Galerkin approximation to the solution of the boundary value problem Lu7auxxcu f XEI7 u 07 X687 and continue assuming that a and c are smooth and that ax 2 04 gt 07 CX 2 Oand mlaxax7 cx M Recall the Green39s function CE7 X l X where I E H6I satisfies the equation LquotX LU 5amp7 where E 6 01 and 6g is the Dirac measure at the point 5 More conventionally I can be defined as the solution of the system 7aI39XX i ci 07 X 6 05 U 517 It is easy to see that 39 6 H6 H207 H2 717 though it is not in H2I as a consequence of thejump in aI39X at E Let J H1I a M denote the operator interpolating functions in H1I into Mh for convenience we shall let JV denote the piecewiselinear interpolant of the grid function vi as well Let E X a node in our partition of I Then it follows from our approximation lemmas that now with GX7 1 HP Jriio W will 6 him him 2 h where as before h max h Now note that for any v E H6I vx V6X v7 L39 Av7 I39 Thus if Wh is the solution of the Galerkin equations then Hi Whli A Whi r A Whi 39 i 7 C E Mao and u 7 W lt C U7 W inf I 7 h 7 ii hiilCEMWii CH1 S Ciui2h iii Jrih Ciuiz iri oxiri x1gt2 h If in each partition XJn with h a 0 there exists a node inn Xi we have proved that the error in the Galerkin approximation is 9h 2 at that fixed point what is needed is a uniform bound on the term in the parenthesis in the inequality above Lemma There is a constant K such that mam mam K 0 lt 5 lt1 Proof Since 390 O and I is not identically zero aI39XO cannot vanish if it did then I would vanish on 05 and aI39X 71 Then there eXists an interval 57 7 gt E on which I lt 0 Then aI XXCl ltO7 E X 7I7 which implies that I39X decreases on 57 which in turn implies that I decreases on 57 so that it follows that 7 1 and that 391 lt 0 which is a contradiction A similar argument shows that aI39XO gt 0 Working back from X 1 shows that aI39X1 lt 0 Hence I increases from zero at X O to a maximum at X E and then decreases to zero at X 1 Thus it follows from the jump condition on aI39X that gt0 0lta Xxlt1 0ltxlt5 gt0 71lta39xxlt0 ltxlt1 22 xx Thus I39X and I are bounded on I independently of E 6 01 Then 1 I39XX 73axl39x 7 cl39 is bounded for all 5 6 01 and all X 6 05 U 51 which is stronger than we set out to prove This lemma leads to gCiuighz i1N71 Mn 7 Whi 7 where the constant C is independent of the partition With JWh indicating the piecewise linear interpolant of WM then HJLliJWh 0 lt Ciuighz since the extrema of piecewiselinear functions occur at nodes So HuiJWh 000 iiJu 7 th 000 Ciui2h27 000 0 HuiJu HuiJu and we need to bound ui Ju in L I djv Koo co co 39 W I7 V6 L I TX 6 L 01717k with associated norm k k iiiHm Z ivijpo 2 10 j 0 djv dxj 000 The restriction of these norms to a set B C I will be indicated by iiViikpoJB Lemma If u E W2gt I then Hu7JuH0m mlax u7JuH0mJ C miaxu2OOJ h2 Qu gmhz Proof Let X E I Then g X H 7 Jux 7X 7 X uxxdt t 7 X1uxxdt7 X71 X71 where 5 lies in I Thus 1 UiJUXXN S Xixi71HU2ooIhi E u ZpoJhiz S C u ZpoJhizv as was to be shown The immediate consequence of the above lemmas is the following theorem Theorem Let the solution u of the two point boundary problem be in W2gt I Then llu 7 JWhllopo lt Clulgmhz This completes the discussion of the piecewiselinear Galerkin method except for an observation concerning the very simple differential equation Lu iuxx f The Green39s function for this operator is piecewise linear with 39 G E 517 5 Obviously I39XX O for X 7 5 Thus for this equation Wh39LI397 Higher Order Galerkin Methods We shall treat Galerkin methods for the two point boundary problem based on piecewise polynomial subspaces of Hampl again associated with a partition I X1X7 i 17 7 N Let M5 v 6 cm v lle PrI i 1N n k1 where is the set of polynomials of degree at mostj on the set B The most interesting cases are given by C 0 piecewise 7 polynomial spaces7 Hermite piecewise 7 polynomial spaces7 Spline spaces CO Piecewise Polynomial Galerkin Approximation Consider the space Mao v 6 M9 v0 v1 0 over the partition with nodes 0 X0 lt X1 lt lt XN 1 Let us define a local basis for Mao which we shall do first on the reference interval 711 Let 1 1 190 51X7 190r 1X7 19 17x1xx1117x2x11 j1n71 Note that 1940 and 190 represent the right and left halves of the piecewise linear basis functions on 711 respectively Lemma Pn711 Span190190191 19n11 Proof lt suffices to consider Xk k 07 n Now 1 1940 190 and x 190 7 1940 If k 2m n is even then Xk 71X2m 711717X2X2m72 X2m74 H139 Similarly if k 2m1 n is odd Xk XXX2m 7 Xi 7X2X2m71 X2m73 HX7 which by induction establishes the lemma Bases for M9 and Mao can be described as follows 1 For i 07 7 N let who be the hat function at X 13009 607 j 07N 2 Set M SPanwm 0N M30 Span p517 17 7 N 71 3 For1N let 2 iJXI9jltFX7Xi171gt7 117n71 4 Then M2MSpan1JJ 1N j1n71 Basiswgo Basiswg wopww In order to estimate the error in the Galerkin approximation to be defined below it is necessary to understand the best approximation properties of the space M20 These can be summarized in the following lemma the proof of which will be given ater Lemma Let v E Hkl H U for some k such that 1g k g n i 1 Let the partition Xi be such that max h g h Then there exists a constant C independent of the partition Xi and v such that inf v7 hv7 ng hk lt6Mio i Ciio ii CH1 i ik If v E Wkgt l HampI where 1 lt k n1 then there eXists a constant C again independent of the partition and v such that 39f 7mh7mltc oohk Ewgy iiv He iiv CH1 ivik The Galerkin approximation Wh E Mao to the solution of the self adjoint problem Lu 7auxx cu f X 6 I7 07 u X687 is defined in like manner to that in the piecewise linear case find Wh 6 M20 such that AW17 v awhx7 VX l cw17 v f7 v7 V E Mao The H1 and L2 error analyses given in the piecewise linear case can be repeated very easily Note that again Au7 Wh7 v au 7 Whx7 VX l CLI 7 Wh7 v 07 V E Mao so that it will follow that llui Whlll Cceijnil l0 llui H1 Clulkhk l7 1g k n17 if u 6 HR H6 The duality argument can also be repeated in an analogous manner to that for the piecewise linear case so that llui While Clulkhk 1lt k n 1 Let us generalize the problem somewhat by adding first order derivative terms to the equation Lu 7auxx 7b1ux l bgux l cu f X 6 I7 u O X E 8 7 The bilinear form on H6 x H6 associated with it is A 7V auX7VX b1u7VX bQUX7V CU7V7 which is no longer necessarily symmetric or positive definite Assume however that the differential problem possesses a unique solution for f E L2I and that the regularity result llullz Cllfllo holds The Galerkin approximation Wh remains being found as the solution of AW17 v f7 v7 v 6 M20 Since it cannot be assumed that Av7 v 2 alvlg it is necessary to prove that the Galerkin problem has a solution or equivalently that uniqueness holds for its solutions So assume that z E Mao satisfies Az7 v 07 v 6 M20 Then 1 0 14272 Z alzlg Clzllllzllo MS 2 gallzllg Cllzll37 or lllel S CllleO Now invoke a duality argument Let 4p 6 H2 O H6 be the solution of PM aka wa 7 bwk cw Z By the regularity assumption above ll pllg Cllzllo and MS 27 PM AZ7 w AZ7 7 XL X E Milo Thus llleg S Cllzlll ian llwixlll S ChllzlllllzllO XEMnb Thus llleo S Chllzlll S ChllzllO Thus for h sufficiently small llzllo 0 and uniqueness is valid and we have proved the following lemma Lemma There exists a unique solution to the Galerkin problem for the two point boundary problem including first order terms for h sufficiently small Lecture 5 A new argument along the lines of the uniqueness argument just presented must be given to bound the error this argument will develop the bounds in L2 and H1 simultaneously and begins with a duality argument Let 4p 6 H6 be the solution of L4p u 7 Wh Then ll pllg Cllui while and llui Whllg U 7 Why PM AU WW AluiwmwiCL EA1207 so that lluiwhllg S Clluiwhlll inf llwi lll S Clluiwhlll ChlluiwhllO EAlie Hence Hu 7 WhHO CHu7 Whth C u 7 Whhh Now the fundamental error equation Au 7 Wh7 v 07 v E Mao implies that AW 7 c v 7 Au 7 c v v e M2107 c 6 M29 So with v Whig AWh C7Wh C A C7Wh 0 S ClluiClllllWhiClll S CluiClllWhiCh For v 6 H1 a simple calculation shows that Avv 2 v 2 2 2 2 0 1 C llVllolVl1 l llVllO 1 2 2 gaivil 7 Chile Relations of this type one of which also occurred in the uniqueness argument above are known as Garding inequalities in the study of partial differential equations another of their typical uses will follow 1 galWrCl S C LI ClllWh Cll llWrCllgl CluidllWrClwllu7CllSllu7WhllS ialWrCl CUluiCll lluiwhll sothat ialWhiCECllui ll hzluiml Then lWrCl lui lg C llui ll hzlui W l Whl S S Thus for sufficiently small h lui Whll S ClluiClll Hence by the approximation lemma if uermHg 13kgn1 then lui Whll C inf lluiClll S Clulkhk l 6Mo We again have an optimal order energy estimate for the error in the Galerkin solution Moreover an optimal order estimate in L2 is an immediate consequence of the estimates above We can summarize these bounds in a theorem Theorem There exists h gt 0 such that for O lt h lt h there exists a unique Galerkin approximation Wh E Mao If u E Hkl H6I is the solution of the boundary value problem for some k such that 1 lt k g n 1 then there exists a constant C such that for O lt h lt h llui While hllui Whlll Clulkhk 1lt k n 1 The Matricial Problem for the CO Galerkin Method Recall that MSOM0Span19J i1Nj1n71 The support of 197 j 1n 71 overlaps exactly those of 1914 190 and 19A 1n 7 The matrix generated by the Galerkin problem is block tridiagonal and the resulting linear algebraic equations can be solved by an obvious block generalization of the Gaussian elimination scheme discussed earlier A more efficient solution technique which is known in the engineering literature on finite element methods as static condensation can be devised quite easily For i 17 N consider the set of linear equations corresponding to AWh719ixjf719ixj7 j1n71 These equations can be solved for the coefficients of j 17 n 71 in terms of the coefficients of the hat functions at X1 and X plus right hand side quantities These can then be substituted into the equations generated by the hat functions Then the remaining equations for the coefficients of the hat functions is just an ordinary tridiagonal system Ie change the order of elimination in the Gaussian procedure The Hermite Piecewise Polynomial Spaces One important property of the CO piecewise polynomial spaces M9 0 n 2 1 is that the basis elements have support on either one or tIO subintervals ln constructing a code with one of these spaces it is easy to associate n basis elements with each node X1 namely the elements 19F and 19 j 1n 71 The Hermite piecewisepolynomial spaces have the property that the support of each basis function consists of two adjacent subintervals The degrees of freedom are associated with nodes Fewer degrees of freedom need be associated with each subinterval for the Hermite case than in the C0 case The standard Hermite spaces are given by HkM n n2k1 k12 The most commonly used Hermite spaces are the Hermite cubics H1 and the Hermite quintics H2 and most of the discussion below will be limited to these two examples Note that the local degrees of the Hermite spaces are the minimum possible in order to have Ck continuity at the nodes since k l 1 constraints are generated at each node by the the continuity requirements Thus there are 2k l 2 constraints imposed on the polynomial on each subinterval thereby requiring a polynomial of degree at least 2k l 1 on each subinterval Let us construct local bases for H1 and H2 Consider the cubic case first Let 7 01 be the reference element Then we need to represent a cubic function on T by the degrees of freedom consisting of its values at X O and 1 along with the values of its first derivative at the same points It is easy to see that the two basis cubics associated with the left hand end of are given by VAX 17 X21 2X and SAX X17 X27 the value and slope basis elements at X 0 respectively ie VAU 1 and Slf0 1 and the remaining three degrees of freedom for each vanish The basis elements associated with X 1 are given by VX X23 7 2X and X X2X 71 Now let us scale these basis functions to be applicable on I U I1 X1X1 where we do not assume that the subintervals have equal lengths The value basis function at X is straight forward V 7 7 X E I7 v hi 1 X 7 xi 6 I 7 X i hi1 1 The slope basis function 5 must be scaled so as to have derivative one from both sides of X thus his xe Ii 5139X I X 7 X hi155 X E I 1 i1 Next consider the basis for H2 on the reference element Here we need three basis functions at each end of the reference element corresponding to the value the slope and the second derivative of the quintic polynomial at an end point The left value basis function can be assumed to have the form V1X17 X31 ax l bxz A short calculation shows that to have Vl 0 Vl 0 0 it is necessary that V1X17X31 3X12X2 and VX Vl17 X7 where VX is obtained by symmetry The slope basis function SI takes the form SAX X17 X31 ax Again a short calculation and symmetry show that SAX X17 X31 3X7 X 717 X Let Kg and Kr denote the second derivative or curvature basis functions Then Kgx xz 7X37 KX Kl17x Now consider scaling these functions to the two subintervals abutting at X Then set V 7 X E h v hi 2 X 7 X VI 7 X E li1 hi1 mslt l xeh 52iX 39 7 X E li1 mltii igt xem hi H2iX 7 7 X E I 1 Given these basis functions it is easy to write down the H1 and H2 interpoants of a function u E C2I uivk ilxl l ulsk ilxllll Dill0 ul nk iX7 ll ll N Jkuxx MZ ll 0 I Optimal order approximation properties for these interpoants will be proved later but will be used in the convergence analyses below The bases for 77 and Hg are obtained by deleting v and kaV from the bases for 775quot Note that the slope and second derivative basis functions at the endpoints of I are retained in the basis for 2 H0 The Hermite Galerkin finite element method is defined by seeking a solution Wh 6 Hquot of AWh72 aWhX7 Zx b1Wh72x bZWhX7 Z CWhiz 1 727 z 6 H5 The analysis of the error in L2 and H1 was reduced to approximation estimates in the treatments of the Mao Galerkin methods both for n O and for n 2 1 and nothing changes in those arguments when repeated for the Hermite spaces except for the approximation results The following approximation result holds inf ui hu7 ltCuhl7 Mg l Cllo i cm lll ifueH forany such thatk nl2k2 Consequently the following theorem is immediate Theorem Assume that the differential problem is HZ regular ie if f 6 L2 then u 6 H2 Then there exists h gt 0 such that the Hermite Galerkin problem has a unique solution for O lt h lt h Moreover there exists a constant C independent of the partition and u such that ll Whllo hl Whll S Clulzhli if0lthlthueH and k nl2k2 The L00 error estimate requires a different approach from that presented for the self adjoint problem as approximated by the piecewiselinear Galerkin process and will be delayed The linear algebraic equations generated by the Hermite Galerkin method are block tridiagonal since each basis function has support in two intervals adjacent to a node The blocks are 2 x 2 for H1 and 3 x 3 for H2 or more generally k 1 x k 1 for M20 n 2k 1 gt Some Extensions Let us address the question of discontinuous ax again For the concepts it suffice to consider ax to be piecewise constant and consistent with the partition ie let 3X3i7 xeli i1N Let us look at the Hermite cubic space 77 There are two possible remedies for requiring the continuity of the first derivative across a jump in the coefficient a The obvious one is to relaX the smoothness at a node across which a is discontinuous and just to require continuity of the solution at these nodes It is trivial to modify the definition of the interpolant in the intervals abutting this relaxed constraint with the result that the convergence theorem can be restated with the error bounds being treated locally subinterval by subinterval as obtained in the approximation arguments earlier for the Hermite case with smooth ax However a more elegant and computationally simpler remedy is to modify the space 77 by replacing the slope basis function 5X by lhisr 7 X 61h sax ai hi I in 5 PM xel ai1 11 l hi1 7 11 Making this modification in the basis is simply imposing the correct flux consistency condition on the finite element space There is no difficulty in extending the convergence theorem to this modified Hermite cubic Galerkin approximation again the approximation results need only to be applied locally Galerkin Approximation by Cubic Splines Given the usual partition 0X0ltX1lt ltXN1 Let us define the Sn spline space over Xi to be M l for n 2 3 Call 3 3 M the space of cubic splines We shall confine our treatment of splines to the cubic case Let us construct a basis for 33 Note that the constraint that v E 3 3 lie in C2I requires three constraints on v at each endpoint of a subinterval I thus it is not possible to give these values for a piecewisecubic function at a point X and then have enough free parameters in the two adjacent subintervals I and I1 to localize a basis function on I U Ii1 Consequently the support of a basis function to be associated with X must spread over XijXj wherej is an integer to be determined by the Cz constraint The number of parameters needed to define the cubics in a basis function bX needs to equal the number of constraints related to the nodes between Xiij and Xj gt Total parameters 4 per intervalx 2 intervals 8139 gt Constraints i At X Xiij biXiij blXiij biXiij 07 ii Atxiig 4111121 bllklxf bfker k 012 12 11 1 71 iii At xi bib biX 17 blkxi7 k 172 iv Total constraints 6j 4 Thuswe need 8 6 i 4 orj 2 so that a basis function to be associated with X should be constructible on the set X2X2 The basis function bX on lisl X2X1 must take the form b X 041X 7 X 237 X E 717 since blikX2 O for k 012 Then on I biX 04lX 7 X1223 BAX 7 Xi7137 X E Ii since this combination agrees through the second derivative at X1 Similarly biX 04rXi1 7X37 X 61427 b X OzX2 7 X3 BX 1 7 X37 X E hurl There are four parameters remaining in the expressions above and there remain the four conditions at X X A short calculation shows that the constraints lead to the following four equations IA721 hi3 zh 1 04rhi1 hi23 rm31 Old721 hi2 5N7 04rhi1 hi22 BrhiZJrl 04lhi71 hi Blhi 04rhi1 hi2 rhi1 7 1 07 0 For the special case of a uniform partition by symmetry bX b 7X and bX 0 so that the system above reduces to the pair of equations 800 l Br hisv 40 l Br 07 which has the solution Thus bX is given by 1 lxixil 3 lxixil 3 Z 27T 717T 0ltlX7Xillth7 bilxl 3 1 lxixil Zlt2iTgt hltlxixllt2h Thus the basis function b is a smooth bell shaped function and it should be possible to interpolate a smooth function in terms of cubic splines Next consider a different special case In many if not most practical problems described by differential equations the solution has regions in which it varies slowly and regions in which it varies rapidly and can have rapidly varying derivatives For these problems it is natural to employ a variable grid spacing and it is of interest to discover the behavior of b where the spacing changes Let hi4 hi 5 lt17 hi1 hi2 1 Then the equations for the four parameters reduce to 804 Bl 5 37 804 Br 17 452W 62m 4a 6 7 26041 5B i 200 7 7 0 l o 726 7 126 04712637 527 3637 7126 7 26 6 126 3639 Consequently as 6 a 0 b X391 X 1126 whereas for a uniform partition ie for 6 1 bX1 25 As a result it is most likely that an attempt to represent the approximate solution of a boundary value problem in the neighborhood of a strong change in spacing in the partition will lead to oscillatory behavior which is of little practical use Thus we are motivated to restrict our consideration to the case of a uniform partition and relatively smooth solutions of the underlying boundary value problem Lecture 6 The transparencies for Lectures 1 5 are available at wwwmathpurdueedudouglas Click on math598C and then on Lectures1 5pdf It is also difficult to take a discontinuous ax into account Thus it seems not too likely that a cubic spline Galerkin method is the ideal way to approximate the solution of a realistic physical problem having a solution with significant character However for the sake of historical completeness we shall analyze the procedure Note that there are many applications of splines in one or more dimensions that are very appropriate though most do not involve differential equations Before going to the differential equations problem let us consider interpolation by cubic splines Assume a uniform grid X ih Note that the basis functions corresponding to X71 and XN1 two nodes external to I are nontrivial in I There eXist a large set of suggested remedies to account for having these basis elements in the interpolation process most of these suggestions involve making some assumption as to the behavior at the end points of I of the function being interpolated Seek an interpolant that is given a function fx on I let us look for a cubic spline N1 Bx Z emuX i71 such that Bxf7 i0N Clearly these relations do not uniquely determine B since we have only N l 1 equations in N l 3 unknowns If f is reasonably smooth then we can augment the equations by requiring that the slopes be matched at the end points then the interpolant would be determined by the equations Bf7 I39ON7 BX fX7 X 01 Order these equations by taking the B O f 0 equation first then the B f equations in order and finally the B 1 f 1 equation last It is easy to see that this system of linear equations is fivediagonal and is nonsingular A simple extension of the tridiagonal Gauss solver handles these equations efficiently It is however nontrivial to show that this interpolant has optimal order approximation and a different type of approximant will be constructed to demonstrate the optimal order approximation properties associated with cubic splines Let us develop a basis for 3 8 v E B3 v0 v1 0 Now the basis elements b1b0b1 can be replaced by two entries b3 and bi that vanish at X 0 b3x b0X e 2b1x b1x 1 X 3 3 x x 3 l X 3 32 is gil ij2i lt1Egt OltXlth Z 5 E gt hltxlt2h Similarly replace bN1bNbN1 by bivi1 and where hive 1 X bfv X bN71X bN1X7 bNX 2bN71X bN1X Then a basis for the N 1 dimensional space 3 8 is given by 3 8 Spanb87 bf b2 7 qu7 by17 biv7 and the cubic spline Galerkin approximation can be defined as the solution Wh 6 3 8 of the equations AW17 v aWthX l b1Wh7VX bgwhx7 v l cw17 v f7 v7 v E 38 The analysis of the error ui Wh can as usual be reduced to approximation and the bounds to be derived later can be applied to show that ll Whllo hllui Whlll S Clul4h47 when h is sufficiently small as to assure the existence of a solution of the Galerkin equations input part3 Elliptic and Parabolic Finite Difference Methods A Model Elliptic Problem Consider the Dirichlet problem iAu f x e o 01 M 07 X E 89 Let 1 hN7 XIh7 yJJh7 xijXyj Denote the discrete Laplacian by Ah where 1 2 2121 Zi1J Zixjil Zij1 42039 AhZL j 5yx5yy2ij h f0quot 4 We shall consider the simplest finite difference approximation of the model problem AhWij 1533 W 07 X0quot 6 Qh X0 6 Q X0quot 6 89h X0 6 Convergence analysis 2 estimates As in the treatment of the two point boundary value problem we shall not attempt to give the sharpest possible error estimates for the finite difference approximation Now Ahuij fij 807 X E 917 where 6039 0 UL 49072 Then if e0 My 7 W0 the error equations are expressed by iAheU 8039 X0 6 Qh e0 07 X0 6 89h Set Vh ivh 5757 5W 5757570 N71 N71 N I 675057770 2 257505777th 1 11 i1 j1 The Poincare inequality holds again 1 2 N71 Mile 5 SClthEllm sens iJ1 where hi1 E E 2 EU 07 xij 6 89h In a single space variable lthEllo dominates llEllom however in more than one variable it does not Now test the error equation against e Ah e Vhethe 679 S llEllollello By the Poincare inequality lthello S llEllo S Clul4ooh27 llello S Clulmohz These bounds can be collected in the following theorem Theorem Assume that lu 490 lt 00 where u is the solution of model Dirichlet problem Thenif W is the solution of the finite difference approximation llui Wllo WW 7 Mile S Cl 40th Lecture 7 Convergence analysis an 600 estimate The 6 analysis is based on the following maximum principle Lemma Let 2 be defined on Qh U 89h and assume that Ahzij gt O on Qh Then max 2039 maxzij mam am Proof If 2 were to have a maximum at a point xij E Qh then Ahzij 0 Now consider the auxiliary function Z i0 W for which Ahzij 1 Note that iAheiji S Ciuizumh2 1 Let C 39y i 72 i e where 7 gt 0 then AhC vnAheZ vnvgt 07 so that am 35 W 77gt ltv 77 Thus 9039 S vnzueij S vn7 V77 gt 0 Analogously 79 g 39y i n2 and 1 Heiiom 5v ciuiimhz Theorem If the solution u of the model Dirichlet problem is such that lu 4 00 lt 00 and W is the solution of its finite difference approximation then llui W 4mh2 000 Cl Actually we proved a bit more Replace 39y by v ng xlAheo39ly which for less regular u can fail to be 9h2 Then we have shown that llu 7 W 000 S Y The Finite Difference Algebraic Equations Order a vector corresponding to WU as follows 7 tr W 7 W117 W127 7 W1N717 W217 7 W2N717 7 WN71N71 Then the difference equations for the model problem can be written in the form Awf where each row in A has at most five nonzero entries however two of the diagonals are removed by N 71 places from the principal diagonal with the other two being adjacent to the principal diagonal Thus if the equations were to be solved by standard Gaussian elimination the factorization of A would require 9N2 arithmetic operations for nearly all of the N7 12 equations The back solution requires 9N operations per equation Consequently the total work required for Gaussian elimination would be 9N4 operations This leads to investigating iterative methods to see if cheaper techniques can be devised 1 There are many possible iterative methods 2 Each method needs to be effective for the algebraic equations associated with more general problems than the simple equations given by the model problem 3 It can be useful to consider the model problem since both the formulation and the analysis of an iterative method are easier to understand for this problem 4 More general and more efficient iterative methods for treating algebraic equations of this nature will be discussed later Jacobi Iteration By considering the unknowns in the order specified above the ijth equation can be written in the form Wixjil Wiiu 4W0quot Wi1J WiJ1 h2 j7 and the Jacobi iteration can be defined by the following recursion gt Let w0 be chosen arbitrarily gt For n 0 let n1 1 n n n n 1 2 WU 1 WA3971 WHJ Wi1J Wan 1h 039 Let us prove that this iteration is convergent though not rapidly Let Cn Wn1 Wn indicate the difference between successive iterates if 2 llCWllo lt 007 n0 then convergence of the iteration is assured Now n 1 n n n n n n 3 H Z Ch11 LL cltld Cid11 c3 l jAth x0 6 m If A were to be replaced by the differential Laplacian we would be led to using an eigenfunction expansion with eigenfunctions sin 7rpxsin 7rqy7 p7 q 127 Fortunately the same technique works in the finite difference case as a consequence of the following lemma Lemma The eigenfunctions of the discrete Laplace operator Ah subject to vanishing boundary values on 012 are given by sinIrpxsinn39qy7 p7 q 1N71 moreover 4 h h iAh sin 7rpxsin 7rqy p sin2 sin2 sin 7rpxsin 7rqy7 sin 7rplxsin 7rqu7 sin 7rng7 sin wqu H6p1p26q1q27 where H gt O is independent h Proof The equation 4 h 6Xsin 7rpx 7 sin2 sin 7rpx results from standard trigonometric identities and the evaluation of the eigenvalue follows The orthogonality claimed in the lemma is implied by the inequality of the eigenvalues for p1 7 p2 or ql 7 qg That H is independent of h is another consequence of standard trigonometric inequalities Set Appq sin 7rpxsin 7rqy and expand W in terms of wpq piq177N N71 Cn Z ath quxU pq1 Then 04 17 sin2 WTph i sin2 04 ppqagg Note that 71ltpN71JV71ltltppqltltp11lt1 so that 04 a O for all p and q thus the Jacobi iteration converges Let us estimate the rate at which the iteration converges Now 2 i i i 2 7rh 7r maxippqi 7 pm 7 pN71JV71 717 2sn 17 Let us determine how many iterations m are required to assure that quot0 max m lt pq 04 7 2 By taking logarithms and expanding the logarithm of 17 713922N2 as N a 00 we see that it is necessary to have gt 2 2 og N2 7139 to assure that desired reduction is satisfied The number of iterations required to reduce the error by a factor 7 is 9N2 logn 1 which implies that the total number of arithmetic operations required for this reduction is 9N4 logn 1 which is not competitive with some other also simple but more sophisticated iterative methods However this very simple iteration can be modified slightly to be quite effective in reducing the error in the span of the more highly oscillatory eigenfunctions As a result the modified Jacobi iteration is very commonly used in the most efficient iterative method known for the algebraic equations associated with numerical methods for approximating elliptic equations this method known as the multigrid method will be discussed later Let us consider the modification of the Jacobi iteration known as Richardson extrapolation The recursion can be changed to 2 n1 n h n WU 7 WU VT Ahwij 7 f where the parameter 39y gt O is introduced to accelerate the convergence rate for the portion of the error associated with one set of eigenvalues while possibly slowing the rate for another portion of the error We shall concentrate on the very oscillatory modes given by 0 wpq i maXP7q Z N27 which includes almost exactly threefourths of the eigenfunctions Then 1 27r 27rph 27rqh sin Egsin Tsin T 27 AppqEO lf0lty 2 then h h pqu 17yltsin2sin2 E 1 V71C 1717 ppq 07 while 1 qul39Y E 1 21 5 07 4pm 6 039 Since lppq yl remains uniformly less than or equal to one for Appq 9 for O lt 39y lt 2 we can choose 39y so as to minimize maqueo lppq yl as a function of 39y This can be accomplished by finding V such that 1V12 or PE forwhich 4 3 PM E g maX WWEO Thus for the more oscillatory three quarters of the eigenfunctions this optimal choice of the parameter 39y causes the reduction of the coefficients of these eigenfunctions in the expansion of the error at least by a factor of three fifths in one iteration instead of taking 9N2 iterations to effect that reduction It will be this characteristic that will allow the use of the Richardson iteration to produce a very effective multigrid iteration A Model Parabolic Problem The model parabolic problem is given by the initial boundary value problem for the heat equation gsAu fxt x Q7f loleJ7 8t 0 x e 89 t 6 J ux0 gx7 XEQ Let us apply the techniques discussed above for the Dirichlet problem to the heat equation First denote the value of a function fx7 t at the point xij7 t where At gt O and t nAt by f0 The Forward or Explicit Difference Method The simplest finite difference procedure for the heat equation is given by approximating the differential equation at xij7 t by a forward difference in time for the time derivative and by Ah for the Laplacian thus the approximate solution Wig must satisfy the system for 0 g t lt T m 7 W n n At iAhWIj 1 X0quot 69h wgll 07 X0 6 89h W3 gij x0 6 Qh Since we can solve explicitly for Wig1 as W1531 Wigl l AtAhWIJr7 x0 6 Qh this procedure is called the explicit finite difference analogue of the heat equation clearly the evaluation of the solution at the new time level is a trivial calculation It is easy to see that u agrees with W initially and on the boundary discretely and that un1 7 un TiAhu f 6 XEQh7 where the subscript U will be suppressed where not needed for clarification and 8339 0lluttllooAt llLl 49072 Thus if e u 7 W denotes the error in the approximate solution then en1 7 6In T iAhe c x E Qh We can employ the same eigenfunction analysis procedure as in the treatment of the Jacobi iteration to obtain an Abound on llenllo Expand e and 6 in terms of Appq N71 N71 en Z airiqu 5 Z 6gqWPq pgtq1 Pq1 Then 4At h h 1qu lt17 7 sin2 i sin2 agq l Attigq Now 4At 27rph 27rqh 1 sin Tsin T The time step restriction is called the Courant Friedrichs Lewy CFL stability condition its consequence is that each error mode evolves boundedly the condition can be replaced by At h 2 g 1 CAt4 where C is independent of I77 h and At It will be used to establish the convergence of the approximate solution to the exact solution max pq At 1 1 Ifandonlyif set 4A h h ppq 17 T sin2 sin2gt Let the CFL condition be satisfied Since e0 0 agq O and then n71 an 2ququot 15 q H 0 By the orthogonality of the eigenfunctions N71 n71 2 quot1 2 iie ii3 7 Z Zippqi 16zqmgt ltZagqmgt pa 0 pq1 n0 Z ltlt 6zq2Atgt S quotfiwzqizm pq n0 re0 pq i A n71 n71 t Hg iigAt g t C1u2At2 C2u2h4 At 0 H0 S tn2 C1L392Af2 C2200 H Thus lle llo t C1uAtC2uh2 lt Ct At h2 gig unl g lUWllUyml Theorem Let Wh be the solution of the explicit finite difference 1 equation and assume that the CFL limit At th has been imposed Let u be the solution of the heat equation and assume that um um and um are bounded on Q x 07 T Then the error e u 7 Wh satisfies the bound above It is also quite easy to prove an ZW convergence theorem Rewrite the error equation in the form 4At At 1 gt 17 T2 emai enu eff11 aimMen and note that all five coefficients of the eff terms are nonnegative if the CFL condition is satisfied moreover they sum to one Thus 1 ie i mgxieih Armkgxism so that n iiGWDiiom S iiequotii0oo iilt quotii0ooAt E Z ii miioooAf7 m0 and under the hypotheses of the last theorem MMquot 7 WWW om hz The 6 argument can be extended to the parabolic equation with variable coefficients with little difficulty Consider the initial boundary problem CV3VU 1 X697 Olttlt T7 u 07 X689 Olttlt T7 u L107 XES1 O7 where c CX 2 6min gt O and a ax 2 amin gt 0 The corresponding forward difference equation is given by 1 Wig39n 7 At Ci VhthWfjn 3th where V thW 6ya6xw l 6ya6yw Then the error equation can be written in the form n1 At n so 7 lt17 CUh2aUgt so N n n n n ch2 lt3i Jei1J ai u39eiiu i aiJ eiJ1 awe euel I and it follows that the error satisfies the same bound as for constant coefficients provided that the CFL condition At 3039 h 7 my 53 hods Remarks 1 If 5a is adjusted to be the sum of the off diagonal values of the coefficient a then the resultjust obtained is valid in n dimensions for n 12 2 The CFL condition imposes a severe constraint on the time step in the forward difference procedure it arises from the fact that the solution ux7 t At of the heat equation depends on all of the values of u at time level 1 If 739 gt O is fixed then the CFL condition requires that the approximate solution Wx7 t 739 to depend on the values WC7 t for K 7 xi 4Th as h a 0 A Disappointing Attempt at Higher Order Accuracy Since the time step allowable for the forward difference equation must be 9h2 it would be of significant interest to obtain higher order accuracy with respect to the time discretization A first try would be to approximate the time derivative to second order Restrict attention to the heat equation in a single space variable and apply a centered first difference to the time derivative n1 n71 W 2AtW kxwlnl39 Consider the evolution of the eigenfunction sin 7rpx Wn 7 n 7 p sm 7rpx7 where pn1 7 pnil 74At Sinz Lph n 2m 2
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'