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,
$ u-\mathcal{K} u=f, f \in \mathbb{X}, $ | (1) |
where u is unknown,
$ (\mathcal{K}\;u)(t):=\int_I K(t, \tau) u(\tau) \mathrm{d} \tau, t \in I:=[0, 1] . $ |
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.
1 Iterated Petrov-Galerkin methodWe 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 space
Let
$ \mathbb{X}_n:=\mathbb{S}_{\mu^n}^k, \mathbb{Y}_n:=\mathbb{S}_{\mu^{n+1}}^{k^{\prime}}, n \in \mathbb{N}_0:=\{0, 1, 2, \cdots\}. $ |
It was shown in Ref. [15] that {
$ \operatorname{dim} \mathbb{X}_n=\operatorname{dim} \mathbb{Y}_n:=S(n)=k \mu^n. $ |
For any n∈
$ \mathbb{U}_n:=\left\{(i, j): j \in \mathbb{Z}_{w(i)}, i \in \mathbb{Z}_{n+1}\right\} $ |
where
$ w(i)= \begin{cases}k, & i=0, \\ k(\mu-1) \mu^{i-1}, & i \in \mathbb{N}.\end{cases} $ | (2) |
As constructed in section 2 in Ref. [6], let {fi, j∶(i, j)∈
Proposition 1.1 Assume that {fi, j∶(i, j)∈
Then, we have
1) {fi, j∶(i, j)∈
2) {gi, j∶(i, j)∈
$ \left\langle g_{i, j}, f_{i^{\prime}, j^{\prime}}\right\rangle=\delta_{i i^{\prime}} \delta_{j j^{\prime}}, \quad i \geqslant i^{\prime} . $ |
3) The functions fi, j, gi, j, (i, j)∈
$ \left\langle f_{i, j}, h\right\rangle=0, \quad\left\langle g_{i, j}, h\right\rangle=0, $ |
where h(t)∶=tr, t∈I, r∈
4) If u∈Hm with 0 < m≤k, then
$ \inf\limits_{x_n \in \mathbb{X}_n}\left\|u-x_n\right\| \leqslant c_{k, m} \mu^{-m n}|u|_{H^m} $ |
where ck, m=(k+1-m)m2-m+1/2.
5) The length of the supports supp(fi, j) and supp(gi, j) satisfy the condition
$ \operatorname{meas}\left(\operatorname{supp} f_{i, j}\right) \leqslant \frac{1}{\mu^{i-1}}, $ |
$ \text { meas }\left(\operatorname{supp} g_{i, j}\right) \leqslant \frac{1}{\mu^{i-1}}, \quad i-1 \in \mathbb{Z}_n. $ |
Next, we recall the generalized best approximation as follows (see Ref. [16]).
Definition[generalized best approximation] Given x∈
$ \left\langle x-\mathcal{P}_n x, y_n\right\rangle=0 \text { for all } y_n \in \mathbb{Y}_n. $ |
Similarly, given y∈
$ \left\langle x_n, y-\mathcal{P}_n^{\prime} y\right\rangle=0 \text { for all } x_n \in \mathbb{X}_n \text {. } $ |
Since
To represent the operator
1) For i′-1∈
$ \left\langle{\xi}_{i^{\prime}, j^{\prime}}, t^{r}\right\rangle=0, r \in Z_{k^{\prime}}, j=\in \mathbb{Z}_{w\left(i^{\prime}\right)}, i^{\prime}-1 \in \mathbb{Z}_n. $ |
2) The auxiliary functions {ξi, j∶(i, j)∈
$ \left\langle\xi_{i^{\prime}, j^{\prime}}, g_{i, j}\right\rangle=\delta_{i^{\prime} i} \delta_{j^{\prime} j}, \quad\left(i^{\prime}, j^{\prime}\right), (i, j) \in \mathbb{U}_n. $ |
These properties imply that the generalized best approximation from
$ \mathcal{P}_n^{\prime} y=\sum\limits_{(i, j) \in \mathbb{U}_n}\left\langle\xi_{i, j}, y\right\rangle g_{i, j}. $ |
With these preparation, we are ready to state the iterated Petrov-Galerkin method as follow.
The Petrov-Galerkin method for equation (1) is: finding un∈
$ \left\langle u_n-\mathcal{K}\;u_n, v_n\right\rangle=\left\langle f, v_n\right\rangle \quad \text { for all } v_n \in \mathbb{Y}_n \text {. } $ | (3) |
The iterated projection method is defined by Sloan iteration,
$ u_n^{\prime}:=f+\mathcal{K}\;u_n. $ | (4) |
It has been proved in Ref. [14] that the iterated projection approximation u′n satisfies the following integral equation
$ u_n^{\prime}-\mathcal{K}_n u_n^{\prime}=f, $ | (5) |
where
To present the convergence results of the iterated Petrov-Galerkin method, we need the following estimate on projection operator
Lemma 1.1 If the kernel function K∈Ck(I×I), then, for any i∈
$ \left|\mathcal{K}\left(\mathcal{I}-\mathcal{P}_i\right)\right| \leqslant c_1 \mu^{-k^{\prime} i}. $ |
Moreover, if u∈Hm with 0 < m≤k, we have
$ \left|\mathcal{K}\left(\mathcal{I}-\mathcal{P}_i\right) u\right| \leqslant c_2 \mu^{-\left(m+k^{\prime}\right) i}|u|_{H^m} . $ |
Proof Let Kt∶=K(t, ·). Since K∈Ck(I×I), we have for all t∈I, Kt∈Hk′(I), and
For any ϕ∈
$ \begin{aligned} \left|\mathcal{K}\left(\mathcal{I}-\mathcal{P}_i\right) \phi\right| & =\left|\int_I K(t, \tau)\left(\phi(\tau)-\mathcal{P}_i \phi(\tau)\right) \mathrm{d} s\right| \\ & =\left|\left\langle\phi-\mathcal{P}_i \phi, K_t\right\rangle\right| \\ & =\left|\left\langle\phi-\mathcal{P}_i \phi, K_t-\mathcal{P}_i^{\prime} K_t\right\rangle\right| \\ & \leqslant \mid\left\langle\phi-\mathcal{P}_i \phi|| K_t-\mathcal{P}_i^{\prime} K_t\right| \\ & \leqslant c_1 \mu^{-k^{\prime} i}|\phi| \end{aligned} $ |
This implies |
If u∈Hm, there exists a positive constant c2, such that |u-
$ \begin{aligned} \mid \mathcal{K}\left(\mathcal{I}-\mathcal{P}_i u \mid\right. & \leqslant\left|u-\mathcal{P}_i u\right|\left|K_t-\mathcal{P}_i^{\prime} K_t\right| \\ & \leqslant c_1 c_2 \mu^{-\left(m+k^{\prime}\right) i}|u|_{H^m}, \end{aligned} $ |
from which the desired estimate follows.
Theorem 1.1 Assume that
$ \left\|u-u_n^{\prime}\right\| \leqslant C \mu^{-\left(m+k^{\prime}\right) n}|u|_{H^m}. $ | (6) |
Proof It has been proved in Ref. [14] that
$ \left\|u-u_n^{\prime}\right\| \leqslant C\left\|\mathcal{K P}_n-\mathcal{K}\right\| \inf\limits_{x_n \in \mathbb{X}_n}\left\|u-x_n\right\| . $ | (7) |
From Lemma 1.1, we know that there exists a positive constant c such that
$ \left\|\mathcal{K} \mathcal{P}_n-\mathcal{K}\right\| \leqslant c \mu^{-k^{\prime} n}. $ |
Meanwhile, by the Proposition 1.1, we have
$ \inf\limits_{x_n \in \mathbb{X}_n}\left\|u-x_n\right\| \leqslant c_{k, m} \mu^{-m n}|u|_{H^m} . $ |
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.
2 Iterated fast wavelet Petrov-Galerkin methodsThis 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
$ \boldsymbol{c}_n:=\left[c_{i, j}\right]_{(i, j) \in \mathbb{U}_n}, \quad \boldsymbol{g}_n:=\left[\left\langle g_{i^{\prime}, j^{\prime}}, f\right\rangle\right]_{\left(i^{\prime}, j^{\prime}\right) \in \mathbb{U}_n}, $ |
and matrix notations
$ \boldsymbol{E}_n:=\left[\left\langle g_{i^{\prime}, j^{\prime}}, f_{i, j}\right\rangle\right]_{\left(i^{\prime}, j^{\prime}\right), (i, j) \in \mathbb{U}_n}, \boldsymbol{K}:=\left[\boldsymbol{K}_{i^{\prime}, i}\right]_{i^{\prime}, i \in \mathbb{Z}_{n+1}}, $ |
where Ki′, i∶=
$ \left(\boldsymbol{E}_n-\boldsymbol{K}_n\right) \boldsymbol{c}_n=\boldsymbol{g}_n. $ | (8) |
In equation (8), the matrix En is sparse, but Kn is dense. Fortunately, the elements in matrix Kn decay 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 matrix Kn will be presented.
Lemma 2.1 If the kernel function K∈Ck(I×I), then, for any i∈
$ \left|K_{i^{\prime}, j^{\prime} ; i, j}\right| \leqslant c \mu^{-\left(i+i^{\prime}\right)(k+1 / 2)}, $ | (9) |
where Ki′, j′; i, j=〈gi′, j′,
Proof By Taylor's Theorem, the kernel K can be rewritten as
$ K=K_1+K_2+K_3, $ |
where K1(t, ·), K2(·, τ) are polynomials of degree less than k-1 respect to τ and t respectively, and K3 is the remainder term in the integral form. That is
$ K_3(t, \tau):=\frac{\left(t-t_0\right)^k\left(\tau-\tau_0\right)^k}{k !\;k !} \gamma_{k, k}(t, \tau), $ |
where τ0∈Ii, j, t0∈I′(i′, j′), and
$ \begin{aligned} \gamma_{k, k}(t, \tau): & =\int_I \int_I K^{(k, k)}\left(t_0+\theta_1\left(t-t_0\right), \tau_0+\theta_2\left(\tau-\tau_0\right)\right) \\ & \left(1-\theta_1\right)^{k-1}\left(1-\theta_2\right)^{k-1} \mathrm{~d} \theta_1 \mathrm{~d} \theta_2 . \end{aligned} $ |
It can be proved that there exists a constant C>0 such that, for all (t, τ)∈I2,
$ \left|\gamma_{k, k}(t, \tau)\right| \leqslant C. $ |
Using the vanishing moments of fi, j, and gi′, j′, we have
$ \begin{aligned} \left|K_{i^{\prime}, j^{\prime} ; i, j}\right| & =\left|\int_I \int_I K(t, \tau) f_{i, j}(t) g_{i^{\prime}, j^{\prime}}(\tau) \mathrm{d}t\mathrm{d} \tau\right| \\ & =\left|\int_I \int_I K_3(t, \tau) f_{i, j}(t) g_{i^{\prime}, j^{\prime}}(\tau) \mathrm{d}t\mathrm{d}\tau\right| \\ & \leqslant\left|f_{i, j}\right|_{\infty}\left|g_{i^{\prime}, j^{\prime}}\right|_{\infty} \int_{I_{i, j}} \int_{I_{i^{\prime} j^{\prime}}}\left|K_3(t, \tau)\right| \mathrm{d}t\mathrm{d} \tau \\ & \leqslant \frac{C}{k !\;k !}\left|f_{i, j}\right|_{\infty}\left|g_{i^{\prime}, j^{\prime}}\right|_{\infty} \cdot \\ & \int_{I_{i, j}} \int_{I_{I^{\prime}, j^{\prime}}}\left|\left(t-t_0\right)^k\left(\tau-\tau_0\right)^k\right| \mathrm{d} t \mathrm{d} \tau \\ & \leqslant C_1\left|f_{i, j}\right|_{\infty}\left|g_{i^{\prime}, j^{\prime}}\right|_{\infty}\left(\left|I_{i, j}\right|\right)^{k+1}\left(\left|I_{i^{\prime}, j^{\prime}}^{\prime}\right|\right)^{k+1} . \end{aligned} $ |
By the Proposition 1.1, we know, for all
$ \begin{aligned} & j \in \mathbb{Z}_{w(i)}, j^{\prime} \in \mathbb{Z}_{w\left(i^{\prime}\right)}, i-1 \in \mathbb{Z}_n \cdot i^{\prime}-1 \in \mathbb{Z}_n, \\ & \sup\limits_{\tau \in I_{i, j}}\left|f_{i, j}(\tau)\right| \leqslant c \mu^{\frac{i-1}{2}}, \sup\limits_{\tau \in I^{\prime}\left(i^{\prime}, j^{\prime}\right)}\left|g_{i^{\prime}, j^{\prime}}(\tau)\right| \leqslant c \mu^{\frac{i^{\prime}-1}{2}} . \end{aligned} $ | (10) |
The following proof is divided into four cases, depending on whether i and i′ equal to zero or not.
Case 1 Assume i≥1, and i′≥1. There exists a positive constant c1 such that
$ \begin{aligned} \left|K_{i^{\prime}, j^{\prime}, i, j}\right| & \leqslant \mu^{\frac{i-1}{2}} \mu^{\frac{i^{\prime}-1}{2}} \mu^{-(k+1)(i-1)} \mu^{-(k+1)\left(i^{\prime}-1\right)} \\ & \leqslant c_1 \mu^{-(k+1 / 2)\left(i+i^{\prime}\right)} . \end{aligned} $ |
Case 2 Assume i=0, and i′≥1. There exists a positive constant c2 such that
$ \begin{aligned} \left|K_{i^{\prime} j^{\prime} ; 0, j}\right| & \leqslant C_1\left|f_{0, j}\right|_{\infty}\left|g_{i^{\prime}, j^{\prime}}\right|_{\infty}\left(\left|I_{i^{\prime}, j^{\prime}}^{\prime}\right|\right)^{k+1} \\ & \leqslant c_2 \mu^{-i^{\prime}(k+1 / 2)} \end{aligned} $ |
by noting that w(0)=k.
Case 3 Assume i≥1, and i′=0. There exists a positive constant c3 such that
$ \begin{aligned} \left|K_{0, j^{\prime} ; i, j}\right| & \leqslant C_1\left|f_{i, j}\right|_{\infty}\left|g_0, j^{\prime}\right|_{\infty}\left(\left|I_{(i, j)}\right|\right)^{k+1} \\ & \leqslant c_3 \mu^{-i(k+1 / 2)}. \end{aligned} $ |
Case 4 Assume i=0, and i′=0. There exists a positive constant c4 such that
$ \left|K_0, j^{\prime} ; 0, j\right| \leqslant c_4. $ |
Taking c∶=max{c1, c2, c3, c4}, we obtain the desired estimate (9).
Lemma 2.2 If the kernel function K∈Ck(I×I), then there exists a positive constant C independent of n such that, for all i, i′∈
$ \left|\boldsymbol{K}_{i^{\prime}, i}\right|_2 \leqslant C \mu^{-k\left(i+i^{\prime}\right)}. $ |
Proof By lemma 2.1, we have
$ \begin{aligned} \left|\boldsymbol{K}_{i^{\prime}, i}\right|_2^2 \leqslant\left|\boldsymbol{K}_{i^{\prime}, i}\right|_F^2 & \leqslant \sum\limits_{j \in w(i)}\sum\limits_{j^{\prime} \in w\left(i^{\prime}\right)}\left|K_{i^{\prime}, j^{\prime} ; i, j}\right|^2 \\ & \leqslant c^2 w(i) w\left(i^{\prime}\right) \mu^{-\left(i+i^{\prime}\right)(2 k+1)}. \end{aligned} $ |
Combing with (2), we get
$ \begin{aligned} \left|\boldsymbol{K}_{i^{\prime}, i}\right|_2^2 & \leqslant c^2 \mu^{i-1} \mu^{i^{\prime}-1} \mu^{-\left(i+i^{\prime}\right)(2 k+1)} \\ & \leqslant \frac{c^2}{\mu^2} \mu^{-2 k\left(i+i^{\prime}\right)}, \end{aligned} $ |
which completes the proof.
With the estimate in lemma 2.2, we present the following truncated matrix. Let
$ \tilde{\boldsymbol{K}}_n:=\left[\tilde{\boldsymbol{K}}_{i^{\prime}, i}\right]_{i^{\prime}, i \in \mathbb{Z}_{n+1}}, $ |
where
$ \tilde{\boldsymbol{K}}_{i^{\prime}, j}:= \begin{cases}\boldsymbol{K}_{i^{\prime}, i}, & i+i^{\prime} \leqslant n, \\ 0, & \text { else. }\end{cases} $ | (11) |
Replacing Kn in (8) by the truncated matrix
$ \left(\boldsymbol{E}_n-\tilde{\boldsymbol{K}}_n\right) \tilde{\boldsymbol{c}}_n=\boldsymbol{g}_n, $ | (12) |
where
Then we can present the fast method as follow.
Algorithm 2.1 iterated fast wavelet Petrov-Galerkin methods
Step 1 Solving the linear equations (12), we get
Step 2 Let
$ \tilde{u}:=\sum\limits_{(i, j) \in \mathbb{U}_n} \tilde{c}_{i, j} f_{i, j}, $ |
Step 3 Let the iterated approximation be
$ \tilde{u}_n^{\prime}:=\mathcal{K}\;\tilde{u}_n+f \text {. } $ | (13) |
To show the sparsity, we present the estimation on the number of nonzero entries of matrix En-
Theorem 2.1 There exists a positive constant C such that for all n∈
$ \mathcal{N}\left(\boldsymbol{E}_n-\boldsymbol{K}_n\right) \leqslant C S(n) \log S(n) $ |
In this section, we will analyze the convergence of the proposed IFPG method.
Let
$ \left|\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \mathcal{P}_n u\right| \leqslant c \mu^{-m n}|u|_{H^m}, $ | (14) |
where
With the help of estimate (14), we can make a conclusion on the iterated projection approximation.
Theorem 3.1 Assume that
$ \tilde{u}_n^{\prime}-\mathcal{K} \mathcal{Q}_n\;\mathcal{P}_n \tilde{u}_n^{\prime}=f, $ | (15) |
where
Proof From (13), we have
$ \begin{aligned} \mathcal{P}_n \tilde{u}_n^{\prime} & =\mathcal{P}_n\;\mathcal{K} \tilde{u}_n+\mathcal{P}_n f \\ & =\mathcal{P}_n\;\mathcal{K} \tilde{u}_n+\left(\tilde{u}_n-\tilde{\mathcal{K}}_n \tilde{u}_n\right) \\ & =\left(\mathcal{I}+\mathcal{P}_n\;\mathcal{K} \mathcal{P}_n-\mathcal{K}_n\right) \tilde{u}_n. \end{aligned} $ |
Since
$ \left|\mathcal{P}_n\;\mathcal{K P}_n-\tilde{\mathcal{K}}_n\right|<\frac{1}{2} . $ |
By Geometric series theorem, the inverse operator
$ \begin{aligned}\left|\left(\mathcal{I}+\mathcal{P}_n\;\mathcal{K} \mathcal{P}_n-\tilde{\mathcal{K}}_n\right)^{-1}\right| & \leqslant \frac{1}{1-\left|\mathcal{P}_n\;\mathcal{K} \mathcal{P}_n-\tilde{\mathcal{K}}_n\right|} \\ & <2 .\end{aligned} $ |
Let
$ \tilde{u}_n=\mathcal{Q}_n\;\mathcal{P}_n \tilde{u}_n^{\prime} $ | (16) |
Submitting (16) into (13), we can obtain (15).
Since
$ \mathcal{K} \mathcal{Q}_n\;\mathcal{P}_n-\mathcal{K}=\mathcal{K} \mathcal{Q}_n\left(\mathcal{P}_n-\mathcal{I}\right)+\mathcal{K} \mathcal{Q}_n\left(\mathcal{P}_n\;\mathcal{K} \mathcal{P}_n-\tilde{\mathcal{K}}_n\right), $ |
we can claim that
$ \lim\limits_{n \rightarrow \infty}\left|\mathcal{K} \mathcal{Q}_n\;\mathcal{P}_n-\mathcal{K}\right|=0. $ |
Hence, for sufficiently large n, the inverse
From equations (1) and (15), we have
$ \begin{aligned} \tilde{u}_n^{\prime}-u & =\left(\mathcal{I}-\mathcal{K} \mathcal{Q}_n\;\mathcal{P}_n\right)^{-1}\left(\mathcal{K} \mathcal{Q}_n\;\mathcal{P}_n-\mathcal{K}\right) u \\ & =\left(\mathcal{I}-\mathcal{K} \mathcal{Q}_n\;\mathcal{P}_n\right)^{-1}\left({\mathit{\Gamma}}_1+{\mathit{\Gamma}}_2+{\mathit{\Gamma}}_3\right), \end{aligned} $ | (17) |
where
Γ1∶=(
Γ2∶=
Γ3∶=
To analyze the convergence, we next focus on the estimate of Γi, i=1, 2, 3.
The estimate on Γ1 has been presented in Lemma 1.1. By Lemmas 1.1 and 2.2, we can state the following estimate on Γ2.
Lemma 3.1 If u∈Hm with 0 < m≤k, then, for a sufficiently large integer n, there exists a positive constant c independent of n such that,
$ \left|\mathcal{K}\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \mathcal{P}_n u\right| \leqslant c n \mu^{-\left(m+k^{\prime}\right) n}|u|_{H^m} . $ |
Proof We know that
$ \begin{aligned} & \left|\mathcal{K}\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \mathcal{P}_n u\right| \\ = & \sup _{v \in \mathbb{H}, v \neq 0}\left|\left\langle\mathcal{K}\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \mathcal{P}_n u, v\right\rangle\right| /|v| \\ = & \sup _{v \in \mathbb{H}, v \neq 0}\left|\left\langle\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \mathcal{P}_n u, K^* v\right\rangle\right| /|v| \\ = & \sup _{v \in \mathbb{H}, v \neq 0}\left|\left\langle\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \mathcal{P}_n u, \mathcal{P}_n^{\prime} K^* v\right\rangle\right| /|v| . \end{aligned} $ |
Since
Hence,
$ \begin{aligned} & \left|\left\langle\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \mathcal{P}_n u, \mathcal{P}_n^{\prime} \mathcal{K}^* v\right\rangle\right| \\ = & \sum\limits_{i, i^{\prime} \in {\mathbb{Z}}_{n+1}} \sum\limits_{j \in {\mathbb{Z}}_{w(i)}, j^{\prime} \in {\mathbb{Z}}_{w\left(j^{\prime}\right)}}\left\langle\mathcal{P}_n u, f_{i, j}\right\rangle\left\langle\xi_{i^{\prime}, j^{\prime}}, \mathcal{K}^* v\right\rangle \cdot \\ & \left\langle\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) f_{i, j}, g_{i^{\prime}, j^{\prime}}\right\rangle \mid \\ = & \sum\limits_{i, i^{\prime} \in {\mathbb{Z}}_{n+1}} \sum\limits_{j \in {\mathbb{Z}}_{w(i)}, j^{\prime} \in {\mathbb{Z}}_{w\left(j^{\prime}\right)}}\left\langle\mathcal{P}_n u, f_{i, j}\right\rangle \cdot \\ & \left\langle\xi_{i^{\prime}, j^{\prime}}, \mathcal{K}^* v\left(\tilde{K}_{i^{\prime}, j^{\prime} ; i, j}-K_{i^{\prime}, j^{\prime} ; i, j}\right)\right|\\ & \leqslant \sum\limits_{i, i^{\prime} \in \mathbb{Z}_{n+1}}\left|\tilde{\boldsymbol{K}}_{i^{\prime}, i}-\boldsymbol{K}_{i^{\prime}, i}\right|_2 \cdot \\ & \left|\left[\left\langle\mathcal{P}_n u, f_{i, j}\right\rangle\right]_{j \in w(i)}\right|_2\left|\left[\left\langle\xi_{i^{\prime}, j^{\prime}}, \mathcal{K}^* v\right\rangle\right]_{j^{\prime} \in w\left(i^{\prime}\right)}\right|_2 \\ & \leqslant \sum\limits_{i \in \mathbb{Z}_{n+1}} \sum\limits_{i+i^{\prime}>n}\left|\mathit{\boldsymbol{K}}_{i^{\prime}, i}\right|_2 \cdot \\ & \left|\left[\left\langle\mathcal{P}_n u, f_{i, j}\right\rangle\right]_{j \in w(i)}\right|_2\left|\left[\left\langle\xi_{i^{\prime}, j^{\prime}}, \mathcal{K}^* v\right\rangle\right]_{j^{\prime} \in w\left(i^{\prime}\right)}\right|_2 \\ \end{aligned} $ | (18) |
By Lemma 2.2, there exists a constant c1>0 such that,
$ \left|\boldsymbol{K}_{i^{\prime}, i}\right|_2 \leqslant c_1 \mu^{-k\left(i+i^{\prime}\right)}, \quad i, i^{\prime} \in \mathbb{Z}_{n+1} . $ | (19) |
To continue the analysis, let us focus on the estimate of |[〈
By noting 〈
$ \left|\left[\left\langle\mathcal{P}_n u, f_{i, j}\right\rangle\right]_{j \in w(i)}\right|_2 \leqslant\left|\left\langle\mathcal{P}_n u-u, f_{i, j}\right\rangle\right|_2+\left|\left\langle u, f_{i, j}\right\rangle\right|_2 . $ |
Meanwhile,
$ \begin{array}{l} \left|\left[\left\langle\mathcal{P}_n u-u, f_{i, j}\right\rangle\right]_{j \in w(i)}\right|_2 \leqslant\left|\mathcal{P}_n u-u\right| \leqslant c \mu^{-n m}|u|_{H^m} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \leqslant c \mu^{-i m}|u|_{H^m}, \\ \left|\left[\left\langle u, f_{i, j}\right\rangle\right]_{j \in w(i)}\right|_2=\left|\left(\chi_i-\chi_{i-1}\right) u\right| \leqslant c \mu^{-i m}|u|_{H^m} . \\ \end{array} $ |
Hence, we can conclude that
$ \left|\left[\left\langle\mathcal{P}_n u, f_{i, j}\right\rangle\right]_{j \in w(i)}\right|_2 \leqslant c \mu^{-i m}|u|_{H^m}. $ | (20) |
For |[〈ξi′, j′,
$ \boldsymbol{h}_{i^{\prime}}:=\left[\left\langle\xi_{p, q}, \left(\mathcal{P}_{i^{\prime}}^{\prime}-\mathcal{P}_{i^{\prime}-1}^{\prime}\right) \mathcal{K}^* v\right\rangle:(p, q) \in \mathbb{U}_{i^{\prime}}\right.. $ |
Since the bases {ξi, j} and {gi, j} are semi-biorthogonal, we get
$ \begin{aligned} \left\langle\xi_{i^{\prime}, q}, \left(\mathcal{P}_{i^{\prime}}^{\prime}-\mathcal{P}_{i^{\prime}-1}^{\prime}\right) \mathcal{K}^* v\right\rangle & =\left\langle\xi_{i^{\prime}, q}, \sum\limits_{j^{\prime} \in w\left(i^{\prime}\right)}\left\langle\xi_{i^{\prime} j^{\prime}}, \mathcal{K}^* v\right\rangle g_{i^{\prime} j^{\prime}}\right\rangle \\ & =\left\langle\xi_{i^{\prime}, q}, \mathcal{K}^* v\right\rangle, q \in w\left(i^{\prime}\right), \end{aligned} $ |
by noting
$ \left(\mathcal{P}_{i^{\prime}}^{\prime}-\mathcal{P}_{i^{\prime}-1}^{\prime}\right) \mathcal{K}^* v=\sum\limits_{j^{\prime} \in w\left(i^{\prime}\right)}\left\langle\xi_{i^{\prime}, j^{\prime}}, \mathcal{K}^* v\right\rangle g_{i^{\prime}, j^{\prime}} \in \mathbb{Y}_{i^{\prime}} $ |
Thus,
$ \left|\left[\left\langle\xi_{i^{\prime}, j^{\prime}}, \mathcal{K}^* v\right\rangle\right]_{j^{\prime} \in w\left(i^{\prime}\right)}\right|_2=\left|\boldsymbol{h}_{i^{\prime}}\right|_{l^2} \text {. } $ | (21) |
By Corollary 3.5 in Ref. [6], there exists a constant c2>0 such that
$ \left|\boldsymbol{h}_{i^{\prime}}\right|_{l^2} \leqslant c_2\left|\left(\mathcal{P}_{i^{\prime}}^{\prime}-\mathcal{P}_{i^{\prime}-1}^{\prime}\right) \mathcal{K}^* v\right|. $ |
Then, by Lemma 1.1, the estimate (21) can be continued as
$ \begin{aligned} \left|\left[\left\langle\xi_{i^{\prime} j^{\prime}}, \mathcal{K}^* v\right\rangle\right]_{j^{\prime} \in w\left(i^{\prime}\right)}\right|_2 & \leqslant c_2\left|\left(\mathcal{P}_{i^{\prime}}^{\prime}-\mathcal{P}_{i^{\prime}-1}^{\prime}\right) \mathcal{K}^* v\right| \\ & \leqslant c_2\left|\mathcal{K}\left(\mathcal{P}_{i^{\prime}}-\mathcal{P}_{i^{\prime}-1}\right)\right||v| \\ & \leqslant c \mu^{-k^{\prime} i^{\prime}}|v| . \end{aligned} $ | (22) |
Submitting (19), (20), and (22) into (18), we have
$ \begin{aligned} & \left|\left[\left\langle\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \mathcal{P}_n u, \mathcal{P}_n^{\prime} \mathcal{K}^* v\right\rangle\right| \\ & \leqslant c \sum\limits_{i \in \mathbb{Z}_{n+1}} \sum\limits_{i+i^{\prime}>n} \mu^{-k\left(i+i^{\prime}\right)} \mu^{-k^{\prime} i^{\prime}} \mu^{-i m}|u|_{H^m}|v| . \\ & \end{aligned} $ |
Noting that,
$ \begin{aligned} & \sum\limits_{i \in \mathbb{Z}_{n+1}} \sum\limits_{i+i^{\prime}>n} \mu^{-k\left(i+i^{\prime}\right)} \mu^{-k^{\prime} i^{\prime}} \mu^{-i m} \\ = & \sum\limits_{i \in \mathbb{Z}_{n+1}} \sum\limits_{i+i^{\prime}>n} \mu^{\left(k^{\prime}-k\right) i} \mu^{(m-k) i^{\prime}} \mu^{-\left(m+k^{\prime}\right)\left(i+i^{\prime}\right)} \\ \leqslant & c \mu^{-\left(m+k^{\prime}\right) n} \sum\limits_{i \in \mathbb{Z}_{n+1}} \sum\limits_{i+i^{\prime}>n} \mu^{-\left(k^{\prime}+m\right)\left(i+u^{\prime}-n\right)} \\ \leqslant & c n \mu^{-\left(m+k^{\prime}\right) n}, \end{aligned} $ |
then we have
$ \left|\mathcal{K}\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \mathcal{P}_n u\right| \leqslant c n \mu^{-\left(m+k^{\prime}\right) n}|u|_{H^m}, $ |
which completes the proof.
Now, we are ready to present the convergence results.
Theorem 3.2 Assume that
$ \left|u-\tilde{u}_n^{\prime}\right| \leqslant c S(n)^{-\left(m+k^{\prime}\right)} \log S(n)|u|_{H^m}, $ | (23) |
where c is a constant independent of n.
Proof From Lemma 1.1 and Lemma 3.1, we know there exist positive constants c1 and c2 such that
$ \begin{aligned} & \left|\mathit{{\Gamma}}_1\right| \leqslant c_1 \mu^{-\left(m+k^{\prime}\right) n}|u|_{H^m}, \\ & \left|{\mathit{\Gamma}}_2\right| \leqslant c_2 n \mu^{-\left(m+k^{\prime}\right) n}|u|_{H^m} . \end{aligned} $ | (24) |
Next, let us focus on Γ3. For any ϕ∈
$ \begin{aligned} \left|\mathcal{K}\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \phi\right| & =\sup _{v \in \mathbb{H}, v \neq 0}\left|\left\langle\mathcal{K}\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \phi, v\right\rangle\right| /|v| \\ & =\sup _{v \in \mathbb{H}, v \neq 0}\left|\left\langle\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \phi, \mathcal{K}^* v\right\rangle\right| /|v| \\ & =\sup _{v \in \mathbb{H}, v \neq 0}\left|\left\langle\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \phi, \mathcal{P}_n^{\prime} \mathcal{K}^* v\right\rangle\right| /|v| \end{aligned} $ |
where
$ \begin{aligned} & \left|\left\langle\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \phi, \mathcal{P}_n^{\prime} \mathcal{K}^* v\right\rangle\right| \\ & \leqslant \sum\limits_{i \in \mathbb{Z}_{n+1}} \sum\limits_{i+i^{\prime}>n}\left|\boldsymbol{K}_{i^{\prime}, i}\right|_2 \cdot \\ & \quad\left|\left[\left\langle\phi, f_{i, j}\right\rangle\right]_{j \in w(i)}\right|_2\left|\left[\left\langle\xi_{i^{\prime}, j^{\prime}}, \mathcal{K}^* v\right\rangle\right]_{j^{\prime} \in w\left(i^{\prime}\right)}\right|_2 . \end{aligned} $ |
Since |[〈ϕ, fi, j〉]j∈w(i)|2≤|ϕ|, we obtain
$ \begin{aligned} \left|\mathcal{K}\left(\tilde{\mathcal{K}}_n-\mathcal{K}_n\right) \phi\right| & \leqslant \sum\limits_{i \in \mathbb{Z}_{n+1}} \sum\limits_{i+i^{\prime}>n} \mu^{-k\left(i+i^{\prime}\right)} \mu^{-k^{\prime} i^{\prime}}|\phi| \\ & \leqslant c n \mu^{-k^{\prime} n}|\phi|, \end{aligned} $ |
by employ Lemma 2.2 and the inequality (22).
Then, by the fact
$ \begin{aligned} \left|{\mathit{\Gamma}}_3\right| & =\left|\mathcal{K}\left(\tilde{\mathcal{K}}_n-\mathcal{P}_n\;\mathcal{K} \mathcal{P}_n\right) \mathcal{Q}_n\left(\tilde{\mathcal{K}}_n-\mathcal{P}_n\;\mathcal{K}\right) \mathcal{P}_n u\right| \\ & \leqslant c n \mu^{-k^{\prime} n}\left|\left(\tilde{\mathcal{K}}_n-\mathcal{P}_n\;\mathcal{K}\right) \mathcal{P}_n u\right| \\ & \leqslant c_3 n \mu^{-\left(m+k^{\prime}\right) n}|u|_{H^m} . \end{aligned} $ |
Finally, submitting the estimate on Γi(i=1, 2, 3) into (17), we get desired (23), by noting the uniform boundedness of
[1] |
Atkinson K E. The numerical solution of integral equations of the second kind[M]. Cambridge: Cambridge University Press, 1997.
|
[2] |
Kress R. Singular integral equations[M]. New York, NY: Springer New York, 1999: 94-124. DOI:10.1007/978-1-4612-0559-3_7
|
[3] |
Beylkin G, Coifman R, Rokhlin V. Fast wavelet transforms and numerical algorithms I[J]. Communications on Pure and Applied Mathematics, 1991, 44(2): 141-183. DOI:10.1002/cpa.3160440202 |
[4] |
Harbrecht H, Schneider R. Wavelet Galerkin schemes for boundary integral equations-implementation and quadrature[J]. SIAM Journal on Scientific Computing, 2006, 27(4): 1347-1370. DOI:10.1137/S1064827503429387 |
[5] |
Harbrecht H, Multerer M. A fast direct solver for nonlocal operators in wavelet coordinates[J]. Journal of Computational Physics, 2021, 428: 110056. DOI:10.1016/j.jcp.2020.110056 |
[6] |
Huang M. A construction of multiscale bases for Petrov-Galerkin methods for integral equations[J]. Advances in Computational Mathematics, 2006, 25(1-3): 7-22. DOI:10.1007/S10444-003-7607-7 |
[7] |
Micchelli C A, Xu Y S, Zhao Y H. Wavelet Galerkin methods for second-kind integral equations[J]. Journal of Computational and Applied Mathematics, 1997, 86(1): 251-270. DOI:10.1016/S0377-0427(97)00160-X |
[8] |
Cai H T, Xu Y S. A fast Fourier-Galerkin method for solving singular boundary integral equations[J]. SIAM Journal on Numerical Analysis, 2008, 46(4): 1965-1984. DOI:10.1137/070703478 |
[9] |
Jiang Y, Xu Y S. Fast Fourier-Galerkin methods for solving singular boundary integral equations: Numerical integration and precondition[J]. Journal of Computational and Applied Mathematics, 2010, 234(9): 2792-2807. DOI:10.1016/j.cam.2010.01.022 |
[10] |
Wang B, Wang R, Xu Y S. Fast Fourier-Galerkin methods for first-kind logarithmic-kernel integral equations on open arcs[J]. Science in China Series A: Mathematics, 2010, 53(1): 1-22. DOI:10.1007/S11425-010-0014-X |
[11] |
Jiang Y, Wang B, Xu Y S. A fast Fourier-Galerkin method solving a boundary integral equation for the biharmonic equation[J]. SIAM Journal on Numerical Analysis, 2014, 52(5): 2530-2554. DOI:10.1137/140955744 |
[12] |
Jiang Y, Wang B, Xu Y S. A fully discrete fast Fourier-Galerkin method solving a boundary integral equation for the biharmonic equation[J]. Journal of Scientific Computing, 2018, 76(3): 1594-1632. DOI:10.1007/S10915-018-0688-8 |
[13] |
Chen Z Y, Xu Y S. The Petrov-Galerkin and iterated Petrov-Galerkin methods for second-kind integral equations[J]. SIAM Journal on Numerical Analysis, 1998, 35(1): 406-434. DOI:10.1137/S0036142996297217 |
[14] |
Sloan I H. Math. Concepts Methods Sci. Engrg. : volume 42 Super-convergence[M]. [S. l. ]: Plenum, New York, 1990: 35-70.
|
[15] |
Chen Z Y, Micchelli C A, Xu Y S. The Petrov-Galerkin method for second kind integral equations Ⅱ: Multiwavelet schemes[J]. Advances in Computational Mathematics, 1997, 7(3): 199-233. DOI:10.1023/A:1018994802659 |
[16] |
Chen Z Y, Micchelli C A, Xu Y S. Multiscale methods for Fredholm integral equations[M]. Cambridge: Cambridge University Press, 2015.
|