YU Dandan, YAN Dunyan
(School of Mathematical Sciences, University of Chinese Academy of Sciences,Beijing 100190, China)
Abstract In this paper, we develop an iterated fast Petrov-Galerkin method for Fredholm integral equations of the second kind with the smooth kernel. The corresponding convergence and the computational complexity are analyzed. Super-convergence can be achieved.
Keywords Petrov-Galerkin method; integral equation; super convergence; iterated method
There have been extensive research activities on numerical solutions of boundary integral equations. Many boundary value problems of partial differential equations can be reduced to Fredholm integral equations of the second kind. We consider in this paper only the classical Fredholm integral equations of the second kind, that is,
(1)
whereuis unknown,is a Hilbert space and:→is a compact operator with smooth kernel functionKdefined by
The quadrature methods (Nystrom’s method) and projection methods (collocation method and Galerkin method) are the two commonly used methods for solving (1) numerically (see Refs. [1-2]). It is well known that the Galerkin methods enjoy nice convergence properties but at the same time suffer from having high computational costs. In Ref. [3], the authors found that the Calderon-Zygmund integral operators have an almost sparse matrix representation under the wavelet basis. This discovery inspired a series of research on fast wavelet algorithms[4-7]. Based on a compression strategy, a fast wavelet Galerkin method was proposed in Ref. [7]. In Refs. [6-7], the fast wavelet Petrov-Galerkin methods and fast collocation methods were developed for integral equations. Recently, in Refs. [8-12], a fast Fourier-Galerkin method was proposed, solving the boundary integral equations deduced from the boundary value problems of the Laplace equations or biharmonic equations.
A theoretical framework for the analysis of super-convergence for the iterated Petrov-Galerkin method was established in Ref. [13]. The Petrov-Galerkin methods admit the trial spaces and test spaces to be different. Therefore, for the trial spaces, we employ piecewise polynomials of higher degrees. While, for the test spaces, we use the piecewise polynomials of lower degrees. In this way, we can still obtain the same convergence rate as the Galerkin method with less computational cost.
In this paper, we aim to develop an Iterated Fast wavelet Petrov-Galerkin method (IFPG) for solving (1). The key idea is to combine the fast wavelet Petrov-Galerkin method with Sloan iteration. The fast wavelet Petrov-Galerkin method has been well studied to get the optimal convergence rate by a sparse linear system. The well-known Sloan iteration is an example of iteration post-processing methods[14], which can achieve super-convergence. In this paper, we first apply a truncation strategy to the wavelet Petrov-Galerkin method to generate a sparse linear system. Then, we employ the Sloan iteration to improve the convergence rate. We will prove that the proposed method can achieve super-convergence by a sparse linear system.
We will recall the standard iterated Petrov-Galerkin method for (1) in this section.
To state the Petrov-Galerkin method, let us begin with the trial space and test spacen⊂andn⊂and the multiscale wavelet bases for them.
It was shown in Ref. [15] that {n,n} forms a regular pair of subspaces, we also call them (k,k′) elements. It is straightforward to compute that
dimn=dimn∶=S(n)=kμn.
For anyn∈∶={1,2,…}, letnbe the set of lattice points in2defined as
n∶={(i,j)∶j∈w(i),i∈n+1}
(2)
Asconstructedinsection2inRef.[6],let{fi,j∶(i,j)∈n}and{gi,j∶(i,j)∈n}bethebasesfornandn,respectively.Thesebasesenjoythefollowingpropositions.WedenotebyHmtheclassicalSobolevspace.
Proposition1.1Assume that {fi,j∶(i,j)∈n} and {gi,j∶(i,j)∈n} are bases fornandn, respectively, constructed as in section 2 in Ref.[6].
Then, we have
1){fi,j∶(i,j)∈n} is an orthonormal basis forn.
2){gi,j∶(i,j)∈n} and {fi′,j′∶(i′,j′)∈n} are semi-biorthogonal, namely
〈gi,j,fi′,j′〉=δii′δjj′,i≥i′.
3)The functionsfi,j,gi,j,(i,j)∈nhavekorder of vanishing moments, i.e.,
〈fi,j,h〉=0, 〈gi,j,h〉=0,
whereh(t)∶=tr,t∈I,r∈k.
4)Ifu∈Hmwith 0 whereck,m=(k+1-m)m2-m+1/2. 5)The length of the supports supp(fi,j) and supp(gi,j) satisfy the condition Next, we recall the generalized best approximation as follows (see Ref. [16]). Definition[generalized best approximation] Givenx∈an elementnx∈nis called a generalized best approximation fromntoxwith respect tonif it satisfies the equation Similarly, giveny∈*=an elementny∈nis called a generalized best approximation fromntoywith respect tonif it satisfies the equation 1) Fori′-1∈n,j′∈w(i′), functionsξi′,j′havek′ order of vanishing moments, that is 〈ξi′,j′,tr〉=0,r∈Zk′,j=∈w(i′),i′-1∈n. 2) The auxiliary functions {ξi,j∶(i,j)∈n} is biorthogonal relative to the set of functions {gi,j∶(i,j)∈n} that is, 〈ξi′,j′,gi,j〉=δi′iδj′j, (i′,j′),(i,j)∈n. These properties imply that the generalized best approximation fromntoywith respect tonis With these preparation, we are ready to state the iterated Petrov-Galerkin method as follow. The Petrov-Galerkin method for equation (1) is: findingun∈n, such that, (3) The iterated projection method is defined by Sloan iteration, (4) It has been proved in Ref. [14] that the iterated projection approximationu′nsatisfies the following integral equation (5) Lemma1.1If the kernel functionK∈Ck(I×I),then, for anyi∈, there exist constantsc1andc2independent ofnsuch that Moreover, ifu∈Hmwith 0 ProofLetKt∶=K(t,·). SinceK∈Ck(I×I), we have for allt∈I,Kt∈Hk′(I), and wherecis a constant independent oftandi. For anyφ∈, we have′iKt∈iand 〈φ-iφ,′iKt〉=0. Hence, ≤c1μ-k′i|φ| ≤c1c2μ-(m+k′)i|u|Hm, from which the desired estimate follows. □ (6) ProofIt has been proved in Ref. [14] that (7) From Lemma 1.1, we know that there exists a positive constantcsuch that Meanwhile, by the Proposition 1.1, we have Substituting the above two inequalities into (7), we obtain the estimate (6). □ This is the super-convergence property of the iterated method. It is well known that the Galerkin method has high-order accuracy but suffers from high computational costs to generate the coefficient matrix. Then, a question arises naturally: Can we design a fast method that can preserve the super-convergence property within quasi-linear computational costs? We will give our answers in the following sections. This section will present a fast and effective algorithm by truncating the dense coefficient matrix to obtain a sparse one. The number of nonzero entries of the sparse matrix will be estimated. We first show the discrete form of equation (3). By introducing the vector notations cn∶=[ci,j](i,j)∈n,gn∶=[〈gi′,j′,f〉](i′,j′)∈n, and matrix notations En∶=[〈gi′,j′,fi,j〉](i′,j′),(i,j)∈n,K∶=[Ki′,i]i′,i∈n+1, (En-Kn)cn=gn. (8) In equation (8), the matrixEnis sparse, butKnis dense. Fortunately, the elements in matrixKndecay speedy, and many of them are insignificant. This observation makes it is possible to obtain a sparse matrix by abandoning some tiny elements. In the following two lemmas, the estimate on the elements′ decay in matrixKnwill be presented. Lemma2.1If the kernel functionK∈Ck(I×I), then, for anyi∈, there exist a positive constantcindependent ofnsuch that, for all (i,j),(i′,j′)∈n |Ki′,j′;i,j|≤cμ-(i+i′)(k+1/2), (9) ProofBy Taylor’s Theorem, the kernelKcan be rewritten as K=K1+K2+K3, whereK1(t,·),K2(·,τ) are polynomials of degree less thank-1 respect toτandtrespectively, andK3is the remainder term in the integral form. That is (1-θ1)k-1(1-θ2)k-1dθ1dθ2. It can be proved that there exists a constantC>0 such that, for all (t,τ)∈I2, |γk,k(t,τ)|≤C. Using the vanishing moments offi,j, andgi′,j′, we have (10) The following proof is divided into four cases, depending on whetheriandi′ equal to zero or not. Case 1 Assumei≥1, andi′≥1. There exists a positive constantc1such that ≤c1μ-(k+1/2)(i+i′). Case 2 Assumei=0, andi′≥1. There exists a positive constantc2such that ≤c2μ-i′(k+1/2) by noting thatw(0)=k. Case 3 Assumei≥1, andi′=0. There exists a positive constantc3such that ≤c3μ-i(k+1/2). Case 4 Assumei=0, andi′=0. There exists a positive constantc4such that |K0,j′;0,j|≤c4. Takingc∶=max{c1,c2,c3,c4}, we obtain the desired estimate (9). □ Lemma2.2If the kernel functionK∈Ck(I×I), then there exists a positive constantCindependent ofnsuch that, for alli,i′∈n+1, |Ki′,i|2≤Cμ-k(i+i′). ProofBy lemma 2.1, we have ≤c2w(i)w(i′)μ-(i+i′)(2k+1). Combing with (2), we get which completes the proof. □ With the estimate in lemma 2.2, we present the following truncated matrix. Let where (11) (12) Then we can present the fast method as follow. Algorithm2.1iterated fast wavelet Petrov-Galerkin methods Step 2 Let Step 3 Let the iterated approximation be (13) Theorem2.1There exists a positive constantCsuch that for alln∈, In this section, we will analyze the convergence of the proposed IFPG method. (14) With the help of estimate (14), we can make a conclusion on the iterated projection approximation. (15) ProofFrom (13), we have <2. (16) Submitting (16) into (13), we can obtain (15). Since we can claim that □ From equations (1) and (15), we have (17) where The estimate onΓ1has been presented in Lemma 1.1. By Lemmas 1.1 and 2.2, we can state the following estimate onΓ2. Lemma3.1Ifu∈Hmwith 0 ProofWe know that Hence, (18) By Lemma 2.2, there exists a constantc1>0 such that, |Ki′,i|2≤c1μ-k(i+i′),i,i′∈n+1. (19) Meanwhile, ≤cμ-im|u|Hm, |[〈u,fi,j〉]j∈w(i)|2=|(χi-χi-1)u|≤cμ-im|u|Hm. Hence, we can conclude that (20) Since the bases {ξi,j} and {gi,j} are semi-biorthogonal, we get by noting Thus, (21) By Corollary 3.5 in Ref. [6], there exists a constantc2>0 such that Then, by Lemma 1.1, the estimate (21) can be continued as ≤cμ-k′i′|v|. (22) Submitting (19), (20), and (22) into (18), we have Noting that, ≤cnμ-(m+k′)n, then we have which completes the proof. □ Now, we are ready to present the convergence results. (23) wherecis a constant independent ofn. ProofFrom Lemma 1.1 and Lemma 3.1, we know there exist positive constantsc1andc2such that |Γ1|≤c1μ-(m+k′)n|u|Hm, |Γ2|≤c2nμ-(m+k′)n|u|Hm. (24) Next, let us focus onΓ3. For anyφ∈n, we have where Since |[〈φ,fi,j〉]j∈w(i)|2≤|φ|, we obtain ≤cnμ-k′n|φ|, by employ Lemma 2.2 and the inequality (22). ≤c3nμ-(m+k′)n|u|Hm. □ 本文来源：http://www.triumph-cn.com/fanwendaquan/gongwenfanwen/2023/0927/109547.html
