Superconvergence of the Iterated Degenerate Kernel

Method

Hideaki Kaneko^{∗}

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

Peter Padilla NASA Langley Research Center

MS-152

Hampton, Virginia 23681-0001

and Yuesheng Xu^{†}

Department of Mathematics North Dakota State University Fargo, North Dakota 58105

∗Partially supported by NASA, project title NCCI-213.

†Partially supported by NASA, project title NCCI-213, National Science Foundation DMS-9504780 and the Alexander von Humboldt Foundation.

SUPERCONVERGENCE OF THE ITERATED DEGENERATE KERNEL METHOD

H. Kaneko, P. Padilla and Y. Xu

Abstract First, in this paper, a general theory for the iterated operator approximation is developed. Some of the known results of the superconvergence of the various iterated schemes can be formulated as special cases of this theory. The method is then subsequently used to prove the superconvergence of the iterated degenerate kernel method for the Fredholm equations of the second kind. A similar result of the superconvergence of the degenerate kernel method for the Hammerstein equations is also given.

1 Introduction

In this paper, we consider the Fredholm integral equation of the second kind

x(t) − ∫_{a}^{b} k(t, s)x(s)ds = f(t)  a ≤ t ≤ b  (1.1)

and the Hammerstein equation

x(t) − ∫_{a}^{b} k(t, s)ψ(s, x(s))ds = f(t)  a ≤ t ≤ b  (1.2)

where k, f in (1.1) and (1.2) and ψ in (1.2) are known functions and in both cases x is the function to be determined. Several numerical methods are available for obtaining approximate solutions of (1.1) and (1.2). It is well known that popularly used methods such as the Galerkin method, the Petrov-Galerkin method and the collocation method can be viewed as special cases of the projection method ( see [2] and [5]). The projection method for the Fredholm integral equation of the second kind (1.1) can be described as follows: Let X denote the Banach space of functions and {X_{n}} a sequence of finite dimensional subspaces of X that is essentially dense in X, -i.e. cl ∪ X_{n} = X where clS denotes the closure of a set S. We denote a family of projections of X onto X_{n} by {P_{n}}. Now we define

Kx(t) ≡ ∫_{a}^{b} k(t, s)x(s)ds  for each t ∈ (a, b).  (1.3)

We assume throughout this paper that K is a compact operator of X into X. Equation (1.1) can be written in operator form as

x = f + Kx.  (1.4)

Here x is assumed to be an element of X. The underlying principle that supports the projection method is to seek an element x_{n} ∈ X_{n} for which the residual r_{n} ≡ f − (x_{n} − Kx_{n}) disappears under the projection P_{n}, -i.e. P_{n}r_{n} = 0 for each n. In the Galerkin method, the projection is orthogonal. On the other hand, in the collocation method, the projection is interpolatory. The projection related to the Petrov-Galerkin method is studied in [5]. A similar discussion for the projection method for the nonlinear Hammerstein equation (1.2) will be left to the reader (see, e.g. [2] [3] [4] [9] [11]).

Let x_{n} denote a numerical solution of equation (1.4). The iterated solution x_{n}^{I} corresponding to x_{n} is defined by

x_{n}^{I}(t) = f(t) + ∫_{a}^{b} k(t, s)x_{n}(s)ds.  (1.5)

If x_{n} denotes the Galerkin or the collocation solution, it is known [7] that, under suitable conditions on the kernel k and the forcing term f, their corresponding iterated solutions converge to x more rapidly than x_{n} does to x, a phenomenon commonly known as superconvergence. For the case of sufficiently smooth kernel and forcing term, the convergence rate of the iterated solution is double of that of the original. It is proved in [5] that the iterated Petrov-Galerkin method achieves a superconvergence with order equal to the sum of the orders of approximation for the trial space and the test space. One of the purposes of this paper is to develop a general iterated approximation scheme for equation (1.1). This will be done in Section 2. The generality of the theory is demonstrated by showing that the results on the superconvergence of the Galerkin and the collocation iterates examined by Graham, Joe and Sloan [7] can be viewed within the framework of the present iterated operator approximation scheme. We remark that the aforementioned results in [7] have been recently generalized to hold for the Hammerstein equation (1.2) [11] [8]. Moreover, in these papers [11] [8], the superconvergence of the iterated solutions for weakly singular Hammerstein equations are also observed. It appears that these results on superconvergence of the weakly singular equations are new even for the Fredholm equations.

The results obtained in Section 2 are subsequently used to establish the superconvergence of the iterated degenerate kernel method for equation (1.1). The degenerate kernel methods for solving equations (1.1) and (1.2) are discussed in [1] and [12] respectively. It turns out that the superconvergence of the iterated degenerate kernel method depends upon the way in which the kernel k in equation (1.1) is decomposed as a finite sum of products of univariate functions. This will be illustrated in Section 3. In Section 4, the iterated degenerate kernel method for Hammerstein equation (1.2) is discussed. Even though the material in Section 4 does not hold a direct relationship with the general theory presented in Section 2, we feel that it is appropriate to include it here since it extends the results of Section 3 as well as those in [12]. Also included in Section 4 is a discussion on computational consideration for solving the system of nonlinear equations that must be solved in order to obtain the degenerate kernel solution of (1.2). We make use of the devise introduced by Kumar and Sloan [13] to ‘linearlize’ the system of nonlinear equations. That is, the integrals that must be evaluated repeatedly at each stage of the iterations, when a conventional iterated scheme is employed, are now evaluated only once at the beginning of computation.

Examples are provided in Sections 3 and 4 to demonstrate our theory.

2 The Iterated Approximation for the Fredholm Integral Equa-

tions of the Second Kind

In this section, we consider the Fredholm integral equation of the second kind given by (1.1). We denote by C[a, b] the Banach space of all continuous functions defined on [a, b] equipped with the uniform norm ∥ · ∥_{∞}. Also we denote by L_{p}[a, b], 1 ≤ p ≤ ∞, the Banach space of measurable functions whose pth power are integrable (1 ≤ p < ∞) or the Banach space of essentially bounded functions (p = ∞) on [a, b]. In equation (1.1), we assume that

f ∈ C[a, b].  (2.1)

When K is viewed as an operator of C[a, b] into C[a, b], the compactness of K is guaranteed, for instance, by assuming that, with k_{t}(s) ≡ k(t, s),

lim_{t→τ} ∫_{a}^{b} |k_{t}(s) − k_{τ} (s)|ds = 0  for each τ ∈ [a, b].  (2.2)

In order to establish a general iterated approximation scheme, we assume that {K_{n}} is a sequence of operators converging to K in operator norm. That is,

∥K_{n} − K∥_{p} → 0 as n → ∞ for some 1 ≤ p ≤ ∞.  (2.3)

For each n ≥ 1, we assume that we have an equation whose solution approximates the solution of (1.4). We denote this approximating equation by

x_{n} = f_{n} + K_{n}x_{n}.  (2.4)

For example, in the case of the projection method, equation (2.4) is identified by letting K_{n} = P_{n}K and f_{n} = P_{n}f where P_{n} is a projection of a Banach space X into its finite dimensional subspace. In the case of the degenerate kernel method, K_{n} denotes the finite rank separable operator, -i.e. K_{n}x(t) = ∫_{a}^{b} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}φ_{i}(t)φ_{j}(s)x(s)ds where {φ_{i}}_{i=1}^{n} is a linearly independent family of functions defined on [a, b] and f_{n} = f for each n ≥ 1. We define the iterated approximation corresponding to (2.4) by

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

As was indicated in Introduction, the iterated approximations for the Galerkin and for the collocation methods exhibit, under suitable smoothness conditions on the kernel k and on the forcing term f, the global superconvergence. It is not known, however, that a similar superconvergence result can be obtained for the iterated approximations for the degenerate kernel method. We are now in a position to prove the main theorem of this section. The advantages of the theory presented are twofold. First, it can be used to describe the known superconvergence results as special cases of this theorem. Second, it can be used to establish the superconvergence of the iterated degenerate kernel method. The latter will be done in Section 3.

Theorem 2.1 Consider equation (1.1) in a Banach space (X, ∥·∥) where K is a compact linear operator of X into X. We assume that 1 is not an eigenvalue of K and that condition (2.3) is satisfied with respect to the norm ∥ · ∥. Let x_{n} and x_{n}^{I} satisfy equations (2.4) and (2.5) respectively. Then, for sufficiently large n, there exists a constant c > 0, independent of n, such that

∥x − x_{n}^{I}∥ ≤ c{∥K − K_{n}∥^{2} + ∥K(K − K_{n})x∥ + ∥K − K_{n}∥ ∥f − f_{n}∥ + ∥K(f − f_{n})∥}. (2.6)

Proof: From (1.4) and (2.5),

x − x_{n}^{I} = K(x − x_{n}).  (2.7)

Applying K on both sides of (1.4) and (2.4), we obtain

Kx = Kf + K^{2}x  (2.8)

and

Kx_{n} = KK_{n}x_{n} + Kf_{n}.  (2.9)

It follows from (2.8) and (2.9) that

K(x − x_{n}) = K^{2}x − KK_{n}x_{n} + K(f − f_{n})
= K(Kx − K_{n}x_{n}) + K_{n}(Kx − Kx_{n}) − K_{n}(Kx − Kx_{n}) + K(f − f_{n})
= K_{n}(Kx − Kx_{n}) + (K − K_{n})(Kx − Kx_{n}) + K(K − K_{n})x_{n} + K(f − f_{n}).
(2.10)

Since ∥K_{n} − K∥ → 0 as n → ∞ and (I − K)^{−1} exists by assumption, we conclude [1] that (I − K_{n})^{−1} exists and uniformly bounded for sufficiently large n. Therefore,

K(x − x_{n}) = (I − K_{n})^{−1}{(K − K_{n})(Kx − Kx_{n}) + K(K − K_{n})x_{n} + K(f − f_{n})}.

Taking the norm on both sides,

\begin{aligned}∥K(x − x_{n})∥ & ≤ ∥(I − K_{n})^{−1}∥\{∥K − K_{n}∥∥K∥∥x − x_{n}∥ + ∥K(K − K_{n})x_{n}∥ \\ & +∥K(f − f_{n})∥\}. \end{aligned}  (2.11)

Since

\begin{aligned}x − x_{n} & = Kx − K_{n}x_{n} + f − f_{n} \\ & = Kx − K_{n}x + K_{n}x − K_{n}x_{n} + f − f_{n} \end{aligned}

we obtain

(I − K_{n})(x − x_{n}) = Kx − K_{n}x + f − f_{n},

or

x − x_{n} = (I − K_{n})^{−1}{(K − K_{n})x + f − f_{n}}.  (2.12)

From (2.7) and (2.12),

∥x − x_{n}^{I}∥ = ∥K(x − x_{n})∥
≤ c{∥K − K_{n}∥∥x − x_{n}∥ + ∥K(K − K_{n})x_{n}∥ + ∥K(f − f_{n})∥}
≤ c{∥K − K_{n}∥^{2} + ∥K − K_{n}∥∥f − f_{n}∥ + ∥K(K − K_{n})x_{n}∥
+∥K(f − f_{n})∥}

where c is a constant independent of n. This completes our proof. □

Corollary 2.2 For the iterated approximation scheme (2.5), if f_{n} = f for all n in (2.4), then

∥x − x_{n}^{I}∥ ≤ c{∥K − K_{n}∥^{2} + ∥K(K − K_{n})x_{n}∥}.

It is straightforward to notice that Theorem 2.1 includes the results of superconvegence of the iterated Galerkin and the iterated collocation schemes. For this end, first, we let W_{p}^{m}, 1 ≤ p ≤ ∞, m nonnegative integer, denote the Sobolev space of functions defined over [a, b]. Namely g ∈ W_{p}^{m} if and only if g^{(k)} ∈ L_{p}[a, b] for k = 0, 1, …, m, where g^{(k)} denotes the kth distributional derivative of g. Let

Π_{n} : a = t_{0} < t_{1} < ⋯ < t_{n} = b

be a partition of [a, b]. Let h = max_{1≤i≤n}(t_{i} − t_{i−1}) and assume h → 0 as n → ∞. Let ν be an integer and r a positive integer such that 0 ≤ ν < r. Let S_{r,n}^{ν} denote the space of splines of order r and continuity ν, namely φ_{n} ∈ S_{r,n}^{ν} if and only if φ_{n} is a piecewise polynomial of degree ≤ r − 1 on each [x_{i−1}, x_{i}] and has ν − 1 continuous derivatives on (a, b). Let P_{n}^{G} denote an orthogonal projection onto S_{r,n}^{ν} with respect to the L_{2} inner product. In the Galerkin method, equation (2.4) becomes

x_{n}^{G} − P_{n}^{G}Kx_{n}^{G} = P_{n}^{G}f  (2.13)

-i.e. K_{n} = P_{n}^{G}K and f_{n} = P_{n}^{G}f. The corresponding iteration approximation to (2.5) is given by

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

If f ∈ W_{p}^{m}, (m ≥ 0), then there exists ψ_{n} ∈ S_{r,n}^{ν} (0 ≤ ν < r) such that

∥f − ψ_{n}∥_{p} ≤ ch^{min{m,r}}∥f∥_{m,p}  (2.15)

where c is a constant independent of n and ∥f∥_{m,p} = ∑_{k=0}^{m} ∥f^{(k)}∥_{p} (see e.g. [14]). Under the assumption of the quasiuniform mesh, -i.e.

\frac{h}{min_{1≤i≤n}(t_{i} − t_{i−1})} < c for each n and for some constant c > 0,

it can be shown that

sup_{n} ∥P_{n}^{G}∥_{L_{p}→L_{p}} ≤ c_{2}.  (2.16)

for some constant c_{2}. Since

\begin{aligned}∥f − P_{n}^{G}f∥_{p} & = ∥f − ψ_{n} + P_{n}^{G}ψ_{n} − P_{n}^{G}f∥_{p} \\ & ≤ (1 + ∥P_{n}^{G}∥)∥f − ψ_{n}∥_{p}, \end{aligned}  (2.17)

from (2.15), (2.16) and (2.17), we obtain

∥f − P_{n}^{G}f∥_{p} ≤ ch^{min{m,r}}∥f∥_{m,p}.  (2.18)

Now let ξ(t) = ∫_{a}^{b} k(t, s)x_{n}^{G}(s)ds. Then

|K(K − K_{n})x_{n}^{G}(t)| = | ∫_{a}^{b} k(t, u){ξ(u) − P_{n}^{G}ξ(u)}du|
= |(k_{t}, ξ − P_{n}^{G}ξ)|
= |(k_{t} − φ_{n}, ξ − P_{n}^{G}ξ)| for every φ_{n} ∈ S_{r,n}^{ν}
≤ ∥k_{t} − φ_{n}∥_{q}∥ξ − P_{n}^{G}ξ∥_{p},

(2.19)

where \frac{1}{q} + \frac{1}{p} = 1 with convention that if p = 1, then q = ∞. In (2.19), we have used the orthogonality in the third equality and the Hölder inequality in the last step. If k_{t} ∈ W_{p}^{m} with ∥k_{t}∥_{m,q} bounded independently of t, then from (2.15) there exists φ_{n} ∈ S_{r,n}^{ν} such that ∥k_{t} − φ_{n}∥_{q} ≤ ch^{min{m,r}}∥k_{t}∥_{m,q}. Finally from (2.19) we obtain

∥K(K − K_{n})x_{n}^{G}∥_{∞} ≤ ch^{2 min{m,r}}.

Similarly, we can show that whenever f ∈ W_{p}^{m},

∥K(f − P_{n}^{G}f)∥_{∞} ≤ ch^{2 min{m,r}}

and that

∥K − K_{n}∥_{∞} ≤ ch^{min{m,r}}.

Using the estimate (2.6), the above discussion leads us to the following theorem.

Theorem 2.3 (Graham, Joe and Sloan [ [7] :Theorem 4.1]) Let x_{n}^{G} and x_{n}^{G^{I}} denote the solutions for (2.13) and (2.14) respectively. Suppose that k_{t} ∈ W_{p}^{m} (0 ≤ m ≤ r) with ∥k_{t}∥_{m,q} bounded independently of t and that f, ξ ∈ W_{p}^{m} where ξ(t) ≡ ∫_{a}^{b} k(t, s)x_{n}^{G}(s)ds. Then

∥x − x_{n}^{G^{I}} ∥_{∞} ≤ ch^{2 min{m,r}}

where c is independent of n.

Now in the partition Π_{n}, for each i, we select {t_{ij}}_{j=1}^{r} such that

x_{i−1} ≤ t_{i1} < t_{i2} < ⋯ < t_{ir} ≤ x_{i}.

Let P_{n}^{C} denote the interpolatory projector of C[a, b] onto S_{r,n}^{ν} defined by P_{n}^{C}x(t_{ij}) = x(t_{ij}) for each i = 1, …, n and j = 1, 2, …, r. In the collocation method, equation (2.4) becomes

x_{n}^{C} − P_{n}^{C}Kx_{n}^{C} = P_{n}^{C}f  (2.20)

-i.e. K_{n} = P_{n}^{C}K and f_{n} = P_{n}^{C}f. The corresponding iterated collocation solution is defined by

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

As in Theorem 2.3 of the iterated Galerkin method, to see that the iterated collocation method of (2.21) is a special case of Theorem 2.1, we must examine the terms in the right side of (2.6). The second term of (2.6) in this case is analyzed as follows: Let y(t) = ∫_{a}^{b} k(t, s)x_{n}^{C}(s)ds. Then

\begin{aligned}K(K − K_{n})x_{n}^{C}(t) & = (k_{t}, y − P_{n}^{C}y) \\ & = (k_{t} − φ_{n,t}, y − P_{n}^{C}y) + (φ_{n,t}, (I − P_{n}^{C})(y − ψ_{n})) \\ & +(φ_{n,t}, (I − P_{n}^{C})ψ_{n}). \end{aligned}  (2.22)

where φ_{n,t} ∈ S_{m,n}^{0} and ψ_{n} ∈ S_{l,n}^{0}. Now arguing exactly as in the proof of theorem 4.2 [7], we obtain

∥K(K − K_{n})x_{n}^{C}∥_{∞} ≤ ch^{min{l,m+r}}

where c is a constant independent of n. Additional terms in (2.6) can be bounded similarly.

Theorem 2.4 (Graham, Joe and Sloan [[7] :Theorem 4.2]) Let x_{n}^{C} and x_{n}^{C′} be the solutions of (2.20) and (2.21) respectively. Suppose f ∈ C[a, b], x ∈ W_{1}^{l} (0 < l ≤ 2r) and k_{t} ∈ W_{1}^{m} (0 < m ≤ r), with ∥k_{t}∥_{m,1} bounded independently of t. Then

∥x − x_{n}^{C^{I}} ∥_{∞} ≤ ch^{min{l,r+m}}

where c is independent of n.

3 The Iterated Degenerate Kernel Methods

The purpose of this section is to use Theorem 2.1, Corollary 2.2 in particular, to prove the superconvergence of the iterated degenerate kernel method. A generalization to the iterated degenerate kernel method for the Hammerstein equations will be done in Section 4.

Consider equation (1.1). The degenerate kernel method for approximating the solution of (1.1) requires us to approximate the kernel k in (1.1) by a degenerate kernel whose general form can be described as

k_{n}(s, t) = ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}φ_{i}(s)φ_{j}(t)  (3.1)

where {φ_{i}}_{i=1}^{n} is a set of linearly independent functions in C[a, b]. The operator K in (1.3) is then approximated by a sequence of finite rank operators

K_{n}y(t) = ∫_{a}^{b} k_{n}(t, s)y(s)ds.  (3.2)

Subsequently an approximate solution x_{n} is found by solving

x_{n}(t) − ∫_{a}^{b} k_{n}(t, s)x_{n}(s)ds = f(t)  a ≤ t ≤ b.  (3.3)

Equation (3.3) can be written as

x_{n}(t) − ∑_{i=1}^{n} φ_{i}(t){∑_{j=1}^{n} ∫_{a}^{b} a_{ij}φ_{j}(s)x_{n}(s)ds} = f(t) a ≤ t ≤ b.

If we put

c_{i} ≡ ∑_{j=1}^{n} ∫_{a}^{b} a_{ij}φ_{j}(s)x_{n}(s)ds,  (3.4)

then x_{n} can be written as

x_{n}(t) = f(t) + ∑_{i=1}^{n} c_{i}φ_{i}(t).  (3.5)

Upon substituting (3.5) into (3.4), we obtain the following n × n system of linear equations for c_{i}.

c_{i} − ∑_{l=1}^{n} c_{l} ∑_{j=1}^{n} ∫_{a}^{b} a_{ij}φ_{j}(s)φ_{l}(s)ds = ∑_{j=1}^{n} ∫_{a}^{b} a_{ij}φ_{j}(s)f(s)ds  1 ≤ i ≤ n.  (3.6)

Finally, once these c_{i}’s are found by solving (3.6), equation (3.5) gives the required approximate solution for the degenerate kernel method. Equation (3.3) is written in operator form as

x_{n} − K_{n}x_{n} = f  (3.7)

which is a special form of (2.4) with f_{n} = f for all n. When the degenerate kernel solution x_{n} is iterated as in (2.5), an interesting question is to ask under what conditions the superconvergence of the iterates is guaranteed. It is the purpose of this section that we provide some answers to this question. It turns out that the superconvergence of the degenerate kernel method hinges critically upon the ways that the kernel k in (3.1) is decomposed. In this section, we demonstrate two different methods that guarantee the superconvergence of the iterates of the degenerate kernel method.

In the first method, we examine the least-squares approximation. For each positive integer N, assume that a partition Π_{N} satisfies the quasiuniform condition (ref. Section 2). Let n denote the dimension of the spline space S_{r,N}^{ν} and B_{1}, B_{2}, …, B_{n} be the B-spline basis for S_{r,N}^{ν}. As in Section 2, r and ν are integers such that 0 ≤ ν < r. Assume that k_{n}(t, s) is the least-squares approximation of k(t, s), -i.e. assume that a_{ij} in (3.1) are such that

∫_{a}^{b} ∫_{a}^{b} |k(t, s) − ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}B_{i}(s)B_{j}(t)|^{2}dsdt = min_{b_{ij}∈R} ∫_{a}^{b} ∫_{a}^{b} |k(t, s) − ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ij}B_{i}(s)B_{j}(t)|^{2}dsdt.

We are now in a position to present the first theorem of this section.

Theorem 3.1 Let x be the solution of (1.1) and x_{n} the solution of (3.7) where k_{n} in (3.1) is defined by the least-squares approximation. Assume that k(t, u) ∈ W_{2}^{m}([a, b] × [a, b]), 0 ≤ m ≤ r, and k_{t}(u)x_{n}(s) ∈ W_{2}^{l}([a, b]×[a, b])) for each n and t ∈ [a, b] and that ∥k_{t}(u)x_{n}(s)∥_{L_{2}} is uniformly bounded in t and n, where 0 ≤ l ≤ r. Then

∥x − x_{n}^{I}∥_{2} = O(h^{ν})

with ν = min{m + l, 2m}.

Proof: Using Theorem 2.2, we obtain

∥x − x_{n}^{I}∥_{2} = O(h^{2m}) + O(∥K(K − K_{n})x_{n}∥_{2}).  (3.8)

Hence we only need to estimate the order of convergence of ∥K(K − K_{n})x_{n}∥_{2}. Note that

\begin{aligned}|K(K − K_{n})x_{n}(t)| & = | ∫_{a}^{b} k(t, u) ∫_{a}^{b}[k(u, s) − k_{n}(u, s)]x_{n}(s)dsdu| \\ & = | ∫_{a}^{b} ∫_{a}^{b} k(t, u)[k(u, s) − k_{n}(u, s)]x_{n}(s)dsdu|. \end{aligned}

Let ψ_{t}(u, s) = k(t, u)x_{n}(s) and let φ_{n}(u, s) = ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ij}B_{i}(u)B_{j}(s) be any element that is a tensor product of B-splines. Then since k_{n} is the least-squares approximation of k,

∫_{a}^{b} ∫_{a}^{b} φ_{n}(u, s)[k(u, s) − k_{n}(u, s)]dsdu = 0,

therefore

|K(K − K_{n})x_{n}(t)| = | ∫_{a}^{b} ∫_{a}^{b}[ψ_{t}(u, s) − φ_{n}(u, s)][k(u, s) − k_{n}(u, s)]dsdu|.

Applying the Cauchy-Schwartz inequality,

|K(K − K_{n})x_{n}(t)| ≤ ∥ψ_{t} − φ_{n}∥_{2}∥k − k_{n}∥_{2}.

Noting that ∥k − k_{n}∥_{2} = O(h^{m}) and choosing particularly φ_{n} so that ∥ψ_{t} − φ_{n}∥_{2} = O(h^{l}), (3.8) proves the desired result. □

The second method that produces superconvergence of the iterates of the degenerate kernel solutions is based upon the idea of approximating the kernel k by interpolation. As before, let

Π_{N} : a = t_{0} < t_{1} < ⋯ < t_{N} = b

be a partition of [a, b]. Let h = max_{1≤i≤N}(t_{i} − t_{i−1}) and assume as in Section 2 that h → 0 as N → ∞. Let ξ_{1}, ξ_{2}, …, ξ_{r} be the zeros of the rth degree Legendre polynomial in [−1, 1]. We shift these points to each subinterval [t_{i−1}, t_{i}], i = 1, 2, …, N to obtain {τ_{ij}}_{j=1}^{r}. Denote the interpolation polynomials by φ_{ij}, -i.e.

φ_{ij}(τ_{α,β}) = \{ \begin{matrix}1 & if (i, j) = (α, β) \\ 0 & if (i, j) ≠ (α, β) \end{matrix}  (3.9)

An approximating degenerate kernel k_{n} (n = Nr) is now defined by

k_{n}(s, t) = ∑_{i=1}^{N} ∑_{j=1}^{r} ∑_{α=1}^{N} ∑_{β=1}^{r} k(τ_{ij}, τ_{α,β})φ_{ij}(s)φ_{α,β}(t).  (3.10)

Let the interpolation projector of C([a, b] × [a, b]) into the tensor product space S_{r,n}^{0} ⊗ S_{r,n}^{0} be denoted by P_{n}. That is,

P_{n}k(s, t) = k_{n}(s, t)

where k_{n} is defined in (3.10). The following theorem demonstrates the superconvergence of the iterated degenerate kernel method when the kernel is decomposed by the interpolation scheme of (3.10).

Theorem 3.2 Assume that in equation (1.1), k(u, s) ∈ W_{1}^{m}([a, b] × [a, b]), 0 < m ≤ r, and k_{t}(u)x_{n}(s) ∈ W_{1}^{l}([a, b] × [a, b]), 0 < l ≤ 2r, for each t ∈ [a, b] with ∥k_{t}(·)x_{n}(·)∥_{W_{1}^{l}([a,b]×[a,b])} bounded independent of t and n. Then

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

Proof: As in the proof of Theorem 3.1, we need to estimate the error of ∥K(K − K_{n})x_{n}∥_{∞}.

By taking φ_{n} ∈ S_{l,n}^{0} ⊗ S_{l,n}^{0} and ψ_{n} ∈ S_{m,n}^{0} ⊗ S_{m,n}^{0}, for each t ∈ [a, b],

K(K − K_{n})x(t) = ∫_{a}^{b} k(t, u) ∫_{a}^{b}[k(u, s) − k_{n}(u, s)]x_{n}(s)dsdu
= ∫_{a}^{b} ∫_{a}^{b} k(t, u)x_{n}(s)[k(u, s) − k_{n}(u, s)]dsdu
≡ (k_{t}(u)x_{n}(s), k(u, s) − k_{n}(u, s))
= (k_{t}(u)x_{n}(s) − φ_{n}(u, s), k(u, s) − k_{n}(u, s))

+(φ_{n}(u, s), (I − P_{n})(k(u, s) − ψ_{n}(u, s)) + (φ_{n}(u, s), (I − P_{n})ψ_{n}(u, s))

The rest of the proof follows once again by an argument similar to the one given in the proof of theorem 4.2 of Graham, Joe and Sloan [7]. A straightforward modification is needed to accomodate the bivariate functions. On this point, the reader is referred to the book by Cheney [6] that contains a discussion on various methods of approximating a bivariate function by elements from the tensor product space of finite dimensional univariate functions. □ Numerical Examples

We present numerical examples for a second kind Fredholm equation using least-squares and interpolation to approximate k(s, t). Let k(s, t) = e^{st}, f is chosen so that the solution is x(t) = 1. Then, the computed errors for the least squares method are shown in the following table.

Errors

n  non-iterated iterated
2  .1362e-1 .8013e-4
3  .6229e-2 .1576e-4
4  .3568e-2 .4978e-5
convergence rate ≈  1.93  4

For the interpolation method, using the roots of the second degree Legendre polynomial, we have the following.

Errors

n  non-iterated iterated
2  .1308e-1 .8242e-4
3  .6087e-2 .1647e-4
4  .3501e-2 .5231e-5
convergence rate ≈  1.9  4

4 The Iterated Degenerate Kernel Method for Hammerstein

Equations

In this section, we extend the results of the previous section to obtain superconvergence of the iterated degenerate kernel method for Hammerstein equation described in (1.2). We assume throughout this section, unless stated otherwise, the following conditions on k, f and ψ:

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

2. M ≡ sup_{a≤s≤b} ∫_{a}^{b} |k(t, s)|dt < ∞;

3. f ∈ C[a, b];

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

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

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

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

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

Additional assumptions will be given later as needed. A study of the degenerate kernel method for Hammerstein equations was made by Kaneko and Xu [12]. A brief outline of the method is described below for convenience. As in the Fredholm equation case, the kernel k in (1.2) is replaced by k_{n} of (3.1). The equation that one must solve is the following;

x_{n}(t) − ∫_{a}^{b} k_{n}(t, s)ψ(s, x_{n}(s)) ds = f(t),  a ≤ t ≤ b.  (4.1)

Following analogously the development made in (3.5) and (3.6), with

c_{i} ≡ ∑_{j=1}^{n} ∫_{a}^{b} a_{ij}φ_{j}(s)ψ(s, x_{n}(s))ds,  (4.2)

x_{n} can be written as

x_{n}(t) = f(t) + ∑_{i=1}^{n} c_{i}φ_{i}(t).  (4.3)

Substituting (4.3) into (4.2), we obtain the following n nonlinear equations in n unknowns c_{1}, ⋯, c_{n},

c_{i} = ∑_{j=1}^{n} ∫_{a}^{b} a_{ij}φ_{j}(s)ψ(s, f(s) + ∑_{l=1}^{n} c_{l}φ_{l}(s))ds,  1 ≤ i ≤ n.  (4.4)

Define

KΨx(t) ≡ ∫_{a}^{b} k(t, s)ψ(s, x(s))ds

so that (1.2) can be written as

x − KΨx = f.  (4.5)

Similarly we write equation (4.1) as

x_{n} − K_{n}Ψx_{n} = f  (4.6)

The iterated solution x_{n}^{I} is now obtained by

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

The Fréchet derivative of KΨ at φ_{0} ∈ C[a, b] is denoted and defined by

(KΨ)′(φ_{0})(φ)(t) = ∫_{a}^{b} k(t, s)ψ_{2}(s, φ_{0}(s))φ(s)ds

for φ ∈ C[a, b] and ψ_{2} denoting the first partial derivative of ψ with respect to the second variable. The following theorem describes the superconvergence phenomenon of x_{n}^{I} to x. Here we assume that the decomposition of the kernel in (3.1) is done by the interpolation scheme of the previous section. The case for the least-squares approximation is similar and will be left to the reader to supply the detail.

Theorem 4.1 Assume that in equation (1.2) k(u, s) ∈ W_{1}^{m}([a, b] × [a, b]), 0 < m ≤ r, and η_{t,n}(u, s) ≡ k_{t}(u)ψ(s, x_{n}(s)) and η_{t,n}(u, s) ∈ W_{1}^{l}([a, b] × [a, b]), 0 < l ≤ 2r, for each n and t ∈ [a, b] where x_{n} is the solution of (4.6). Assume also that 1 is not an eigenvalue (KΨ)′(x) and that ∥η_{t,n}∥_{W_{1}^{l}} is uniformly bounded in t and n. Then

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

Proof: From (4.5) and (4.6),

x − x_{n}^{I} = KΨx − KΨx_{n}.  (4.8)

Now

KΨx − KΨx_{n} = KΨ(f + KΨx) − KΨ(f + K_{n}Ψx_{n})
= (KΨ)′(θ(n)(f + K_{n}Ψx_{n}) + (1 − θ(n))(f + KΨx))(KΨx − K_{n}Ψx_{n})
for some 0 ≤ θ(n) ≤ 1
= K_{θ(n)}(KΨx − K_{n}Ψx_{n} + (KΨx − KΨx_{n}) − (KΨx − KΨx_{n})),

where K_{θ(n)} ≡ (KΨ)′(θ(n)(f + K_{n}Ψx_{n}) + (1 − θ(n))(f + KΨx)). Since K is compact, (KΨ)′(x) is also compact. Also since the solutions {x_{n}} of degenerate kernel method converge to the solution x of (4.5), [12], {K_{θ(n)}} converges in operator norm to (KΨ)′(x). From this along with the fact that 1 is not an eigenvalue of (KΨ)′(x), a standard theorem (see e.g. [1]) yields that (I − K_{θ(n)})^{−1} exists and uniformly bounded for sufficiently large n. Hence we obtain

KΨx − KΨx_{n} = (I − K_{θ(n)})^{−1}K_{θ(n)}(K − K_{n})Ψx_{n}.  (4.9)

Combining (4.8) and (4.9), and taking the norm on both sides, we obtain

∥x − x_{n}^{I}∥_{∞} ≤ c∥(K − K_{n})Ψx_{n}∥_{∞},

for some constant c independent of n. Now using the assupmtions on k and η_{t} and arguing as in the proof of Theorem 3.2, we obtain the desired result. □

Finally we consider a computational problem associated with (4.4). It is customary that the system of nonlinear equations (4.4) is solved by an iterative scheme. For example, the fixed point iteration scheme for (4.4) is to generate {c_{i}^{(k)}}_{i=1}^{n} for k ≥ 1 with a given initial vector {c_{i}^{(0)}}_{i=1}^{n} by

c_{i}^{(k+1)} = ∑_{j=1}^{n} ∫_{a}^{b} a_{ij}φ_{j}(s)ψ(s, f(s) + ∑_{l=1}^{n} c_{l}^{(k)}φ_{l}(s))ds,  1 ≤ i ≤ n.  (4.10)

In this scheme, at each step of iteration, the integrals in (4.10) must be computed since the integrands contain the different values of c_{i}^{(k)}. To circumvent this difficulty. we propose the following device whose idea was originally discussed in [13]. We let

z_{n}(t) = ψ(t, x_{n}(t))  (4.11)

where x_{n} is defined in (4.3). We have, assuming that k_{n} takes the form of (3.1),

z_{n}(t) = ψ(t, f(t) + ∑_{i=1}^{n} a_{ij}φ_{i}(t) ∫_{a}^{b} ∑_{j=1}^{n} φ_{j}(s)z_{n}(s)ds).  (4.12)

The equation (4.12) can be solved by the collocation-type scheme that was developed by Kumar and Sloan [13]. Namely let {η_{i}}_{i=1}^{n} be n functions defined on [a, b] and let {t_{j}}_{j=1}^{n} be n distinct points for which

det(η_{i}(t_{j})) ≠ 0.  (4.13)

The element z_{n} in (4.11) is now approximated in the form ∑_{j=1}^{n} α_{j}η_{j}. The α_{j}’s can be found by solving the following nonlinear equations. Note that the constants α_{j}’s are moved out of the integrals. This makes the repeated computations of the integrals unnecessary when the following system of nonlinear equations is to be solved by an iterated scheme.

∑_{j=1}^{n} α_{j}η_{j}(t_{k}) = ψ(t_{k}, f(t_{k}) + ∑_{i=1}^{n} a_{ij}φ_{i}(t_{k}) ∑_{l=1}^{n} α_{l} ∫_{a}^{b} ∑_{j=1}^{n} φ_{j}(s)η_{l}(s)ds).  (4.14)

for 1 ≤ k ≤ n. If we denote A ≡ [η_{j}(t_{i})] and the right side of (4.14) by ψ_{i}(ᾱ), then with ψ̄(ᾱ) ≡ (ψ_{i}(ᾱ)) and ᾱ^{(k)} ≡ (α_{i}^{(k)}), (4.14) may be solved by the fixed point iteration scheme that can be described as

ᾱ^{(k)} = A^{−1}ψ̄(ᾱ^{(k−1)}).  (4.14)

Numerical Examples

Here we present numerical examples for a Hammerstein equation using least-squares and interpolation to approximate k(s, t). Let k(s, t) = e^{st}, ψ(s, t) = cos(s + t), and f is chosen so that x(t) = 1. Then, the computed errors for the least squares method are shown in the following table.

Errors

n  non-iterated iterated
2  .2805e-2 .5667e-5
3  .1290e-2 .1212e-5
4  .74154e-3 .3939e-6
convergence rate ≈  1.92  3.85

For the interpolation method, using the roots of the second order Legendre polynomial for interploation points, we obtained the following.

Errors

n  non-iterated iterated
2  .2755e-2 .3615e-4
3  .1272e-2 .7050e-5
4  .7306e-3 .2219e-5
convergence rate ≈  1.92  4

References

[1] K. E. Atkinson, A Survey of Numerical Methods for the Solution of fredholm Integral Equations of the Second Kind,SIAM Philadephia, PA. (1976)

[2] K. E. Atkinson, A survey of numerical methods for solving nonlinear integral equations, J. Integral Equations 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 and F. Potra, Projection and iterated projection methods for nonlinear integral equations, SIAM J. Numer. Anal. 24 (1987), 1352-1373.

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

[6] E. W. Cheney, Multivariate Approximation Theory: Selected Topics, CBMS-NSF 51, Regional Series in Applied Math. SIAM (1986).

[7] 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.

[8] H. Kaneko, R. Noren and P. Padilla, Superconvergence of the iterated collocation method for Hammerstein equations, J. Comp. Appl. Math. 80 (1997), 335-349.

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

[10] H. Kaneko, R. Noren and Y. Xu, Regularity of the solution of Hammerstein equations with weakly singular kernels, Integral Equations Operator Theory 13 (1990), 660-670.

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

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

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

[14] L. Schumaker, Spline Functions: Basis Theory, Wiley-Interscience, (1981).