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, $\mathbb{X}$ is a Hilbert space and $\mathcal{K}$: $\mathbb{X}$→$\mathbb{X}$ is a compact operator with smooth kernel function K defined by

$(\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 method

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 space $\mathbb{X}_n \subset \mathbb{X}$ and $\mathbb{Y}_n \subset \mathbb{X}$ and the multiscale wavelet bases for them.

Let $\mathbb{S}^k_m$ be the space of piecewise polynomials of degree at most k-1 defined on I, corresponding to m sub-intervals equally divided. We choose positive integers k, k′, μ satisfying k=k′μ and define trial spaces and test spaces

$\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 {$\mathbb{X}_n$, $\mathbb{Y}_n$} forms a regular pair of subspaces, we also call them (k, k′) elements. It is straightforward to compute that

$\operatorname{dim} \mathbb{X}_n=\operatorname{dim} \mathbb{Y}_n:=S(n)=k \mu^n.$

For any n∈$\mathbb{N}$∶={1, 2, …}, let $\mathbb{U}_n$ be the set of lattice points in $\mathbb{R}^2$ defined as

$\mathbb{U}_n:=\left\{(i, j): j \in \mathbb{Z}_{w(i)}, i \in \mathbb{Z}_{n+1}\right\}$

where $\mathbb{Z}_{n+1}$∶={0, 1, 2, …, n}, and

$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 {f_{i, j}∶(i, j)∈$\mathbb{U}_n$} and {g_{i, j}∶(i, j)∈$\mathbb{U}_n$} be the bases for $\mathbb{X}_n$ and $\mathbb{Y}_n$, respectively. These bases enjoy the following propositions. We denote by H^m the classical Sobolev space.

Proposition 1.1  Assume that {f_{i, j}∶(i, j)∈$\mathbb{U}_n$} and {g_{i, j}∶(i, j)∈$\mathbb{U}_n$} are bases for $\mathbb{X}_n$ and $\mathbb{Y}_n$, respectively, constructed as in section 2 in Ref.[6].

Then, we have

1) {f_{i, j}∶(i, j)∈$\mathbb{U}_n$} is an orthonormal basis for $\mathbb{X}_n$.

2) {g_{i, j}∶(i, j)∈$\mathbb{U}_n$} and {f_{i′, j′}∶(i′, j′)∈$\mathbb{U}_n$} are semi-biorthogonal, namely

$\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 f_{i, j}, g_{i, j}, (i, j)∈$\mathbb{U}_n$ have k order of vanishing moments, i.e.,

$\left\langle f_{i, j}, h\right\rangle=0, \quad\left\langle g_{i, j}, h\right\rangle=0,$

where h(t)∶=t^r, t∈I, r∈$\mathbb{Z}_k$.

4) If u∈H^m 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 c_{k, m}=(k+1-m)^m2^-m+1/2.

5) The length of the supports supp(f_{i, j}) and supp(g_{i, 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∈$\mathbb{X}$ an element $\mathcal{P}_{n}x$∈$\mathbb{X}_n$ is called a generalized best approximation from $\mathbb{X}_n$ to x with respect to $\mathbb{Y}_n$ if it satisfies the equation

$\left\langle x-\mathcal{P}_n x, y_n\right\rangle=0 \text { for all } y_n \in \mathbb{Y}_n.$

Similarly, given y∈$\mathbb{X}^*$=$\mathbb{X}$ an element $\mathcal{P}_{n}y$∈$\mathbb{Y}_n$ is called a generalized best approximation from $\mathbb{Y}_n$ to y with respect to $\mathbb{X}_n$ if it satisfies the equation

$\left\langle x_n, y-\mathcal{P}_n^{\prime} y\right\rangle=0 \text { for all } x_n \in \mathbb{X}_n \text {. }$

Since $\mathbb{Y}_n$∩$\mathbb{X}_n^⊥$=0, the operator $\mathcal{P}_n$∶$\mathbb{X}$→ $\mathbb{X}_n$ is a projection.

To represent the operator $\mathcal{P}_n^′$ specifically, we also need a sequence of auxiliary functions {ξ_{i, j}∶(i, j)∈$\mathbb{U}_n$} in $\mathbb{X}_n$ (see Ref. [6]). These auxiliary functions enjoy the following properties.

1) For i′-1∈$\mathbb{Z}_n$, j′∈$\mathbb{Z}_{w(i′)}$, functions ξ_{i′, j′} have k′ order of vanishing moments, that is

$\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)∈$\mathbb{U}_n$} is biorthogonal relative to the set of functions {g_{i, j}∶(i, j)∈$\mathbb{U}_n$} that is,

$\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 $\mathbb{Y}_n$ to y with respect to $\mathbb{X}_n$ is

$\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 u_n∈$\mathbb{X}_n$, such that,

$\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 $\mathcal{K}_n$∶=$\mathcal{P}_{n}\mathcal{K}|_{\mathbb{X}_n}$.

To present the convergence results of the iterated Petrov-Galerkin method, we need the following estimate on projection operator $\mathcal{P}_n$.

Lemma 1.1  If the kernel function K∈C^k(I×I), then, for any i∈$\mathbb{N}$, there exist constants c₁ and c₂ independent of n such that

$\left|\mathcal{K}\left(\mathcal{I}-\mathcal{P}_i\right)\right| \leqslant c_1 \mu^{-k^{\prime} i}.$

Moreover, if u∈H^m 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 K_t∶=K(t, ·). Since K∈C^k(I×I), we have for all t∈I, K_t∈H^k′(I), and

$\left|K_t-\mathcal{P}_i^{\prime} K_t\right| \leqslant c \mu^{-k^{\prime} i}\left|K_t\right|_{H^{k^{\prime}}} \leqslant c|K|_{H^k} \mu^{-k^{\prime} i}$, where c is a constant independent of t and i.

For any ϕ∈$\mathbb{X}$, we have $\mathcal{P}_i^′K_t$∈$\mathbb{Y}_i$ and 〈ϕ-$\mathcal{P}_i$ϕ, $\mathcal{P}_i^′K_t$〉=0. Hence,

$\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 |$\mathcal{K}$(-$\mathcal{I}-\mathcal{P}_i$)|≤c₁μ^-k′i.

If u∈H^m, there exists a positive constant c₂, such that |u-${\mathcal{P}_i}^u$|≤c₂μ^-mi. Then

$\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 $\mathcal{K}$ is a compact operator on $\mathbb{X}$ not having 1 as an eigenvalue. Let u∈L²(I) be the unique solution of (1) and u′_n be the iterated projection approximation defined by (4). Then, there exists a positive constant C independent of n for which

$\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 methods

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

$\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 K_{i′, i}∶=$\left[\left\langle g_{i^{\prime}, j^{\prime}}, \mathcal{K} f_{i, j}\right\rangle\right]_{j^{\prime} \in \mathbb{Z}_{w\left(i^{\prime}\right)}, j \in \mathbb{Z} w(i)}$, the equation (3) can be rewritten as

$\left(\boldsymbol{E}_n-\boldsymbol{K}_n\right) \boldsymbol{c}_n=\boldsymbol{g}_n.$

(8)

In equation (8), the matrix E_n is sparse, but K_n is dense. Fortunately, the elements in matrix K_n 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 K_n will be presented.

Lemma 2.1  If the kernel function K∈C^k(I×I), then, for any i∈$\mathbb{N}$, there exist a positive constant c independent of n such that, for all (i, j), (i′, j′)∈$\mathbb{U}_n$

$\left|K_{i^{\prime}, j^{\prime} ; i, j}\right| \leqslant c \mu^{-\left(i+i^{\prime}\right)(k+1 / 2)},$

(9)

where K_{i′, j′; i, j}=〈g_{i′, j′}, $\mathcal{K}\; f_{i, j}$〉.

Proof  By Taylor's Theorem, the kernel K can be rewritten as

$K=K_1+K_2+K_3,$

where K₁(t, ·), K₂(·, τ) are polynomials of degree less than k-1 respect to τ and t respectively, and K₃ 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 τ₀∈I_{i, j}, t₀∈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, τ)∈I²,

$\left|\gamma_{k, k}(t, \tau)\right| \leqslant C.$

Using the vanishing moments of f_{i, j}, and g_{i′, 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 c₁ 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 c₂ 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 c₃ 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 c₄ such that

$\left|K_0, j^{\prime} ; 0, j\right| \leqslant c_4.$

Taking c∶=max{c₁, c₂, c₃, c₄}, we obtain the desired estimate (9).□

Lemma 2.2  If the kernel function K∈C^k(I×I), then there exists a positive constant C independent of n such that, for all i, i′∈$\mathbb{Z}_{n+1}$,

$\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 K_n in (8) by the truncated matrix $\tilde{\boldsymbol{K}}_n$, we get the sparse linear system

$\left(\boldsymbol{E}_n-\tilde{\boldsymbol{K}}_n\right) \tilde{\boldsymbol{c}}_n=\boldsymbol{g}_n,$

(12)

where $\tilde{\boldsymbol{c}}_n: =\left[\tilde{c}_{i, j}: =(i, j) \in \mathbb{U}_n\right]$ is desired.

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 $\tilde{\boldsymbol{c}}_n$.

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 E_n-$\widetilde{\boldsymbol{K}}_n$, which has been proved in Ref. [16]. We use the notation $\mathcal{N}(M)$ to denote the number of nonzero entries of matrix M.

Theorem 2.1  There exists a positive constant C such that for all n∈$\mathbb{N}$,

$\mathcal{N}\left(\boldsymbol{E}_n-\boldsymbol{K}_n\right) \leqslant C S(n) \log S(n)$

3 Convergence analysis

In this section, we will analyze the convergence of the proposed IFPG method.

Let $\mathcal{K}_n$ be a bounded linear integral operator relative to the basis {f_{i, j}∶=(i, j)∈$\mathbb{U}_n$} having the matrix representation E_n^-1$\widetilde{\boldsymbol{K}}_n$. It has been proved in Ref. [16, Theorem 3.4.12] that if u∈H^m, then there exists a constant c > 0 such that

$\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 $\mathcal{K}_n$∶=$\mathcal{P}_n\mathcal{K}\mathcal{P}_n$.

With the help of estimate (14), we can make a conclusion on the iterated projection approximation.

Theorem 3.1  Assume that $\mathcal{K}$ is a compact operator on $\mathbb{X}$ not having 1 as an eigenvalue. Then, the iterated projection approximation $\tilde{u}_n^{\prime}$, defined by (13), satisfies

$\tilde{u}_n^{\prime}-\mathcal{K} \mathcal{Q}_n\;\mathcal{P}_n \tilde{u}_n^{\prime}=f,$

(15)

where $\mathcal{Q}_n=\left(\mathcal{I}+\mathcal{P}_n\;\mathcal{K \mathcal { P } _ { n }}-\tilde{K}_n\right)^{-1}$.

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 $\lim\limits_{n \rightarrow \infty}\left|\mathcal{P}_n\;\mathcal{K} \mathcal{P}_n-\tilde{\mathcal{K}}_n\right|=0$, then there exists N>0 such that, for all n≥N,

$\left|\mathcal{P}_n\;\mathcal{K P}_n-\tilde{\mathcal{K}}_n\right|<\frac{1}{2} .$

By Geometric series theorem, the inverse operator $\left[\mathcal{I}+\mathcal{P}_n\;\mathcal{K} \mathcal{P}_n-\tilde{\mathcal{K}}_n\right]^{-1}$ exists, and

$\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 $\mathcal{Q}_n: =\left(\mathcal{I}+\mathcal{P}_n\;\mathcal{K} \mathcal{P}_n-\tilde{\mathcal{K}}_n\right)^{-1}$, then we have

$\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 $\left[\mathcal{I}-\mathcal{K} \mathcal{Q}_n\;\mathcal{P}_n\right]^{-1}$ exists. The equation (15) has a unique solution $\tilde u\mathit{'}$.□

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

Γ₁∶=($\mathcal{K}$$\mathcal{P}_n-\mathcal{K}$)u,

Γ₂∶=$\mathcal{K}\left(\tilde{\mathcal{K}}_n-\mathcal{P}_n\;\mathcal{K}\right) \mathcal{P}_n u$,

Γ₃∶=$\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$.

To analyze the convergence, we next focus on the estimate of Γ_i, i=1, 2, 3.

The estimate on Γ₁ has been presented in Lemma 1.1. By Lemmas 1.1 and 2.2, we can state the following estimate on Γ₂.

Lemma 3.1  If u∈H^m 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 ${\mathcal{P}_n}^u$∈$\mathbb{X}_n$, $\mathcal{P}^′_nv$∈$\mathbb{Y}_n$, we can represent them as $\mathcal{P}_n$u=$\sum\limits_{(i, j) \in \mathbb{U}_n}\left\langle\mathcal{P}_n u, f_{i, j}\right\rangle f_{i, j}$, $\mathcal{P}_n^{\prime} v=\sum\limits_{(i, j) \in \mathbb{U}_n}\left\langle\xi_{i, j}, v\right\rangle g_{i, j}$.

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 c₁>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 |[〈$\mathcal{P}_nu$, f_{i, j}〉]_j∈w(i)|₂, and |[〈ξ_{i′, j′}, $\mathcal{K}^*v$〉]_{j′∈w(i′)}|₂, respectively.

By noting 〈 $\mathcal{P}_n$u, f_{i, j}〉=〈 $\mathcal{P}_n$u-u, f_{i, j}〉+〈u, f_{i, j}〉, we have

$\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′}, $\mathcal{K}^*\; \; v$〉]_{j′∈w(i′)}|₂, we introduce a notation

$\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 {g_{i, 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 c₂>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 $\mathcal{K}$ is a compact operator on $\mathbb{X}$ not having 1 as an eigenvalue. For 0 < m≤k, if u∈H^m and K∈C^k(I×I), then, for a sufficiently large integer n, the iterated projection approximation $\tilde{u}_n^{\prime}$, defined by (13), satisfies.

$\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 c₁ and c₂ 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 Γ₃. For any ϕ∈$\mathbb{X}_n$, we have

$\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 |[〈ϕ, f_{i, j}〉]_j∈w(i)|₂≤|ϕ|, 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 $\mathcal{Q}_n\left(\tilde{\mathcal{K}}_n-\mathcal{P}_n\;\mathcal{K}\right) \mathcal{P}_n u \in \mathbb{X}_n$ and the inequality (14), we know that

$\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 $\left(\mathcal{I}-\mathcal{K Q}_n \mathcal{P}_n\right)^{-1}$.□