1、Applied Mathematics Letters() Contents lists available at SciVerse ScienceDirect Applied Mathematics Letters journal homepage: A second-generation wavelet-based finite element method for the solution of partial differential equations Youming Wanga, Xuefeng Chenb, Zhengjia Heb aSchool of Automation,

2、Xian University of Posts and Telecommunications, Xian 710121, Peoples Republic of China bState Key Laboratory for Manufacturing System Engineering, Xian Jiaotong University, Xian 710049, Peoples Republic of China a r t i c l ei n f o Article history: Received 26 January 2010 Received in revised form

3、 7 January 2012 Accepted 21 January 2012 Keywords: Second-generation wavelet Equivalent filter Partial differential equation a b s t r a c t A new second-generation wavelet (SGW)-based finite element method is proposed for solving partial differential equations (PDEs). An important property of SGWs

4、is that they can be custom designed by selecting appropriate lifting coefficients depending on the application. As a typical problem of SGW algorithm, the calculation of the connection coefficients is described, based on the equivalent filters of SGWs. The formulation of SGW-based finite element equ

5、ations is derived and a multiscale lifting algorithm for the SGW-basedfiniteelementmethodisdeveloped.Numericalexamplesdemonstratethatthe proposed method is an accurate and effective tool for the solution of PDEs, especially ones with singularities. 2012 Elsevier Ltd. All rights reserved. 1. Introduc

6、tion In recent years, wavelet methods have been developed as a new powerful tool for mathematical analysis and engineering computation since the multiresolution properties and various basis functions of wavelets can lead to fast, hierarchical and accurate algorithms. The current wavelet-based numeri

7、cal algorithms include waveletGalerkin 1,2, waveletcollocation 3,4, waveletfinite element 5,6 type, etc. As a general numerical method, the wavelet-based finiteelementmethodadoptsscalingandwaveletfunctionsinsteadoftraditionalpolynomialinterpolation.Sincetraditional wavelets are constructed from scal

8、ed and shifted versions of a single mother wavelet on a regularly spaced grid over a theoretically infinite or periodic domain, traditional wavelets cannot be constructed on complicated, irregularly spaced meshes, which are commonly encountered in the finite element method. The second-generation wav

9、elets (SGWs) based on a lifting scheme 7 were introduced to eliminate the restrictions and deficiencies of traditional wavelets. The lifting scheme provides users with much flexibility for building different SGW bases with prediction and update coefficients for engineering problems depending on the

10、applications. In the recent applications of the SGW method in engineering computations, different kinds of wavelets have been designed for grid interpolation and multiscale computation 810. A typical problem in the numerical analysis of wavelet methods is the calculation of the connection coefficien

11、t of SGWs, which is an integral of products of wavelet scaling functions or derivative operators associated with these. However, for SGWs lacking explicit function expressions, traditional numerical integrals such as Gauss integrals cannot provide the desirable precision. In the last few decades, th

12、e computation of connection coefficients of wavelets without explicit function expressions has been receiving much attention. The algorithms for computing the connectioncoefficientsonunboundeddomainsorperiodicboundaryconditionsweredevelopedbyCohen,Dahmen,Beylkin et al. 1113, in order to solve partia

13、l differential equations. To apply the wavelet method to the solution of finite domain Corresponding author. E-mail address: (Y. Wang). 0893-9659/$ see front matter2012 Elsevier Ltd. All rights reserved. doi:10.1016/j.aml.2012.01.021 2Y. Wang et al. / Applied Mathematics Letters() Merge Split a b Fi

14、g. 1. Second-generation wavelet transform: (a) decomposition; (b) reconstruction. problems, connection coefficients with integral form on the intervals 0, x and 0, 2j were respectively presented by MonasseandLinetal.14,15.Withthedevelopmentofwaveletmethodsforgeneralmathematicalorengineeringproblems,

15、 connection coefficients with integral form on the interval 0, 1 were proposed by Ko, Chen, Ma et al. 1618, to improve the efficiency and accuracy of the multiscale computation. In this work, the relation between lifting coefficients and wavelet filters is described, based on the second-generation w

16、avelet transform (SGWT). The connection coefficients on the interval 0, 1 are calculated efficiently, based on the equivalent filters of SGWs. The SGW-based finite element equations are formulated in order to calculate all kinds of stiffness matrices and load vectors that are necessary for higher-di

17、mensional mathematical problems. A multiscale lifting algorithm for the SGW-based finite element method is also presented. Some numerical examples with high gradients and singularities are presented to verify the accuracy and efficiency of the proposed method. 2. The second-generation wavelet transf

18、orm A lifting scheme was presented by Sweldens in order to custom design a new family of SGWs. Fig. 1 shows the decomposition and reconstruction of the SGWT. Consider a signal: X= xk,kZ,k=1,2,.,L. The approximation signal sj+1(k)of X at scale j+1 is split into two disjoint sets, namely even indexed

19、samples sj(2k)and odd indexed samples sj(2k+1). Then, a predictor is used to predict the odd indexed samples sj(2k+1)with N neighbors of the even indexed samples at scale j, and N is determined as the required number of vanishing moments of the underlying wavelet function. The errors in prediction a

20、re defined as the detail signal at scale j in the form dj(k) =sj+1(2k+1) N m=1 p(m)sj+1(2m+kN),k=1,2,.,L/2,m=1,2,.,N(1) where p(m)is a prediction coefficient and P=p(1),.,p(N) denotes the predictor for detail signal calculation. Then a numberN of detail signals dj(k)obtained from Eq. (1) are adopted

21、 to update the even indexed samples sj(2k), and the approximation signal sj(k)is sj(k) =sj+1(2k) N n=1 u(n)dj(n+kN/21),k=1,2,.,L/2,n=1,2,.,N(2) where u(n)is an update coefficient and U= u(1),.,u(N) T , denotes the updater for the approximation signal calculation. The underlying wavelet of the wavele

22、t transform via the lifting scheme can be denoted as(N,N). Fig. 2 shows an SGW with the predictor order N=4 and the updater orderN=4. Rearranging Eqs. (1) and (2), we find the relation between dj(k)and sj+1(k),sj(k)and sj+1(k)as follows: dj(k) = l g(2kl)sj+1(l)(3) sj(k) = l h(2kl)sj+1(l)(4) where g(

23、2kl)is an equivalent high-pass filter coefficient of the SGWT, the high-pass filter is g= gk,N+1kN1,kZ(5) where g(2k1) = p(k)and g(2k) = (kN/2)for k=1,2,.,N, and(k)is the Dirac function; h(2kl)is the equivalent low-pass filter coefficient of SGWT, the low-pass filter is h= hk,NN+2kN+N2 (6) where h(2

24、k1) = (kz) N m=1p(m)u(k m+1)for k=1,2,.,N and z= (N+ N)/2; h(2k) =u(k)for k=1,2,.,N. On the basis of the flexible design of the prediction and update coefficients, we can calculate the wavelet filters and define SGWs according to the application. Y. Wang et al. / Applied Mathematics Letters()3 1.5 1

25、 0 0.5 -0.5 1 0 0.5 -0.5 -4-2024 -8-4048 a b Fig. 2. Second-generation wavelet: (a) scaling functions SGW(4); (b) wavelet functions SGW(4, 4). 3. Connection coefficients Since the wavelet numerical method can be viewed as a method in which the approximating function is defined by use of a multiresol

26、ution technique, the computation of connection coefficients is based on the multiresolution analysis of the wavelets and scaling functions. While using the scaling function of SGW as a test function for the finite element method, we would obtain two typical connection coefficients on the interval 0,

27、 1 for forming stiffness matrices and load vectors 5,18, such as j,a,b N,k,l= + 0,1()(a) j,k (b) j,kd (7) Rj,c N,k= + 0,1()cj,kd(8) where0,1() = 10 1 0otherwise , which satisfies a simple two-scale relation 0,1 1 2 = 0,1() + 1,2() = 0,1() + 0,1( 1).(9) On the basis of the multiresolution analysis of

28、 SGWs 7, the scaling functionj,kL2(R)at level j and j+1 satisfies the two-scale relation j,k= l j,k,lj+1,l,(10) wherej,k,ldenote the low-pass filters of SGWs relating the filters in the SGWT withj(1k) = (1)kgj(k). By using the two-scale relation of Eqs. (9) and (10), the connection coefficient matri

29、x can be derived as (2m+n1GI)j,m,n N =0(11) where G is the coefficient matrix, I an identity matrix, G= s,t (s2kt2l+ s2k+2jt2l+2j)(12) where(2N1) k,l2j1, andj,m,n N denotes the(2j+2N1) (2j+2N1)stiffness matrix. Eq. (7) cannot be determined uniquely through the homogeneous equation (11), so independe

30、nt inhomogeneous equations are required for a unique solution as follows: q! (qm)! w! (w n)! 2 q+ w mn+1 =2j(m+n) k,l Cq j,kC w j,l j,m,n N,k,l (13) where Cq j,k= xq,j,k. For the computation of the connection coefficients of load vectors, the multiresolution analysis of the SGWs will derive the foll

31、owing equation: (2m+1IB)Rj,m N,k= i i2k+2j m s=1 m s Rms N,i (14) where(2N1) k2j1,B= i,k i2k+ i2k+2j . 4Y. Wang et al. / Applied Mathematics Letters() 4. The SGW-based finite element method Consider a boundary value problem. Suppose that a spatial domainR2has a Lipschitz boundary= DN whereDandNare t

32、he Dirichlet and Neumann boundaries, respectively. The boundary value problem consists of finding the solution u that satisfies Lu:= (Au)+bu+cu=fin(15) u=0onD(16) u=tonN(17) where L is in principle a second-order differential operator andis the boundary operator. The data are assumed to be sufficien

33、tly smooth, i.e. A,b,c,f and t are sufficiently regular functions. For a variational formulation of Eq. (13), we introduce the bilinear form as a(u,v) := A(x)u(x)v(x) +b(x)u(x)v(x) +c(x)u(x)v(x)dx(18) l(v) := f(x)vdx.(19) If the unknown field function u is interpolated using the SGWs, the field func

34、tion can be u() =Nae(20) whereis the nondimensional element coordinate with 0 1.N= j N,2N+1(), j N,2N(),., j N,2j1() is the row vector combined by the second-generation scaling functions for order N at the scale j, and ae= ajN,2N+1,ajN,2N,.,aj N,2j1 T is the column vector of coefficients. Since the

35、elemental nodal solution ueand scaling function coefficients aehave the relation ue=Reae(21) where Re= T (1)T(2)T(n+1) T, the field function can be written as u() =N(Re)1ue=NTeue(22) where the transformation matrix Te= (Re)1. Substituting Eqs. (18) and (19) with Eq. (22), we obtain Ke= 1 0 A()(Te)T

36、dT d d d Te+b()(Te)T dT d Te+c()(Te)TTTe d(23) Pe=le 1 0 f()(Te)TTd.(24) Therefore, solving equations by the SGW-based finite element method can be represented as Keue=Pe(25) where the boundary condition can be treated as in the traditional finite element method. 5. The multiscale lifting algorithm

37、The multiresolution analysis property of SGWs is the foundation of the multiscale lifting numerical algorithm, which approximates the exact solution of the problems analyzed at high convergence rate. The key ingredients of the multiscale lifting algorithm are a reliable error estimation and lifting

38、algorithm, which are described in this section. 5.1. Error estimation Given an SGW-based finite element solution ujand the exact solution u of the problems analyzed, the error estimation e is defined as e= uuj =max u(x) uj(x). (26) Y. Wang et al. / Applied Mathematics Letters()5 a b Fig. 3. Converge

39、nce of the SGW-based finite element solution with the number of levels: (a) Example 1; (b) Example 2. Ref.19provesthatthefunctionu(x)inspaceL2(R)canbeapproximatedwiththeprojectionuj(x)inVjandtheprojection can capture all the details of the initial function u(x)as the scale j gets larger (i.e. as j +

40、), such as lim j uuj=0. (27) Since the exact solution u cannot always be found for PDEs, we use a simple two-level error estimate in the form e=max uj+1(x) uj(x) (28) where uj+1and ujin the neighbor approximate space, j+1 and j. 5.2. The multiscale lifting algorithm Given an initial mesh onand a thr

41、eshold value, the multiscale lifting algorithm for the SGW-based finite element method is summarized as follows: (1) Select second-generation wavelets of order N for an approximate space Vj. (2) Compute the SGW-based finite element solution and the two-level error estimation e. (3) If e , stop and g

42、ive the answer. (4) Lift the approximate space Vjto Vj+1and construct the new solving domainj+1; go to step (2). 6. Numerical examples We present numerical experiments with high gradient and singularity to demonstrate the efficiency and accuracy of the SGW-based finite element method compared to tho

43、se for FEM. Example 1. Consider a typical problem with high gradient as follows: u=f,x0,1(29) with the boundary condition u(x)|x=0,1=0; the right-hand function is f=560 x6200 x3and the exact solution u(x) =10 x5(1x3). An SGW-based finite element with order N=2,4,6 and the multiscale lifting algorith

44、m are used to solve this problem. Fig. 3(a) shows the convergence of the SGW-based finite element solution with the number of levels. Table 1 illustrates the comparison of the SGW-based finite element solution at each scale and the finite element solution. It can be observed that the solution by the

45、 SGW with higher order will lead to a faster convergence rate or smaller error estimation. Due to the multiresolution analysis of the SGW, the solution approximates the exact solution of the problem with high convergence rate using the dynamic lifting of the solution scale. Compared to the ten cubic

46、 finite elements (FEs), SGW(6) has shown its priority of convergence when the solution scale j=4. It can be derived that the SGW with order N=2,4 will give random accurate results when the scale is lifted to higher numbers. Therefore, the SGW-based finite element method is very suitable for this pro

47、blem with high gradient. Example 2. Consider a PDE with singularities on the boundary as follows: u(x) u(x) =1x0,1(30) withtheparameter = 0.01,theboundaryconditionu(x)|x=0,1=0,andtheexactsolutionu(x) = x 1 1+e1/+ ex/ 1+e1/ . 6Y. Wang et al. / Applied Mathematics Letters() Table 1 Convergence of the

48、SGW-based finite element solution at each scale and the finite element solution. TypeSpace V0V1V2V3V4 N=21.55211.28910.81760.35870.1227 N=40.64230.20810.11240.01060.0017 N=60.13600.06220.00650.00090.0002 10 cubic FEs0.0006 Table 2 Convergence of the SGW-based finite element solution at each scale an

49、d the finite element solution. TypeSpace V0V1V2V3V4 N=212.00000.87420.75810.63320.4953 N=42.24670.72400.42270.22180.1203 N=60.18170.12490.07940.03760.0125 10 cubic FEs0.1084 This problem can be solved using one SGW-based finite element with order N=2,4,6 and the multiscale lifting algorithm. Fig. 3(

50、b) compares the convergence of the SGW-based finite element solution with the number of levels while Table 2 shows the comparison of the SGW-based finite element solution at each scale and the finite element solution. It can seen that the multiscale computation of the singular problem using SGW(6) g

51、ives accurate results as compared with the other SGW finite elements and ten cubic FEs. Hence, the SGW-based finite element method is also suitable for the high- precision solution of singular problems. 7. Conclusions A SGW-based finite element method is developed for solving PDEs efficiently. The a

52、dvantage of SGWs over traditional wavelets is the flexible construction by selecting appropriate prediction and update coefficients according to the problems analyzed. According to the two-scale equations and normalization conditions of the SGWs, the connection coefficients on the interval are compu

53、ted accurately, based on the equivalent filters. The numerical results verify the efficiency of the proposed method and the method can be applied to a wide range of PDEs and engineering problems efficiently, such as multidimensional or nonlinear equations, etc. Acknowledgment This work was supported

54、 by the National Natural Science Foundation of China (No. 51175401). References 1 J.M. Restrepo, G.K. Leaf, WaveletGalerkin discretization of hyperbolic equations, J. Comput. Phys. 122 (1) (1995) 118128. 2 G. Beylkin, J.M. Keiser, On the adaptive numerical solution of nonlinear partial differential

55、equations in wavelet bases, J. Comput. Phys. 132 (2) (1997) 233259. 3 O.V. Vasilyev, S. Paolucci, M. Sen, A multilevel wavelet collocation method for solving partial differential equations in a finite domain, J. Comput. Phys. 120 (1) (1995) 3347. 4 W.Cai, J.Z.Wang, Adaptive multiresolutioncollocatio

56、n methodsfor initial boundary value problems of nonlinear PDEs, SIAM J. Numer. Anal. 33 (1996) 937970. 5 L.A. Diaz, M.T. Martin, V. Vampa, Daubechies wavelet beam and plate finite elements, Finite Elem. Anal. Des. 45 (3) (2009) 200209. 6 X.F. Chen, S.J. Yang, The construction of wavelet finite element and its applicatio