Superconvergence of the Iterated Collocation

Methods for Hammerstein Equations

Hideaki Kaneko^{∗} Richard D. Noren Department of Mathematics and Statistics

Old Dominion University Norfolk, Virginia 23529-0077, USA and Peter A. Padilla NASA Langley Research Center MS-130 Hampton, Virginia 23681-0001, USA

∗

SUPERCONVERGENCE OF THE ITERATED COLLOCATION METHODS FOR HAMMERSTEIN EQUATIONS

H. Kaneko, R. D. Noren and P. A. Padilla

Abstract In this paper, we analyse the iterated collocation method for Hammerstein equations with smooth and weakly singular kernels. The paper expands the study which began in [?] concerning the superconvergence of the iterated Galerkin method for Hammerstein equations. We obtain in this paper a similar superconvergence result for the iterated collocation method for Hammerstein equations. We also discuss the discrete collocation method for weakly singular Hammerstein equations. Some discrete collocation methods for Hammerstein equations with smooth kernels were given previously in [?] and [?].

Key words: the iterated collocation method, the discrete collocation method, Hammerstein equations with weakly singular kernels, superconvergence. Mathematics Subject Classification (1990): 65B05, 45L10.

1 Introduction

In this paper, we investigate the superconvergence property of the iterated collocation method for Hammerstein equations. In the recent paper [?], the superconvergence of the iterated Galerkin method for Hammerstein equations with smooth as well as weakly singular kernels was established. The paper generalizes the previously reported results on the superconvergence of the iterated Galerkin method for the Fredholm integral equations of the second kind [?], [?] [?]. A more important contribution made in [?] lies in the fact that the superconvergence result was established under weaker assumptions (Theorem 3.3 [?]). The approach used in [?] to establish the superconvergence of the iterated Galerkin method can easily be adopted to prove the results of Graham, Joe and Sloan [?], Joe [?] and Sloan [?] under weaker conditions imposed upon the Fredholm equations. This will be demonstrated in Section 3. In Section 2, we review the collocation method for Hammerstein equations as well as some necessary known results that will be pertinent to the matreials in the ensuing sections. We recall that the collocation method for weakly singular Hammerstein equations was discussed and some superconvergence results of the numerical solutions at the collocation points were discovered by Kaneko, Noren and Xu in [?]. In Section 3, the supereconvergence of the iterated collocation method for Hammerstein equations is established. The results obtained there encompass Hammerstein equations with smooth as well as weakly singular kernels. Finally, in Section 4, we discuss the discrete collocation method for Hammerstein equations with weakly singular kernels. The result obtained in this section extends the results of [?] and [?] which deals with the discrete collocation methods for Hammeratein equations with smooth kernels. Some examples are also included in this section.

We note that there have been several other research papers published in recent years that describe various numerical methods for Hammerstein equations. A variant of Nystöm method was proposed by Lardy [?]. The degenerate kernel method was studied by Kaneko and Xu [?]. We point out that a superconvergence of the iterates of the degenerate kernel method was recently observed when a decomposition of the kernel is done properly. This will be reported in a future paper [?]. The reader who is interested in more information on numerical methods for a wider class of nonlinear integral equations may find necessary materials in [?] and [?].

2 The Collocation Method

In this section, the collocation method for Hammerstein equations is presented. Some materials from the approximation theory are also reviewed in this section to make the present paper selfcontained. We consider the following Hammerstein equation

x(t) − ∫_{0}^{1} k(t, s)ψ(s, x(s))ds = f(t), 0 ≤ t ≤ 1,  (2.1)

where k, f and ψ are known functions and x is the function to be determined. Define k_{t}(s) ≡ k(t, s) for t, s ∈ [0, 1] to be the t section of k. We assume throughout this paper unless stated otherwise, the following conditions on k, f and ψ:

1. lim_{t→τ} ∥k_{t} − k_{τ} ∥_{∞} = 0, τ ∈ [0, 1];

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

3. f ∈ C[0, 1];

4. ψ(s, x) is continuous in s ∈ [0, 1] and Lipschitz continuous in x ∈ (−∞, ∞), i.e., there exists a constant C_{1} > 0 for which

|ψ(s, x_{1}) − ψ(s, x_{2})| ≤ C_{1}|x_{1} − x_{2}|, for all x_{1}, x_{2} ∈ (−∞, ∞);

5. the partial derivative ψ^{(0,1)} of ψ with respect to the second variable exists and is Lipschitz continuous, i.e., there exists a constant C_{2} > 0 such that

|ψ^{(0,1)}(t, x_{1}) − ψ^{(0,1)}(t, x_{2})| ≤ C_{2}|x_{1} − x_{2}|, for all x_{1}, x_{2} ∈ (−∞, ∞);  (2.2)

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

We let

(KΨ)(x)(t) ≡ ∫_{0}^{1} k(t, s)ψ(s, x(s))ds.

With this notation, equation (2.1) takes the following operator form

x − KΨx = f.  (2.3)

For any positive integer n, we let

Π_{n} : 0 = t_{0} < t_{1} < ... < t_{n−1} < t_{n} = 1

be a partition of [0, 1]. Let r and ν be nonnegative integers satisfying 0 ≤ ν < r. Let S_{r}^{ν}(Π_{n}) denote the space of splines of order r, continuity ν, with knots at Π_{n}, that is

S_{r}^{ν}(Π_{n}) = {x ∈ C^{ν}[0, 1] : x|_{[t_{i},t_{i+1}]} ∈ P_{r−1}, for each i = 0, 1, …, n − 1}

where P_{r−1} denotes the space of polynomials of degree ≤ r − 1. For the collocation method, we are interested in the cases ν = 0 or 1. That is, it is possible to work with the space of piecewise polynomials with no continuity at the knots or with the space of continuous piecewise polynomials with no continuity requirement on the derivatives at the knots. We assume that the sequence of partitions Π_{n} of [0, 1] satisfies the condition that there exists a constant C > 0, independent of n, with the property:

\frac{max_{1≤i≤n}(t_{i} − t_{i−1})}{min_{1≤i≤n}(t_{i} − t_{i−1})} ≤ C, for all n.  (2.4)

In many cases, equation (2.1) possesses multiple solutions (see e.g. [?]). Hence, it is assumed for the remainder of this paper that we treat an isolated solution x_{0} of (2.1). Let I_{i} = (t_{i−1}, t_{i}) for each i = 1, …, n. Then for ν = 0, we let τ_{i1}, τ_{i2}, …, τ_{ir} be the Gaussian points (the zeros of the rth degree Legendre polynomial on [−1, 1]) shifted to the interval I_{i}. We define

G_{0} = {τ_{ij}: 1 ≤ i ≤ n, 1 ≤ j ≤ r}.  (2.5)

The points in G_{0} give rise to the piecewise collocation method where no continuity between polynomials is assumed. This is the approach taken by Graham, Joe and Sloan [?]. Joe [?], on the other hand, considered the continuous piecewise polynomial collocation method. His method corresponds with taking ν = 1. Here we define the set G_{1} of the collocation points to be the set consisting of the knots along with the Labatto points (the zeros of the first derivative of the r − 1th degree Legendre polynomial) shifted to the interval I_{i}. Namely, let ξ_{r−1} = 1 and for 1 ≤ l ≤ r − 2 (r ≥ 3), let ξ_{l} denotes the lth Labatto point. If |I_{i}| denotes the length of I_{i}, then G_{1} contains

τ_{(i−1)(r−1)+l+1} = \frac{1}{2}(t_{i−1} + t_{i} + |I_{i}|ξ_{l}),  1 ≤ i ≤ n, 1 ≤ l ≤ r − 1, and τ_{1} = t_{0} = 0 (2.6)

The analyses of [?] and [?] are very similar. We therefore confine ourselves to developing the collocation method for Hammerstein equations that is analogous to the method of [?]. An obvious extension to the continuous piecewise collocation method will be left to the reader. Define the interpolatory projection P_{n} from C[0, 1] + S_{r}^{ν}(Π_{n}) to S_{r}^{ν}(Π_{n}) by requiring that, for x ∈ C[0, 1] + S_{r}^{ν}(Π_{n}),

P_{n}x(τ_{ij}) = x(τ_{ij}), for all τ_{ij} ∈ G_{0}. (2.7)

Then we have, for x ∈ C[0, 1] + S_{r}^{ν}(Π_{n})

P_{n}x → x,  as n → ∞  (2.8a)

and consequently

sup_{n} ∥P_{n}∥ < c.  (2.8b)

The collocation equation corresponding to (2.3) can be written as

x_{n} − P_{n}KΨx_{n} = P_{n}f  (2.9)

where x_{n} ∈ S_{r}^{ν}(Π_{n}). Now we let

T̂x ≡ f + KΨx

and

T_{n}x_{n} ≡ P_{n}f + P_{n}KΨx_{n}

so that equations (2.3) and (2.9) can be written respectively as x = T̂x and x_{n} = T_{n}x_{n}. We obtain;

Theorem 2.1 Let x_{0} ∈ C[0, 1] be an isolated solution of equation (2.3). Assume that 1 is not an eigenvalue of the linear operator (KΨ)′(x_{0}), where (KΨ)′(x_{0}) denotes the Fréchet derivative of KΨ at x_{0}. Then the collocation approximation equation (2.9) has a unique solution x_{n} ∈ B(x_{0}, δ) for some δ > 0 and for sufficiently large n. Moreover, there exists a constant 0 < q < 1, independent of n, such that

\frac{α_{n}}{1 + q} ≤ ∥x_{n} − x_{0}∥_{∞} ≤ \frac{α_{n}}{1 − q} ,  (2.10)

where α_{n} ≡ ∥(I − T′_{n}(x_{0}))^{−1}(T_{n}(x_{0}) − T̂(x_{0}))∥_{∞}. Finally,

E_{n}(x_{0}) ≤ ∥x_{n} − x_{0}∥_{∞} ≤ CE_{n}(x_{0}),  (2.11)

where C is a constant independent of n and E_{n}(x_{0}) = inf_{u∈S_{r}^{ν}(Π_{n})} ∥x_{0} − u∥_{∞}.

A proof is a straight application of Theorem 2 of Vainikko [?] and is demonstrated in the proof of Theorem 2.1 [?]. We denote by W_{p}^{m}[0, 1], 1 ≤ p ≤ ∞, the Sobolev space of functions g whose m-th generalized derivative g^{(m)} belongs to L_{p}[0, 1]. The space W_{p}^{m}[0, 1] is equipped with the norm

∥g∥_{W_{p}^{m}} ≡ ∑_{k=0}^{m} ∥g^{(k)}∥_{p}.

It is known from Demko [?] and De Vore [?] that if 0 ≤ ν < r, 1 ≤ p ≤ ∞, m ≥ 0 and x ∈ W_{p}^{m}, then for each n ≥ 1, there exists u_{n} ∈ S_{r}^{ν}(Π_{n}) such that

∥x − u_{n}∥_{p} ≤ Ch^{μ}∥x∥_{W_{p}^{μ}},  (2.12)

where μ = min{m, r} and h = max_{1≤i≤n}(t_{i} − t_{i−1}). The inequality (2.12) when combined with Theorem 2.1 yields the following theorem;

Theorem 2.2 Let x_{0} be an isolated solution of equation (2.3) and let x_{n} be the solution of equation (2.9) in a neighborhood of x_{0}. Assume that 1 is not an eigenvalue of (KΨ)′(x_{0}). If x_{0} ∈ W_{∞}^{l}, then

∥x_{0} − x_{n}∥_{∞} = O(h^{μ}),

where μ = min{l, r}. If x_{0} ∈ W_{p}^{l} (1 ≤ p < ∞), then

∥x_{0} − x_{n}∥_{∞} = O(h^{ν}),

where ν = min{l − 1, r}.

When the kernel k is of weakly singular type, namely if

k(t, s) = m(t, s)g_{α}(|t − s|),  (2.13)

where m ∈ C^{μ+1}([0, 1] × [0, 1]) and

g_{α}(s) = \{ \begin{matrix}s^{α−1}, & 0 < α < 1, \\ log s, & α = 1. \end{matrix}  (2.14)

then the solution x_{0} of equation (2.3) does not, in general, belong to W_{p}^{m}. To better characterize the regularity of the soution of (2.3) with weakly singular kernel, consider a finite set S in [0, 1] and define the function ω_{S}(t) = inf{|t − s| : s ∈ S}. A function x is said to be of T ype(α, k, S), for −1 < α < 0, if

|x^{(k)}(t)| ≤ C[ω_{S}(t)]^{α−k} t ∉ S,

and for α > 0, if the above condition holds and x ∈ Lip(α). Here Lip(α) = {x: |x(t) − x(s)| ≤ C|t − s|^{α}}. It was proved by Kaneko, Noren and Xu [?] that if f is of T ype(β, μ, {0, 1}), then a solution of equation (2.1) with the kernel defined by (2.13) is of T ype(γ, μ, {0, 1}), where γ = min{α, β}. The optimal rate of convergence of the collocation solution x_{n} to x_{0} can be recovered by selecting the knots that are defined by

\begin{matrix}t_{i} = (1/2)(2i/n)^{q}, & 0 ≤ i ≤ n/2, \\ t_{i} = 1 − t_{n−i}, & n/2 < i ≤ n, \end{matrix}  (2.15)

where q = r/γ denotes the index of singularity. Details can be found in [?].

3 The Iterated Collocation Method

The faster convergence of the iterated Galerkin method for the Fredholm integral equations of the second kind compared to the Galerkin method was first observed by Sloan in [?] and [?]. On the other hand, the superconvergence of the iterated collocation method was studied in [?] and [?]. Given the equation of the second kind

x − Kx = f,  (3.1)

where K is a compact operator on X ≡ C[0, 1] and x, f ∈ X, the collocation approximation x_{n} is the solution of the following projection equation

x_{n} − P_{n}Kx_{n} = P_{n}f.  (3.2)

Here P_{n} is the interpolatory projection of (2.7). The iterated collocation method obtains a solution x_{n}^{I} by

x_{n}^{I} = f + Kx_{n}.  (3.3)

Under the assumption of

∥KP_{n} − K∥ → 0  as n → ∞  (3.4)

it can be shown that

∥x − x_{n}^{I}∥ ≤ ∥(I − KP_{n})^{−1}∥∥K(x − P_{n}x)∥.  (3.5)

The assumption (3.4) is satisfied if X = L_{2} and P_{n} is the orthogonal projection satisfying ∥P_{n}g − g∥ → 0 for all g in the closure of the range of the adjoint K^{∗} of K since in this case ∥KP_{n} − K∥ = ∥P_{n}K^{∗} − K^{∗}∥. The results of Sloan were recently generalized to the iterated Galerkin method for Hammerstein equations by Kaneko and Xu [?]. The main theorem of [?], Theorem 3.3, that guarantees the superconvergence of the iterates was proved by making use of the collectively compact operator theory.

The purpose of this section is to study the superconvergence of the iterated collocation method. For the collocation solution x_{n} of (2.9), we define

x_{n}^{I} = f + KΨx_{n}.  (3.6)

A standard argument shows that x_{n}^{I} satisfies

x_{n}^{I} = f + KΨP_{n}x_{n}^{I}.  (3.7a)

We denote the right side of (3.7a) by S_{n}x_{n}^{I}, namely

S_{n}x_{n}^{I} ≡ f + KΨP_{n}x_{n}^{I}.  (3.7b)

We recall the following two lemmas from [?].

Lemma 3.1 Let x_{0} ∈ C[0, 1] be an isolated solution of (2.3). Assume that 1 is not an eigenvalue of (KΨ)′(x_{0}). Then for sufficiently large n, the operators I−S′_{n}(x_{0}) are invertible and there exists a constant L > 0 such that

∥(I − S′_{n}(x_{0}))^{−1}∥_{∞} ≤ L, for sufficiently large n.

Lemma 3.2 Let x_{0} ∈ C[0, 1] be an isolated solution of equation (2.3) and x_{n} be the unique solution of (2.9) in the sphere B(x_{0}, δ_{1}). Assume that 1 is not an eigenvalue of (KΨ)′(x_{0}). Then for sufficiently large n, x_{n}^{I} defined by the iterated scheme (3.6) is the unique solution of (3.7) in the sphere B(x_{0}, δ). Moreover, there exists a constant 0 < q < 1, independent of n, such that

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

where β_{n} = ∥(I − S′_{n}(x_{0}))^{−1}[S_{n}(x_{0}) − T̂(x_{0})]∥_{∞}. Finally,

∥x_{n}^{I} − x_{0}∥_{∞} ≤ CE_{n}(x_{0}).

The definitions of δ and δ_{1} are described in [?]. Following the development made in [?], we let

ψ(s, y) = ψ(s, y_{0}) + ψ^{(0,1)}(s, y_{0} + θ(y − y_{0}))(y − y_{0}),  (3.8)

where θ := θ(s, y_{0}, y) with 0 < θ < 1. Also let

g(t, s, y_{0}, y, θ) = k(t, s)ψ^{(0,1)}(s, y_{0} + θ(y − y_{0})),
(G_{n}x)(t) = ∫_{0}^{1} g(t, s, P_{n}x_{0}(s), P_{n}x_{n}^{I}(s), θ)x(s)ds,

and (Gx)(t) = ∫_{0}^{1} g_{t}(s)x(s)ds, where g_{t}(s) = k(t, s)ψ^{(0,1)}(s, x_{0}(s)). Now we are ready to state and prove our main theorem of this paper. The proof is a combination of the idea used in [?] (Theorem 3.3) and the one used in [?] (Theorem 4.2).

Theorem 3.3 Let x_{0} ∈ C[0, 1] be an isolated solution of equation (2.3) and x_{n} be the unique solution of (2.9) in the sphere B(x_{0}, δ_{1}). Let x_{n}^{I} be defined by the iterated scheme (3.7). Assume that 1 is not an eigenvalue of (KΨ)′(x_{0}). Assume that x_{0} ∈ W_{1}^{l} (0 < l ≤ 2r) and g_{t} ∈ W_{1}^{m} (0 < m ≤ r) with ∥g_{t}∥_{W_{1}^{m}} bounded independently of t. Then

∥x_{0} − x_{n}^{I}∥_{∞} = O(h^{γ}), where γ = min{l, r + m}.

Proof: From equations (2.3) and (3.7), we obtain

x_{0} − x_{n}^{I} = K(Ψx_{0} − ΨP_{n}x_{n}^{I}) = K(Ψx_{0} − ΨP_{n}x_{0}) + K(ΨP_{n}x_{0} − ΨP_{n}x_{n}^{I}).  (3.9)

Using (3.8), the last term of (3.9) can be written as

K(ΨP_{n}x_{0} − ΨP_{n}x_{n}^{I})(t) = (G_{n}P_{n}(x_{0} − x_{n}^{I}))(t).

Equation (3.9) then becomes

x_{0} − x_{n}^{I} = K(Ψx_{0} − ΨP_{n}x_{0}) + G_{n}P_{n}(x_{0} − x_{n}^{I}).  (3.10)

Using the Lipschitz condition (2.2) imposed on ψ^{(0,1)}, for x ∈ C[0, 1],

∥(G_{n}x) − (Gx)∥_{∞} ≤ C_{2} sup_{0≤t≤1} ∫_{0}^{1} |k(t, s)|ds∥x∥_{∞}(∥P_{n}x_{0} − x_{0}∥_{∞} + ∥P_{n}∥_{∞}∥x_{n}^{I} − x_{0}∥_{∞}).

This shows that

∥G_{n} − G∥_{∞} ≤ MC_{2}(∥P_{n}x_{0} − x_{0}∥_{∞} + c∥x_{n}^{I} − x_{0}∥_{∞}) → 0 as n → ∞.

Also, for each x ∈ C[0, 1],

sup_{0≤t≤1} |(GP_{n}x)(t) − (Gx)(t)| = sup_{0≤t≤1} | ∫_{0}^{1} g_{t}(s)[P_{n}x(s) − x(s)]ds| ≤ MM_{1}∥P_{n}x − x∥_{∞},

where

M_{1} = sup_{0≤t≤1} |ψ^{(0,1)}(t, x_{0}(t))| < +∞.

It follows that GP_{n} → G pointwise in C[0, 1] as n → ∞. Again since P_{n} is uniformly bounded, we have for each x ∈ C[0, 1],

∥G_{n}P_{n}x − Gx∥_{∞} ≤ ∥G_{n} − G∥_{∞}∥P_{n}∥_{∞}∥x∥_{∞} + ∥GP_{n}x − Gx∥_{∞}.

Thus, G_{n}P_{n} → G pointwise in C[0, 1] as n → ∞. By Assumptions 2, 5, and 6, we see that there exists a constant C > 0 such that for all n

|ψ^{(0,1)}(s, P_{n}x_{0}(s) + θ(P_{n}x_{n}^{I}(s) − P_{n}x_{0}(s)))| ≤ C_{2}∥P_{n}x_{0} − x_{0}∥_{∞} + θC_{2}P ∥x_{n}^{I} − x_{0}∥_{∞} + M_{1} ≤ C.

This implies that {G_{n}P_{n}} is a family of collectively compact operators [?]. Since G = (KΨ)′(x_{0}) is compact and (I − G)^{−1} exists, it follows from the theory of collectively compact operators that (I − G_{n}P_{n})^{−1} exists and is uniformly bounded for sufficiently large n. Now using (3.10), we see that

∥x_{0} − x_{n}^{I}∥_{∞} ≤ C∥K(Ψx_{0} − ΨP_{n}x_{0})∥.

Hence we need to estimate ∥K(Ψx_{0} − ΨP_{n}x_{0})∥. The following four inequalities are known (Theorem 4.2 [?]). Let ψ_{n} ∈ S_{l}^{0}(Π_{n}) be such that

∑_{i=1}^{n} ∥(x_{0} − ψ_{n})^{(j)}∥_{W_{1}^{m}(I_{i})} ≤ ch^{l−j}∥x_{0}∥_{W_{1}^{l}},  0 ≤ j ≤ l,  (3.11)
max_{1≤i≤n} ∥ψ_{n}^{(j)}∥_{W_{∞}^{m}(I_{i})} ≤ c∥x_{0}∥_{W_{1}^{l}},  j ≥ 0.  (3.12)

Also for each t ∈ [0, 1], there exists φ_{n,t} ∈ S_{m}^{0}(Π_{n}) such that

∑_{i=1}^{n} ∥(g_{t} − φ_{n,t})^{(j)}∥_{W_{1}^{m}(I_{i})} ≤ ch^{m−j}K_{m},  0 ≤ j ≤ m,  (3.13)
max_{1≤i≤n} ∥φ_{n,t}^{(j)}∥_{W_{∞}^{m}(I_{i})} ≤ cK_{m},  j ≥ 0,  (3.14)

where K_{m} = sup_{0≤t≤1} ∥k_{t}∥_{W_{1}^{m}} < ∞. Now for t ∈ [0, 1] we have

\begin{aligned}K(Ψx_{0} − ΨP_{n}x_{0})(t) & = (g_{t} − φ_{n,t}, x_{0} − P_{n}x_{0}) + (φ_{n,t}, (I − P_{n})(x_{0} − ψ_{n})) \\ & +(φ_{n,t}, (I − P_{n})ψ_{n}). \end{aligned}  (3.15)

Using equations (3.11)-(3.14) along with the arguments from [?] (p.362) we can show that each of the three terms is bounded by ch^{γ} uniformly in t. This completes our proof. □

One way to establish the superconvergence of the iterated collocation method for the Fredholm equation is to assume (3.4). In the context of the present discussion, (3.4) is equivalent to assuming

∥(KΨ)′(x_{0})(I − P_{n})|_{C[a,b]}∥_{∞} → 0  as n → ∞.  (3.16)

Theorem 3.3 was thus proved under weaker assumptions. The idea used to prove Theorem 3.3 originates from [?] (section 6) in which the superconvergence of the iterated collocation method for the Fredholm equations was established by showing that {KP_{n}} is a family of collectively compact operators.

Finally in this section, we investigate the superconvergence of the iterated collocation method for weakly singular Hammerstein equation. Specifically, we consider equation (2.3) with kernel given by (2.13) and (2.14). An enhancement in the rate of convergence is given in the following theorem.

Theorem 3.4 Let x_{0} ∈ C[0, 1] be an isolated solution of equation (2.3) and x_{n} be the unique solution of (2.9) in the sphere B(x_{0}, δ_{1}) with kernel defined by (2.13) and (2.14) and knots defined by (2.15). Let x_{n}^{I} be defined by the iterated scheme (3.7). Assume that 1 is not an eigenvalue of (KΨ)′(x_{0}) and that ψ^{(0,1)}(·, x_{0}(·)) is of T ype(α, r, {0, 1}) for α > 0 whenever x_{0} is of the same type. Then

∥x_{0} − x_{n}^{I}∥_{∞} = O(h^{r+α}).

Proof: We follow the proof of Theorem 3.3 exactly the same way to (3.15), which is

\begin{aligned}K(Ψx_{0} − ΨP_{n}x_{0})(t) & = (g_{t} − φ_{n,t}, x_{0} − P_{n}x_{0}) + (φ_{n,t}, (I − P_{n})(x_{0} − ψ_{n})) \\ & +(φ_{n,t}, (I − P_{n})ψ_{n}). \end{aligned}

The difference in superconvergence arises from the degree to which we may bound the first term. As in Kaneko and Xu [?] (Theorem 3.6), using an argument similar to [?], it can be proved that there exists u ∈ S_{r}^{ν}(Π_{n}) with knots Π_{n} given by (2.15) such that ∥g_{t} − u∥_{1} = O(h^{α}). Here h = max_{1≤i≤n}{x_{i} − x_{i−1}}. Then

\begin{aligned}|(g_{t} − φ_{n,t}, x_{0} − P_{n}x_{0})| & ≤ ∥g_{t} − φ_{n,t}∥_{1}∥x_{0} − P_{n}x_{0}∥_{∞} \\ & = O(h^{α+r}). \end{aligned}

The rest of proof follows in the same way as described in [?] (p.362).□

4 The Discrete Collocation Method for Weakly Singular Ham-

merstein Equations

Several papers have been written on the subject of the discrete collocation method. Joe [?] gave an analysis of discrete collocation method for second kind Fredholm integral equations. A discrete collocation-type method for Hammerstein equations was described by Kumar in [?]. Most recently Atkinson and Flores [?] put together the general analysis of the discrete collocation methods for nonlinear integral equations. In this section, we describe a discrete collocation method for weakly singular Hammerstein equations. In the aforementioned papers [?, ?, ?], their discussions are primarily concerned with integral equations with smooth kernels. Even though, in principle, an analysis for the discrete collocation method for weakly singular Hammerstein equations is similar to the one given in [?], we feel that a detailed discussion on some specific points pertinent to weakly singular equations, -e.g.,a selection of a particular quadrature scheme and a convergence analysis etc, will be of great interest to practioners. Our convergence analysis of the discrete collocation method presented in this section is different from the one given in [?] in that it is based upon theorem 2 of Vainikko [?]. The idea of the quadrature used here was recently developed by Kaneko and Xu [?] and a complete Fortran program based on the idea is being developed by Kaneko and Padilla [?]. A particular case of the quadrature schemes developed in [?] is concerned with an approximation of the integral

I(f) = ∫_{0}^{1} f(s)ds,  (4.1)

where f ∈ T ype(α, 2r, S) with α > −1. For simplicity of demonstration, we assume S = {0}. We define q = \frac{2r+1}{α+1} and a partition

π_{α}: s_{0} = 0, s_{1} = n^{−q}, s_{j} = j^{q}s_{1},  j = 2, 3, …, n.  (4.2)

Now we construct a piecewise polynomial S_{r} of degree r − 1 by the following rule; S_{r}(s) = 0, s ∈ [s_{0}, s_{1}) and S_{r}(s) is the Lagrange polynomial of degree r − 1 interpolating f at {u_{j}^{(i)}}_{j=1}^{r} for s ∈ [s_{i}, s_{i+1}), i = 1, 2, …, n − 2 and for x ∈ [x_{n−1}, x_{n}]. Here {u_{j}^{(i)}}_{j=1}^{r} denote the zeros of the rth degree Legendre polynomial transformed into [s_{i}, s_{i+1}). Our approximation process consists of two stages. First, I(f) is approximated by

Î(f) = ∫_{x_{1}}^{1} f(s)ds = ∑_{i=1}^{n−1} ∫_{s_{i}}^{s_{i+1}} f(s)ds.  (4.3)

Second, Î(f) is approximated by Î(S_{r}) = ∫_{s_{1}}^{1} S_{r}(s)ds. A computation of Î(S_{r}) can be accomplished as follows; let θ: [s_{i}, s_{i+1}] → [−1, 1] be defined by θ = \frac{2s−(s_{i+1}+s_{i})}{s_{i+1}−s_{i}} so that

Î(f) = ∫_{−1}^{1} F_{f}(θ)dθ  (4.4)

where

F_{f}(θ) = ∑_{i=1}^{n−1} \frac{1}{2}(s_{i+1} − s_{i})f(\frac{1}{2}(s_{i+1} − s_{i})θ + \frac{1}{2}(s_{i+1} + s_{i})).

If {u_{i}: i = 1, 2 …, r} denotes the zeros of the Legendre polynomial of degree r, then

S_{r}(s) = ∑_{i=1}^{r} F_{f}(u_{i})l_{i}(s)

with l_{i}(s) the fundamental Lagrange polynomial of degree r − 1 so that

Î(S_{r}) = ∑_{i=1}^{r} w_{i}F_{f}(u_{i}),  where w_{i} = ∫_{−1}^{1} l_{i}(s)ds.  (4.5)

It was proved in [?] that

|I(f) − Î(S_{r})| = O(n^{−2r}).  (4.6)

In this section, we examine equation (2.1) with the kernel k defined by (2.13) and (2.14). When the knots are selected according to (2.15), as stated earlier, it was shown in [?] that the solution x_{n} of the collocation equation (2.9) converges to the solution x of (2.1) in the rate that is optimal to the degree of polynomials used. Specifically, x_{n} must be found by solving

x_{n}(u_{j}^{(i)}) − ∫_{0}^{1} g_{α}(|u_{j}^{(i)} − s|)m(u_{j}^{(i)}, s)ψ(s, x_{n}(s))ds = f(u_{j}^{(i)})  (4.7)

where i = 0, 1, … n − 1 and j = 1, 2, … r.

The discrete collocation method for equation (2.1) is obtained when the integral in (4.7) is replaced by a numerical quadrature given in (4.5). Let k_{ij}(s) ≡ g_{α}(|u_{j}^{(i)} − s|)m(u_{j}^{(i)}, s). Then

\begin{aligned}∫_{0}^{1} g_{α}(|u_{j}^{(i)} − s|)m(u_{j}^{(i)}, s)ψ(s, x_{n}(s))ds & = ∫_{0}^{1} k_{ij}(s)ψ(s, x_{n}(s))ds \\ & = ∫_{0}^{u_{j}^{(i)}} + ∫_{u_{j}^{(i)}}^{1} k_{ij}(s)ψ(s, x_{n}(s))ds. \end{aligned}  (4.8)

The integrals in the last expression of (4.8) represent two weakly singular integrals which can be approximated to within O(n^{−2r}) order of accuracy by (4.5) by transforming them to [−1, 1] and selecting the points in (4.2) appropriately.

Writing (4.7) as

P_{n}x_{n} − P_{n}KΨx_{n} = P_{n}f,  (4.9)

we consider the approximation x̃_{n} to x_{n} defined as the solution of

x̃_{n} = Q_{n}x̃_{n} ≡ P_{n}K_{n}Ψx̃_{n} + P_{n}f,  (4.10)

where K_{n} is the discrete collocation approximation to the integrals in (4.8) described above.

We will use Theorem 2 of [?] to find a unique solution to (4.10) in some δ neighborhood of x_{n}, where n is sufficiently large. Clearly, Q′_{n}(x) = P_{n}K_{n}Ψ′(x), where Ψ′(x)[y](s) = ψ^{(0,1)}(s, x(s))y(s). For sufficiently large n, (4.9) has a unique solution in some δ neighborhood of x. To see that I − Q′_{n}(x_{n}) is continuously invertible with {(I − Q′_{n}(x_{n}))^{−1}}_{n=N}^{∞} uniformly bounded, it is enough to observe that {Q′_{n}(x_{n})}_{n=1}^{∞} is collectively compact, and to do this we will show that

| Q′_{n}(x_{n})[x](t) − Q′_{n}(x_{n})[x](t′) |=| P_{n}K_{n}Ψ′(x_{n})x(t) − P_{n}K_{n}Ψ′(x_{n})x(t′) |→ 0  (4.11)

as t → t′, for each x ∈ C[0, 1], [?]. Here N is some sufficiently large number.

If we show (4.11), then part (a) of Theorem 2 [?] is also verified. In order to verify part (b) of Theorem 2 [?], we only need to establish (because of the uniform boundedness of {(I − Q_{n}(x_{n}))^{−1}}_{n=N}^{∞}) that

∥ Q′_{n}(x) − Q′_{n}(x_{n}) ∥_{∞}≤ L ∥ x − x_{n} ∥_{∞}≤ Lδ,  (4.12)

for some constant L, and

∥ Q_{n}(x_{n}) − T_{n}(x_{n}) ∥→ 0 as n → ∞.  (4.13)

Once this is done, Theorem 2 [?] applies yielding a unique solution x̃_{n} in some neighborhood of x_{n} (for sufficiently large n) and

∥ x_{n} − x̃_{n} ∥≤ Lα̃_{n} ≤ L ∥ Q_{n}(x_{n}) − T_{n}(x_{n}) ∥_{∞} .  (4.14)

(Here and throughout the remainder of the section, L denotes a generic constant, the exact value of which may differ at each occurance.) This inequality will be used to obtain the order of convergence.

Considering (4.11), the right hand side is bounded by T_{1} + T_{2} + T_{3}, where

\begin{aligned}T_{1} & =| P_{n}K_{n}Ψ′(x_{n})x(t) − P_{n}KΨ′(x_{n})x(t) |, \\ T_{2} & =| P_{n}KΨ′(x_{n})x(t) − P_{n}KΨ′(x_{n})x(t′) |, \\ T_{3} & =| P_{n}K_{n}Ψ′(x_{n})x(t′) − P_{n}K_{n}Ψ′(x_{n})x(t′) | . \end{aligned}

Let ϵ > 0. Since \{P_{n}\}_{n=1}^{∞} is uniformly bounded, T_{1} + T_{3} < \frac{2ϵ}{3} by applying (4.6) with f(s) = ψ^{(0,1)}(s, x_{n}(s))x(s) and letting n be sufficiently large. For T_{2} we have T_{2} ≤ M ∫_{0}^{1} | k(t, s) − k(t′, s) | ds ≤ M(S_{1} + S_{2}), where

S_{1} = ∫_{0}^{1} g_{α}(| s − t |) | m(t, s) − m(t′, s) | ds

and

S_{2} = ∫_{0}^{1} | g_{α}(| t − s |) − g_{α}(| t′ − s |) || m(t′, s) | ds.

but

S_{1} ≤ sup_{0≤s≤1} | m(t, s) − m(t′, s) | ∫_{0}^{1} g_{α}(| t − s |)ds

≤ L sup_{0≤s≤1} | m(t, s) − m(t′, s) |→ 0 as t → t′,

and

S_{2} ≤ L ∫_{0}^{1} | g_{α}(| t − s |) − g_{α}(| t′ − s |) | ds
= \frac{L}{α}\{| t^{α} − (t′)^{α} | + | (1 − t)^{α} − (1 − t′)^{α} | +\frac{4}{2^{α}} | t − t′ |^{α}\}
→ 0 as t → t′.

Hence (4.11) holds. For (4.12),

∥ Q′_{n}(x) − Q′_{n}(x_{n}) ∥_{∞}=∥ P_{n}K_{n}(Ψ′(x) − Ψ′(x_{n})) ∥≤ MC ∥ x − x_{n} ∥≤ Mδ = q < 1

for δ sufficiently small. Note that we have used the uniform boundedness of {P_{n}}, {K_{n}} and because Ψ^{(0,1)}(s, y(s)) is locally Lipschitz, so is the operator Ψ′ : C[0, 1] → B(C[0, 1], C[0, 1]) (the space of bounded linear operators from C[0, 1] into C[0, 1]).

For (4.13), we have

∥ Q_{n}(x_{n})−T_{n}(x_{n}) ∥_{∞}=∥ P_{n}(K_{n}Ψx_{n}−KΨx_{n}) ∥≤ L ∥ (K_{n}−K)Ψ(x_{n}) ≤ L(R_{1}+R_{2}+R_{3}) (4.15)

where

R_{1} =∥ K_{n}Ψ(x_{n})−K_{n}Ψ(x_{0}) ∥, R_{2} =∥ K_{n}Ψ(x_{0})−KΨ(x_{0}) ∥, R_{3} =∥ KΨ(x_{0})−KΨ(x_{n}) ∥ . (4.16)

But

R_{1} ≤ L ∥ Ψ(x_{n}) − Ψ(x_{0}) ∥≤ C_{1}L ∥ x_{n} − x_{0} ∥  (4.17)

because Ψ is a Lipschitz operator and {K_{n}} is uniformly bounded, and also

R_{3} ≤ M ∥ Ψ(x_{0}) − Ψ(x_{n}) ∥≤ C_{1}M ∥ x_{n} − x_{0} ∥ .  (4.18)

Finally,

R_{2} = O(n^{−2r})  (4.19)

by (4.6) using f(s) = Ψ(x, x_{0}(s)).

Thus Vainikko’s Theorem yields a unique solution x̃_{n} for n sufficiently large and (4.14) holds. Now (4.14) and (4.15) - (4.19) show that

∥ x_{n} − x̃_{n} ∥= O(n^{−β})  (4.20)

where β is the minimum of 2r and the order of convergence of ∥ x_{0} − x_{n} ∥. We summerize the results obtained above in the following theorem:

Theorem 4.1 Let x_{0} be an isolated solution of equation (2.3) and let x_{n} be the solution of equation (2.9) in a neighborhood of x_{0}. Moreover, let x̃_{n} be the solution of (4.10). Assume that 1 is not an eigenvalue of (KΨ)′(x_{0}). If x_{0} ∈ W_{∞}^{l}, then

∥x_{0} − x̃_{n}∥_{∞} = O(h^{μ}),

where μ = min{l, r}. If x_{0} ∈ W_{p}^{l} (1 ≤ p < ∞), then

∥x_{0} − x̃_{n}∥_{∞} = O(h^{ν}),

where ν = min{l − 1, r}.

5 Numerical Examples

In this section we present two numerical examples. Let k(s, t) = e^{s−t} and Ψ(s, x(s)) = cos(s + x(s)). The spline coefficients were obtained using a Newton-Raphson algorithm. Also, the Gausstype quadrature algorithm described in [?] is used to calculate all integrations. The computed errors for the solution and the iterated solution are shown in the following table.

Errors

n non-iterated iterated
2  .153571593748756e-1 .286029074365e-4
3  .71758714356116e-2 .47721991441e-5
4  .41291276625525e-2 .14180649575e-5
5  .26770046422053e-2 .5636996160e-6
convergence rate ≈ 2 4

For the second example, let k(s, t) = log(|s−t|) and Ψ(s, x(s)) = cos(s+x(s)). The computed errors for the solution and iterated solution of the weakly singular integral are shown in the following table.

Errors

n non-iterated iterated
2  .157961272540103e-1 .24257900549439e-2
3  .71150661058771e-2 .7663852778203e-3
4  .41192622669880e-2 .3210258989686e-3
5  .25982238843077e-2 .1770978040470e-3
convergence rate ≈ 2 3

For the third example, let k(s, t) = \frac{1}{\sqrt{|s−t|}}, Ψ(s, x(s)) = cos(s + x(s)), and x(t) = cos(t). The computed errors for the solution and iterated solution of the weakly singular integral are shown in the following table.

Errors

n non-iterated iterated
2  0.01540556116740788 0.005968844100471715
3  0.00722550448387438 0.002566222099442683
4  0.00416092487581254 0.001371170616411344
5  0.00269785684908008 0.000835161756464808
convergence rate ≈  2  2.2

References

[1] P. M. Anselone, Collectively Compact Operator Approximation Theory and Applications to Integral Equations, Prentice-Hall, Englewood Cliffs, N.J., (1971).

[2] K. E. Atkinson, A survey of numerical methods for solving nonlinear integral equations, J. Int. Equ. Appl. 4 (1992), 15-46.

[3] K. E. Atkinson and J. Flores, The discrete collocation method for nonlinear integral equations, Report on Computational Mathematics, No. 10, the University of Iowa, 1991.

[4] K. E. Atkinson, I. Graham and I. Sloan, Piecewise continuous collocation for integral equations, SIAM J. Numer. Anal. 20 (1983), 172-186.

[5] K. E. Atkinson and F. Potra, Projection and iterated projection methods for nonlinear integral equations, SIAM J. Numer. Anal. 24 (1987), 1352-1373.

[6] S. Demko, Splines approximation in Banach function spaces, in Theory of Approximation with Applications A. G. Law, & B. N. Sahney, eds., New York, Academic Press (1976), 146-154.

[7] R. A. De Vore, Degree of approximation, in Approximation Theory II G. G. Lorentz, C. K. Chui, & L. L. Schumaker, eds., New York, Academic Press ( 1976), 117-161.

[8] I. Graham, S. Joe and I. Sloan, Iterated Galerkin versus iterated collocation for integral equations of the second kind, IMA J. Numer. Anal. 5 (1985), 355-369.

[9] S. Joe, Collocation methods using piecewise polynomials for second kind integral equations, Jl. of Comp. and Appl. Math. 12&13 (1985), 391-400.

[10] S. Joe, Discrete collocation methods for second kind Fredholm integral equations, SIAM Jl. Numer. Anal.22 (1985), 1167-1177.

[11] H. Kaneko, R. Noren and Y. Xu, Numerical solutions for weakly singular Hammerstein equations and their superconvergence, J. Int. Eqs. Appl. 4 (1992), 391-407.

[12] H. Kaneko, R. Noren and Y. Xu, Regularity of the solution of Hammerstein equations with weakly singular kernels, Int. Eqs. Op. Thy. 13 (1990), 660-670.

[13] H. Kaneko and P. Padilla, Numerical Quadratures for Weakly Singular Integrals, Technical Report NASA Langley Research Center, May (1996), Report # NCC1-213.

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

[15] H. Kaneko and Y. Xu, Gauss-type quadratures for weakly singular integrals and their application to Fredholm integral equations of the second kind, Math. Comp. , 62 (1994), 739-753.

[16] H. Kaneko and Y. Xu, Degenerate kernel method for Hammerstein equations, Math. Comp. 56 (1991), 141-148.

[17] H. Kaneko, P. A. Padilla and Y. Xu, The iterated operator approximation method and its application to superconvergence of degenerate kernel method, (in preparation).

[18] S. Kumar, A discrete collocation-type method for Hammerstein equation, SIAM J. Numer. Anal. 25 (1988), 328-341.

[19] L. J. Lardy, A variation of Nystrom’s method for Hammerstein equations, J. Int. Eqs. 3 (1981), 43-60.

[20] I. H. Sloan, Four variants of the Galerkin methods for integral equations of the second kind, IMA J. Numer. Anal. 4 (1984), 9-17.

[21] I. H. Sloan, Error analysis for a class of degenerate-kernel methods, Num. Math. 25 (1976), 231-238.

[22] I. H. Sloan, Improvement by iteration for compact operator equations, Math. Comp.30 (1976), 758-764.

[23] G. Vainikko, Perturbed Galerkin method and general theory of approximate methods for nonlinear equations, Zh. Vychisl. Mat. Fiz. 7 (1967), 723-751. Engl. Translation, U.S.S.R. Comp. Math. and Math. Phys. 7, No. 4 (1967), 1-41.