Wavelets Application to the Petrov-Galerkin Method

for Hammerstein Equations

Hideaki Kaneko, Richard D. Noren and Boriboon Novaprateep

Department of Mathematics and Statistics Old Dominion University Norfolk, Virginia 23529-0077

WAVELETS APPLICATION TO THE PETROV-GALERKIN METHOD FOR HAMMERSTEIN EQUATIONS

H. Kaneko, R. D. Noren and B. Novaprateep

Abstract The purpose of this paper is two-fold. First, we develop the Petrov-Galerkin method and the iterated Petrov-Galerkin method for a class of nonlinear Hammerstein equations. Alpert [?] established a class of wavelet basis and applied it to approximate solutions of the Fredholm second kind integral equations by the Galerkin method. He then demonstrated an advantage of a wavelet basis application to such equations by showing that the corresponding linear system is sparse. The second purpose of this paper is to study how this advantage of the sparsity can be extended to nonlinear Hammerstein equations.

1 Introduction

In this paper we study the Hammerstein integral equation

u(t) − ∫_{0}^{1} k(s, t)ψ(s, u(s))ds = f(t),  0 ≤ t ≤ 1.  (1.1)

For known functions k, ψ and f, an unknown solution u is to be approximated. We establish in this paper the Petrov-Galerkin and iterated Petrov-Galerkin methods to approximate u. Equation (1.1) arises as a reformulation of two-point boundary value problems with a certain nonlinear boundary condition, [?]. Also multi-dimensional analogues of equation (1.1) appear as various reformulations of an elliptic partial differential equation with nonlinear boundary conditions; see, e.g., [?, ?]. We shall discuss the present methods in relation to one-dimensional Hammerstein equation of (1.1), however, the theory developed in this paper can be extended straightforwardly to multi-dimensional cases.

The Galerkin and collocation methods are two commonly used methods for the numerical solution of the second kind Fredholm equations as well as for the Hammerstein equation (1.1). Many papers have appeared on these methods and a large part of the results presented in these papers were recently compiled in the monograph by Atkinson, [?]. The superconvergence of the iterated Galerkin method and that of the iterated collocation method for Hammerstein equation (1.1) were obtained recently in [?] and in [?] respectively. On the other hand, the Petrov-Galerkin and iterated Petrov-Galerkin methods are established in [?] for the second kind Fredholm equation

u(t) − ∫_{0}^{1} k(s, t)u(s)ds = f(t), 0 ≤ t ≤ 1. (1.2)

It is noted in [?] that the Petrov-Galerkin method includes the Galerkin, collocation, and least squares methods as well as many other nonstandard but useful methods as special cases. Unlike the standard Galerkin method, the Petrov-Galerkin method allows the trial space sequence X_{n} ⊂ X and the test space sequence Y_{n} ⊂ X^{∗} (the dual of X) to be different. This feature provides a greater freedom in choosing a pair of space sequences {X_{n}, Y_{n}} so as to improve the computational efficiency over the standard Galerkin method while preserving its convergence order.

In [?], Chen, Micchelli and Xu established the Petrov-Galerkin method for equation (1.2) using a class of orthogonal multiwavelets on [0,1]. Results of this paper show that the wavelet Petrov-Galerkin method for second kind Fredholm integral equations yields linear systems having numerically sparse coefficient matrices whose condition number is bounded. They also developed a truncation strategy that leads to linear systems having sparse coefficient matrices, thus providing a framework for fast algorithms for obtaining approximate solutions. Moreover, their approximate solutions have almost optimal order of convergence. In this paper, we use the wavelet basis constructed by Alpert in [?] to examine closely how the advantage of sparsity obtained by the application of the wavelet basis for the linear equations would manifest itself in the nonlinear equations (1.1).

Throughout this paper we will make the following assumptions on ψ, k and f.

1. lim_{t→τ} ∥ k_{t} − k_{τ} ∥_{∞}= 0, τ ∈ [0, 1] (k_{a}(b) ≡ k(a, b));

2. M_{1} ≡ sup_{0≤t≤1} ∫_{0}^{1} |k(t, s)|ds < ∞;

3. f ∈ C[0, 1];

4. ψ(s, x) is continuous on [0, 1] × R and there exists C_{1} > 0 such that |ψ(s, x_{1}) − ψ(s, x_{2})| ≤ C_{1}|x_{1} − x_{2}| for all x_{1}, x_{2} ∈ R;

5. There is a constant C_{2} such that the partial derivative ψ^{(0,1)} of ψ with respect to the second variable satisfies |ψ^{(0,1)}(t, x_{1}) − ψ^{(0,1)}(t, x_{2})| ≤ C_{2}|x_{1} − x_{2}| for all x_{1}, x_{2} ∈ R;

6. For x ∈ C[0, 1], ψ(·, x(·)), ψ^{(0,1)}(·, x(·)) ∈ C[0, 1].

Although 2 follows from 1 by compactness of [0, 1] and continuity, we list 2 explicitly for convenience.

Our first objective in this paper is to establish the Petrov-Galerkin and iterated Petrov-Galerkin methods for the Hammerstein equation (1.1). We will use the theoretical framework of Chen and Xu [?], and a detailed analysis similar to that of Kaneko and Xu [?], and to Vainikko [?]. Our main theorems in this regard are Theorems 2.6 and 2.7.

Our second objective is to establish a framework for fast algorithms for obtaining approximate solutions. As was stated earlier, a utilization of wavelet basis in approximating a solution of the second kind Fredholm equation results in a matrix system that is sparse, see [?] and [?]. The sparsity is obtained from two important characteristics of the wavelet bases; the property of vanishing moments and the property that each wavelet basis element away from the diagonal has a small support. In section 3, we discuss the Petrov-Galerkin method with wavelet bases and its related topics. The main theorem is Theorem 3.4. In section 4, we address the problem of obtaining sparsity results for the Hammerstein equations (1.1). The substitution z = ψ(·, u(·)) used in [?] will allow us to accomplish this in the setting of nonlinear equations. With this substitution, it will be shown that the sparsity takes place in the Jacobian matrix during the application of the Newton’s iterative method.

2 The Petrov-Galerkin Method for Hammerstein Equation

We begin this section with a brief review of the Petrov-Galerkin method. We follow closely the paper by Chen and Xu, [?]. Let X be a Banach space and X^{∗} its dual space of continuous linear functionals. For each positive integer n, we assume that X_{n} ⊂ X, Y_{n} ⊂ X^{∗}, and X_{n} and Y_{n} are finite dimensional vector spaces with

dim X_{n} = dim Y_{n}.

We further assume the following approximation property.

(H) If x ∈ X and y ∈ Y, then there are sequences {x_{n}}, {y_{n}} with x_{n} ∈ X_{n}, y_{n} ∈ Y_{n} for all n such that x_{n} → x, and y_{n} → y.

Define K by

Ku(t) = ∫_{0}^{1} k(s, t)u(s)ds

and Ψ by

Ψx(t) = ψ(t, x(t)).

With the assumption K, Ψ : X → X, equation (1.1) can be written as

u − KΨu = f, f ∈ X.  (2.1)

Define, for x ∈ X, an element P_{n}x ∈ X_{n} called the generalized best approximation from X_{n} to x with respect to Y_{n} by the equation

⟨x − P_{n}x, y_{n}⟩ = 0  for all y_{n} ∈ Y_{n}.  (2.2)

It is proved in [?], [Proposition 2.1], that for each x ∈ X, the generalized best approximation from X_{n} to x with respect to Y_{n} exists uniquely if and only if

Y_{n} ⋂ X_{n}^{⊥} = {0},  (2.3)

where X_{n}^{⊥} = {x^{∗} ∈ X^{∗} : ⟨x, x^{∗}⟩ = 0 for all x ∈ X_{n}}. When condition (2.3) is satisfied, P_{n} defines a projection; P_{n}^{2} = P_{n}. Throughout the remainder of this paper, condition (2.3) is assumed.

In order to formulate the Petrov-Galerkin method as part of the general projection scheme and render an appropriate error analysis accordingly, it is important to establish that P_{n} converges pointwise to the identity operator I. To this end, the notion of regular pair is introduced. Assume that, for each n, there is a linear operator Π_{n}: X_{n} → Y_{n} with Π_{n}X_{n} = Y_{n} and satisfying the following two conditions.

(H-1) ∥ x_{n} ∥≤ C_{1}⟨x_{n}, Π_{n}x_{n}⟩^{1/2} for all x_{n} ∈ X_{n}.

(H-2) ∥ Π_{n}x_{n} ∥≤ C_{2} ∥ x_{n} ∥ for all x_{n} ∈ X_{n}.

Here C_{1} and C_{2} are constants independent of n.

If a pair of space sequences {X_{n}} and {Y_{n}} satisfy (H-1) and (H-2) , we call {X_{n}, Y_{n}} a regular pair. It is shown in [?], [Proposition 2.4], that, if a regular pair {X_{n}, Y_{n}} satisfies dim X_{n} = dim Y_{n} and condition (H), then the corresponding generalized projection P_{n} satisfies:

(P1) ∥ P_{n}x − x ∥→ 0 as n → ∞ for all x ∈ X,

(P2) ∥ P_{n} ∥≤ C, n = 1, 2, 3, ..., for some constant C, and

(P3) ∥ P_{n}x − x ∥≤ c ∥ Q_{n}x − x ∥, n = 1, 2, 3, ..., for some constant c,

where Q_{n}x is the best approximation from X_{n} to x.

The Petrov-Galerkin approximation to the Fredholm second kind equation (1.2) is obtained by solving for u_{n} of the following equation:

⟨u_{n} − Ku_{n}, y_{n}⟩ = ⟨f, y_{n}⟩  for all y_{n} ∈ Y_{n}.  (2.4)

This is consistent with the basic principle that underlies the projection method, which requires the residual r_{n} ≡ u_{n}−Ku_{n}−f to disappear under a projection. Using the generalized projection P_{n}, equation (2.4) can be written in operator form as

u_{n} − P_{n}Ku_{n} = P_{n}f.  (2.5)

Therefore, the Petrov-Galerkin method is a projection method.

We recall the following three theorems that will become instrumental in establishing our main theorems in this section.

Theorem 2.1 (see, e.g.,[?]) Let X be a Banach space and {X_{n}} a sequence of finite-dimensional subspaces of X. Assume that K: X → X is a compact linear operator not having 1 as an eigenvalue. Let P̂_{n} : X → X_{n} be a sequence of linear projections that converges pointwise to the identity operator I in X. Then, for sufficiently large n, the equation

u_{n} − P̂_{n}Ku_{n} = P̂_{n}f  (2.6)

has a unique solution u_{n} ∈ X_{n} with

∥ u_{n} − u ∥≤ C ∥ u − P̂_{n}u ∥,

where C is a constant independent of n and u is the unique solution of equation (1.1).

Theorem 2.2 ([?]) Let X be a Banach space and K: X → X a compact linear operator. Assume that 1 is not an eigenvalue of the operator K. Suppose that {X_{n}, Y_{n}} is a regular pair that satisfies dim X_{n} = dim Y_{n} and condition (H). Then, for any given f ∈ X, there exists a positive integer N such that, for all n ≥ N, the Petrov-Galerkin equation (2.6) has a unique solution u_{n} ∈ X_{n} that satisfies

∥ u − u_{n} ∥≤ C inf_{x_{n}∈X_{n}} ∥ u − x_{n} ∥, n ≥ N,

where C is a constant independent of n and u ∈ X is the unique solution of equation (1.1).

We will establish an analogous result to Theorem 2.2 for the Hammerstein equation (2.1). To this end, we recall the third theorem below which is due to Vainikko [?]. This useful theorem describes the conditions that are necessary to approximate a solution of a class of nonlinear operator equation.

Theorem 2.3 Let T and T̃ be continuous over an open set Ω in a Banach space X. Let the equation

x = T̃x

have an isolated solution x̃_{0} ∈ Ω and let the following conditions be satisfied:

(a) The operator T is Fréchet differentiable in some neighborhood of the point x̃_{0} while the linear operator I − T′(x̃_{0}) is continuously invertible;

(b) Suppose that for some δ > 0, and 0 < q < 1, the following inequalities are valid (the number δ is assumed to be so small that the sphere ∥ x − x̃_{0} ∥≤ δ is contained within Ω)

sup_{∥x−x̃_{0}∥≤δ} ∥ (I − T′(x̃_{0}))^{−1}(T′(x) − T′(x̃_{0})) ∥≤ q,  (2.7)
α ≡∥ (I − T′(x̃_{0}))^{−1}(T (x̃_{0}) − T̃(x̃_{0})) ∥≤ δ(1 − q).  (2.8)

Then the equation x = T x has in the sphere ∥ x − x̃_{0} ∥≤ δ a unique solution x_{0}. Moreover, the inequality

\frac{α}{1 + q} ≤∥ x_{0} − x̃_{0} ∥≤ \frac{α}{1 − q}  (2.9)

is valid.

The Petrov-Galerkin method for the Hammerstein equation (2.1) is defined by

⟨u_{n} − KΨu_{n}, y_{n}⟩ = ⟨f, y_{n}⟩  for all y_{n} ∈ Y_{n}.  (2.10)

Equation (2.10) is equivalent, in operator form, to

u_{n} − P_{n}KΨu_{n} = P_{n}f.  (2.11)

Let

T̃x ≡ KΨx + f  (2.12)

and

T_{n}x_{n} ≡ P_{n}KΨx_{n} + P_{n}f,  (2.13)

Then equations (2.1) and (2.11) can be written as

u = T̃u  (2.14)

and

u_{n} = T_{n}u_{n}  (2.15)

respectively. We are now ready to state and prove our first theorem.

Theorem 2.4 Let u_{0} be an isolated solution of equation (2.1) in the Banach space X = L^{∞}[0, 1]. Assume that 1 is not an eigenvalue of KΨ′(u_{0}), where Ψ′(x_{0}) denotes the Fréchet derivative of Ψ at x_{0}. Then the Petrov-Galerkin approximation equation (2.11) has, for each sufficiently large n, a unique solution u_{n} in some ball of radius δ centered at x_{0}, B(x_{0}, δ). Further, there exists 0 < q < 1, independent of n, such that if

α_{n} ≡∥ (I − T′_{n}(u_{0}))^{−1}(T_{n}(u_{0}) − T̃(u_{0})) ∥

then

\frac{α_{n}}{1 + q} ≤∥ u_{n} − u ∥_{∞}≤ \frac{α_{n}}{1 − q} .  (2.16)

Finally, if the distance from u_{0} to X_{n} is E_{n}(u_{0}) ≡ inf_{x∈X_{n}} ∥ u_{0} − x ∥_{∞}, then there exists a constant C, independent of n, such that

E_{n}(u_{0}) ≤∥ u_{n} − u_{0} ∥_{∞}≤ C{E_{n}(KΨ(u_{0})) + E_{n}(f)}.  (2.17)

Proof: We will apply Theorem 2.3 of Vainikko. It requires that T_{n} be Fréchet differentiable in some neighborhood of u_{0} and that I − T′_{n}(u_{0}) be continuously invertible. But these follow from assumption 5 of Section 1 and from (P1)-(P3) above. Hence, condition (a) of Theorem 2.3 is verified. We next check condition (b) of Theorem 2.3. To establish (2.7), we need the uniform boundedness of (I − T′_{n}(u_{0}))^{−1} for all sufficiently large n and the local Lipschitz condition

∥ T′_{n}(u_{0}) − T′_{n}(u) ∥_{∞}≤ M ∥ u_{0} − u ∥_{∞}  (2.18)

for all u in some neighborhood of u_{0}. (Here and throughout the remainder of the paper we use M to denote a generic constant the exact value of which may change at each occurrence.) Then, choosing δ sufficiently small, (2.7) holds. But (2.18) holds because for each ∥ u ∥_{∞}≤ 1,

∥ T′_{n}(u_{0})[x] − T′_{n}(u)[x] ∥_{∞}= ∥ P_{n}KΨ′(u_{0})x − P_{n}KΨ′(u)x ∥_{∞}

≤ C sup_{0≤t≤1} | ∫_{0}^{1} k(t, s)[ψ^{(0,1)}(s, u_{0}(s)) − ψ^{(0,1)}(s, u(s))]x(s) ds|

≤ C C_{2}M_{1} sup_{0≤t≤1} |u_{0}(t) − u(t)| = M ∥ u_{0} − u ∥_{∞} .

where C and C_{2} are constants defined earlier in proposition 2.4 of [?] and in assumption 5 of Section 1 respectively.

The fact that, for sufficiently large n, I − T′_{n}(u_{0}) is invertible and ∥ (I − T′_{n}(u_{0}))^{−1} ∥ is uniformly bounded can be established by observing that for each x ∈ X,

∥ T′_{n}(u_{0})[x] − T′(u_{0})[x] ∥_{∞}=∥ P_{n}KΨ′(u_{0})[x] − KΨ′(u_{0})[x] ∥_{∞}→ 0

by Proposition 2.4, [?]. Thus T′_{n}(u_{0}) converges in operator norm to T′(u_{0}), and the result follows from the hypothesis that (I − T′(u_{0}))^{−1} exists and from the fact that the set of continuously invertible operators is an open set. Hence (2.7) is satisfied.

To check (2.8), we use the previous result;

\begin{aligned}α_{n} & ≤ M ∥ T_{n}(u_{0}) − T̃(u_{0}) ∥_{∞} \\ & ≤ M\{∥ P_{n}f − f ∥_{∞} + ∥ P_{n}KΨ(u_{0}) − KΨ(u_{0}) ∥_{∞}\} \\ & → 0, as n → ∞. \end{aligned}  (2.19)

Thus, (2.8) is implied, and (2.16) follows from Theorem 2.3.

For (2.17), the first inequality is trivial, as u_{n} ∈ X_{n}. The second inequality follows from (2.16), (2.19) and the fact proved in Proposition 2.4 of [?] that

∥ P_{n}KΨ(u_{0}) − KΨ(u_{0}) ∥_{∞}≤ M ∥ Q_{n}KΨ(u_{0}) − KΨ(u_{0}) ∥_{∞} .

□

2.1 Iterated Petrov-Galerkin Method

.

In this subsection, we discuss the iterated Petrov-Galerkin method. This extends the result of the iterated Galerkin method for Hammerstein equation obtained in [?]. Define the iterated approximation for Hammerstein equation by

x′_{n} = f + KΨx_{n}.  (2.20)

Then as in [?], [?], we find that the iterated approximation x′_{n} satisfies

x′_{n} − KΨP_{n}x′_{n} = f.  (2.21)

Define T̂_{n} by

T̂_{n}x = KΨP_{n}x + f.  (2.22)

The following is instrumental to the stability of the iterated approximation whose effectiveness will be demonstrated in Theorem 2.6 below.

Theorem 2.5 Let x_{0} ∈ L^{∞}[0, 1] be an isolated solution of (1.1). Assume 1 is not an eigenvalue of (KΨ)′(x_{0}). Then, I −T̂′_{n}(x_{0}) is invertible and there exists L > 0 such that ∥ (I −T̂′_{n}(x_{0}))^{−1} ∥≤ L for all sufficient large n,

Proof: By Hölder’s inequality and hypotheses 2 and 5,

∥ T̃′(x_{0})[x] − T̂′_{n}(x_{0})[x] ∥_{∞}
=∥ ∫_{0}^{1} k(s, ·)ψ^{(0,1)}(s, x_{0}(s))x(s) − k(s, ·)ψ^{(0,1)}(s, P_{n}x_{0}(s))x(s)ds ∥_{∞}
≤ M_{1} ∥ (ψ^{(0,1)}(·, x_{0}) − ψ^{(0,1)}(·, P_{n}x_{0})x ∥_{∞}
≤ MC_{2} ∥ x_{0} − P_{n}x_{0} ∥_{∞} ∥ x ∥_{∞}→ 0, n → ∞.

Thus T̂′_{n}(x_{0}) converges to T̃′(x_{0}) pointwise.

Note also that

∥ ψ^{(0,1)}(·, P_{n}x_{0}) ∥_{∞} ≤∥ ψ^{(0,1)}(·, P_{n}x_{0}) − ψ^{(0,1)}(·, x_{0}) ∥_{∞} + ∥ ψ^{(0,1)}(·, x_{0}) ∥_{∞}
≤ C_{2} ∥ P_{n}x_{0} − x_{0} ∥_{∞} + ∥ ψ^{(0,1)}(·, x_{0}) ∥_{∞}
→∥ ψ^{(0,1)}(·, x_{0}) ∥_{∞} n → ∞.

Thus ∥ ψ^{(0,1)}(·, P_{n}x_{0}) ∥_{∞} is bounded uniformly in n, say ∥ ψ^{(0,1)}(·, P_{n}x_{0}) ∥_{∞}≤ M_{2}. Then

∥ T̂′_{n}(x_{0})[x] ∥_{∞}=∥ KΨ′(P_{n}x_{0})[x] ∥_{∞}≤ M_{1}M_{2} ∥ x ∥_{∞} .

This implies that T̂′_{n} is collectively compact. By [?], ∥ (I −T̂′_{0}(x_{0}))^{−1} ∥_{∞} exists for all sufficiently large n and there exists L > 0 such that ∥ (I − T̂′_{n}(x_{0}))^{−1} ∥_{∞}≤ L for these n. □

Theorem 2.6 Let x_{0} ∈ L^{∞}[0, 1] be an isolated solution of (1.1). Assume 1 is not an eigenvalue of (KΨ)′(x_{0}). Then there exists δ > 0 such that equation (2.21) has, for each sufficiently large n, a unique solution x′_{n} in B(x_{0}, δ). Further if

β_{n} ≡∥ (I − T̂′_{n}(x_{0}))^{−1}(T̂_{n}(x_{0}) − T̃(x_{0})) ∥_{∞},

then x′_{n} satisfies

\frac{β_{n}}{1 + q} ≤∥ x_{0} − x′_{n} ∥_{∞}≤ \frac{β_{n}}{1 − q} ,

for some 0 < q < 1.

Proof: First notice that hypothesis (a) of Theorem 2.3 holds; for

\begin{aligned}∥ (I − T̂′_{n}(x_{0}))^{−1}[T̂′_{n}(x) − T̂′_{n}(x_{0}) ∥_{∞} & ≤ M ∥ T̂′_{n}(x) − T̂′_{n}(x_{0}) ∥_{∞} \\ & =∥ KΨ′(P_{n}x) − KΨ′(P_{n}x_{0}) ∥_{∞} . \end{aligned}

But for y ∈ C[0, 1], we have

∥ KΨ′(P_{n}x)[y] −KΨ′(P_{n}x_{0})[y] ∥_{∞}
=∥ ∫_{0}^{1} k(s, ·)[ψ^{(0,1)}(s, P_{n}x(s)) − ψ^{(0,1)}(s, P_{n}x_{0}(s))]y(s)ds ∥_{∞}
≤∥ ∫_{0}^{1} |k(s, ·)|C_{2}|P_{n}x(s) − P_{n}x_{0}(s)| |y(s)|ds ∥_{∞}
≤ M_{1}C_{2} ∥ P_{n}x − P_{n}x_{0} ∥_{∞}∥ y ∥_{∞} .

The two previous results and Theorem 3.4 of [?], concerning the uniform boundedness of the generalized projection P_{n}, yield a constant C such that

\begin{aligned}∥ (I − T̂′_{n}(x_{0}))^{−1}[T̂′_{n}(x) − T̂′_{n}(x_{0})] ∥_{∞} & ≤ M_{1}C_{2} ∥ P_{n}x − P_{n}x_{0} ∥_{∞} \\ & ≤ C ∥ x − x_{0} ∥_{∞} . \end{aligned}

Next, by the Lipschitz condition on ψ,

β_{n} ≡∥ (I − T̂′_{n}(x_{0}))^{−1}(T̂_{n}(x_{0}) − T̃(x_{0})) ∥_{∞}
≤ M ∥ KΨP_{n}x_{0} − KΨx_{0} ∥_{∞}
= M ∥ ∫_{0}^{1} k(s, ·)[ψ(s, P_{n}x_{0}(s)) − ψ(s, x_{0}(s)]ds ∥_{∞}
≤ M_{1}MC_{1} ∥ P_{n}x_{0} − x_{0} ∥_{∞}→ 0 as n → ∞.

The application of Theorem 2.3 completes the proof. □

Our next task is to establish the superconvergence of the iterated Petrov-Galerkin approximation x′_{n}. Notice that a necessary and sufficient condition for the superconvergence is

β_{n} = o(α_{n}).  (2.23)

Let us obtain (2.23) by estimating β_{n} using the method to prove theorem 3.3, [?]. First of all,

\begin{aligned}β_{n} & ≤ M ∥ T̂_{n}(x_{0}) − T̂(x_{0}) ∥_{∞} \\ & = M ∥ K[Ψ(P_{n}x_{0}) − Ψ(x_{0})] ∥_{∞} \\ & = M ∥ ∫_{0}^{1} k(s, ·)[ψ(s, P_{n}x_{0}(s)) − ψ(s, x_{0}(s))]ds ∥_{∞} . \end{aligned}  (2.24)

Define

d(t) ≡ | ∫_{0}^{1} k(s, t)[ψ(s, P_{n}x_{0}(s)) − ψ(s, x_{0}(s))]ds|.

By the mean value theorem, there exists 0 < θ < 1 such that

d(t) = | ∫_{0}^{1} k(s, t)ψ^{(0,1)}(s, x_{0}(s) + θ(P_{n}x_{0}(s) − x_{0}(s)))(x_{0}(s) − P_{n}x_{0}(s))ds|

Note that ∫_{0}^{1} u(s)[x_{0}(s) − P_{n}x_{0}(s)]ds =< u, x_{0} − P_{n}x_{0} >= 0 for all u ∈ Y_{n}. Thus, for all u ∈ Y_{n},

d(t) = | ∫_{0}^{1} k(s, t)[ψ^{(0,1)}(s, x_{0}(s) + θ(P_{n}x_{0}(s) − x_{0}(s))) − u(s)][x_{0}(s) − P_{n}x_{0}(s)]ds|
≤ | ∫_{0}^{1} k(s, t)ψ^{(0,1)}(s, x_{0}(s) + θ(P_{n}x_{0}(s) − x_{0}(s)))[x_{0}(s) − P_{n}x_{0}(s)]
−k(s, t)ψ^{(0,1)}(s, x_{0}(s))[x_{0}(s) − P_{n}x_{0}(s)]ds|
+| ∫_{0}^{1} k(s, t)[ψ^{(0,1)}(s, x_{0}(s)) − u(s)][(x_{0}(s) − P_{n}x_{0}(s)]ds|
≡ T_{1}(t) + T_{2}(t).

Assuming that x_{0} ∈ L^{∞}[0, 1], we proceed as follows:

\begin{aligned}T_{1}(t) & ≤ C_{1} ∫_{0}^{1} |k(s, t)|θ|P_{n}x_{0}(s) − x_{0}(s)|^{2}ds \\ & ≤ C ∥ P_{n}x_{0} − x_{0} ∥_{∞}^{2} ∫_{0}^{1} |k(s, t)|ds, \end{aligned}

So

∥ T_{1} ∥_{∞}≤ M_{1} ∥ P_{n}x_{0} − x_{0} ∥_{∞}^{2} .  (2.25)

We also have

T_{2}(t) ≤ [∫_{0}^{1} |k(s, t)|ψ^{(0,1)}(s, x_{0}(s)) − u(s)|^{q}ds]^{1/q}[∫_{0}^{1} |x_{0}(s) − P_{n}x_{0}(s)|^{p}ds]^{1/p}.  (2.26)

where \frac{1}{p} + \frac{1}{q} = 1, p, q ≥ 1 with p = 1 and q = ∞.

Summarizing the discussion above, we arrive at the following theorem establishing the superconvergence of the iterated Petrov-Galerkin approximation for Hammerstein equations. It generalizes theorem 3.3 of [?] by extending the condition x_{0} ∈ C[0, 1] to x_{0} ∈ L^{∞}[0, 1].

Theorem 2.7 Under the hypotheses of Theorem 2.3, there is a constant C such that

\begin{aligned}∥ x_{0} − x′_{n} ∥_{∞} & ≤ C\{∥ P_{n}x_{0} − x_{0} ∥_{∞}^{2} \\ & + ∫_{0}^{1} |k(s, t)|ψ^{(0,1)}(s, x_{0}(s)) − u(s)|^{q}ds]^{1/q}[∫_{0}^{1} |x_{0}(s) − P_{n}x_{0}(s)|^{p}ds]^{1/p}\}. \end{aligned}

3 The Wavelet Petrov-Galerkin Method

Alpert [?] constructed a class of wavelet basis in L^{2}[0, 1] and applied it to approximate the solution of the Fredholm equation (1.2). The numerical method employed in [?] is the Galerkin method. The sparsity of the matrix in the associated linear system is obtained using the vanishing moment property of the wavelets as well as using the notion of ‘separation from the diagonal’ for the supports of the wavelet basis elements. We provide below a brief review of Alpert’s wavelets and how they can be applied to produce this sparsity. The wavelet basis for L^{2}[0, 1] is comprised of dilates and translates of a set of functions h_{1}, h_{2}, …, h_{k}. In particular, for k a positive integer, and for m = 0, 1, … we define a space S_{m}^{k} of piecewise polynomial functions,

S_{m}^{k} = {f: the restriction of f to the interval (2^{−m}n, 2^{−m}(n + 1)) is a polynomial

of degree less than k, for n = 0, …, 2^{m} − 1, and f vanishes elsewhere}.

(3.1)

Note that dim S_{m}^{k} = 2^{m}k and

S_{0}^{k} ⊂ S_{1}^{k} ⊂ ⋯ S_{m}^{k} ⊂ · · · .

The orthogonal complement of S_{m}^{k} in S_{m+1}^{k} is denoted by R_{m}^{k} so that dim R_{m}^{k} = 2^{m}k and

S_{m}^{k} ⊕ R_{m}^{k} = S_{m+1}^{k}, R_{m}^{k}⊥S_{m}^{k}.

Note that

S_{m}^{k} = S_{0}^{k} ⊕ R_{0}^{k} ⊕ R_{1}^{k} ⊕ ⋯ ⊕ R_{m−1}^{k}.  (3.2)

The set of functions h_{1}, h_{2}, …, h_{k} mentioned above is taken as an orthonomal basis for R_{0}^{k}. Since R_{0}^{k} is orthogonal to S_{0}^{k}, the first k moments of h_{1}, h_{2}, …, h_{k} vanish,

∫_{0}^{1} h_{j}(s)s^{i} dx = 0,  i = 0, 1, …, k − 1.  (3.3)

The wavelet basis of Alpert is constructed by defining orthonormal systems

h_{j,m}^{n}(s) = 2^{m/2}h_{j}(2^{m}s − n),  j = 1, …, k; m, n ∈ Z.  (3.4)

We refer the reader to [?] for detailed constructions of h_{1}, h_{2}, …, h_{k}. The functions h_{j,m}^{n} generated in (3.4) become an orthonomal basis for R_{m}^{k};

R_{m}^{k} = linear span {h_{j,m}^{n}: j = 1, …, k; n = 0, …, 2^{m} − 1}.

If we let {u_{1}, …, u_{k}} denote an orthonormal basis for S_{0}^{k}, then the orthonormal system

\begin{aligned}B_{k} = & \{u_{j}: j = 1, …, k\} \\ & ∪\{h_{j,m}^{n}: j = 1, …, k; m = 0, 1, …; n = 0, 1, …, 2^{m} − 1\} \end{aligned}

becomes the multiwavelet basis of order k for L^{2}[0, 1]. In practice, we take an arbitrarily large but a fixed value for m and use

\begin{aligned}B̃_{k} & = \{u_{j}: j = 1, …, k\} ∪ \{h_{j,m}^{n}: j = 1, …, k; n = 0, 1, …, 2^{m} − 1\} \\ & ≡ \{b_{j}\}_{j=1}^{k(2^{m}+1)} \end{aligned}  (3.5)

for an orthonormal basis for S_{m}^{k}. The approximating power of the wavelets is given as follows [?]:

Lemma 3.1 Let Q_{m}^{k} be the orthogonal projection of L^{2}[0, 1] onto S_{m}^{k}. If f ∈ C^{k}[0, 1], then

∥Q_{m}^{k}f − f∥ ≤ 2^{−mk} \frac{2}{4^{k}k!} sup_{x∈[0,1]} |f^{(k)}(x)|.

The Galerkin method for approximating the solution of the Fredholm equation (1.2) using the basis b_{j} in (3.5) requires computations of

K_{ij} = ∫_{0}^{1} ∫_{0}^{1} k(t, s)b_{i}(t)b_{j}(s) dtds.  (3.6)

What Alpert observed at this point is that a large majority of K_{ij} can be neglected from actual computations because of their insignificant sizes, resulting in a sparse matrix for the linear system for the Galerkin method. More precisely, he defined the following regarding the separation from the diagonal of a support of b_{i} ⊗ b_{j}.

Definition We say that a rectangular region [t, t + a] × [s, s + b] ⊂ R^{2} is separated from the diagonal if a + max{a, b} ≤ s − t or b + max{a, b} ≤ t − s.

For k(t, s) = log |t − s|, the following are proved in [?].

Lemma 3.2 Suppose that k(t, s) = log |t − s| is given and B_{k} is the multiwavelet basis of order k. Denote the supports of b_{i}(t) and b_{j}(s) in (3.6) by [x_{0}, x_{0} + a] and I_{j} = [y_{0}, y_{0} + b] respectively and assume that they are separated from the diagonal. Then

|K_{ij}| ≤ \frac{\sqrt{ab}}{2k · 3^{k−1}} .

Lemma 3.3 Suppose that I_{1}, I_{2}, …, I_{n} are the nonincreasing intervals of support of the first n functions of the basis b_{k}. Of the n^{2} rectangular regions I_{i} × I_{j}, we denote the number separated from the diagonal by S(n) and the number “near” the diagonal by N(n) = n^{2} − S(n). Then N(n) = ◯(n log n).

Equation (2.11), when approximated by the Galerkin method with the wavelet basis , requires computations of the following integrals. Here the approximate solution is written as u_{n}(s) = ∑_{i=1}^{n} a_{i}b_{i}(s) for some a_{i} ∈ R.

∫_{0}^{1} ∫_{0}^{1} k(t, s)ψ(x, ∑_{i=1}^{n} a_{i}b_{i}(s))b_{j}(t)dsdt.  (3.7)

The unknowns a_{i} are, in many applications, found by an iterative scheme. Note that, at each step of iteration, the integrals in (3.7) must be recomputed as each a_{i} has different values, making the computations costly. To circumvent the difficulty, we use the technique that was developed in [?]. If we let

z = Ψu,

in (2.11), then

u = Kz + f.

Hence z satisfies

z = Ψ(Kz + f).  (3.8)

We approximate this equation by

z_{n}(t) = ψ(t, ∫_{0}^{1} z_{n}(s)k(t, s)ds + f(t)),

where z_{n}(t) = ∑_{i=1}^{n} a_{i}b_{i}(t) ∈ X_{n} is computed via

< z_{n}, y >=< Ψ(Kz_{n} + f), y >,  y ∈ Y_{n}.  (3.9)

We note that the Petrov-Galerkin method used in (3.9) is distinct from the collocation method of Kumar and Sloan in [?] to solve equation (3.8). Equation (3.9) is equivalent to (compare this with (3.7))

∑_{i=1}^{n} a_{i} ∫_{0}^{1} b_{i}(t)b_{j}^{∗}(t)dt = ∫_{0}^{1} ψ(t, ∑_{i=1}^{n} a_{i} ∫_{0}^{1} k(t, s)b_{i}(s)ds + f(t))b_{j}^{∗}(t)dt,  j = 1, … n. (3.9′)

where {b_{j}^{∗}} is a wavelet basis for Y_{n}. Note that the unknown a_{i}’s now appear outside the third integral, allowing us to compute the integral ∫_{0}^{1} k(t, s)b_{i}(s) ds for each i only once throughout the iterative process for approximating a_{i}’s. It is important to maintain the condition dim X_{n} = dim Y_{n}. In operator notation, equation (3.9) becomes

z_{n} = P_{n}Ψ(Kz_{n} + f),  (3.10)

where P_{n} is the generalized projection onto Y_{n}. Define T_{n} by

T_{n}z ≡ P_{n}Ψ(Kz + f).

Then (3.10) can be written as

z_{n} = T_{n}z_{n}.

Let T̃ be defined as

T̃z ≡ Ψ(Kz + f),

so that equation (3.8) becomes

z = T̃z.

Theorem 3.4 Let z_{0} ∈ L^{∞}[0, 1] be an isolated solution of (3.8) with f ∈ L^{∞}[0, 1]. Assume that 1 is not an eigenvalue of Ψ′(Kz_{0} + f)K and that ψ^{(0,1)}(t, (Kz)(t) + f(t)) ∈ L^{∞}[0, 1] for each z ∈ L^{∞}[0, 1]. If K: L^{∞}[0, 1] → L^{∞}[0, 1], then there exists δ > 0 such that equation (3.9) has a unique solution z_{n} ∈ B(z_{0}, δ) for sufficiently large n. Further if

α_{n} ≡∥ (I − T′_{n}(z_{0}))^{−1}(T_{n}z_{0} − T̃z_{0}) ∥,

then z_{n} satisfies

\frac{α_{n}}{1 + q} ≤∥ z_{0} − z_{n} ∥≤ \frac{α_{n}}{1 − q} ,

for some 0 < q < 1, and

∥z_{0} − z_{n}∥ ≤ C2^{−mk} \frac{2}{4^{k}k!} sup_{x∈[0,1]} |g^{(k)}(x)|.

provided that g ≡ Ψ(Kz_{0} + f) ∈ C^{k}[0, 1].

Proof: Since K : X → X and for z ∈ X, ψ^{(0,1)}(t, (Kz)(t) + f(t)) ∈ X, the Fréchet derivative T′_{n} exists in a neighborhood of z_{0} and

T′_{n}(z_{0})[z](t) = P_{n}ψ^{(0,1)}(t, ∫_{0}^{1} k(t, s)z_{0}(s)ds + f(t)) ∫_{0}^{1} k(t, s)z(s)ds.

Since P_{n} converges pointwise to the identity, T′_{n}(z_{0})(z) converges to Ψ′(Kz_{0} + f)(K(z)), where Ψ′(x_{0})(x)(t) = ψ^{(0,1)}(t, x_{0}(t))x(t). As 1 is not an eigenvalue of Ψ′(Kz_{0} + f)K, we find that I − T′_{n}(z_{0}) is continuously invertible for all sufficiently large n. Thus hypothesis (a) of Theorem 2.3 holds.

Suppose ∥ (I − T′_{n}(z_{0}))^{−1} ∥≤ L for some L > 0. We then have

∥ (I − T′_{n}(z_{0}))^{−1}(T′_{n}(z) − T′_{n}(z_{0})) ∥≤ L ∥ T′_{n}(z) − T′_{n}(z_{0})) ∥,

and for ∥ w ∥≤ 1, using a Lipschitz condition on Ψ′, we obtain

∥ T′_{n}(z)(w)− T′_{n}(z_{0})(w) ∥
=∥ P_{n}Ψ′(Kz + f)(K(w)) − P_{n}Ψ′(Kz_{0} + f)(K(w)) ∥
≤ M ∥ (Ψ′(Kz + f) − Ψ′(Kz_{0} + f))(K(w)) ∥
≤ M ∥ Ψ′(Kz + f) − Ψ′(Kz_{0} + f)) ∥ ∥ w ∥
≤ M ∥ z − z_{0} ∥ .

Hence condition (2.7) in hypothesis (b) of theorem 2.3 is satisfied for δ sufficiently small (with any q, 0 < q < 1).

Finally, since ∥ (I − T′_{n}(z_{0}))^{−1} ∥≤ L and

∥ T̃(z_{0}) − T_{n}(z_{0}) ∥=∥ Ψ(Kz_{0} + f) − P_{n}Ψ(Kz_{0} + f) ∥

converges to zero (by pointwise convergence of P_{n} to the identity), condition (2.8) in hypothesis (b) of theorem 2.3 is satisfied.

The application of Theorem 2.3 yields

\frac{α_{n}}{1 + q} ≤∥ z_{0} − z_{n} ∥≤ \frac{α_{n}}{1 − q} ,

Finally, lemma 3.1 and (P3) give

∥z_{0} − z_{n}∥ ≤ C2^{−mk} \frac{2}{4^{k}k!} sup_{t∈[0,1]} |g^{(k)}(t)|,

since α_{n} ≤ C ∥ (I − P_{n})(Ψ(Kz_{0} + f)) ∥ . □

We now observe the superconvergence of u_{n} to u in L^{∞} norm. Since u_{0} = Kz_{0} + f and u_{n} = Kz_{n} + f, for any ϕ_{n} ∈ S_{m}^{k},

∥ u_{0} − u_{n} ∥_{∞} =∥ K(z_{0} − z_{n}) ∥_{∞}
= sup_{t∈[0,1]} | ∫_{0}^{1} k(t, s)(z_{0}(s) − z_{n}(s))ds|
= sup_{t∈[0,1]} | < k_{t}, z_{0} − z_{n} > |
= sup_{t∈[0,1]} | < k_{t} − ϕ_{n}, z_{0} − z_{n} > |
≤ sup_{t∈[0,1]} ∥k_{t} − ϕ_{n}∥∥z_{0} − z_{n}∥.

(3.11)

Let D^{(k)}u denote the generalized derivative of u of order k. Define the Sobolev space of functions as follows:

W_{2}^{k} = {u : D^{(i)}u ∈ L^{2}(0, 1), for i = 0, 1, …, k}.

The space is endowed with the norm

∥u∥_{W_{2}^{k}} = ∑_{i=0}^{k} ∥D^{(i)}u∥.

From (3.11) and lemma 3.1, we have the following:

Theorem 3.5 We assume that sup_{t∈[0,1]} ∥k_{t}∥_{W_{2}^{k}} < ∞ and that all the hypotheses of Theorem 3.4 hold. Then

∥u_{0} − u_{n}∥_{∞} ≤ C(k) 2^{2(1−mk)},

where C(k) is a constant that depends upon k but not upon m.

3.1 The Iterated Solution z′_{n}

Equation (3.10) suggests that we investigate the iterated variant of z_{n}. Namely, we define

z′_{n} ≡ Ψ(Kz_{n} + f).  (3.12)

and

u′_{n} ≡ Kz′_{n} + f.  (3.13)

From (3.10) and (3.12),

P_{n}z′_{n} = P_{n}Ψ(Kz_{n} + f) = z_{n}.  (3.14)

Equation (3.12) subsequently gives the following equation for z′_{n},

z′_{n} = Ψ(KP_{n}z′_{n} + f).  (3.15)

The next two theorems provide the rates of convergence of z′_{n} and u′_{n} to z_{0}. The proofs are only outlined as they are similar to the one given for theorem 3.4. Here T̃z = Ψ(Kz + f) as defined earlier and

T̂_{n}z ≡ Ψ(KP_{n}z + f).

Theorem 3.6 Let z_{0} ∈ L^{∞}[0, 1] be an isolated solution of (3.8) with f ∈ L^{∞}[0, 1]. Assume that 1 is not an eigenvalue of Ψ′(KP_{n}z_{0} + f)KP_{n} and that ψ^{(0,1)}(t, (KP_{n}z)(t) + f(t)) ∈ L^{∞}[0, 1] for each z ∈ L^{∞}[0, 1]. If K: L^{∞}[0, 1] → L^{∞}[0, 1], then there exists δ > 0 such that equation (3.14) has a unique solution z′_{n} ∈ B(z_{0}, δ) for sufficiently large n. Further if

β_{n} ≡∥ (I − T̂′_{n}(z_{0}))^{−1}(T̂_{n}z_{0} − T̃z_{0}) ∥,

then z′_{n} satisfies

\frac{β_{n}}{1 + q} ≤∥ z_{0} − z′_{n} ∥≤ \frac{β_{n}}{1 − q} ,  (3.16)

for some 0 < q < 1, and

∥z_{0} − z′_{n}∥ ≤ C2^{−mk} \frac{2}{4^{k}k!} sup_{t∈[0,1]} |z_{0}^{(k)}(t)|.  (3.17)

provided that z_{0} ∈ C^{k}[0, 1]. Finally, if sup_{t} ∈ [0, 1]∥z_{0}∥_{W_{t}^{2}} < ∞, then

∥z_{0} − z′_{n}∥_{∞} ≤ C(k) 2^{2(1−mk)},  (3.18)

where C(k) depends only upon k.

Proof: The Fréchet derivative T̂′_{n} exists in a neighborhood of z_{0} and

\begin{aligned}T̂′_{n}(z_{0})[z](t) & = Ψ′(KP_{n}z_{0} + f)(KP_{n}z)(t) \\ & = ψ^{(0,1)}(t, ∫_{0}^{1} k(t, s)P_{n}z_{0}(s)ds + f(t)) ∫_{0}^{1} k(t, s)P_{n}z(s)ds. \end{aligned}

Since 1 is not an eigenvalue of T̂′_{n}(z_{0}), (I−T̂′_{n}(z_{0}))^{−1} exists and uniformly bounded for sufficiently large n. We also note that for ∥w∥ < 1,

∥T̂′_{n}(z)(w) − T̂′_{n}(z_{0})(w)∥ ≤ M∥z − z_{0}∥.

Moreover,

∥T̃(z_{0}) − T̂_{n}(z_{0})∥ = ∥Ψ(Kz_{0} + f) − Ψ(KP_{n}z_{0} + f)∥ ≤ M∥z_{0} − P_{n}z_{0}∥.

Applications of theorem 2.3 and lemma 3.1 yield (3.16) and (3.17). To obtain (3.18),

∥z_{0} − z′_{n}∥_{∞} ≤ M∥T̃(z_{0}) − T̂_{n}(z_{0})∥_{∞}
= ∥Ψ(Kz_{0} + f) − Ψ(KP_{n}z_{0} + f)∥_{∞}
≤ M∥K(z_{0} − P_{n}z_{0})∥_{∞}
= M sup_{t∈[0,1]} | < k_{t}, z_{0} − P_{n}z_{0} > |,

and follow the argument that was used to establish theorem 3.5. □

Theorem 3.7 We assume that sup_{t∈[0,1]} ∥k_{t}∥_{W_{2}^{k}} < ∞ and that all the hypotheses of Theorem 3.6 hold. Then

∥u_{0} − u′_{n}∥_{∞} ≤ C(k) 2^{4(1−mk)},

where C(k) is a constant that depends upon k but not upon m.

Proof: From (3.13), we obtain

∥u_{0} − u′_{n}∥_{∞} = ∥Kz_{0} + f − K(z′_{n} + f)∥_{∞} = ∥K(z_{0} − z′_{n})∥_{∞}.

□

4 Sparsity in Nonlinear Equations

In this section, we examine closely some issues associated with solving equations in (3.9’). Particularly, we propose to approximate {a_{i}} by the Newton’s method. Before we proceed, we recall from (3.2) that dim S_{m}^{k} = 2^{m}k. With n ≡ 2^{m}k for some nonnegative integers m and k, we let X_{n} = S_{m}^{k}. The main advantage of the Petrov-Galerkin method is the flexibility for choosing Y_{n} in the regular pair different from X_{n} so as to simplify the computations in (3.9’). In the current situation, this can be attained by taking a lower order wavelet to form Y_{n}. Let k′ < k and Y_{n} ≡ S_{m′}^{k′}. The condition dim X_{n} = dim Y_{n} demands 2^{m}k = 2^{m′}k′. For convenience, we take k and k′ to satisfy \frac{k}{k′} = 2^{q} for some nonnegative integer q. If q = 0, we have the traditional Galerkin method. Note that m′ = m + q. As in section 3, we let X_{n} = span{b_{i}} and Y_{n} = span{b_{j}^{∗}}. The following lemma generalizes Lemma 3.3.

Lemma 4.1 Suppose that I_{1}, I_{2}, …, I_{n} and I_{1}^{∗}, I_{2}^{∗}, …, I_{n}^{∗} are the nonincreasing intervals of support of the bases elements b_{i} and b_{j}^{∗} respectively. Of the n^{2} rectangular regions I_{i} × I_{j}^{∗}, we denote the number separated from the diagonal by S(n) and the number “near” the diagonal by N(n) = n^{2} − S(n). Then N(n) = ◯(n log n). In particular, for n = 2^{m}k = 2^{m′}k′, we have

N(n) ≤ 6mkn − (6 − 2^{3−m})kn − 9k′n + (8 + 6m)kk′.

Proof: We define S_{1}(p) to be the number of pairs (i, j) such that the rectangular region I_{i}×I_{j}^{∗} is separated from the diagonal and m(I_{i}) = m(I_{j}^{∗}) = 2^{−p} where m denotes the Lebesque measure. We have S_{1}(p) = (2^{p} −1)(2^{p} −2)kk′ for p = 0, 1, . . .. We further define S_{2}(p, q) to be the number of pairs (i, j) such that I_{i} ×I_{j}^{∗} is separated from the diagonal and m(I_{i}) = 2^{−p} and m(I_{j}^{∗}) = 2^{−q}. As in [?], S_{2}(p, q) = S_{1}(min{p, q})2^{|p−q|} for p, q = 0, 1, 2, . . .. Then

S(n) = ∑_{p=0}^{m−1}(S_{1}(p) + ∑_{q=p+1}^{m′−1}(S_{2}(p, q) + S_{2}(q, p))
= ∑_{p=0}^{m−1} S_{1}(p)[1 + 2 ∑_{q=p+1}^{m′−1} 2^{q−p}]
= ∑_{p=0}^{m−1}(2^{p} − 1)(2^{p} − 2)kk′[1 + 4(2^{m′−1−p} − 1)]
≥ [2 · 2^{m′+m} − 2 · 2^{m′} − 6m2^{m′} − 2^{m′−m+3} + 8 · 2^{m′}
−2^{m′+m} − 8 + 9 · 2^{m} − 6m]kk′
= n^{2} − 6mkn + (6 − 2^{3−m})kn + 9k′n − (8 + 6m)kk′.

This proves N(n) = ◯(n log n). □

Now define

\begin{aligned}f_{j}(a_{1}, a_{2}, …, a_{n}) & ≡ ∑_{i=1}^{n} a_{i} ∫_{0}^{1} b_{i}(t)b_{j}^{∗}(t)dt \\ & − ∫_{0}^{1} ψ(t, ∑_{i=1}^{n} a_{i} ∫_{0}^{1} k(t, s)b_{i}(s)ds + f(t))b_{j}^{∗}(t)dt, j = 1, … n, \end{aligned}

(4.1)

so that

\frac{∂f_{j}}{∂a_{l}} = ∫_{0}^{1} b_{l}(t)b_{j}^{∗}(t)dt − ∫_{0}^{1} ψ^{(0,1)}(t, ∑_{i=1}^{n} a_{i} ∫_{0}^{1} k(t, s)b_{i}(s)ds + f(t)) ∫_{0}^{1} k(t, s)b_{l}(s)b_{j}^{∗}(t)dtds, (4.2)

for 1 ≤ j, l ≤ n.

Let ā ≡ (a_{1}, a_{2}, … a_{n})^{T} and F (ā) ≡ (f_{1}(ā), f_{2}(ā), …, f_{n}(ā))^{T}. Denote the Jacobian matrix for F at ā by J(ā), J(ā) = (\frac{∂f_{j}}{∂a_{k}})_{j,k=1}^{n}. Using the Newton method, with ā_{0} ∈ R^{n} given,

ā_{α+1} = ā_{α} − J(ā_{α})^{−1}F (ā_{α}),  for each α = 0, 1, …  (4.3)

Let us examine the terms in (4.2). If I_{l} × I_{j}^{∗} is separated from the diagonal, m(I_{l} ∩ I_{j}^{∗}) = 0 and

∫_{0}^{1} b_{l}(t)b_{j}^{∗}(t)dt = ∫_{I_{l} ⋂ I_{j}^{∗}} b_{l}(t)b_{j}^{∗}(t)dt = 0.

Lemma 4.1 shows thus that only ◯(n log n) of such integrals need computation. Now, consider the second term on the right side of (4.2). If we put Ψ(t) ≡ ψ^{(0,1)}(t, ∑_{i=1}^{n} a_{i} ∫_{0}^{1} k(t, s)b_{i}(s)ds + f(t)), then by assumption 6, there is a constant M > 0 such that sup_{t∈[0,1]} |Ψ(t)| ≤ M, and

| ∫_{0}^{1} ψ^{(0,1)}(t, ∑_{i=1}^{n} a_{i} ∫_{0}^{1} k(t, s)b_{i}(s)ds +f(t)) ∫_{0}^{1} k(t, s)b_{l}(s)b_{j}^{∗}(t)dtds|
= | ∫_{0}^{1} ∫_{0}^{1} Ψ(t)k(t, s)b_{l}(s)b_{j}^{∗}(t)dsdt|
≤ M| ∫_{0}^{1} ∫_{0}^{1} k(t, s)b_{l}(s)b_{j}^{∗}(t)dsdt|.

Even though b_{l} and b_{j}^{∗} are elements of wavelet bases of different orders, a result similar to Lemma 3.2 can be obtained in the present setting. For k(t, s) = log |t − s| and K_{l,j}^{∗} = ∫_{0}^{1} ∫_{0}^{1} k(t, s)b_{l}(s)b_{j}^{∗}(t)dsdt, the following theorem describes the size of K_{l,j}^{∗}. Despite the differences in the orders of wavelets, an argument can be made so that an upper bound for K_{l,j}^{∗} contains only the parameter k of higher order wavelet. This is because the vanishing moment property of the wavelet basis element is utilized only relative to b_{l} whose order is k. The wavelet basis element b_{j}^{∗} contributes in controlling the size of K_{l,j}^{∗} by virtue of the size of its support. The proof is given here for completeness.

Lemma 4.2 Let B_{k} and B_{k′}^{∗} be the multiwavelet bases of orders k and k′ respectively, where 2^{m}k = 2^{m′}k′ and \frac{k}{k′} = 2^{q} for some nonnegative integer q. Denote the supports I_{l} of b_{l} ∈ B_{k} and I_{j}^{∗} of b_{j}^{∗} ∈ B_{k′}^{∗} by [x_{0}, x_{0} + a] and [y_{0}, y_{0} + b] respectively and assume that they are separated from the diagonal. Then

|K_{l,j}^{∗}| ≤ \frac{\sqrt{ab}}{2k · 3^{k−1}} .

Proof:

|K_{l,j}^{∗}| = | ∫_{y_{0}}^{y_{0}+b} ∫_{x_{0}}^{x_{0}+a} k(t, s)b_{l}(s)b_{j}^{∗}(t)dsdt|
≤ ∫_{y_{0}}^{y_{0}+b} | ∫_{x_{0}}^{x_{0}+a}[log(x_{0} + \frac{a}{2} − t)
− ∑_{m=1}^{∞} \frac{1}{m}(\frac{x_{0}+a/2−x}{x_{0}+a/2−t})^{m}]b_{l}(s)ds||b_{j}^{∗}(t)|dt
≤ ∫_{y_{0}}^{y_{0}+b} | ∫_{x_{0}}^{x_{0}+a} ∑_{m=k}^{∞} \frac{1}{m}(\frac{x_{0}+a/2−x}{x_{0}+a/2−t})^{m}]b_{l}(s)ds||b_{j}^{∗}(t)|dt
≤ ∫_{y_{0}}^{y_{0}+b} | ∫_{x_{0}}^{x_{0}+a} \frac{1}{k} ∑_{m=k}^{∞}(\frac{1}{3})^{m}|b_{l}(s)|ds|b_{j}^{∗}(t)dt
≤ ∫_{y_{0}}^{y_{0}+b} ∫_{x_{0}}^{x_{0}+a} \frac{1}{2k·3^{k−1}} |b_{l}(s)|ds|b_{j}^{∗}(t)|dt
≤ \frac{1}{2k·3^{k−1}} ∫_{y_{0}}^{y_{0}+b} \sqrt{∫_{x_{0}}^{x_{0}+a} b_{l}(s)^{2}ds ∫_{x_{0}}^{x_{0}+a} 1ds} |b_{j}^{∗}(t)|dt
≤ \frac{\sqrt{ab}}{2k·3^{k−1}} .

□

Let D be the closed disk of radius \frac{3}{2} centered at z = \frac{1}{2} and L is analytic in a domain containing D × D ⊂ C^{2}. Suppose that K is the restriction of L to [0, 1] × [0, 1]. With this kernel K, the following is possible,

Lemma 4.3 Let B_{k} and B_{k′}^{∗} be the multiwavelet bases of orders k and k′ respectively, where 2^{m}k = 2^{m′}k′ and \frac{k}{k′} = 2^{q} for some nonnegative integer q. Denote the supports I_{l} of b_{l} ∈ B_{k} and I_{j}^{∗} of b_{j}^{∗} ∈ B_{k′}^{∗} by [x_{0}, x_{0} + a] and [y_{0}, y_{0} + b] respectively and assume that they are separated from the diagonal. Then, for K_{l,j}^{∗} ≡ ∫_{y_{0}}^{y_{0}+b} ∫_{x_{0}}^{x_{0}+a} K(t, s)b_{l}(s)b_{j}^{∗}(t)dsdt, where K is defined above,

|K_{l,j}^{∗}| ≤ \frac{\sqrt{ab}}{7 · 8^{k−1}} sup_{s,t∈∂D} |K(s, t)|.

References

[1] B. K. Alpert, A class of bases in L^{2} for the sparse representation of integral operators, SIAM Jl. Math. Anal., Vol. 24, pp. 246-262, (1993).

[2] K. E. Atkinson, The Numerical Solution of Integral Equations of the Second Kind, Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, (1997).

[3] K. E. Atkinson, The numerical solution of a nonlinear boundary integral equation on smooth surfaces, IMA Jl. Num. Anal., Vol. 14, pp. 461-483, (1994).

[4] K. E. Atkinson and G. Chandler, BIE methods for solving Laplace’s equation with nonlinear boundary conditions: The smooth boundary case, Math. Comp. Vol. 55, pp. 455-472, (1990).

[5] Z. Chen and Y. Xu, The Petrov-Galerkin and iterated Petrov-Galerkin methods for second kind integral equations,SIAM Jl. Num. Anal. Vol. 35, pp. 406-434, (1998).

[6] Z. Chen, C. A. Micchelli and Y. Xu, The Petrov-Galerkin method for second kind integral equations II: multiwavelet schemes, Adv. in Comp. Math. (to appear).

[7] L. M. Delves and J. L. Mohamed, Computational Methods for Integral Equations, Cambridge University Press, (1985).

[8] H. Kaneko, R. D. Noren and P. A. Padilla, Superconvergence of the iterated collocation methods for Hammerstein equations, Jl. Comp. and Appl. Math., Vol. 80, pp. 335-349, (1997).

[9] H. Kaneko and Y. Xu, Superconvergence of the iterated Galerkin methods for Hammerstein equations, SIAM Jl. Num. Anal., Vol. 33, pp. 1048-1064, (1996).

[10] S. Kumar and I. H. Sloan, A new collocation-type method for Hammerstein equations, Math. Comp., Vol. 48, pp. 585-593, (1987).

[11] G. Vainikko, Perturbed Galerkin method and general theory of approximate methods for nonlinear equations, U.S.S.R. Comp. Math. Math. Phys., Vol. 7, pp. 1-41, (1967).